Cost-Based Optimization for Magic: Algebra and Implementation
Summary: Cost-based optimization treats magic sets rewriting as a join-like method, with cost formulas to select the best variant and a bounded search space; implemented in IBM DB2 V2 with practical performance gains. An algebraic model extends multiset relational algebra with a multiset theta-semi-join operator, defining search space and equivalence rules to enable a rule-based optimizer for non-recursive SQL. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Praveen Seshadri (University of Wisconsin)
- 2. Joseph M. Hellerstein (University of California Berkeley)
- 3. Hamid Pirahesh (IBM)
- 4. T. Y. Cliff Leung (IBM)
- 5. Raghu Ramakrishnan (University of Wisconsin)
- 6. Divesh Srivastava (AT&T)
- 7. Peter J. Stuckey (University of Melbourne)
- 8. S. Sudarshan (Indian Institute of Technology Mumbai)
BibTeX Citation
@inproceedings{seshadri_sigmod96,
title = {{Cost-Based Optimization for Magic: Algebra and Implementation}},
author = {Seshadri, Praveen and Hellerstein, Joseph M. and Pirahesh, Hamid and Leung, T. Y. Cliff and Ramakrishnan, Raghu and Srivastava, Divesh and Stuckey, Peter J. and Sudarshan, S.},
series = {{SIGMOD} '96},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/233269.233360},
url = {https://dl.acm.org/doi/10.1145/233269.233360},
year = {1996}
}
Incoming Citations (Sorted by Pagerank)
Showing 31 of 31 citing papers.
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1 | Access Path Selection in a Relational Database Management System | 1979 | SIGMOD | 0.0024089429 |
| 16 | MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) | 1986 | PODS | 0.00060089598 |
| 143 | Optimization of Nonrecursive Queries | 1986 | VLDB | 0.0002959213 |
| 434 | Query Optimization for Parallel Execution | 1992 | SIGMOD | 0.00018531826 |
| 770 | Parametric Query Optimization | 1992 | VLDB | 0.00014166811 |
| 1,095 | An Extended Relational Algebra with Control Over Duplicate Elimination | 1982 | PODS | 0.00012207515 |
| 1,410 | Magic is Relevant | 1990 | SIGMOD | 0.00010853223 |
| 3,650 | Implementation of Magic-sets in a Relational Database System | 1994 | SIGMOD | 7.2249961e-05 |
| 8,827 | Compiling Query Constraints | 1994 | PODS | 5.3615981e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 143 | Optimization of Nonrecursive Queries | 1986 | VLDB |
| 2 | 10,296 | Succinct Structure Representations for Efficient Query Optimization | 2026 | SIGMOD |
| 3 | 3,307 | Magic Conditions | 1990 | PODS |
| 4 | 1,921 | Efficient Evaluation of Right-, Left-, and Multi-Linear Rules | 1989 | SIGMOD |
| 5 | 527 | The Magic of Duplicates and Aggregates | 1990 | VLDB |
| 6 | 16 | MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) | 1986 | PODS |
| 7 | 7,079 | Adding Magic to an Optimising Datalog Compiler | 2008 | SIGMOD |
| 8 | 7,131 | Magic-sets Transformation in Nonrecursive Systems | 1992 | PODS |
| 9 | 3,650 | Implementation of Magic-sets in a Relational Database System | 1994 | SIGMOD |
| 10 | 1,410 | Magic is Relevant | 1990 | SIGMOD |