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)
Incoming Non-self Citations Over Time
Authors
- 1. Alon Y. Levy
- 2. Yehoshua Sagiv
Incoming Citations (Sorted by Pagerank)
Showing 8 of 8 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 971 | Rewriting Aggregate Queries Using Views | 1999 | PODS | 0.00014925576 |
| 2,103 | Deciding Equivalences among Aggregate Queries | 1998 | PODS | 9.5385023e-05 |
| 3,858 | Distributed Query Processing and Catalogs for Peer-to-Peer Systems | 2003 | CIDR | 6.6913167e-05 |
| 4,553 | View-Based Query Containment | 2003 | PODS | 6.091702e-05 |
| 5,195 | Equivalence of Queries Combining Set and Bag-Set Semantics | 2006 | PODS | 5.6366303e-05 |
| 6,254 | More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets | 2011 | SIGMOD | 5.1368042e-05 |
| 7,638 | Unifying Data and Domain Knowledge Using Virtual Views | 2007 | VLDB | 4.6905993e-05 |
| 9,410 | Leveraging Application Data Constraints to Optimize Database-Backed Web Applications | 2023 | VLDB | 4.3441378e-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 |
|---|---|---|---|---|
| 581 | The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) | 1992 | PODS | 0.00019767772 |
| 909 | On the Equivalence of Recursive and Nonrecursive Datalog Programs | 1992 | PODS | 0.00015428222 |
| 938 | Queries Independent of Updates | 1993 | VLDB | 0.00015197786 |
| 1,302 | Query Optimization by Predicate Move-Around | 1994 | VLDB | 0.00012705525 |
| 1,688 | Automata Theory for Database Theoreticians | 1989 | PODS | 0.00010913301 |
| 2,830 | Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions | 1993 | PODS | 8.054172e-05 |
| 3,857 | Constraints and Redundancy in Datalog | 1992 | PODS | 6.6939005e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,168 | Query Containment for Data Integration Systems | 2000 | PODS | 7.4508875e-05 |
| 8,937 | Efficiently Ordering Subgoals with Access Constraints [Extended Abstract] | 2006 | PODS | 4.427232e-05 |
| 1,490 | On the Decidability of Query Containment under Constraints | 1998 | PODS | 0.00011699154 |
| 2,907 | Convergence of Datalog over (Pre-) Semirings | 2022 | PODS | 7.933806e-05 |
| 2,830 | Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions | 1993 | PODS | 8.054172e-05 |
| 12,921 | Semigroup techniques in recursive query optimization | 1990 | PODS | 4.1945683e-05 |
| 4,119 | A System for Semantic Query Optimization | 1987 | SIGMOD | 6.4365852e-05 |
| 2,727 | Semantic Query Optimization in the Presence of Types | 2010 | PODS | 8.2216778e-05 |
| 12,904 | Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases | 1991 | PODS | 4.1945683e-05 |
| 11,829 | Semantic Acyclicity Under Constraints | 2016 | PODS | 4.1945683e-05 |