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.00038731283
Overall Rank
173 | 98.80%
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.00054430106
209 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00034147258
256 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00030241337
297 Complexity of Answering Queries Using Materialized Views 1998 PODS 0.00028572729
533 Answering Recursive Queries Using Views 1997 PODS 0.00020767726
907 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015417107
937 Queries Independent of Updates 1993 VLDB 0.00015194231
1,189 Independence of Logic Database Queries and Updates 1990 PODS 0.0001342924
1,450 Theory of Database Queries (Extended Abstract) 1988 PODS 0.00011926567
1,579 Constraint Checking with Partial Information 1994 PODS 0.00011273105
1,636 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00011058643
2,038 Proof-Tree Transformation Theorems and Their Applications 1989 PODS 9.7062591e-05
2,227 A New Paradigm For Parallel And Distributed Rule-Processing 1990 SIGMOD 9.2521507e-05
2,790 An Axiomatic Approach to Deciding Query Safety in Deductive Databases 1988 PODS 8.1203289e-05
2,836 Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions 1993 PODS 8.0466188e-05
3,012 A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract) 1988 SIGMOD 7.7129076e-05
3,320 Data Functions, Datalog and Negation (Extended Abstract) 1988 SIGMOD 7.2212998e-05
3,414 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS 7.1172834e-05
3,440 Inference of Inequality Constraints in Logic Programs (Extended Abstract) 1991 PODS 7.0897313e-05
3,859 Constraints and Redundancy in Datalog 1992 PODS 6.6875648e-05
3,889 On the Expressive Power of Datalog: Tools and a Case Study 1990 PODS 6.6570358e-05
4,138 Safety of Datalog Queries over Infinite Databases 1989 PODS 6.4127061e-05
4,494 Non-Deterministic Languages to Express Deterministic Transformations 1990 PODS 6.1363251e-05
4,631 Tools for Datalog Boundedness 1991 PODS 6.0289457e-05
4,729 On the Equivalence of Database Restructurings Involving Object Identifiers 1991 PODS 5.9614713e-05
6,035 On Datalog vs. Polynomial Time 1991 PODS 5.2365238e-05
6,412 Optimizing Existential Datalog Queries 1988 PODS 5.0668361e-05
6,881 Modular Acyclicity and Tail Recursion in Logic Programs 1991 PODS 4.8929836e-05
7,018 Hard problems for simple logic programs 1990 SIGMOD 4.8555836e-05
12,791 Static Analysis of Intensional Databases in U-Datalog 1996 PODS 4.1905499e-05
12,835 Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract) 1994 PODS 4.1905499e-05
12,838 Universal Finiteness and Satisfiability 1994 PODS 4.1905499e-05
12,894 Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations 1992 PODS 4.1905499e-05
12,992 A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule 1987 SIGMOD 4.1905499e-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.00040747653
209 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00034147258
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,273 Determinacy of Real Conjunctive Queries. The Boolean Case 2022 PODS 5.1270241e-05
1,520 The Containment Problem for Real Conjunctive Queries with Inequalities 2006 PODS 0.00011524911
401 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00024281448
6,380 Finite Queries do not Have Effective Syntax 1995 PODS 5.0841675e-05
4,343 Languages for Relational Databases over Interpreted Structures 1997 PODS 6.2665123e-05
7,066 On the Decidability of Containment of Recursive Datalog Queries - Preliminary report 2004 PODS 4.8389293e-05
490 Horn Clauses and the Fixpoint Query Hierarchy 1982 PODS 0.00021979489
937 Queries Independent of Updates 1993 VLDB 0.00015194231
7,244 Positive Higher-Order Queries 2010 PODS 4.7856771e-05
1,489 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011687823