Testing containment of conjunctive queries under functional and inclusion dependencies
The relational database model is studied from the point of view of optimization of queries. A brief basic definition of the relational database model, a formal definition of inclusion (IND) and functional (FD) dependencies and the key-based property are presented (Section 2). Next, the authors show how to test for query containment in nondeterministic polynomial time if the set of dependencies obeys a fixed bound on IND width and either contains no FD or is key-based. The results assume that infinite databases are allowed (Section 3). The following discussion deals with a more practical problem: containment for finite databases (Section 4). Final remarks and a discussion of open problems and directions of future research are added to conclude the article.
- A normal form for relational databases that is based on domains and keys
- A relational model of data for large shared data banks
- Equivalences among Relational Expressions
- Inclusion dependencies and their interaction with functional dependencies
- Optimizing Conjunctive Queries that Contain Untyped Variables
- The implication problem for functional and inclusion dependencies
- Inclusion dependencies and their interaction with functional dependencies
- Testing unboundedness of database schemes and functional dependencies
- Some results on the containment and minimization of (in)equality queries
- Optimization of a subclass of conjunctive queries
- Null inclusion dependencies in relational databases
- Logical foundations of information disclosure in ontology-based data integration
- Independent database schemes under functional and inclusion dependencies
- Testing bag-containment of conjunctive queries
- Computing optimal repairs of quantified ABoxes w.r.t. static \(\mathcal{EL}\) TBoxes
- Logical separability of labeled data examples under ontologies
- Query answering under probabilistic uncertainty in Datalog\(+/-\) ontologies
- Tractable reasoning and efficient query answering in description logics: The DL-Lite family
- On the finite and general implication problems of independence atoms and keys
- Semantic acyclicity for conjunctive queries: approximations and constraints
- On the interaction of existential rules and equality constraints in ontology querying
- Converging to the chase -- a tool for finite controllability
- Querying regular graph patterns
- Querying incomplete data over extended ER schemata
- Relaxed notions of schema mapping equivalence revisited
- Towards more expressive ontology languages: the query answering problem
- Ontologies and Databases: The DL-Lite Approach
- Dynamic query optimization under access limitations and dependencies
- Extending inclusion dependencies with conditions
- Capturing model-based ontology evolution at the instance level: the case of DL-Lite
- Semantic query optimization in the presence of types
- On the containment of conjunctive queries
- Finite model reasoning over existential rules
- Datalog and Its Extensions for Semantic Web Databases
- Disjunctive Datalog with existential quantifiers: semantics, decidability, and complexity issues
- The complexity of higher-order queries
- Datalog: Bag Semantics via Set Semantics
- When can we answer queries using result-bounded data interfaces?
- Reasoning on anonymity in Datalog+/--
- On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules
- The impact of active domain predicates on guarded existential rules
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- On the finite controllability of conjunctive query answering in databases under open-world assumption
- A Chasm Between Identity and Equivalence Testing with Conditional Queries
- Combining decidability paradigms for existential rules
- Logic, languages, and rules for web data extraction and reasoning over data
- Guaranteeing no interaction between functional dependencies and tree-like inclusion dependencies
- Answer Counting under Guarded TGDs
- Polynomial combined first-order rewritings for linear and guarded existential rules
- On rules with existential variables: walking the decidability line
- Query containment under bag and bag-set semantics
- Conjunctive query containment with respect to views and constraints
- Containment of regular path queries under path constraints
- Dyadic existential rules
- Answer counting under guarded TGDs
- Fine-grained complexity of ontology mediated queries (invited paper)
- Tighter bounds for query answering with guarded TGDs
- Inclusion dependencies and their interaction with functional dependencies in SQL
- Answering path queries under linear and guarded existential rules
This page was built for publication: Testing containment of conjunctive queries under functional and inclusion dependencies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1057666)