The Implication Problem for Functional and Inclusion Dependencies is Undecidable

DOI10.1137/0214049zbMATH Open0603.68100OpenAlexW1970782121WikidataQ114615485 ScholiaQ114615485MaRDI QIDQ3740280FDOQ3740280

Authors: 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

Recommendations

• The implication problem for functional and inclusion dependencies
• On the undecidability of implications between embedded multivalued database dependencies
• The inference problem for template dependencies
• Inclusion dependencies and their interaction with functional dependencies
• Reasoning about embedded dependencies using inclusion dependencies

zbMATH Keywords

axiomatizationundecidabilityfunctional dependencyrelational data baseinclusion dependencyrecursive inseparabilitydata base dependency

Mathematics Subject Classification ID

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

Cited In (40)

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

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

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