Adding Magic to an Optimising Datalog Compiler

Summary: Magic-sets added to a fully automatic Datalog-to-SQL optimiser with no DB optimiser support. An abstract-interpretation of Datalog programs estimates relation sizes to drive a heuristic SIPS choice; evaluated on 100+ queries, it yields significant gains and never degrades when magic is unhelpful. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hf6dd82036be7cf9b
Venue: SIGMOD
Year: 2008
Pagerank: 5.5810777e-05
Overall Rank: 7,225 | 51.43%
DOI: 10.1145/1376616.1376673

Incoming Non-self Citations Over Time

Authors

1. Damien Sereni (Semmle Limited)
2. Pavel Avgustinov (Semmle Limited)
3. Oege de Moor (Semmle Limited)

BibTeX Citation

@inproceedings{sereni_sigmod08,
        title = {{Adding Magic to an Optimising Datalog Compiler}},
        author = {Sereni, Damien and Avgustinov, Pavel and de Moor, Oege},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376673},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376673},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,131	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD	5.8779512e-05
10,034	Materializing Knowledge Bases via Trigger Graphs	2021	VLDB	5.0925155e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00029179719
352	On the Power of Magic	1987	PODS	0.00020223279
708	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00014629998
1,032	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.00012401489
1,332	An Algorithm For Ordering Subgoals In Nail!	1988	PODS	0.00010998392
1,416	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010734049
1,438	Magic is Relevant	1990	SIGMOD	0.00010648031
3,707	Implementation of Magic-sets in a Relational Database System	1994	SIGMOD	7.0820673e-05
4,618	Context-Sensitive Program Analysis as Database Queries	2005	PODS	6.4995364e-05
6,437	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS	5.7853525e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,675	Overbound and Right-Linear Queries	1991	PODS
2	7,088	On the Expected Size of Recursive Datalog Queries	1991	PODS
3	18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
4	3,364	Magic Conditions	1990	PODS
5	10,159	Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs	1987	VLDB
6	6,131	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD
7	1,032	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD
8	7,278	Magic-sets Transformation in Nonrecursive Systems	1992	PODS
9	3,707	Implementation of Magic-sets in a Relational Database System	1994	SIGMOD
10	1,438	Magic is Relevant	1990	SIGMOD