An optimization strategy for recursive queries in logic databases

Seppo Sippu, Eljas Soisalon-Soininen

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

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.
Alkuperäiskielienglanti
OtsikkoProceedings of the Fourth International Conference on Data Engineering : February 1-5, 1988, Los Angeles Airport Hilton and Towers, Los Angeles, California, USA
Sivumäärä8
JulkaisupaikkaWashington, D.C.
KustantajaIEEE Computer Society
Julkaisupäivä1988
Sivut470-477
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)

Lisätietoja


Volume:
Proceeding volume:

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä