On the expressive power of data dependencies

DOI10.1007/BF00289111MaRDI QIDQ1822528zbMATH OpenOpenAlexWikidataFDO

Authors Moshe Y. Vardi, Johann A. Makowsky

Publication date 1986

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00289111

zbMATH Keywords

algebraic closure conditionsaxiomatizabilityconsistent databasesdata dependenciesexternal viewspreservation properties of dependenciessemantic specification of databases

Mathematics Subject Classification ID

Other classical first-order model theory (03C68) Data structures (68P05) Information storage and retrieval of data (68P20)

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.

Recommendations

• scientific article; zbMATH DE number 465520
• An algebraic point of view of the data structures of database systems
• scientific article; zbMATH DE number 4003563
• Finite approximatization of languages for representation of system properties: Axiomatization of dependencies
• scientific article; zbMATH DE number 3974346

Cites work

• A Proof Procedure for Data Dependencies
• A relational model of data for large shared data banks
• Characterizations for functional dependency and Boyce-Codd normal form families
• Equivalences among Relational Expressions
• Finitely Specifiable Implicational Dependency Families
• Horn clauses and database dependencies
• scientific article; zbMATH DE number 3648167 (Why is no real title available?)
• scientific article; zbMATH DE number 3881877 (Why is no real title available?)
• scientific article; zbMATH DE number 3815000 (Why is no real title available?)
• scientific article; zbMATH DE number 3898209 (Why is no real title available?)
• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• scientific article; zbMATH DE number 3657792 (Why is no real title available?)
• scientific article; zbMATH DE number 3485741 (Why is no real title available?)
• On interpretations of relational languages and solutions to the implied constraint problem
• Properties of functional-dependency families
• Testing satisfaction of functional dependencies
• The decision problem for some classes of sentences without quantifiers
• The Semantics of Predicate Logic as a Programming Language
• Vopěnka's principle and compact logics

Cited in

(11)

• Why Horn formulas matter in computer science: initial structures and generic examples
• Finite approximatization of languages for representation of system properties: Axiomatization of dependencies
• Permutation dependency in datalog programs
• Unique complements and decompositions of database schemata
• Reasoning about functional and full hierarchical dependencies over partial relations
• On a general class of data dependencies in the relational model and its implication problems
• Logics of finite Hankel rank
• scientific article; zbMATH DE number 2061713 (Why is no real title available?)
• Schema mappings: a case of logical dynamics in database theory
• My writing
• Characterizing data dependencies then and now

This page was built for publication: On the expressive power of data dependencies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1822528)