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.00014915911 |
| 2,105 | Deciding Equivalences among Aggregate Queries | 1998 | PODS | 9.5309231e-05 |
| 3,861 | Distributed Query Processing and Catalogs for Peer-to-Peer Systems | 2003 | CIDR | 6.6848619e-05 |
| 4,552 | View-Based Query Containment | 2003 | PODS | 6.0856349e-05 |
| 5,196 | Equivalence of Queries Combining Set and Bag-Set Semantics | 2006 | PODS | 5.6311982e-05 |
| 6,253 | More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets | 2011 | SIGMOD | 5.1318715e-05 |
| 7,638 | Unifying Data and Domain Knowledge Using Virtual Views | 2007 | VLDB | 4.6861004e-05 |
| 9,416 | Leveraging Application Data Constraints to Optimize Database-Backed Web Applications | 2023 | VLDB | 4.3399748e-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 |
|---|---|---|---|---|
| 582 | The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) | 1992 | PODS | 0.00019753367 |
| 907 | On the Equivalence of Recursive and Nonrecursive Datalog Programs | 1992 | PODS | 0.00015417107 |
| 937 | Queries Independent of Updates | 1993 | VLDB | 0.00015194231 |
| 1,303 | Query Optimization by Predicate Move-Around | 1994 | VLDB | 0.00012692678 |
| 1,687 | Automata Theory for Database Theoreticians | 1989 | PODS | 0.0001090256 |
| 2,836 | Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions | 1993 | PODS | 8.0466188e-05 |
| 3,859 | Constraints and Redundancy in Datalog | 1992 | PODS | 6.6875648e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,174 | Query Containment for Data Integration Systems | 2000 | PODS | 7.444226e-05 |
| 1,489 | On the Decidability of Query Containment under Constraints | 1998 | PODS | 0.00011687823 |
| 8,941 | Efficiently Ordering Subgoals with Access Constraints [Extended Abstract] | 2006 | PODS | 4.4229886e-05 |
| 2,912 | Convergence of Datalog over (Pre-) Semirings | 2022 | PODS | 7.9261665e-05 |
| 2,836 | Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions | 1993 | PODS | 8.0466188e-05 |
| 12,931 | Semigroup techniques in recursive query optimization | 1990 | PODS | 4.1905499e-05 |
| 4,118 | A System for Semantic Query Optimization | 1987 | SIGMOD | 6.4313372e-05 |
| 2,732 | Semantic Query Optimization in the Presence of Types | 2010 | PODS | 8.2137395e-05 |
| 12,914 | Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases | 1991 | PODS | 4.1905499e-05 |
| 11,837 | Semantic Acyclicity Under Constraints | 2016 | PODS | 4.1905499e-05 |