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: 797
Venue: PODS
Year: 1987
Pagerank: 0.00027231487
Overall Rank: 174 | 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
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
225	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00024101949
300	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00022046803
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
515	Answering Recursive Queries Using Views	1997	PODS	0.00017177428
853	Queries Independent of Updates	1993	VLDB	0.00013587101
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
1,314	Independence of Logic Database Queries and Updates	1990	PODS	0.00011182427
1,489	Constraint Checking with Partial Information	1994	PODS	0.00010612225
1,653	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.000101081
1,970	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.3746238e-05
2,110	Theory of Database Queries (Extended Abstract)	1988	PODS	9.1532803e-05
2,662	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.2831426e-05
3,025	An Axiomatic Approach to Deciding Query Safety in Deductive Databases	1988	PODS	7.8386928e-05
3,076	A New Paradigm For Parallel And Distributed Rule-Processing	1990	SIGMOD	7.7817058e-05
3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.60327e-05
3,355	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.4912272e-05
3,476	Data Functions, Datalog and Negation (Extended Abstract)	1988	SIGMOD	7.3807586e-05
3,712	Non-Deterministic Languages to Express Deterministic Transformations	1990	PODS	7.1777407e-05
3,800	On the Expressive Power of Datalog: Tools and a Case Study	1990	PODS	7.1130834e-05
3,812	Constraints and Redundancy in Datalog	1992	PODS	7.105413e-05
3,824	Inference of Inequality Constraints in Logic Programs (Extended Abstract)	1991	PODS	7.0919497e-05
4,555	On the Equivalence of Database Restructurings Involving Object Identifiers	1991	PODS	6.6344715e-05
4,615	Tools for Datalog Boundedness	1991	PODS	6.6050069e-05
6,077	Safety of Datalog Queries over Infinite Databases	1989	PODS	5.9850223e-05
6,209	On Datalog vs. Polynomial Time	1991	PODS	5.9425753e-05
6,307	Optimizing Existential Datalog Queries	1988	PODS	5.9196585e-05
7,454	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.6128072e-05
7,549	Hard problems for simple logic programs	1990	SIGMOD	5.6011655e-05
12,976	Static Analysis of Intensional Databases in U-Datalog	1996	PODS	5.093636e-05
13,020	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	5.093636e-05
13,023	Universal Finiteness and Satisfiability	1994	PODS	5.093636e-05
13,078	Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations	1992	PODS	5.093636e-05
13,179	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	5.093636e-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
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
357	An Optimizing Prolog Front-End to a Relational Query System	1984	SIGMOD	0.00020283734

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,542	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS
2	1,269	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
3	382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS
4	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS
5	6,286	Finite Queries do not Have Effective Syntax	1995	PODS
6	6,926	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS
7	888	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS
8	853	Queries Independent of Updates	1993	VLDB
9	7,654	Positive Higher-Order Queries	2010	PODS
10	1,630	On the Decidability of Query Containment under Constraints	1998	PODS