Optimizarea semantică a interogărilor DBMS

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 septembrie 2021; verificările necesită 5 modificări .

Optimizarea semantică a interogărilor DBMS  este procesul de validare și transformare a arborelui de sintaxă a interogărilor într-o formă potrivită pentru pașii de optimizare ulterioare.

În această etapă, se efectuează următoarele:

  1. Convertiți interogările în formă canonică;
    1. Vederi revelatoare;
    2. Convertiți subinterogări în alinări;
    3. Coborarea predicatelor
  2. Simplificarea condițiilor și distribuția predicatelor;
  3. Convertirea unui arbore de condiții într-o cale de selecție.

Conversia interogărilor în formă canonică

Interogările sunt canonizate, adică rescrise pentru a conține numărul minim de instrucțiuni SELECT (join-filter-projection). Ori de câte ori este posibil, interogarea ar trebui redusă la forma unei singure instrucțiuni SELECT. Acest lucru poate permite fazelor ulterioare de optimizare să genereze un plan de execuție mult mai eficient (cu 2-3 ordine de mărime) pentru interogări complexe.

Extinderea vizualizărilor

Extinderea vizualizării este utilizată astfel încât interogarea finală să conțină referințe doar la relații materializate (tabele) și este posibil să se utilizeze procesarea pipeline de date.

cererea inițială Rezultat
selectați a din V unde cond2

unde V ca selectați a, b din T unde cond1

selectați a din T unde (cond1 și cond2)

Conversia subinterogărilor în îmbinări

Convertirea subinterogărilor în îmbinări este necesară pentru a aplica procesarea pipelinei de date și pentru a minimiza cantitatea de rezultate ale subinterogărilor acumulate în discul temporar sau RAM.

cererea inițială Rezultat
selectați Ta distinctă de la T unde Tb in (selectați T1.b din T1 unde T1.c < Tc) selectați Ta distinctă de la T,T1 unde Tb = T1.b și T1.c < Tc

Descendența predicatului

cererea inițială Rezultat
(A unește B) unde condA și condB (A unde condA) unire (B unde condB)

Simplificarea condițiilor și distribuirea predicatelor

Simplificarea condițiilor

Se realizează prin conversia arborelui operațiilor logice în CNF și simplificarea funcției logice rezultate.

Transformarea arborelui operațiilor logice în CNF se realizează astfel:

  1. Pentru toate disjuncțiile cuprinse în formă directă se aplică legea distributivă:
P SAU (Q ȘI R) = (P SAU Q) ȘI (P SAU R) (P ȘI Q) SAU R = (P SAU R) ȘI (Q SAU R)
  1. Pentru toate disjuncțiile care apar în formă inversă, se aplică regula lui de Morgan :
NU (P SAU Q) = NU P ȘI NU Q

Transformarea continuă recursiv până când arborele este format din conjuncții ale constituentului 0 .

Funcția booleană rezultată este în formă normală conjunctivă , dar este redundantă. Pentru simplificare, sunt utilizate metode de optimizare a funcției logice, cum ar fi Espresso (Logic) sau Quine-McCluskey .

Distribuția predicatelor

Distribuția predicaților se face

  1. pentru toate predicatele de forma:

AB pred C

pentru care există un predicat

AB=DE

Ca rezultat, obținem predicatul

DB pred C

unde C este o constantă; A,D - relații; B,E - atribute comparate. Această simplificare se bazează pe presupunerea că predicatul original AB pred C poate fi mai eficient pentru relația D.

  1. pentru fiecare condiție de alăturare a vizualizării:

AB pred DE

se generează condiția inversă

DE inversat pre AB

pentru a se putea conecta în ordine inversă.

Convertirea unui arbore de condiții într-o cale de preluare

După simplificarea arborelui de condiții, fiecare conjuncție din arbore este o cale de preluare. Predicatele din conjuncții sunt grupate după relații. Pentru a obține rezultatul final, este necesar să combinați rezultatele fiecăreia dintre căile de eșantionare.

Vezi și

Literatură