On the expressive power of data dependencies
type: Item
instance of: scholarly article
title: On the expressive power of data dependencies
zbMATH Open document ID: 0617.68085
DOI: 10.1007/BF00289111
author: Moshe Y. Vardi
author: Johann A. Makowsky
published in: Acta Informatica
publication date: 1986-01-01T00:00:00Z
review text: Since the language of data dependencies is a language for semantic specification of databases, it is highly desirable to know which classes of databases are axiomatizable by different kinds of data dependencies. As a decisive step towards a comprehensive theory, the paper under review gives characterizations of axiomatizability of (finite) databases by data dependencies, using algebraic closure conditions. Some preservation properties of dependencies are given, following the line of investigation of \textit{J. A. Makowsky} [Logic Colloquium '82, Proc. Colloq., Florence 1982, Stud. Logic Found. Math. 112, 303-343 (1984; Zbl 0553.68028)]. Then, the algebraic characterizations of axiomatizability are proved by means of two model-theoretic techniques. These characterizations are used to obtain axiomatizability results for external views and consistent databases.
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 03C68
zbMATH DE Number: 4001522
zbMATH Keywords: data dependencies
zbMATH Keywords: semantic specification of databases
zbMATH Keywords: axiomatizability
zbMATH Keywords: algebraic closure conditions
zbMATH Keywords: preservation properties of dependencies
zbMATH Keywords: external views
zbMATH Keywords: consistent databases
reviewed by: H. Luchian
MaRDI profile type: Publication
Wikidata QID: Q114694751
cites work: Equivalences among Relational Expressions
cites work: A Proof Procedure for Data Dependencies
cites work: Q3856756
cites work: A relational model of data for large shared data banks
cites work: The Semantics of Predicate Logic as a Programming Language
cites work: Horn clauses and database dependencies
cites work: Characterizations for functional dependency and Boyce-Codd normal form families
cites work: Properties of functional-dependency families
cites work: Q3758820
cites work: Testing satisfaction of functional dependencies
cites work: Finitely Specifiable Implicational Dependency Families
cites work: On interpretations of relational languages and solutions to the implied constraint problem
cites work: Q3662644
cites work: Q3216138
cites work: Q3677149
cites work: Q4068696
cites work: Vopěnka's principle and compact logics
cites work: The decision problem for some classes of sentences without quantifiers
cites work: Q3206351
full work available at URL: https://doi.org/10.1007/bf00289111
OpenAlex ID: W2062099202
description: scientific article; zbMATH DE number 4001522