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: h4d2b440ec4d50715
Venue: PODS
Year: 1988
Pagerank: 5.7868542e-05
Overall Rank: 6,433 | 56.75%
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,187	Argument Reduction by Factoring	1989	VLDB	6.748235e-05
5,099	Implementation of the CORAL Deductive Database System	1993	SIGMOD	6.2734925e-05
8,051	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	5.3992494e-05
8,464	How to Forget the Past Without Repeating It	1990	VLDB	5.3350162e-05
13,366	Learning Efficient Query Processing Strategies	1992	PODS	4.9793485e-05
13,395	A Non-deterministic Deductive Database Language	1991	SIGMOD	4.9793485e-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
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038009523
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.000266613
352	On the Power of Magic	1987	PODS	0.00020223279
1,079	CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract)	1986	PODS	0.00012135519
1,534	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00010331296
7,740	Functional Dependencies in Logic Programs	1985	VLDB	5.4615863e-05

Semantically Similar Papers

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