An optimization strategy for recursive queries in logic databases

Seppo Sippu, Eljas Soisalon-Soininen

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu


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.
OtsikkoProceedings of the Fourth International Conference on Data Engineering : February 1-5, 1988, Los Angeles Airport Hilton and Towers, Los Angeles, California, USA
JulkaisupaikkaWashington, D.C.
KustantajaIEEE Computer Society
ISBN (painettu)0-8186-0827-7
DOI - pysyväislinkit
TilaJulkaistu - 1988
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Conference on Data Engineering - Los Angeles, California, Yhdysvallat (USA)
Kesto: 1 helmikuuta 19885 helmikuuta 1988
Konferenssinumero: 4 (ICDE)


Proceeding volume:


  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä