The decision problem for database dependencies

DOI10.1016/0020-0190(81)90025-9zbMath0482.68094OpenAlexW2112512808WikidataQ114685347 ScholiaQ114685347MaRDI QIDQ1162832

Moshe Y. Vardi

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90025-9

zbMATH Keywords

data dependenciesrecursive solvability

Mathematics Subject Classification ID

Model theory (03C99) Decidability of theories and sets of sentences (03B25) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (9)

The complexity of propositional closed world reasoning and circumscription ⋮ Relational lattices: from databases to universal algebra ⋮ Domain-independent formulas and databases ⋮ Propagating XML constraints to relations ⋮ Is intractability of nonmonotonic reasoning a real drawback? ⋮ Efficient Evaluation of Arbitrary Relational Calculus Queries ⋮ Finite queries do not have effective syntax. ⋮ A note on lossless database decompositions ⋮ Formal systems for join dependencies

Cites Work

• Unnamed Item
• Undecidable theories
• Solvable cases of the decision problem
• The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas
• Impossibility of an algorithm for the decision problem in finite classes

This page was built for publication: The decision problem for database dependencies