Database Paper Browser

Back to papers

Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)

Summary: Establishes CQ containment (hence equivalence/non-minimality) in NP for inclusion dependencies when either no FDs or FDs are key-based, under infinite-database semantics. Finite databases may add containments, but a compactness theorem rules out finite-only counterexamples in the key-based case. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
623
Venue
PODS
Year
1982
Pagerank
0.00041462501
Overall Rank
144 | 99.01%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 49 of 49 citing papers.

Rank Citing Paper Year Venue Pagerank
48 Data Integration: A Theoretical Perspective 2002 PODS 0.00069720859
104 Inclusion dependencies and their interaction with functional dependencies (Extended abstract) 1982 PODS 0.00048766186
154 An Optimizing Prolog Front-End to a Relational Query System 1984 SIGMOD 0.00040645847
297 Complexity of Answering Queries Using Materialized Views 1998 PODS 0.00028596715
1,018 ILOG: Declarative Creation and Manipulation of Object Identifiers 1990 VLDB 0.00014627963
1,102 On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases 2003 PODS 0.00014049364
1,384 Managing Semantic Heterogeneity in Databases : A Theoretical Perspective 1997 PODS 0.00012262892
1,401 Extending Dependencies with Conditions 2007 VLDB 0.00012187775
1,490 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011699154
1,954 Inference Rules for Functional and Inclusion Dependencies 1983 PODS 9.9639379e-05
2,058 Functional and Inclusion Dependencies: A Graph Theoretic Approach 1984 PODS 9.6585264e-05
2,327 Obtaining Complete Answers from Incomplete Databases 1996 VLDB 9.0276061e-05
2,481 LAURA: A Formal Data Model and her Logical Design Methodology 1983 VLDB 8.6870033e-05
2,712 Query Processing in Deductive Databases with Incomplete Information 1986 SIGMOD 8.2488274e-05
2,720 A General Datalog-Based Framework for Tractable Query Answering over Ontologies 2009 PODS 8.2367715e-05
2,727 Semantic Query Optimization in the Presence of Types 2010 PODS 8.2216778e-05
2,755 Advanced Processing for Ontological Queries 2010 VLDB 8.1690695e-05
3,324 On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information 2006 PODS 7.2213002e-05
3,361 Functional Dependencies on Cyclic Database Schemes 1983 SIGMOD 7.1735665e-05
3,489 On Chase Termination Beyond Stratification 2009 VLDB 7.0468114e-05
3,877 Inclusion Dependencies and the Universal Instance 1983 PODS 6.6739427e-05
4,752 Normalization and Optimization of Schema Mappings 2009 VLDB 5.9481448e-05
4,946 Querying Graph Patterns 2011 PODS 5.8149362e-05
5,195 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 5.6366303e-05
7,110 Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable. 2016 PODS 4.8290408e-05
7,248 Positive Higher-Order Queries 2010 PODS 4.7902631e-05
7,473 The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability 2010 PODS 4.7198203e-05
7,509 Optimizing the Chase: Scalable Data Integration under Constraints 2014 VLDB 4.7180617e-05
7,674 Query Containment in Entity SQL (Extended Abstract) 2013 SIGMOD 4.6818255e-05
7,758 Containment and Equivalence of Well-Designed SPARQL 2014 PODS 4.6598957e-05
7,795 ForBackBench: A Benchmark for Chasing vs. Query-Rewriting 2022 VLDB 4.6482625e-05
7,957 On the BDD/FC Conjecture 2013 PODS 4.613363e-05
7,984 The Equivalence of Solving Queries and Producing Tree Projections (Extended Abstract) 1986 PODS 4.613363e-05
8,249 Optimizing Query Answering under Ontological Constraints 2011 VLDB 4.5508077e-05
8,493 Efficient XML-to-SQL Query Translation: Where to Add the Intelligence? 2004 VLDB 4.4991066e-05
8,704 Equivalence of Nested Queries with Mixed Semantics 2009 PODS 4.4647149e-05
8,815 Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability 2015 PODS 4.4432234e-05
8,995 Efficiently Enumerating Answers to Ontology-Mediated Queries 2022 PODS 4.412512e-05
9,738 The Space-Efficient Core of Vadalog 2019 PODS 4.2936538e-05
9,741 Containment of Conjunctive Object Meta-Queries 2006 VLDB 4.2936538e-05
10,350 No Cliques Allowed: The Next Step Towards BDD/FC Conjecture 2025 PODS 4.1945683e-05
11,301 SparqLog: A System for Efficient Evaluation of SPARQL 1.1 Queries via Datalog 2023 VLDB 4.1945683e-05
11,325 A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys 2022 PODS 4.1945683e-05
11,386 Rewriting the Infinite Chase 2022 VLDB 4.1945683e-05
11,556 The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs 2020 PODS 4.1945683e-05
11,829 Semantic Acyclicity Under Constraints 2016 PODS 4.1945683e-05
12,798 Applying an update method to a set of receivers (extended abstract) 1995 PODS 4.1945683e-05
12,986 Independent Database Schemes Under Functional And Inclusion Dependencies 1987 VLDB 4.1945683e-05
12,996 ON FINITE FD-ACYCLICITY (Extended Abstract) 1986 PODS 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
38 Testing Implications Of Data Dependencies 1979 SIGMOD 0.00075110004
58 Efficient Optimization of a Class of Relational Expressions 1978 SIGMOD 0.00064826446
104 Inclusion dependencies and their interaction with functional dependencies (Extended abstract) 1982 PODS 0.00048766186
397 Design Of Relational Views Over Network Schemas 1979 SIGMOD 0.00024384664
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,168 Query Containment for Data Integration Systems 2000 PODS 7.4508875e-05
1,490 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011699154
5,709 On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract) 1997 PODS 5.3602702e-05
2,398 Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract) 1992 PODS 8.8973978e-05
407 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00024004562
6,949 Tree-Width and Functional Dependencies in Databases 2008 PODS 4.8898337e-05
7,598 Polynomial-time program transformations in deductive databases 1990 PODS 4.7004867e-05
4,048 On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates 1998 PODS 6.4968603e-05
1,952 Deciding Containment for Queries with Complex Objects (Extended Abstract) 1997 PODS 9.9677831e-05
1,522 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.0001153051