An optimization strategy for recursive queries in logic databases

Seppo Sippu, Eljas Soisalon-Soininen

Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review


We consider the optimization of recursive database queries expressed in Datalog (function-free Horn clause programs). We present a general strategy for rewriting a Datalog program to cut down the number of database facts consulted in the bottom-up evaluation of queries containing bound arguments. The strategy can be interpreted as a preprocessing task in which an `envelope' containing the facts relevant to the query is determined by computing an easily evaluable query, and then the original query is applied to facts belonging to this envelope, which usually is only a small subset of all facts. The strategy applies to any Datalog program, and there exists a variant of the basic strategy that always produces `regular envelopes' that can be determined using a regularly recursive program.
Titel på gästpublikationProceedings of the Fourth International Conference on Data Engineering : February 1-5, 1988, Los Angeles Airport Hilton and Towers, Los Angeles, California, USA
Antal sidor8
UtgivningsortWashington, D.C.
FörlagIEEE Computer Society
ISBN (tryckt)0-8186-0827-7
StatusPublicerad - 1988
MoE-publikationstypA4 Artikel i en konferenspublikation
EvenemangInternational Conference on Data Engineering - Los Angeles, California, Förenta Staterna (USA)
Varaktighet: 1 feb 19885 feb 1988
Konferensnummer: 4 (ICDE)


  • 113 Data- och informationsvetenskap

Citera det här