Optimizing Existential Datalog Queries

Summary: Defines existential subqueries in function-free Datalog with a syntactic test and rule rewrites that expose them for cut-like pruning in bottom-up evaluation. Uses projection-pushing to remove arguments in recursive rules and to detect redundant rules. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 818
Venue: PODS
Year: 1988
Pagerank: 5.9196585e-05
Overall Rank: 6,307 | 56.73%
DOI: 10.1145/308386.308420

Incoming Non-self Citations Over Time

Authors

1. Raghu Ramakrishnan (University of Wisconsin)
2. Catriel Beeri (Hebrew University; Microelectronics And Technology Computer Corporation)
3. Ravi Krishnamurthy (Hebrew University)

BibTeX Citation

@inproceedings{ramakrishnan_pods88,
        address = {New York, NY, USA},
        series = {{PODS} '88},
        title = {{Optimizing Existential Datalog Queries}},
        url = {https://dl.acm.org/doi/10.1145/308386.308420},
        doi = {10.1145/308386.308420},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ramakrishnan, Raghu and Beeri, Catriel and Krishnamurthy, Ravi},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,099	Argument Reduction by Factoring	1989	VLDB	6.9030568e-05
4,975	Implementation of the CORAL Deductive Database System	1993	SIGMOD	6.41738e-05
7,885	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	5.5228272e-05
8,296	How to Forget the Past Without Repeating It	1990	VLDB	5.4574671e-05
13,076	Learning Efficient Query Processing Strategies	1992	PODS	5.093636e-05
13,105	A Non-deterministic Deductive Database Language	1991	SIGMOD	5.093636e-05

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
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
344	On the Power of Magic	1987	PODS	0.00020659405
1,051	CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract)	1986	PODS	0.00012406675
1,498	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00010567892
7,599	Functional Dependencies in Logic Programs	1985	VLDB	5.5869408e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,310	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS
2	11,135	Query Optimization by Quantifier Elimination	2024	PODS
3	13,116	Semigroup techniques in recursive query optimization	1990	PODS
4	7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS
5	313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS
6	7,035	Optimizing Recursive Queries with Program Synthesis	2022	SIGMOD
7	2,883	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
8	6,785	Expressiveness of Guarded Existential Rule Languages	2014	PODS
9	6,613	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
10	13,099	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS