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.8518874e-05
Overall Rank
2,923 | 80.35%
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
880 Rewriting Aggregate Queries Using Views 1999 PODS 0.00013280642
2,269 Deciding Equivalences among Aggregate Queries 1998 PODS 8.7196256e-05
4,514 View-Based Query Containment 2003 PODS 6.5650143e-05
4,695 Distributed Query Processing and Catalogs for Peer-to-Peer Systems 2003 CIDR 6.4654203e-05
5,187 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 6.2371772e-05
5,869 Leveraging Application Data Constraints to Optimize Database-Backed Web Applications 2023 VLDB 5.9648445e-05
6,131 More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets 2011 SIGMOD 5.8779512e-05
7,770 Unifying Data and Domain Knowledge Using Virtual Views 2007 VLDB 5.4554766e-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
642 The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) 1992 PODS 0.00015243164
875 Queries Independent of Updates 1993 VLDB 0.00013316445
979 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00012729663
1,119 Query Optimization by Predicate Move-Around 1994 VLDB 0.00011950395
1,908 Automata Theory for Database Theoreticians 1989 PODS 9.3940283e-05
2,716 Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions 1993 PODS 8.1006747e-05
3,886 Constraints and Redundancy in Datalog 1992 PODS 6.9461797e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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