The Implication Problem for Functional and Inclusion Dependencies is Undecidable

DOI10.1137/0214049zbMath0603.68100OpenAlexW1970782121WikidataQ114615485 ScholiaQ114615485MaRDI QIDQ3740280

Ashok K. Chandra, Moshe Y. Vardi

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0214049

zbMATH Keywords

undecidabilityfunctional dependencyinclusion dependencyaxiomatizationrelational data baserecursive inseparabilitydata base dependency

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (32)

Deciding confluence for a simple class of relational transducer networks ⋮ On the finite and general implication problems of independence atoms and keys ⋮ On the Interaction of Existential Rules and Equality Constraints in Ontology Querying ⋮ A finite axiomatization of conditional independence and inclusion dependencies ⋮ Non-determinism in logic-based languages ⋮ Null inclusion dependencies in relational databases ⋮ Towards more expressive ontology languages: the query answering problem ⋮ Well-definedness and semantic type-checking for the nested relational calculus ⋮ Specification and verification of data-driven Web applications ⋮ XML with data values: Typechecking revisited. ⋮ Robustness against Read Committed for Transaction Templates with Functional Constraints ⋮ Appropriate inferences of data dependencies in relational databases ⋮ Dependence and independence ⋮ On rules with existential variables: walking the decidability line ⋮ A semideterministic approach to object creation and nondeterminism in database queries ⋮ On the formal properties of transitive inheritance in databases ⋮ Datalog and Its Extensions for Semantic Web Databases ⋮ Selective inheritance of attribute values in relational databases ⋮ On the finite controllability of conjunctive query answering in databases under open-world assumption ⋮ The effect of unary inclusion dependencies on relational database design ⋮ Guaranteeing no interaction between functional dependencies and tree-like inclusion dependencies ⋮ The complexity of embedded axiomatization for a class of closed database views ⋮ Inclusion dependencies and their interaction with functional dependencies in SQL ⋮ Complexity of propositional projection temporal logic with star ⋮ Independent database schemes under functional and inclusion dependencies ⋮ Evaluating Datalog via tree automata and cycluits ⋮ A theory of data dependencies over relational expressions ⋮ Relational transducers for electronic commerce ⋮ The implication problem for functional dependencies and variants of marginal distribution equivalences ⋮ Thue trees ⋮ Objects in relational database schemes with functional, inclusion, and exclusion dependencies ⋮ Inclusion dependencies and their interaction with functional dependencies

This page was built for publication: The Implication Problem for Functional and Inclusion Dependencies is Undecidable