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: h0efd536f34d71ff1
Venue: PODS
Year: 1987
Pagerank: 0.00026563438
Overall Rank: 179 | 98.81%
DOI: 10.1145/28659.28685

Incoming Non-self Citations Over Time

Authors

1. Oded Shmueh (Microelectronics And Technology Computer Corporation; Technion)

BibTeX Citation

@inproceedings{shmueh_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{DECIDABILITY AND EXPRESSIVENESS ASPECTS OF LOGIC QUERIES}},
        url = {https://dl.acm.org/doi/10.1145/28659.28685},
        doi = {10.1145/28659.28685},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Shmueh, Oded},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037421163
239	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023510465
299	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00021766741
319	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021142713
534	Answering Recursive Queries Using Views	1997	PODS	0.0001677412
878	Queries Independent of Updates	1993	VLDB	0.0001326705
981	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012688969
1,355	Independence of Logic Database Queries and Updates	1990	PODS	0.00010910619
1,522	Constraint Checking with Partial Information	1994	PODS	0.00010341308
1,688	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8481921e-05
2,038	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.1328477e-05
2,161	Theory of Database Queries (Extended Abstract)	1988	PODS	8.9203568e-05
2,727	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.0704592e-05
3,098	An Axiomatic Approach to Deciding Query Safety in Deductive Databases	1988	PODS	7.6343278e-05
3,147	A New Paradigm For Parallel And Distributed Rule-Processing	1990	SIGMOD	7.5793335e-05
3,326	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.4103766e-05
3,427	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.2959413e-05
3,551	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.188942e-05
3,808	Non-Deterministic Languages to Express Deterministic Transformations	1990	PODS	6.9901793e-05
3,888	On the Expressive Power of Datalog: Tools and a Case Study	1990	PODS	6.9272122e-05
3,898	Constraints and Redundancy in Datalog	1992	PODS	6.9199453e-05
3,917	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	6.90746e-05
4,664	On the Equivalence of Database Restructurings Involving Object Identifiers	1991	PODS	6.4635254e-05
4,728	Tools for Datalog Boundedness	1991	PODS	6.4324136e-05
6,219	Safety of Datalog Queries over Infinite Databases	1989	PODS	5.8286278e-05
6,384	On Datalog vs. Polynomial Time	1991	PODS	5.78729e-05
6,448	Optimizing Existential Datalog Queries	1988	PODS	5.7650024e-05
7,622	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.4663379e-05
7,716	Hard problems for simple logic programs	1990	SIGMOD	5.4548161e-05
13,313	Static Analysis of Intensional Databases in U-Datalog	1996	PODS	4.9605343e-05
13,357	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	4.9605343e-05
13,360	Universal Finiteness and Satisfiability	1994	PODS	4.9605343e-05
13,415	Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations	1992	PODS	4.9605343e-05
13,516	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.9605343e-05

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
319	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021142713
369	An Optimizing Prolog Front-End to a Relational Query System	1984	SIGMOD	0.00019791902

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,683	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS
2	1,279	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
3	391	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS
4	6,422	Finite Queries do not Have Effective Syntax	1995	PODS
5	4,448	Languages for Relational Databases over Interpreted Structures	1997	PODS
6	7,086	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS
7	916	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS
8	878	Queries Independent of Updates	1993	VLDB
9	7,829	Positive Higher-Order Queries	2010	PODS
10	1,667	On the Decidability of Query Containment under Constraints	1998	PODS