The decision problem for database dependencies

DOI10.1016/0020-0190(81)90025-9MaRDI QIDQ1162832zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Cites work

• scientific article; zbMATH DE number 3596227 (Why is no real title available?)
• Impossibility of an algorithm for the decision problem in finite classes
• Solvable cases of the decision problem
• The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas
• Undecidable theories

Cited in

(10)

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

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

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