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
1064
Venue
PODS
Year
1995
Pagerank
8.0012184e-05
Overall Rank
2,883 | 80.23%
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
869 Rewriting Aggregate Queries Using Views 1999 PODS 0.00013503594
2,238 Deciding Equivalences among Aggregate Queries 1998 PODS 8.8882317e-05
4,445 View-Based Query Containment 2003 PODS 6.699172e-05
4,594 Distributed Query Processing and Catalogs for Peer-to-Peer Systems 2003 CIDR 6.6138159e-05
5,062 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 6.3799383e-05
6,008 More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets 2011 SIGMOD 6.0114207e-05
7,621 Unifying Data and Domain Knowledge Using Virtual Views 2007 VLDB 5.5806924e-05
9,561 Leveraging Application Data Constraints to Optimize Database-Backed Web Applications 2023 VLDB 5.2528121e-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
633 The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) 1992 PODS 0.00015560958
853 Queries Independent of Updates 1993 VLDB 0.00013587101
953 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00012997935
1,124 Query Optimization by Predicate Move-Around 1994 VLDB 0.00012087356
1,856 Automata Theory for Database Theoreticians 1989 PODS 9.6053834e-05
2,662 Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions 1993 PODS 8.2831426e-05
3,812 Constraints and Redundancy in Datalog 1992 PODS 7.105413e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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