Inclusion dependencies and their interaction with functional dependencies
Inclusion dependencies, or INDs (which can say, for example, that every manager is an employee) are studied, including their interaction with functional dependencies, or FDs. A simple complete axiomatization for INDs is presented, and the decision problem for INDs is shown to be PSPACE-complete. (The decision problem for INDs is the problem of determining whether or not \(\Sigma\) logically implies \(\sigma\), given a set \(\Sigma\) of INDs and a single IND \(\sigma)\). It is shown that finite implication (implication over databases with a finite number of tuples) is the same as unrestricted implications for INDs, although finite implication and unrestricted implication are distinct for FDs and INDs taken together. It is shown that, although there are simple complete axiomatizations for FDs alone and for INDs alone, there is no complete axiomatization for FDs and INDs taken together, in which every rule is k- ary for some fixed k (and in particular, there is no finite complete axiomatization). Thus, no k-ary axiomatization can fully describe the interaction between FDs and INDs. This is true whether we consider finite implication or unrestricted implication. In the case of finite implication, this result holds, even if no relation scheme has more than two attributes, and if all of the dependencies are unary (a dependency is unary if the left-hand side and right-hand side each contain only one attribute). In the case of unrestricted implication, the result holds, even if no relation scheme has more than three attributes, each FD is unary, and each IND is binary.
- Inclusion dependencies and their interaction with functional dependencies in SQL
- On the interaction of inclusion dependencies with independence atoms
- The implication problem for functional and inclusion dependencies
- Null inclusion dependencies in relational databases
- Guaranteeing no interaction between functional dependencies and tree-like inclusion dependencies
- A normal form for relational databases that is based on domains and keys
- Algebraic dependencies
- Armstrong databases for functional and inclusion dependencies
- Formal systems for join dependencies
- Functional Dependencies in a Relational Database and Propositional Logic
- Horn clauses and database dependencies
- scientific article; zbMATH DE number 3715502 (Why is no real title available?)
- scientific article; zbMATH DE number 3727583 (Why is no real title available?)
- scientific article; zbMATH DE number 42986 (Why is no real title available?)
- scientific article; zbMATH DE number 3464827 (Why is no real title available?)
- scientific article; zbMATH DE number 3596227 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Relationships between nondeterministic and deterministic tape complexities
- Subset Dependencies and a Completeness Result for a Subclass of Embedded Multivalued Dependencies
- Template Dependencies
- Testing containment of conjunctive queries under functional and inclusion dependencies
- The implication problem for functional and inclusion dependencies
- The Implication Problem for Functional and Inclusion Dependencies is Undecidable
- Tools for Template Dependencies
- Testing containment of conjunctive queries under functional and inclusion dependencies
- Inferences for numerical dependencies
- On the formal properties of transitive inheritance in databases
- Selective inheritance of attribute values in relational databases
- The effect of unary inclusion dependencies on relational database design
- A characterization of finite fd-acyclicity
- Axiomatisation of functional dependencies in incomplete relations
- Dependency preservation in semantic databases
- Characterization of desirable properties of general database decompositions.
- Foundations of entity-relationship modeling
- Incomplete deductive databases
- Null inclusion dependencies in relational databases
- Adding inclusion dependencies to an object-oriented data model with uniqueness constraints
- How to prevent interaction of functional and inclusion dependencies
- Independent database schemes under functional and inclusion dependencies
- Functional dependency restricted insertion propagation
- A finite axiomatization of conditional independence and inclusion dependencies
- On the finite and general implication problems of independence atoms and keys
- Independence in database relations
- Recent advances in Datalog^
- Objects in relational database schemes with functional, inclusion, and exclusion dependencies
- The implication problem for functional and inclusion dependencies
- Polynomial-time implication problems for unary inclusion dependencies
- A theory of data dependencies over relational expressions
- The Implication Problem for Functional and Inclusion Dependencies is Undecidable
- On the properties of extended inclusion dependences
- Extending inclusion dependencies with conditions
- On the interaction of inclusion dependencies with independence atoms
- scientific article; zbMATH DE number 3995095 (Why is no real title available?)
- The complexity of higher-order queries
- A Generalization of the Inference Rules for Join Dependencies in Databases
- Axiomatizing first order consequences in inclusion logic
- Characterizing downwards closed, strongly first-order, relativizable dependencies
- On dependence logic
- On the finite controllability of conjunctive query answering in databases under open-world assumption
- A finite axiomatization of conditional independence and inclusion dependencies
- Data exchange: semantics and query answering
- Partition semantics for relations
- Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
- Guaranteeing no interaction between functional dependencies and tree-like inclusion dependencies
- Controlling entity integrity with key sets
- COMPLETE LOGICS FOR ELEMENTARY TEAM PROPERTIES
- Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
- Minimal coverage of generalized typed inclusion dependencies in databases
- Axiomatization of implication for probabilistic independence and unary variants of marginal identity and marginal distribution equivalence
- Inclusion with repetitions and Boolean constants -- implication problems revisited
- Axiomatizing modal inclusion logic and its variants
- Inclusion dependencies and their interaction with functional dependencies in SQL
This page was built for publication: Inclusion dependencies and their interaction with functional dependencies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1071523)
