The Selfish Models Property: Bounding the Complexity of Query Containment and Entailment Problems
Summary: Introduce the "selfish models" property: when containment reduces to enumerating a bounded set of models of the antecedent and testing the consequent, it gives decidability and complexity upper bounds. Used to uniformly recover known results and derive two new FO containment upper bounds. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Hubie Chen (Birkbeck, University of London)
BibTeX Citation
@inproceedings{chen_pods19,
address = {New York, NY, USA},
series = {{PODS} '19},
title = {{The Selfish Models Property: Bounding the Complexity of Query Containment and Entailment Problems}},
url = {https://dl.acm.org/doi/10.1145/3294052.3319682},
doi = {10.1145/3294052.3319682},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Chen, Hubie},
year = {2019}
}
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 22 | Data Integration: A Theoretical Perspective | 2002 | PODS | 0.00056204792 |
| 69 | Answering Queries Using Views (Extended Abstract) | 1995 | PODS | 0.00038090878 |
| 4,266 | Counting Answers to Existential Positive Queries: A Complexity Classification | 2016 | PODS | 6.7936492e-05 |
| 4,445 | View-Based Query Containment | 2003 | PODS | 6.699172e-05 |
| 12,229 | The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity | 2013 | PODS | 5.093636e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 10,175 | Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories | 2026 | PODS |
| 2 | 382 | Conjunctive-Query Containment and Constraint Satisfaction | 1998 | PODS |
| 3 | 3,433 | On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information | 2006 | PODS |
| 4 | 4,445 | View-Based Query Containment | 2003 | PODS |
| 5 | 9,946 | Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability. | 2024 | PODS |
| 6 | 1,777 | Deciding Containment for Queries with Complex Objects (Extended Abstract) | 1997 | PODS |
| 7 | 6,926 | On the Decidability of Containment of Recursive Datalog Queries - Preliminary report | 2004 | PODS |
| 8 | 1,269 | The Containment Problem for Real Conjunctive Queries with Inequalities | 2006 | PODS |
| 9 | 3,039 | Query Containment for Data Integration Systems | 2000 | PODS |
| 10 | 1,630 | On the Decidability of Query Containment under Constraints | 1998 | PODS |