Query Containment for Data Integration Systems

Summary: Define “relative containment” to capture query containment relative to the sources available to a data integration system (vs. classical containment). Provide tight complexity/decidability bounds for datalog fragments including conjunctive queries, show decidability even with binding-pattern access restrictions, and give tight extensions when comparisons are allowed. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h07ca80fe16fb9737
Venue: PODS
Year: 2000
Pagerank: 7.649698e-05
Overall Rank: 3,097 | 79.19%
DOI: 10.1145/335168.335208

Incoming Non-self Citations Over Time

Authors

1. Todd Millstein (University of Washington)
2. Alon Levy (University of Washington)
3. Marc Friedman (University of Washington; Viathan Corporation)

BibTeX Citation

@inproceedings{millstein_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{Query Containment for Data Integration Systems}},
        url = {https://dl.acm.org/doi/10.1145/335168.335208},
        doi = {10.1145/335168.335208},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Millstein, Todd and Levy, Alon and Friedman, Marc},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055018384
2,790	Processing First-Order Queries under Limited Access Patterns	2004	PODS	8.0065062e-05
4,516	View-Based Query Containment	2003	PODS	6.5619066e-05
6,891	Query Processing under GLAV Mappings for Relational and Graph Databases	2013	VLDB	5.6523677e-05
10,060	Containment of Conjunctive Object Meta-Queries	2006	VLDB	5.0853865e-05
12,873	Optimization of Multi-Domain Queries on the Web	2008	VLDB	4.9769913e-05
13,021	Determining Source Contribution in Integration Systems	2005	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.0003753293
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00031616101
162	Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity	1998	SIGMOD	0.00027524669
167	Query Transformation for PSJ-queries	1987	VLDB	0.00027190577
173	Optimizing Queries across Diverse Data Sources	1997	VLDB	0.00026814969
238	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023580688
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021673683
334	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00020682536
399	Query Caching and Optimization in Distributed Mediator Systems	1996	SIGMOD	0.00019134783
410	Semantic Data Caching and Replacement	1996	VLDB	0.00018796567
532	Answering Recursive Queries Using Views	1997	PODS	0.00016821057
577	The GMAP: A Versatile Tool for Physical Data Independence	1994	VLDB	0.00016111779
642	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015236058
875	Queries Independent of Updates	1993	VLDB	0.0001331025
979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012723733
1,521	Constraint Checking with Partial Information	1994	PODS	0.00010374735
2,574	Rewriting Queries Using Views in Description Logics	1997	PODS	8.2749164e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,924	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
2	10,134	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS
3	2,350	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS
4	3,526	Bag Query Containment and Information Theory	2020	PODS
5	10,060	Containment of Conjunctive Object Meta-Queries	2006	VLDB
6	7,066	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS
7	1,276	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
8	391	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS
9	4,516	View-Based Query Containment	2003	PODS
10	1,661	On the Decidability of Query Containment under Constraints	1998	PODS