DBScholar

Back to papers

Semantic Query Optimization in Datalog Programs (Extended Abstract)

Summary: Characterizes when semantic query optimization for arbitrary Datalog is decidable: possible iff order constraints and negated EDB subgoals appear only inside recursive rules and not in integrity constraints. If such features occur in ic's it's undecidable; yields new (un)decidability results for Datalog→UCQ containment. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h28c42f897df974da
Venue
PODS
Year
1995
Pagerank
7.8226419e-05
Overall Rank
2,937 | 80.32%
DOI
10.1145/212433.220207

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{levy_pods95,
        address = {New York, NY, USA},
        series = {{PODS} '95},
        title = {{Semantic Query Optimization in Datalog Programs (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/212433.220207},
        doi = {10.1145/212433.220207},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Levy, Alon Y. and Sagiv, Yehoshua},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank Citing Paper Year Venue Pagerank
882 Rewriting Aggregate Queries Using Views 1999 PODS 0.00013239752
2,284 Deciding Equivalences among Aggregate Queries 1998 PODS 8.6880978e-05
4,533 View-Based Query Containment 2003 PODS 6.540906e-05
4,711 Distributed Query Processing and Catalogs for Peer-to-Peer Systems 2003 CIDR 6.440991e-05
5,214 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 6.2136202e-05
5,883 Leveraging Application Data Constraints to Optimize Database-Backed Web Applications 2023 VLDB 5.9423067e-05
6,149 More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets 2011 SIGMOD 5.8557417e-05
7,795 Unifying Data and Domain Knowledge Using Virtual Views 2007 VLDB 5.4348634e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank Cited Paper Year Venue Pagerank
645 The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) 1992 PODS 0.00015188342
878 Queries Independent of Updates 1993 VLDB 0.0001326705
981 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00012688969
1,122 Query Optimization by Predicate Move-Around 1994 VLDB 0.00011915958
1,920 Automata Theory for Database Theoreticians 1989 PODS 9.3586444e-05
2,727 Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions 1993 PODS 8.0704592e-05
3,898 Constraints and Redundancy in Datalog 1992 PODS 6.9199453e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,103 Query Containment for Data Integration Systems 2000 PODS
2 9,300 Efficiently Ordering Subgoals with Access Constraints [Extended Abstract] 2006 PODS
3 1,667 On the Decidability of Query Containment under Constraints 1998 PODS
4 2,638 Convergence of Datalog over (Pre-) Semirings 2022 PODS
5 2,727 Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions 1993 PODS
6 13,453 Semigroup techniques in recursive query optimization 1990 PODS
7 3,956 A System for Semantic Query Optimization 1987 SIGMOD
8 4,482 Semantic Query Optimization in the Presence of Types 2010 PODS
9 13,436 Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases 1991 PODS
10 10,156 Semantic Acyclicity Under Constraints 2016 PODS