Magic Sets and Other Strange Ways to Implement Logic Programs.

François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15

@inproceedings{DBLP:conf/pods/BancilhonMSU86,
  author    = {Fran\c{c}ois Bancilhon and
               David Maier and
               Yehoshua Sagiv and
               Jeffrey D. Ullman},
  title     = {Magic Sets and Other Strange Ways to Implement Logic Programs},
  booktitle = {Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 24-26, 1986, Cambridge, Massachusetts},
  publisher = {ACM},
  year      = {1986},
  isbn      = {0-89791-179-2},
  pages     = {1-15},
  ee        = {http://doi.acm.org/10.1145/6012.15399, db/conf/pods/BancilhonMSU86.html},
  crossref  = {DBLP:conf/pods/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Several methods for implementing database queries expressed as logical rules are given and they are compared for efficiency. One method, called "magic sets," is a general algorithm for rewriting logical rules so that they may be implemented bottom-up (= forward chaining) in a way that cuts down on the irrelevant facts that are generated. The advantage of this scheme is that by working bottom-up, we can take advantage of efficient methods for doing massive joins. Two other methods are ad hoc ways of implementing "linear" rules, i.e., rules where at most one predicate in any body is recursive. These methods are introduced not only because they could be the right way to implement certain queries, but because they illustrate the difficulty of proving anything concrete about optimal ways to evaluate queries.

Copyright © 1986 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 24-26, 1986, Cambridge, Massachusetts. ACM 1986, ISBN 0-89791-179-2
Contents

Online Edition: ACM Digital Library

References

[Bancilhon 1985a]: ...
[Bancilhon 1985b]: ...
[Brough and Walker 1984]: Derek R. Brough, Adrian Walker: Some Practical Properties of Logic Programming Interpreters. FGCS 1984: 149-156
[Gallaire and Minker 1978]: ...
[Lozinskii 1984]: ...
[Maier 1983]: David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents
[Maier and Warren 1985]: ...
[McKay and Shapiro 1981]: ...
[Pereira and Warren 1983]: ...
[Porter 1985]: ...
[Sagiv and Ullman 1984]: ...
[Ullman 1982]: Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
[Ullman 1985]: Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985)
[Van Gelder 1985]: Allen Van Gelder: A Message Passing Framework for Logical Query Evaluation. SIGMOD Conference 1986: 155-165