An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic

DOI10.1145/322261.322263zbMath0462.68082WikidataQ114614037 ScholiaQ114614037MaRDI QIDQ3912077

Yehoshua Sagiv, Ronald Fagin, D. Stott Parker, Claude Delobel

Publication date: 1981

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322261.322263

zbMATH Keywords

functional dependency; multivalued dependency; join dependency

Mathematics Subject Classification ID

68P15: Database theory

68N25: Theory of operating systems

03B20: Subsystems of classical logic (including intuitionistic logic)

Related Items

Dependencies for an extended object-oriented database model, Appropriate Reasoning about Data Dependencies in Fixed and Undetermined Universes, Approximate inference of functional dependencies from relations, When do non-conflict-free multivalued dependency sets appear?, Numerical constraints on XML data, Order dependency in the relational model, A simple characterization of database dependency implication, An algebraic theory of functional and multivalued dependencies in relational databases, Positive Boolean dependencies, Functional dependencies, supervenience, and consequence relations, Functional dependencies among Boolean dependencies, Insertion anomalies and the justification for 4NF in relational databases, Characterising nested database dependencies by fragments of propositional logic, Border Algorithms for Computing Hasse Diagrams of Arbitrary Lattices, Spoilt for Choice: Full First-Order Hierarchical Decompositions, Logic and linguistics meeting, Stanford, 1987