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.00041780711
Overall Rank
142 | 99.02%
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
47 Data Integration: A Theoretical Perspective 2002 PODS 0.00069691761
105 Inclusion dependencies and their interaction with functional dependencies (Extended abstract) 1982 PODS 0.00049082041
154 An Optimizing Prolog Front-End to a Relational Query System 1984 SIGMOD 0.00040747653
297 Complexity of Answering Queries Using Materialized Views 1998 PODS 0.00028572729
1,020 ILOG: Declarative Creation and Manipulation of Object Identifiers 1990 VLDB 0.00014614067
1,101 On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases 2003 PODS 0.00014037952
1,386 Managing Semantic Heterogeneity in Databases : A Theoretical Perspective 1997 PODS 0.00012251453
1,405 Extending Dependencies with Conditions 2007 VLDB 0.00012174499
1,489 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011687823
1,960 Inference Rules for Functional and Inclusion Dependencies 1983 PODS 9.9543811e-05
2,064 Functional and Inclusion Dependencies: A Graph Theoretic Approach 1984 PODS 9.6485054e-05
2,331 Obtaining Complete Answers from Incomplete Databases 1996 VLDB 9.019917e-05
2,482 LAURA: A Formal Data Model and her Logical Design Methodology 1983 VLDB 8.6783176e-05
2,715 Query Processing in Deductive Databases with Incomplete Information 1986 SIGMOD 8.2411079e-05
2,723 A General Datalog-Based Framework for Tractable Query Answering over Ontologies 2009 PODS 8.2314732e-05
2,732 Semantic Query Optimization in the Presence of Types 2010 PODS 8.2137395e-05
2,763 Advanced Processing for Ontological Queries 2010 VLDB 8.1614123e-05
3,325 On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information 2006 PODS 7.2149375e-05
3,367 Functional Dependencies on Cyclic Database Schemes 1983 SIGMOD 7.1665323e-05
3,494 On Chase Termination Beyond Stratification 2009 VLDB 7.0401e-05
3,877 Inclusion Dependencies and the Universal Instance 1983 PODS 6.6673599e-05
4,750 Normalization and Optimization of Schema Mappings 2009 VLDB 5.9424107e-05
4,949 Querying Graph Patterns 2011 PODS 5.8090034e-05
5,196 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 5.6311982e-05
7,108 Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable. 2016 PODS 4.8244082e-05
7,244 Positive Higher-Order Queries 2010 PODS 4.7856771e-05
7,464 The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability 2010 PODS 4.7186999e-05
7,508 Optimizing the Chase: Scalable Data Integration under Constraints 2014 VLDB 4.7135369e-05
7,672 Query Containment in Entity SQL (Extended Abstract) 2013 SIGMOD 4.6773488e-05
7,758 Containment and Equivalence of Well-Designed SPARQL 2014 PODS 4.6554272e-05
7,797 ForBackBench: A Benchmark for Chasing vs. Query-Rewriting 2022 VLDB 4.6438053e-05
7,960 On the BDD/FC Conjecture 2013 PODS 4.6089395e-05
7,987 The Equivalence of Solving Queries and Producing Tree Projections (Extended Abstract) 1986 PODS 4.6089395e-05
8,244 Optimizing Query Answering under Ontological Constraints 2011 VLDB 4.5464433e-05
8,492 Efficient XML-to-SQL Query Translation: Where to Add the Intelligence? 2004 VLDB 4.4947925e-05
8,699 Equivalence of Nested Queries with Mixed Semantics 2009 PODS 4.4604187e-05
8,816 Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability 2015 PODS 4.438964e-05
9,001 Efficiently Enumerating Answers to Ontology-Mediated Queries 2022 PODS 4.4082817e-05
9,737 The Space-Efficient Core of Vadalog 2019 PODS 4.2895392e-05
9,740 Containment of Conjunctive Object Meta-Queries 2006 VLDB 4.2895392e-05
10,362 No Cliques Allowed: The Next Step Towards BDD/FC Conjecture 2025 PODS 4.1905499e-05
11,303 SparqLog: A System for Efficient Evaluation of SPARQL 1.1 Queries via Datalog 2023 VLDB 4.1905499e-05
11,327 A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys 2022 PODS 4.1905499e-05
11,388 Rewriting the Infinite Chase 2022 VLDB 4.1905499e-05
11,560 The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs 2020 PODS 4.1905499e-05
11,837 Semantic Acyclicity Under Constraints 2016 PODS 4.1905499e-05
12,807 Applying an update method to a set of receivers (extended abstract) 1995 PODS 4.1905499e-05
12,997 Independent Database Schemes Under Functional And Inclusion Dependencies 1987 VLDB 4.1905499e-05
13,007 ON FINITE FD-ACYCLICITY (Extended Abstract) 1986 PODS 4.1905499e-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.0007528369
58 Efficient Optimization of a Class of Relational Expressions 1978 SIGMOD 0.00064817807
105 Inclusion dependencies and their interaction with functional dependencies (Extended abstract) 1982 PODS 0.00049082041
390 Design Of Relational Views Over Network Schemas 1979 SIGMOD 0.00024612268
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,174 Query Containment for Data Integration Systems 2000 PODS 7.444226e-05
5,719 On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract) 1997 PODS 5.3551435e-05
1,489 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011687823
2,396 Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract) 1992 PODS 8.8892825e-05
401 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00024281448
6,946 Tree-Width and Functional Dependencies in Databases 2008 PODS 4.8874695e-05
7,603 Polynomial-time program transformations in deductive databases 1990 PODS 4.6959912e-05
4,055 On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates 1998 PODS 6.4906839e-05
1,520 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.00011524911
1,959 Deciding Containment for Queries with Complex Objects (Extended Abstract) 1997 PODS 9.958725e-05