DBMS-kyselyiden semanttinen optimointi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 30.9.2021 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Semanttinen DBMS-kyselyn optimointi  on prosessi, jossa kyselyn syntaksipuu validoidaan ja muunnetaan muotoon, joka soveltuu lisäoptimointivaiheisiin.

Tässä vaiheessa suoritetaan seuraavaa:

  1. Muunna kyselyt kanoniseen muotoon;
    1. Paljastaa näkemyksiä;
    2. Muunna alikyselyt liitoksiksi;
    3. Predikaattien synty
  2. Ehtojen yksinkertaistaminen ja predikaattien jakelu;
  3. Ehtopuun muuntaminen valintapoluksi.

Kyselyjen muuntaminen kanoniseen muotoon

Kyselyt kanonisoidaan, eli ne kirjoitetaan uudelleen sisältämään vähimmäismäärä SELECT-lauseita (join-filter-projection). Aina kun mahdollista, kysely tulee pelkistää yhdeksi SELECT-lauseeksi. Tämän ansiosta myöhemmät optimointivaiheet voivat luoda paljon tehokkaamman (2-3 suuruusluokkaa) suoritussuunnitelman monimutkaisille kyselyille.

Laajentuvat näkymät

Näkymän laajennusta käytetään siten, että lopullinen kysely sisältää viittauksia vain materialisoituneisiin suhteisiin (taulukoihin) ja on mahdollista käyttää dataliukuhihnakäsittelyä.

alkuperäinen pyyntö Tulos
valitse a kohdasta V, jossa kond2

jossa V as valitse a, b kohdasta T missä cond1

valitse a kohdasta T, jossa (kond1 ja ehto2)

Alikyselyjen muuntaminen liitoksiksi

Alikyselyiden muuntaminen liitoksiksi on välttämätöntä dataputkien käsittelyn soveltamiseksi ja väliaikaiselle levylle tai RAM-muistiin kertyneiden alikyselytulosten määrän minimoimiseksi.

alkuperäinen pyyntö Tulos
valitse erillinen Ta alkaen T jossa Tb sisään (valitse T1.b kohdasta T1, jossa T1.c < Tc) valitse erillinen Ta alkaen T,T1 jossa Tb = T1.b ja T1.c < Tc

Predikaatin laskeutuminen

alkuperäinen pyyntö Tulos
(A liittyy B) missä condA ja condB (A missä condA) liitos (B missä condB)

Ehtojen yksinkertaistaminen ja predikaattien jakaminen

Ehtojen yksinkertaistaminen

Se suoritetaan muuntamalla loogisten operaatioiden puu CNF :ksi ja yksinkertaistamalla tuloksena olevaa loogista funktiota.

Loogisten operaatioiden puun muunnos CNF :ksi suoritetaan seuraavasti:

  1. Kaikkiin suoraan muotoon sisältyviin disjunktioihin sovelletaan jakautumislakia:
P TAI (Q JA R) = (P TAI Q) JA (P TAI R) (P JA Q) TAI R = (P TAI R) JA (Q TAI R)
  1. Kaikkiin käänteisessä muodossa esiintyviin disjunktioihin pätee de Morganin sääntö :
EI (P TAI Q) = EI P JA EI Q

Muunnos jatkuu rekursiivisesti, kunnes puu koostuu aineosan 0 konjunktioista .

Tuloksena oleva Boolen funktio on konjunktiivisessa normaalimuodossa , mutta on redundantti. Yksinkertaistamiseksi käytetään loogisten funktioiden optimointimenetelmiä, kuten Espresso (Logic) tai Quine-McCluskey .

Predikaattien jakautuminen

Predikaattijako on tehty

  1. kaikille muodon predikaateille:

AB ennen C

jolle on olemassa predikaatti

AB=DE

Tuloksena saamme predikaatin

DB ennen C:tä

jossa C on vakio; A,D - suhteet; B,E - vertaillut attribuutteja. Tämä yksinkertaistus perustuu oletukseen, että alkuperäinen predikaatti AB pred C voi olla tehokkaampi relaatiolle D.

  1. jokaiselle näkymän liitosehdolle:

AB ennen DE

käänteinen ehto luodaan

DE käänteinen ennen AB

jotta voidaan kytkeä päinvastaisessa järjestyksessä.

Ehtopuun muuntaminen hakupoluksi

Ehtopuun yksinkertaistamisen jälkeen jokainen puun konjunktio on hakupolku. Konjunktioiden sisällä olevat predikaatit ryhmitellään suhteen mukaan. Lopullisen tuloksen saamiseksi on tarpeen yhdistää kunkin näytteenottopolun tulokset.

Katso myös

Kirjallisuus