Semantic Query Optimization in the Presence of Types

Summary: Unifying logic-based framework merging semantic and type-based optimization by extending the chase to conjunctive queries (with union/negation) under dependencies with negation/disjunction. Provides new chase-termination conditions, fragments ensuring minimal rewritings w.r.t. a generic cost, and complexity results. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1511
Venue: PODS
Year: 2010
Pagerank: 6.7390374e-05
Overall Rank: 4,369 | 70.03%
DOI: 10.1145/1807085.1807102

Incoming Non-self Citations Over Time

Authors

1. Michael Meier (University of Freiburg)
2. Michael Schmidt (University of Freiburg)
3. Fang Wei (University of Freiburg)
4. Georg Lausen (University of Freiburg)

BibTeX Citation

@inproceedings{meier_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Semantic Query Optimization in the Presence of Types}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807102},
        doi = {10.1145/1807085.1807102},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Meier, Michael and Schmidt, Michael and Wei, Fang and Lausen, Georg},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,874	Verification of Relational Data-Centric Dynamic Systems with External Services	2013	PODS	6.0586728e-05
7,593	Query Containment in Entity SQL (Extended Abstract)	2013	SIGMOD	5.5893275e-05
9,811	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.214913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 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
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506
134	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00030343737
525	The Chase Revisited	2008	PODS	0.00017118255
1,541	Generalized Schema-Mappings: From Termination To Tractability	2009	PODS	0.00010427058
1,777	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.7849758e-05
2,261	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	8.846133e-05
2,296	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.7908999e-05
2,481	A General Datalog-Based Framework for Tractable Query Answering over Ontologies	2009	PODS	8.5196153e-05
2,510	Peer Data Exchange	2005	PODS	8.4855313e-05
2,515	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.4811795e-05
3,247	On Chase Termination Beyond Stratification	2009	VLDB	7.5993811e-05
3,801	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	7.1130194e-05
4,426	A Chase Too Far?	2000	SIGMOD	6.7098324e-05
5,734	Methods and Rules	1993	SIGMOD	6.105443e-05
6,310	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS	5.9176726e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,122	A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization	1988	VLDB
2	13,116	Semigroup techniques in recursive query optimization	1990	PODS
3	2,296	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS
4	143	Optimization of Nonrecursive Queries	1986	VLDB
5	2,189	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB
6	12,492	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS
7	9,933	Semantic Acyclicity Under Constraints	2016	PODS
8	2,883	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
9	309	Optimization of Real Conjunctive Queries	1993	PODS
10	3,901	A System for Semantic Query Optimization	1987	SIGMOD