Efficient implementation of loops in bottom-up evaluation of logic queries

Juhani Kuittinen, Otto Nurmi, Seppo Sippu, Eljas Soisalon-Soininen

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

We consider the efficient implementation of the bottom-up evaluation method for recursive queries in logic databases. In the bottom-up evaluation algorithms the non-mutually-recursive rules are evaluated in certain order, whereas the evaluation order within a set of the mutually recursive rules is free. However, significant savings in join operations can be achieved by arranging the mutually recursive rules appropriately. We present an algorithm for splitting the evaluation loop for mutually recursive rules into subloops and for determining the order in which the rules shouldbe evaluated within a loop. The semi- naive evaluation algorithm is modified accordingly to gain advantagefrom the evaluation order and to work with the incremental relations ("deltas") appearing at different levels in the loop structure. The computation within a subloop is optimized by identifying loop- invariant factors in the rules to be evaluated. Using an experimental logic database system we demonstrate the usefulness of our algorithm in implementing data- log queries optimized by the "magic sets" and related term rewriting strategies.
Alkuperäiskielienglanti
OtsikkoProceedings of the 6th International Conference on Very Large Data Bases : August 13-16, 1990, Brisbane, Australia
ToimittajatDennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek
Sivumäärä8
JulkaisupaikkaPalo Alto, CA
KustantajaMorgan Kaufmann Publishers
Julkaisupäivä1990
Sivut372-379
ISBN (painettu)1-55860-149-X
TilaJulkaistu - 1990
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Conference on Very Large Data Bases - Brisbane, Queensland, Australia
Kesto: 13 elokuuta 199016 elokuuta 1990
Konferenssinumero: 16 (VLDB)

Lisätietoja


Volume:
Proceeding volume:

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä