Database Paper Browser

Back to papers

Decidability And Expressiveness Aspects Of Logic Queries

Summary: Defines equality-free fragments H+ and YE++, proves H+ strictly more expressive and normalizable to a single recursive predicate (no =/≠), yielding a fixpoint-formula characterization. Analyzes containment/equivalence/satisfiability, extending classical results, and shows safety and literal-redundancy are undecidable. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
798
Venue
PODS
Year
1987
Pagerank
0.00038808816
Overall Rank
172 | 98.81%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank Citing Paper Year Venue Pagerank
82 Answering Queries Using Views (Extended Abstract) 1995 PODS 0.00054402763
200 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00035012858
256 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00030259041
297 Complexity of Answering Queries Using Materialized Views 1998 PODS 0.00028596715
532 Answering Recursive Queries Using Views 1997 PODS 0.00020778506
909 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015428222
938 Queries Independent of Updates 1993 VLDB 0.00015197786
1,189 Independence of Logic Database Queries and Updates 1990 PODS 0.00013441514
1,448 Theory of Database Queries (Extended Abstract) 1988 PODS 0.00011938045
1,578 Constraint Checking with Partial Information 1994 PODS 0.00011284233
1,712 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00010804573
2,036 Proof-Tree Transformation Theorems and Their Applications 1989 PODS 9.714898e-05
2,221 A New Paradigm For Parallel And Distributed Rule-Processing 1990 SIGMOD 9.2614541e-05
2,786 An Axiomatic Approach to Deciding Query Safety in Deductive Databases 1988 PODS 8.1283801e-05
2,830 Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions 1993 PODS 8.054172e-05
3,010 A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract) 1988 SIGMOD 7.7205569e-05
3,317 Data Functions, Datalog and Negation (Extended Abstract) 1988 SIGMOD 7.2283048e-05
3,413 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS 7.1240395e-05
3,435 Inference of Inequality Constraints in Logic Programs (Extended Abstract) 1991 PODS 7.0966834e-05
3,857 Constraints and Redundancy in Datalog 1992 PODS 6.6939005e-05
3,888 On the Expressive Power of Datalog: Tools and a Case Study 1990 PODS 6.6634475e-05
4,136 Safety of Datalog Queries over Infinite Databases 1989 PODS 6.4188795e-05
4,491 Non-Deterministic Languages to Express Deterministic Transformations 1990 PODS 6.1422281e-05
4,631 Tools for Datalog Boundedness 1991 PODS 6.0347472e-05
4,730 On the Equivalence of Database Restructurings Involving Object Identifiers 1991 PODS 5.967211e-05
6,031 On Datalog vs. Polynomial Time 1991 PODS 5.2415551e-05
6,417 Optimizing Existential Datalog Queries 1988 PODS 5.0717071e-05
6,876 Modular Acyclicity and Tail Recursion in Logic Programs 1991 PODS 4.8977465e-05
7,018 Hard problems for simple logic programs 1990 SIGMOD 4.8602644e-05
12,782 Static Analysis of Intensional Databases in U-Datalog 1996 PODS 4.1945683e-05
12,826 Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract) 1994 PODS 4.1945683e-05
12,829 Universal Finiteness and Satisfiability 1994 PODS 4.1945683e-05
12,884 Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations 1992 PODS 4.1945683e-05
12,981 A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule 1987 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank Cited Paper Year Venue Pagerank
154 An Optimizing Prolog Front-End to a Relational Query System 1984 SIGMOD 0.00040645847
200 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00035012858
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,275 Determinacy of Real Conjunctive Queries. The Boolean Case 2022 PODS 5.1319495e-05
1,522 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.0001153051
407 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00024004562
4,346 Languages for Relational Databases over Interpreted Structures 1997 PODS 6.2725564e-05
6,382 Finite Queries do not Have Effective Syntax 1995 PODS 5.0890445e-05
7,070 On the Decidability of Containment of Recursive Datalog Queries - Preliminary report 2004 PODS 4.843579e-05
490 Horn Clauses and the Fixpoint Query Hierarchy 1982 PODS 0.00022016773
938 Queries Independent of Updates 1993 VLDB 0.00015197786
7,248 Positive Higher-Order Queries 2010 PODS 4.7902631e-05
1,490 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011699154