On the Power of Magic

Summary: Formalizes sideways information passing (SIP) and models recursive evaluation as SIP+control, isolating a strategy class subsuming most DB recursive-evaluation algorithms. Shows any strategy is realizable by program rewrites evaluated bottom-up, generalizing Magic Sets/Counting, with safety and optimality results. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 801
Venue: PODS
Year: 1987
Pagerank: 0.00020659405
Overall Rank: 344 | 97.65%
DOI: 10.1145/28659.28689

Incoming Non-self Citations Over Time

Authors

1. Catriel Beeri (Hebrew University)
2. Raghu Ramakrishnan (Microelectronics And Technology Computer Corporation; University of Texas)

BibTeX Citation

@inproceedings{beeri_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{On the Power of Magic}},
        url = {https://dl.acm.org/doi/10.1145/28659.28689},
        doi = {10.1145/28659.28689},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Beeri, Catriel and Ramakrishnan, Raghu},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 53 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
13,124	Factoring Augmented Regular Chain Programs	1990	VLDB	5.093636e-05
13,160	A Data/Knowledge Base Management Testbed and Experimental Results on Data/Knowledge Base Query and Update Processing	1988	SIGMOD	5.093636e-05
13,167	Computing Facts in Non-Horn Deductive Systems	1988	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018607152
1,026	Sets and Negation in a Logic Database Language (LDL1)	1987	PODS	0.00012578477

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,603	Overbound and Right-Linear Queries	1991	PODS
2	1,498	Safety of Recursive Horn Clauses With Infinite Relations	1987	PODS
3	6,729	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB
4	3,307	Magic Conditions	1990	PODS
5	1,410	Magic is Relevant	1990	SIGMOD
6	7,131	Magic-sets Transformation in Nonrecursive Systems	1992	PODS
7	429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS
8	63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD
9	16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
10	1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD