CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract)

Summary: Top-down AND-OR evaluation for Datalog that performs sideways information passing to instantiate sibling subgoals using monotonicity (partial-order) constraints on relations. Presents an efficient convergence/termination test for a common program class, characterizes the combinatorial properties governing termination, and identifies cases where testing is intractable. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 744
Venue: PODS
Year: 1986
Pagerank: 0.00012406675
Overall Rank: 1,051 | 92.80%
DOI: 10.1145/6012.15400

Incoming Non-self Citations Over Time

Authors

1. Foto Afrati (National Technical University of Athens)
2. Christos H. Papadimitriou (National Technical University of Athens; Stanford University)
3. George Papageorgiou (National Technical University of Athens)
4. Athena Roussou (Carnegie Mellon University; National Technical University of Athens)
5. Yehoshua Sagiv (Hebrew University; Stanford University)
6. Jeffrey D. Ullman (Stanford University)

BibTeX Citation

@inproceedings{afrati_pods86,
        address = {New York, NY, USA},
        series = {{PODS} '86},
        title = {{CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/6012.15400},
        doi = {10.1145/6012.15400},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Afrati, Foto and Papadimitriou, Christos H. and Papageorgiou, George and Roussou, Athena and Sagiv, Yehoshua and Ullman, Jeffrey D.},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
1,498	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS	0.00010567892
3,355	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.4912272e-05
3,360	Deriving Constraints Among Argument Sizes in Logic Programs (Extended Abstract)	1990	PODS	7.4890377e-05
6,307	Optimizing Existential Datalog Queries	1988	PODS	5.9196585e-05
6,621	On the Power of Alexander Templates (Extended Abstract)	1989	PODS	5.8212982e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,579	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS
2	9,093	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS
3	13,049	Query Evaluation under the Well Founded Semantics (Extended Abstract)	1993	PODS
4	6,587	Selective Provenance for Datalog Programs Using Top-K Queries	2015	VLDB
5	174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS
6	11,147	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS
7	616	Parallel Evaluation of Recursive Rule Queries	1986	PODS
8	2,883	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
9	6,729	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB
10	2,600	Convergence of Datalog over (Pre-) Semirings	2022	PODS