Evaluarea Interogarilor Recursive In Baze de Date Recursive

C U P R I N S

INTRODUCERE

CAPITOLUL I

CAPITOLUL II

CAPITOLUL III

CAPITOLUL IV

Aplicatie

BIBLIOGRAFIE

În această lucrare, studiem execuția interogărilor logice întru-un mediu de baze de date distribuit. Presupunem că oricare sistem bază de date poate executa interogări logice, și construim metode pentru efectuarea eficientă a interogărilor ce cer date din site-uri multiple. Strategiile convenționale de optimizare care sînt bine cunoscute în domeniul bazelor de date distribuite, cum ar fi evaluarea inițială a condițiilor de selecție și împărțirea pe clustere a prelucrării pentru a manipula și a face schimb de multe seturi de înregistrări (set de valori corelate), sînt redefinite în vederea dificultăților în plus din timpul interogărilor logice, în particular, în reguli recusive.

Pentru a permite prelucrarea eficientă a acestor interogări logice, prezentăm cîteva tehnici de transformare a programelor ce încearcă să micșoreze costurile, bazate pe ideea de semi-unire și semi-unirea generalizată în bazele de date convenționale. Deși calculul local al semi-unirilor nu e posibil în general, indicăm clasele de programe pentru care aceste transformări reușesc să producă calcule orientate pe setări. Descriem procesele evaluînd programul recursiv într-o rețea distribuită și dezvoltăm o metodă eficientă de testare a terminațiilor calculului. În sfîrșit comparăm abordarea noastră cu cea secvențială și cu cea bazată pe fluxul de date ( evaluări ). Datalog e considerat un limbaj de programare logic.

O dată cu dezvoltarea multor sisteme comerciale tehnologia bazelor de date a devenit foarte utilizată. În acelasi timp, există un interes în creștere despre interogarea bazelor de date relaționale prin limbaje de programare logice.

Aceasta lucrare se ocupă cu o problemă aflată între aceste doua discipline.

Deși prelucrarea interogărilor logice într-o bază de date e departe de statutul de artă, ne așteptăm că programarea logică va fi produsul unui limbaj paradigmă de interogare bazat pe baze de date avansate și cunoștință despre arhitecturi. Mai departe ne așteptăm să devină intrinsec distribuite în special în stațiile de lucru ce functionează pe LAM. Deci cînd sistemele de date vor suporta programarea logică ca pe un limbaj de interogare vor suporta și distribuția.

În general, interogările unei baze de date distribuită cere efectuarea unui schimb de date între site-uri. Încercările de îmbunătățire a interogărilor distribuite

micșorează costul prelucrării locale și a transmiterii datelor.Un criteriu important al acestei îmbunătățiri spune că este mai bine să transferi datele între site-uri cu o abordare bazată pe mulțime, mai degrabă decît să transferi liste individuale între site-uri.Un alt criteriu este că selecția condițiilor ar trebui să fie evaluată cît de repede posibil pentru a reduce mărimea relațiilor intermediare produse de calculare.

Tehnici speciale cum ar fi semi-uniri, permit reducerea operanzilor de unire. Vă amintiți că scopul unei semi-uniri este să ia toate listele dintr-o relație R ce participă la unirea cu o altă relație S

unde R și R∩S sunt proiecțiile referitoare la mulțimile de atribute.O privire de ansamblu asupra abordărilor variate de a construi programe de semi-unire, poate fii găsită în exemplul [11].

Ca un rezultat al îmbunătățirii interogărilor distribuite, sistemul produce un plan de execuție al interogărilor, ce constă in cîteva programe locale ( programe ce pot fii executate pe un site ), în sincronizarea lor la mesajele de control și în transmiterea de date cerută între site-uri.

De asemenea în îmbunătățirea programelor logice, evaluarea inițială a condițiilor de selecție e fundamentală. Metode ca mulțimi magice ( [12], [13] ) sau ca numărări ( [14], [15] ), au fost proiectate pentru a propaga legăturile în timpul disputelor constante asupra scopurilor. Metodele de mai sus oricum nu produc în mod necesar o calculare bazată pe setare unde presupunem că relațiile bazelor de date sînt distribuite pe diferite site-uri. În această lucrare prezentăm metode pentru rescrierea programelor logice despre baze de date relaționale distribuite intr-o colecție de programe logice, fiecare pentru a fii executat pe un site, și o colecție de transmisiuni de date între site-uri. Combinăm strategiile dezvoltate pentru îmbunătățirea și a interogărilor logice și a celor distribuite. Astfel folosim metode inspirate din prelucrarea interogarilor recursive pentru a transmite legăturile scopurilor propuse (propuse), dar în același timp folosim metode inspirate de prelucrarea interogărilor distribuite pentru a genera programe orientate pe setări locale, de largă folosință ce pot fii executate pe un site.

O proprietate fundamentală a bazelor de date distribuite este transparența distribuției. Datorită acestei transparențe a distribuției, programele nu au nevoie să indice locația relațiilor. Mai departe, relațiile bazei de date pot fii fragmentate.

O a doua proprietate, numită transparența fragmentării, este cînd programele nu au nevoie să indice structura fragmentelor relațiilor [10]. În aceată lucrare, noi punem transparența prelucrării și a distribuției pe seama programelor logice. Deși nu ne concentrăm prea mult asupra acestui aspect arătăm că programarea logică este potrivită pentru definirea fragmentării, iar regula de compoziție poate fii folosită pentru transformarea programelor utilizatorului.

B. Arhitectură

Abordarea noastră specială cu privire la translația și îmbunătățirea unei interogări logice distribuite este arătată în Figura 1. Programul logic inițial LP0 și scopul inițial G0 sînt sursele ale aceluiași site de origine al interogării. În principiu este posibil ca programul LP0 să fie el însuși distribuit prin asumarea ca, regulile (în sensul de linie de comandă) lui LP0 să fie stocate pe cîteva site-uri.

În acest caz o căutare preliminară a regulii de bază trebuie să fie făcută, pentru a aduna regulile ce sînt cerute pentru ajungerea la scopul G0.

Considerăm că toate regulile relevante unei interogări trebuie să fie adunate înainte de recuperarea datelor. Acest fapt este consistent în cazul calculării interogărilor în baze de date distribuite, unde planurile de scopuri sînt construite inițial pentru execuția interogării.

Prima transformare, numită compoziția fragmentată, folosește reguli de fragmentare pentru a transforma programul logic LP0 și scopul G0, amîndouă exprimate folosind relații, în programul logic LPf și scopul Gf, amîndouă exprimate folosind fragmente. Perechile (LP0, G0) și (LPf , Gf ) sînt echivalente, în sensul că scopurile G0 și Gf evaluează aceleași seturi de date [2] îmbunătățiri ce țintesc includerea în LPf doar a acelor fragmente care sînt cerute cu adevărat pentru calcularea unui răspuns, cum am discutat în [10]. Întradevăr, compoziția fragmentată nu e o transformare grea, și aparține conceptului de bază distribuită

ca artă. Deci exemplificăm pe scurt compoziția fragmentată în secțiunea B, fără a ne concentra prea mult pe ea. După această transformare, putem privi fiecare fragment inclus în LPf ca o colecție de date individuale, de vreme ce semantica transformării e capturată total de transformare. Evident,compoziția fragmentelor e omisă dacă baza de date nu e inițial fragmentată.

G0, LP0

|

|

Compoziție fragmentată ←― Regulile fragmentării

|

|

Gf, LPf

|

|

Îmbunătățire logică

|

|

{ LPred }, Gc, LPc

|

|

Îmbunătățire logică ←― alocare

|

|

PS

|

|

Execuție

Figura 1 : Abordarea generală a transformării interogărilor,

îmbunătățirii și execuției

A doua transformare, numită îmbunătățire logică este responsabilă pentru transformarea Gf și LPf într-o colecție de programe logice. Ceea ce rezultă din această transformare constă în trei elemente :

O mulțime de mici programe logice LPred, fiecare aplicîndu-se la un fragment individual cu referință în LPf și extrage optimizările de date ce sînt relevante pentru calcule. În general, regulile din LPred sînt mutual recursive. Aceasta se întîmplă pentru că, pentru a determina organizările ( seturi de valori, bucăți din baza de date, structuri ) relevante din fragmentul Fk, trebuie să se știe care sînt aceste seturi de valori relevante ale fragmentelor Fh și viceversa. Global aceste programe construiesc o îmbrăcătură, ce cuprinde toate datele relevante calculării răspunsului scopului (vezi [17] ). Evaluarea fiecărui LPf e orientată pe setare (unde se poate ).

Un program logic LP0 și scopul Gc, astfel încît perechile (LPf,Gf) și (LPc,Gc) sînt echivalente, și LPc folosește fragmente reduse evaluate de LPred.

Programele LPred pot fii considerate specializate în găsirea seturilor de date relevante dintr-un fragment specific. Sînt executate la stocarea pe site a fiecărui fragment, unde operează de fapt ca servere de baze de date dedicate. Evaluarea lor are loc prin transmiterea datelor prin site-uri de baze de date distribuite. Evaluarea lui LPc este pînă la urmă făcută pe un singur site, numit site-ul colector, unde toate fragmentele reduse sînt trimise de servere, după ce sunt prelucrate. Pînă la urmă răspunsul la G0 e trimis la site-ul de origine al interogării (această transmisie e omisă, evident, dacă site-ul colector și site-ul de origine sînt unul și același ).

Această lucrare este în mare măsură despre îmbunătățirile logice. Secțiunile III și IV indică modul de construire a unui program LPred numit Reducerea și Reduceri Generalizate.

Un pas final, numit îmbunătățirea fizică se ocupă cu selecționarea copiilor (atunci cînd fragmentele sînt copiate ) cu determinarea site-ului colector și cu execuția eficientă a lui LPred in fiecare site implicat și a LPc în site-ul colector. De fapt așa cum vă vom prezenta metode variate, pentru optimizarea logică acest pas este responsabil și cu selectarea celei mai bune metode de optimizare. Apoi optimizarea fizică este responsabilă pentru selectarea între cea mai bună strategie logică și execuția directă a Gf și LPf. Deși improbabil, nu putem de fapt exclude că programele efectuate local sînt din ce in ce mai scump de executat deoarece evaluarea costurilor e strîns legată cu alegerea unui model de cost particular. Vom face cîteva comparații cîteva computații simple și primitive de comunicație în secțiunea C.

În această lucrare, nu sîntem preocupați nici de costul unui model, nici de probleme de optimizare fizică. Descriem totuși în secțiunea V un model de calcul ce poate fii folosit pentru execuția distribuită a programelor logice. În particular incump de executat deoarece evaluarea costurilor e strîns legată cu alegerea unui model de cost particular. Vom face cîteva comparații cîteva computații simple și primitive de comunicație în secțiunea C.

În această lucrare, nu sîntem preocupați nici de costul unui model, nici de probleme de optimizare fizică. Descriem totuși în secțiunea V un model de calcul ce poate fii folosit pentru execuția distribuită a programelor logice. În particular includem în model o procedură terminație, care are cîteva avantaje față de algoritmii anteriori de notat că modelul de calcul dezoltat în secțiunea V se aplică oricărui program logic ce lucrează cu baze distribuite și poate fii aplicat întradevăr pentru evaluarea variantelor LPf, sau altfel poate fii aplicat direct la (Lf,Gf).

C. Organizare

Această lucrare e organizată după cum urmează. În secțiunea II, prezentăm pașii preliminari pentru adunarea setului de reguli relevante unei interogări date de utilizator, un program logic inițial și o fragmentare a bazei de date.

Secțiunea III prezintă o metodă de rescriere a unei interogări pentru construirea “precedance reducer”ale predicatelor din componentele puternice. O precedence reducer folosește toate informațiile adiacente ce trec propagate direct de la legăturile interogării inițiale. Full reducers folosesc constrîngeri și de la sub-scopurile parțiale pentru a reduce mărimea relațiilor intermediare ; aceștia sînt descriși în algebra relațională în [18].

Secțiunea III introduce de asemenea notația de esențial reducers. Dacă reducerea este esențială atunci relațiile produse sînt capabile să producă un răspuns la interogarea inițială prin simpla proiecție și selecție. Indicăm și clasa de interogări care are reducător esențial.

În sfîrșit, secțiunea IV prezintă reducătorii generalizați. Această noțiune este o extensie a programelor precedente de reducere ce permite ca informația adițională să fie trecută mai departe. Reducătorii generalizați extind ideile de la cercetarea bazelor de adte non-recursive, ( [19] ), la cazurile recursive. Folosind numărarea și alți indici putem construi programe reducător care sînt esențiale.

Secțiunea V arată cum se evaluează interogarile recursive distribuite de o mulțime de procese pe site-uri diferite. Seturile de date ce rezultă imediat sînt adunate în mesaje și transmise între diferite site-uri. Protocolul final (de terminare) asigură că, calculul distribuit e oprit cînd a atins un punct fixat. Comparam de asemenea variatele comparări bazate pe reduceri cu o simplă abordare “ flux de date “ (de a lungul direcției lui ( [20] ) și evaluarea secvențială. unele considerații din afara sferei comerciale (a progarmelor ) sunt subliniate.

În final, descriem cîteva lucrări în secțiunea VI și prezentăm concluziile noastre extins în secțiunea VII.

În apendix descriem programele reducător pentru o bază de date simplificată a unei companii.

II. Preliminarii

În paragraful următor, vom definii cîteva notații folosite în restul lucrării. Pentru o și mai generală introducere în programele logice recursive vezi [21].

În plus arătăm cum să descrieți fragmentarea într-o bază de date distribuită folosind reguli logice non-recursive. După aceste preliminarii vom fii pregătiți să ne concentram atenția pe optimizarea logică și pe strategii de execuție presupunînd transparența fragmentării.

A. Notații

Definiția 1. ( Programul logic LP ). Un program logic LP constă din reguli Ri incluzînd doar predicate recursive, obținute non-recursiv sau predicate bază.

În cele ce urmează nu vom menționa niciodată predicatele obținute non-recursiv ca o clasă specială. De obicei ele sînt tratate în același mod ca predicatele recursive.

Facem presupunerea adișțională că toate “literals” dintr-o regulă sînt conectate între ele. De aceea fluxul de legături ajunge la fiecare “liferals” din corp (al programului). unele predicate dacă nu au fost legate la capăt, nu vor fii considerate de o strategie de transfer de transfer de informații care încearcă să propage legături de la capul liferal la liferals din corpul unei interogări.

Definiția 2. ( interogarea ) O interogare asupra unui program logic LP e demonstrată de , unde ține locul numelui unui predicat recursiv in R și C e lista de egalități xi = ci ,……., xk = ck ce arată legăturile din interogare.

Definiția 3. ( Părți de intrare și de ieșire a unui literal ). Dacă p() e un literal, atunci pb(b) este literal de intrare obținut prin restricționarea argumentelor lui P la cele legate și pf(f ) este literal de ieșire obținut prin restricționarea argumentelor pentru cele libere.

B. Fragmentarea

Cum am menționat în secțiunea B, fragmentarea unui program logic este ușor de scris. vom descrie de aceea pe scurt modelarea și optimizarea unei compoziții de fragment folosind reguli logice non –recursive și presupunem transparența fragmentării în capitolul ce urmează. Conceptele folosite aici sînt strîns legate cu cele folosite în (10).

Exemplul 1. Presupunem următoarele relații faptice :

companie( Numărul_companiei, Numele_companiei, Președinte )

produse( Numărul_companiei, Numărul_părții, Cantitate )

facturi_materiale( Partea_nr1, Partea_nr2, Cantitate )

rezervă( Companie_nr1, Companie_nr2, Număr_de_părți,Cantitate )

Fragmentarea orizontală va fii definită după regulile următoare :

produse( Numărul_companiei, Numărul_părții, Cantitate ) :–cal 1( Numărul_companiei), produse1( Numărul_companiei, Numărul_părții, Cantitate )

produse( Numărul_companiei, Numărul_părții, Cantitate ) :–cal 2( Numărul_companiei), produse2( Numărul_companiei, Numărul_părții,

Cantitate )

cal 1 ( 1 ).

cal 2 ( 2 ).

cal 3 ( 3 ).

cal 4 ( 4 ).

Fragmentarea verticală e definită de altă regulă :

companie( Numărul_companiei, Numele_companiei, Președinte ) :– companie1

( Numărul_companiei, Numele_companiei )

:– companie2

( Numărul_companiei, Președinte )

Aceste fragmente sînt alocate pe patru site-uri diferite :

Produs1 : site 1

Produs1 : site 2

Companie 1 : site 3

Companie 1 : site 4

Programul inițial LP0 :

președinte_productivitate ( X, Y, Z, T ) : – companie ( X, N, Y ), produse ( X, Z, T ). este de aceea transformat într-o variantă transformată a lui LP0 :

președinte_productivitate ( X, Y, Z, T ) : – companie 1 ( X, N ),

companie 2 ( X, Y ),

cal 1 ( X ), produse 1 ( X, Z, T ).

președinte_productivitate ( X, Y, Z, T ) : – companie 1 ( X, N ),

companie 2 ( X, Y ),

cal 2 ( X ), produse 2 ( X, Z, T ).

Dacă vrem acum să evaluăm scopul

?– președinte_productivitate ( X, Y, Z, T ).

pe site-ul 5, vom folosi programul optimizat LPf :

președinte_productivitate ( X, Y, Z, T ) : – companie 2 ( X, Y ),

produse 1 ( X, Z, T ).

Strategia logică de evaluare e ușor de construit căci am folosit doar linii de comandă non-recursive pentru definirea fragmentelor. E exprimată de următorul program LP0 ce constă în cîteva LPi :

LP1 : rezultat 1( Y ) : – companie 2 ( 1, Y ).

LP2 : rezultat 2( Z, T ) : – produse 1 ( X, Z, T ).

LPc : președinte_productivitate ( X, Y, Z, T ) : – rezultat 1( Y ),

rezultat 2( Z, T ).

Executarea finală a interogării e arătată mai jos, unde simbolul || separă execuțiile ce pot fii făcute în paralel.

[execută ( LP1 : 4 ), trimite ( 4, 5, rezultat 1 ) || execută ( LP2 : 1 ),

, trimite ( 1, 5, rezultat 2 )], execută ( LPc, 5 ).

III. Optimizarea Logică

A. Întîietatea liniilor de comandă de trecere a informațiilor adiacente

În această vom defini conceptul de informații adiacente ( P_SIP ) Rules. Aceste comenzi P_SIP extend noțiunea de comenzi SIP definite în ( 13 ), descriind o strategie de transfer a informațiilor eficientă și – trecînd peste orice considerație fizică – optimă într-olinie de comandă logică, și recursiv într-un program logic, depinzînd de tipul interogării.

Definiția 4. ( P—SIP ). Fie r o linie logică ( în notație Prolog ),

h() : ―B( r ).

cu capătul literal h() și o mulțime de literale corporale B( r ). Vom nota cu hb(b) partea literală ce dau argumente ale capătului literal, cu hf(f) partea liberă a capătului literal și cu interogarea cu legături în C.

și sînt vectori arbitrari de argumente.

Definim linia P—SIP pentru a indica ordinea evaluării literalilor în B( r ) și fluxul informațiilor rezultate în linia r. Avem nevoie de o mulțime de o mulțime de linii B—SIP pentru fiecare model de argumente legătură în capătul literal h() ce conduce la un hb(b) diferit. Oricum doar o submulțime din aceste linii

P—SIP sînt folosite propriu-zis pentru că depind de modelul de interogare dată și de invocarea tiparelor din alte linii de comandă.

O linie de comandă P—SIP pentru linia de comandă r are forma

N→x p().

unde N este o mulțime de literali ( q1(1),…, q2(2) ) ( coada mulțimii literale ), p() este un singur literal ( capătul mulțimii literale ) și X sînt variabilele, ale căror legături sînt propagate de la literalii lui N la p().

Înțelesul unei asemenea linii de comandă P—SIP este că p() este evaluată dacă toți literalii din N au fost deja evaluați. Înainte de a evalua pe p(),

Legăturile tuturor variabilelor cu privire la literalii lui N sînt propagați în p().

Notăm această ordine de evaluare prin relația . Relația q()p() este adevărată dacă q() trebuie să fie evaluată înaintea lui p().

Literalii folosiți în linia P—SIP pentru o linie logică sînt membrii ai mulțimii S unde

S = B(r) hb(b) hf(f) .

Cîteva produse ale unu predicat în interiorul unei linii de comandă, sînt puse în evidență de diferite variabile din acești literali.

Plasarea literalilor în linia de comandă P—SIP se supune unor restricții :

1. Interogareasurvine doar în linia de comandă P—SIP specială

→x hb(b).

arătînd fluxul de informații ale legăturilor C în interogare către capătul h() a unei linii de comandă unificabilă cu . Cum predicatul interogării este întotdeauna același cu literalul capăt în această linie de comandă P—SIP admitem predicatul interogării în exemplele noastre și vom scrie :

( C ) →x hb(b).

2. Exceptînd linia de comandă P—SIP arătată la 1, partea de legătură a literalului capăt, hb(b), are loc doar în interiorul unei linii de comandă P—SIP.

Nici un flux de informații nu are loc de la un literal din corp la hb(b).

3. Variabilele ale literalilor cap notate cu hf(f), sînt exemplificate doar după ce toți ceilalți literali au fost evaluați. hf(f) are loc de aceea, doar ca și capăt al unei linii de comandă P—SIP.

Considerăm următoarele proprietăți condiționale :

* Dacă avem un argument compus ai ( incluzînd funcții simbol ) în p(), atunci sau toate variabilele din ai se leagă de valori propagate de X, sau niciuna

* O strategie de trecere totală de informații au loc cînd variabilele în X sînt exact care apar și intru-un literal a lui N și în p(). În continuarea acestei lucrări declarăm trecerea de la informații totală și de aceea renunșăm la eticheta X, ca să poată fii mod unic.

* Liniile de reconstruită în comandă P—SIP sînt non-redundante căci fiecare literal a lui N include cel puțin o variabilă ce are loc de asemenea în p(). Dacă un literal al lui N nu contribuie cu noi variabile la X, putem să îl omitem.

* Liniile de comandă P—SIP sînt complete, în sensul că un literal deja evaluat

q(), care include cel puțin o variabilă a p() ne-inclusă în alt literal din N, este inclusă în N ca linie de command P—SIP N→x p(). În timpul acestei condiții de completare, un literal dat există o singură dată la capătul unei linii de comandă P—SIP.

* Relația ““trebuie să fie aciclică. Altfel doi literali vor face o asumare ciclică inconsistentă despre ordinea evaluării, adică fiecare literal va așteota ca un altul să fie evaluat, rezultînd o situație de blocaj.

Aceste definiții încearcă să contureze conceptul de optimizare pentru strategia de transmitere a informațiilor secundare. Folosind liniile de comandă P—SIP, informația cuprinsă de interogare transmisă prin literali deja evaluați constringe evaluarea unui următor literal, pe cît posibil. Bineînțeles, putem alege între diferite linii de comandă P—SIP pentru a face o adaptare la presupunerile variate desper proprietățiile fizice ale relațiilor (cardinalitate, selectivitate, locație, etc.)

O altă variantă a liniilor de comandă P-SIP sunt așa numitele unite complet P-SIP-uri linii de comandă. Aceste linii de comandă includ toți acei literali qi(i) în mulțimea lor de origine N, care au fiecare variabilă în comun cu literalul capăt p() sau altă mulțime de origine a literalilor qi(i) N și unde qi(i) – qj(j) . De acceea liniile de comandă “unire completă” P-SIP pot fii redundante în sensul definit mai sus, dar folosesc și operația de unire între diferiți literali în corpul liniei de comandă, si nu numai constrîngerea informațiilor din interogare, pentru a limita literalii bazei. deși aceste variante de linii de comandă P-SIP pot transmite mai multe informașii decît liniile de comandă P-SIP, predicatele sînt mai interconectate în aceste cazuri, ceeace reprezintă un dezavantaj într-un mediu distribuit. oricum, toate conceptele descrise mai tîrziu în această lucrare pot fii de altfel mai ușor adaptate, pentru a lucra cu linii de comandă “ unire completă “P-SIP.

Lucrări anterioare despre acest subiect introduc notația de P-SIP “totală” în [13] care sînt mai generale ca liniile de comandă P-SIP și strategia de transmitere a informațiilor “greedy” în [20], care e mai restrînsă decît conceptul nostru de linie de comandă P-SIP (și folosește transmiterea limitată “unire totală”. În general linia noastră de comandă P-SIP poate fii văzută ca o specializare a liniilor de comandă SIP definite în [13] (ce trebuie să se supună limitărilor de totalitate, non-redundantă și completivitate și să includă linii de comandă ce descriu fluxul de informații de la interogare la capăt și de la corp înapoi la cap la (hf ) ). Oricum le vom folosi diferit, fără a construi mulțimi magice ( pentru a constrînge predicatele recursive ) ci pentru areduce relațiile bazelor (distribuite ) înainte de a calcula relațiile recursive.

Definiția 5. ( liniile de comandă P-SIP îmbogățite ). Folosind strategia de transmitere a informației definită ca un set de linii de comandă P-SIP, îmbogățim toți literalii din linia de comandă P-SIP în modul care este evident. Ca întotdeauna, îmbogățirea unui literal L este o segvență de litere b pentru legătură și f pentru liberă, unde fiecare literăm este un argument a lui L.

Îmbogăția unui literal e definită de o regulă a liniei de comandă P-SIP (incluse în X ), scriem litera b la această poziție altfel scriem f. Partea liberă a corpului unui literal a unei linii de comandă (hf(f) ) este singurul caz special, căci moștenește îmbogățirea partenerilor săi de legătură hb(b).

Adițional, similar cu capul unei linii de comandă, substituim toate întîmplările de existență apredicatelor recursive prin părțile lor de intrare, ieșire.

Împărțim fiecare literal recursiv rp() în părțile sale de input rpb(b) și părțile sale de output rpf(f) în acord cu această îmbunătățire. Părțile de intrare ieșier nu au variabile comune. Amfolosit deja aceiași distincție pentru capul literal al liniei noastre de comandă.

De aceea o apariție a unui literal recursiv rp la capătul unei săgeți P-SIP (→) este substituită cu corespondentul său rpb și fiecare apariție de rp la coada unei săgeți cu, rpf .

Această subliniază predicatele recursive ca noduri de transfer principale, fără corespondență între intrare și ieșire ca nod. Bineînțeles că pierdem informația prin această transmitere, dar nu vom putea obține relații de bază reduse, fără calcularea însuși a prediactelor recursive (vezi secțiunea D ). Această abordare implică și că nu trebuie să distingem între apariții diferite ale acelorași literali recursivi.

Îmbogățirea e importantă mai departe, pentru scrierea multor variabile în coada setului de literali ale predicatelor de bază. Doar variabilele libere sînt scrise folosind numele lor, variabilele de legătură sînt scrise ca variabile fără nume ( excepție face hb(b) ) . Aceasta corespunde cu scopul inițial de a transmite doar constîngerile interogării, dar nici o informație de unire.

Putem formula, de aceea, următorul algoritm ce definește setul de linii de comandă cu linii de comandă P-SIP complete și non-redundante pentru o logică dată a unei linii de comandă.

Algoritmul 1 : Definește o strategie de transmitere a informațiilor secundare folosind linii de comandă P-SIP pentru o linie logică de comandă logică r :

procedure main ;

begin

/* Iniațializează liniile de comandă P-SIP……………………..*/

/* Informația pentru aceste chestionări constrînge către capul literalului */

RS : = { ( C ) → x hb(b) };

/* */

Se : = { x hb(b) } ;

/* */

Su : = B( r ) ;

While Su ≠ Ø do

Begin

/* */

Head : = member ( Head, Su ) ;

/* */

make_P_SIP_rule ( Head, Se, Tail );

/* */

adorn_head ( Head, Tail );

/* */

/* */

partition ( Head, Head b, Head f ) ;

/* */

/* */

replace _bound_variables ( Tail ) ;

Su : = Su \ { Head } ;

Se : = Se \ { Headf } ;

RS : = RS { Tail → x Headb };

End ;

/* */

/* */

make_P_SIP_rule (hf(f) , Se, Tail );

RS : = RS { Tail → x hf(f) };

End ;

Procedure make_P_SIP_rule (Head , Tposs, var Tail );

Begin

/* */

Tail : = Ø ;

/* */

repeat

TL : = member ( TL, Tposs ) ;

/* */

/* */

if cover ( TL, Head, V ) cover ( TL, Tail, V )

then Tail : = Tail TL ;

Tposs : = Tposs \ { TL } ;

Until Tposs = Ø ;

End ;

Exemplul. 2 Presupunem următoarea linie de comandă recursivă :

p ( X, Y, K ) : – a ( X, W, Z ),

b ( X, Y, Z, V ),

p ( W, Z, U ),

c ( U, V, K ).

și interogarea p ( a, b, K ).

Putem defini următoarele linii de comandă P-SIP îmbogățite pentru această linie de comandă.

( X = a, Y =b ) → pbbbf ( X, Y ). (1)

pbbbf ( X, _ ) → abff ( X, W, Z ). (2)

pbbbf ( X, Y ), abff ( _, _, Z ) → bbbbf ( X, Y, Z, V ). (3)

abff ( _, _, Z ) → pbbbf ( W, Z ). (4)

bbbbf ( _, _, _, V ), pfbbf ( U ) → cbbf ( U, V, K ) . (5)

cbbf ( _, _, K ) → pfbbf ( K ). (6)

Linia de comamdă P-SIP 1. modelează fluxul de informații de la interogare la capul liniei. Linia P-SIP 6. arată urgentarea trecerii variabilelor libere spre capul literal, după ce toți literalii din corpul liniei de comandă au fost evaluați.

De notat constrîngerile impuse de definiția noastră despre liniile de comandă P-SIP :

Literalul pb( X, Y ) e necesar în linia 3. pentru a o completa.

Literalul b( _, _, Z, _ ) care împarete o variabilă cu capul liniei 4., nu este totuși îngăduit, pentru că e redundant.

Dacă vom transmite doar legăturile lui X și Z în linia 3, nu vom avea o linie P-SIP totală.

Folosind linii P-SIP “ unire completă “, putem include abff ( X, W, Z ) și bbbbf ( X, _, Y, _ ) în linia 4.

Alte linii de comandă P-SIP s-ar putea să fie preferabile depinzînd de cardinalitatea relațiilor sau de selectivitatea argumentelor de legătură. Strategia “Greedy” descrisă în [20] evaluează acele relații mai întîi care au cele mai legate argumente și folosesc linii de comandă P-SIP “unire completă “. Acasta conduce la alt posibil set de linii P-SIP, unde linia 4 este substituită de linia sa P-SIP “ unire completă “ cum am descris mai sus și regulile 2 și 3 sînt înlocuite de următoarele două linii :

pbbbf ( X, Y ) → bbbff ( X, Y, Z, V ) (7)

pbbbf ( X, Y ), bbbff ( X, Y, Z, _ ) → a ( X, W, Y ) (8)

Unirea liniilor de comandă P-SIP din mai mult de o linie de comandă

În secțiunea A am definit noțiunea de linie P-SIP a unei linii de comandă logice. În această secțiune vom extinde această definiție la mai mult de o linie,

Permițîndu-ne să descriem comportamentul fluxului de date între diferite linii.

Notăm că dacă urgentarea duce la diferite urgentări ale capului unei linii recursive, cînd avem mai mult de un set de linii P-SIP.

Ca și înainte, toți literalii apăruți în liniile date, trebuie să fie diferențiați. Dacă avem mai mult de o linie literalii nu pot fii distinși după numele lor de variabile și trebuie să folosim indici condiționali pentru a distinge literalii altfel similari. Nu trebuie să distingem între literali recursivi cu aceleași îmbunătățiri, așa cum sînt partiționați în legături, și părți libere și sînt folosite doar pentru a corecta literalii predicat de bază.

Exemplul următor arată definiția pentru aceiași generație de predicate non-stabile. Avem patru seturi de linii P-SIP, originare diferite ale linilor recursive și non –recursive.

Folosim îmbogățirea literalilor de bază să facă diferența înter diferiți literali. Acest lucru e posibil e posibil, căci ei sunt mici pentru fiecare literal de bază al unui predicat anume.

Exempul 3. Programe nestabile din aceiași generație ;

sg ( X, Y ) :– f( X, Y ).

sg (X, Y ) :– u ( X, X1 ), sg( Y1, X1 ) , d ( Y1, Y ).

?—sg( X, Y ), X = a.

Îmbogățirea linilor de comandă P-SIP :

Q : (X=a) → sg bbf (X) .

R11 : sg bbf (X) →f bf( X, Y ) .

f bf( X, Y ) → sg fbf (Y) .

R21 : sg fbf (X)→ ubf( X, X1 ).

ubf( X, X1 ) → sg bbf (Y1) .

sg fbf (X1) → ufb( X, X1 ).

ufb( X, X1 )→ sg ffb (X) .

C. Programe Reducătoare

Pentru a micșora transferul structurilor de date între diferite noduri, dezvoltăm ideea de programe reducătoare cre sînt acpabile să reducă mărimea relațiilor de bază folosite în timpul evaluării unei interogări recursive.

Pornind de la un program logic LP0 incluzînd o interogare Q. Operatorii LP0 operează pe baza relațiilor . O strategie de transmitere a informațiilor e definită de un set de linii P-SIP, care pot fii transformate în linii P-SIP de bază

( bP-SIP ) incluzînd doar predicatele de bază.

Aceste linii bP-SIP sînt folosite la producerea unui program reducător LPred. Evaluarea calculului LPred produce relațiile reduse pi. Într-un pas secundar de evaluare evaluăm un program logic complement LPc derivat din LP0 ce operează pe relațiile de bază reduse . Și LP0 și LPc au același răspuns pentru Q, dar LPc folosește realții mai mici ca LP0 , lucru care este important într-un mediu distribuit.

Un asemenea pas de optimizare anterior prelucrării actuale ale relațiilor dorite este similar în spirit tehnicii semi-unire folosită în baze de date relaționale obișnuite ( [22], [23], [19] ) și lucrarea noastră extinde și generalizează conceptul de program reducător semi-unire bine-cunoscut în bazele de date distribute pentru relațiile non-recursive în cazuri recursive. Vom da de asemenea definiții corespunzătoare pentru toate programele reducătoare varianta full și semi-unire. Pentru definiții de bază ale teoriei semi-unire cititorul va citi [10] .

De notat că , în contrast cu strategia setului magic (vezi [12] și [13] ), într-o bază de date distribuită nu este suficientă restricționarea predicatelor recursive, cînd avem de transmis relații de bază ale site-urilor îndepărate. De asemenea, din cauza strategiei noastre de evaluare în două faze predicatele recursive nu trebuie să intervină în programul reducător. Rezultatele acestor predicate sînt calculate în timpul celei de adoua faze și de aceea nu sînt disponibile pentru evaluarea programului reducător.

Definiția 6. ( Programul reducător pentru pi ) Fie LP0 un program logic, Q o interogare și p1,…, pi,…, pn relațiile de bază folosite în LP0. Fie A ( Q, LP0, p1,…, pi,…, pn ) notația setului complet de răspunuri la interogarea Q. Atunci numim un program LPred un program freducător pentru scrierile pi , LP0, LPred produce o submulțime de pi notate , astfel încît

A ( Q, LP0, p1,…, pi,…, pn ) = A ( Q, LP0, ,…, ,…, ) .

Definiția 7. ( programul reducător full pentru pi ) Numim un program LPred program reducător întreg pentru scrierile pi , dacă LPred este un program reducător întreg pentru scrierile pi . LP0 și pentru toate celelalte programe reducătoare Lred ce produc o mulțime , produce relația .

Definiția 8 ( program reducător întreg pentru LP0 ) Numim un program LPred un program reducător întreg pentru LP0, dacă LPred e un program reducător pentru toți Pi, care sînt folosiți în LP0.

Deși construcția unui program reducător întreg ar fii alegerea optimă în restricționarea unei relații de bază, poate implica prea mult aclcul pentrua fii considerat pas de prelucrare convenabil pentru evaluarea majorității programelor recursive. În sensul strict de mai sus a trebuit să construim recursivitatea însăși pentru a obține relații de bază reduse în întregime. Chiar dacă definim o noțiune mai slabă de program reducător întreg în sensul lui [18] ( astfel încît poate fii construit fără definirea relației recursive ) toate relațiile bazei trebuiesc folosite pentru a obține o reducere completă a unei alte relații a bazei. Deci, ori toate relațiile bazei sînt locate într-un nod, ori nu putem da o legătură independentă de mărimea locațiilor bazei pentru numărul de mesaje dintre noduri.

De aceea definim o noțiune mai pragmatică orientată spre întîietatea programelor reducătoare, ce utilizează formalismul liniilor P-SIP definite în secțiunea A.

Definiția 9 ( program reducător cu întîietate pentru Pi ) Numim un program LPred un program cu întîietate pentru scrierile Pi ale lui LP0, dacă LPred e un program reducător pentru fieare linie de comandă a lui LP0, și liniile sale de comandă P-SIP acompaniatoare ( definind o relație de întîietate ), programul reducător pentru Pi folosește toate informațiile de restrîngere a interogărilor așa cum a fost definit de liniile de comandă P-SIP și propagate prin toți Pj cu Pj Pi, fără evaluarea relațiilor recursive.

Definița 10 ( program reducător au întîietate pentru LP0 ) Numim un program LPred un program reducător cu întîietate LP0, dacă LPred e un program reducător cu întîietate pentru toți Pi care sînt folosiți în LP0.

D. Construcția unui program reducător cu întîietate

În această secțiune vom descrie cum să transformi o mulțime de linii de comandă P- SIP definite în secțiunea anterioară, micșorînd mărimea relațiilor bazei de care e nevoie pentru evaluarea programului logic.

Construcția unui program reducător cu întîietate pornind de la liniile de comandă P-SIP definite în secțiunea anterioară este relativ “ cinstită ”.

Constrîngerea principală este aceea că nu permitem apariția predicatelor recursive în programul reducător LPred. Acesta va cere evaluarea ( parțială ) a predicatelor recursive, amestecînd optimizarea semi-unire și evaluarea propriu-zisă a interogării într-un mod care face interogarea orientată pe mulțime imposibilă.

De aceea definim un algoritm de transformare din linia noastră P-SIP originală la așa numita linie bP-SIP ( linie P-SIP bază ) care include doar literali corespunzînd cu relațiile bazei sau cu constrîngerea interogării.

Algoritmul 2.Transformarea liniilor de comandă P-SIP în bP-SIP : cap corespunzînd cu o relație a bazei prin încheierea tranzitivă constînd doar în literali ai bazei.

1. Pentru fiecare literal al bazei ce apare ca și cap al unei linii P-SIP se face următoarea transformare a acestei linii în linie bP-SIP.

2. Se pornește ca mulțimea coadă a liniei P-SIP.

3. În această mulțime se lărgesc toate granițele de predicate recursive, în mod recursiv, în predicate de bază conform definiției liniei P-SIP. Un pas al expansiunii substituie un literal recursiv RP, cu mulțimea coadă a liniilor ei P-SIP, avînd cap literal pe RP. Cîteva posibilități de extindere duc la cîteva figuri ce au soluții diferite.

4. Soluția unui literal recursiv e o mulțime de literali ce conțin doar predicate de bază, nici unul recursiv. Aceste relații sînt depozitate pentru fiecare literal recursiv.

5. Nu se extind literalii recursivi, ci se suspendă.

6. Se folosesc soluțiile anterioare ca substituții pentru literalii recursivi suspendați.

7. Stop dacă toate ramificările sînt extinse la maxim ( pînă la literalii bazei și la cei recursivi suspendați ) și tate soluțiile anterioare au fost deja încărcate în literalii suspendați sau dacă au condus doar la literali fără variabile împărțite ( comune ) cu capul unei linii P-SIP.

8. Soluțiile la literalii recursivi din mulțimea coadă originală și literalii de bază în această mulțime sînt mulțimea coadă a noi linii bP-SIP.

9. Dacă putem găsi alt literal al bazei ca și cap al unei linii P-SIP, pe care nu l-am extins deja, îi luăm mulțimea coadă și goto la pasul 2.

10. Se șterg toate liniile P-SIP cu corespondent literal la o situație recursivă. Acest lucru e posibil din cauză că toate informațiile lor au fost transferate liniiilor cu capete literale din relațiile bazei.

Acest algoritm e foarte asemănător cu algoritmii folosiți în prelucrarea interogărilor recursive sus –jos ( exemplu [7], [24], [25], [8] ). Diferența e în principal, că soluția nu constă în instantaneizarea produsă de etapele unei expansiuni totale, ci de etapa însăși (în mod similar cu tehnicile de evaluare totală) .

Putem acum transforma ușor un set de linii bP-SIP într-un program reducător cu întîietate în notație Prolog.

Algoritmul 3. Producem program reducător cu întîietate pornind de la linii bP-SIP.

1. Redenumește toți literalii bazei bPi în b sau similar notează relațiile bază reduse.

2. Adaugă un literal adițional bPh() la fiecare linie, literal ce corespunde cu un cap literal b().

Exemplul 4. Următorul exemplu arată transformarea unei mulțimi de linii P-SIP pentru aceiași generație de linii într-un program reducător cu prioritate.

sg ( X, Y ) : – f ( X, Y ).

sg ( X, Y ) :– u ( X, X1 ), sg ( X1, Y1 ), d ( Y1, Y ).

?– sg ( X, Y ), X = a.

liniile îmbogățite P-SIP :

Q : ( X = a ) → sg bbf ( X ) .

R1 : sg bbf ( X ) → fbf( X, Y ).

fbf( _, Y ) → sg fbf ( Y ).

R2 : sg bbf ( X ) → ubf ( X, X1 ).

ubf ( _, X1 ) → sg bbf X1.

sg fbf ( Y1 ) → dbf( Y1, Y ).

dbf( _, Y ) → sg fbf ( Y ).

liniile bP-SIP :

ubf ( X, X1 ) ← sg bbf ( X ) ← ( X = a )

← ubf ( _, X )

fbf( X, Y ) ← sg bbf ( X ) ← ( X = a )

← ubf ( _, X )

dbf (Y1, Y )← sg fbf ( Y1 )← dbf ( _, Y1 )

← fbf( _, Y1 )

programul reducător :

ubf ( X, Y ) :– ( X = a ), u ( X, Y ).

ubf ( X, Y ) :– ubf ( _, X ), u ( X, Y ).

fbf( X, Y ) :– ( X = a ), f ( X, Y ).

fbf( X, Y ) :– ubf ( _, X ), f ( X, Y ).

dbf ( X, Y ) :– fbf( _, Y ), d ( X, Y ).

dbf ( X, Y ) :– dbf ( _, Y ), d ( X, Y ).

costuri de comunicare :

Dacă presupunem că fiecare relație bază rezidă înt-un mod diferit, îmbogățirea literalilor bazei e determinată, argumente ce trebuie transferate altui nod. Argumentele libere sînt primite cele libere sînt transferate. În exemplul nostru trimitem 2ubf la nodul f1 și 2fbf la nodul d, unde putem calcula dbf .

Exemplul 5. Liniile bP-SIP și programul reducător pentru programul instabil descris în exemplul 3 sînt descrise în paragrafele următoare.

Linii bP-SIP :

ubf ( X, Y ) ← sg bbf ( X ) ← ( X = a ).

← dfb ( X, _ ).

ufb ( X, Y ) ← sg fbf ( Y )← fbf( _, Y ).

← dbf ( _, Y ).

fbf( X, Y ) ← sg bbf ( X ) ← ( X = a ) .

← dfb ( X, _ ).

ffb( X, Y ) ← sg bfb Y ← ubf ( _, Y ).

dbf ( X, Y ) ← sg ffb ( X ) ← ffb( X, _ ).

←ufb( X, _ ).

dfb ( X, Y ) ← sg bfb ( X ) ←ubf( _, Y ).

programul reducător :

ubf ( X, Y ) : – ( X = a ), u( X, Y ).

ubf ( X, Y ) :– dfb ( X, _ ), u( X, Y ).

dfb ( X, Y ) :– ubf( _, Y ), d( X, Y ).

fbf( X, Y ) :– ( X = a ), f( X, Y ).

fbf( X, Y ) :– dfb ( X, _ ), f( X, Y ).

ffb( X, Y ) :– ubf ( _, Y ), f( X, Y ).

ufb ( X, Y ) :– fbf ( _, Y ), u( X, Y ).

ufb ( X, Y ) :– dbf ( _, Y ), u( X, Y ).

dbf ( X, Y ) :– ffb( X, _ ), d( X, Y ).

dbf ( X, Y ) :– ufb( X, _ ), d( X, Y ).

Alt exemplu este dat în secțiunea E..

E. Proprietăți avansate ale programelor reducătoare

Cele mai interesante clase de reducători sînt :

Reducătorii cu întîietate : Folosesc informația disponibilă din constrîngerea interogării ( acordînd unei informații cu întîietate strategia trecerii ) pentru a restrînge relațiile bazei. Le-am definit în secțiunea D.

Reducători esențiali : Calculează deja toate răspunsurile la programul original. Faza a doua ( evaluarea interogării ) nu mai este necesară, răspunsurile pot fii găsite prin evaluarea expresiilor algebrice relaționale despre relațiile reduse. LPc e derivat din LP0 prin substituirea relațiilor inițiale relațiilor reduse.

Reducători orientați pe mulțime cu legături complete. Reducerea majorității sau a tuturor relațiilor bază ce pot fii calculate local pe un nod, fară a fii nevoie de un număr de mesaje nelegate de la alte noduri.

Vom defini formal a doua și a treia clasă și proprietățile lor în

cele ce urmează.

Definiția 11. ( Programe reducătoare esențiale pentru LP0 ) Numim un program LPred program reducător esențial pentru LP0, dacă mulțimea răspuns A pentru LP0 poate fii obținută din relațiile reduse prin aplicații de operații algebrice relaționale ce nu implică recursivitatea sau punctele fixe.

Dacă nu avem un program reducător esențial pentru LP0, atunci trebuie să evaluăm adițional interogarea inițială Q și un program LPc care este derivat din LP0 și care generează doar relații reduse Pi.

Exemplul 6 Exemplul următor arată liniile P-SIP și programul reducător LPred pentru programul liniar strămoș P. LPred e deja un reducător esențial, nu e nevoie de nici o evaluare finală a programului inițial. Interogarea finală Qc constă doar într-o selecție pe paritate a cărei formă poate fii derivată din linia P-SIP pentru ancfbf( Y ).

anc ( X, Y ) : – par ( X, Y ).

anc ( X, Y ) : – anc ( X, Z ), par ( X ,Y ).

?—anc ( a, Y ).

Q : ( X = a ) → ancbbf( X )

R1: ancbbf( X ) → parbf ( X, Y )

parbf ( _, Y ) →ancfbf( Y )

R2: ancfbf( Z ) → parbf ( Z, Y )

parbf ( _, Y ) →ancfbf( Y ).

parbf ( X, Y ) :– ( X = a ), par ( X ,Y ).

parbf ( X, Y ) :– parbf ( _, X ) , par ( X ,Y ).

Qc : answer ( anc( a, Y ) ) :– parbf ( _, Y ).

Teorema 1 Putem construi o procedură reducător esențială pentru un program LP0 dacă LP0 e o repetare unilaterală ( vezi [26] ).

În timp ce ne referim la [26] pentru o definiție exactă a repetării unilaterale informal, aceste repetiții sînt definite după cum urmează : Dacă un predicat recursiv definit de o repartiție unilaterală ( calculează mulțimea tuturor conjuncțiilor de predicate EDB care pot fii generate de o secvență de linie aplicație care începe cu aplicarea unei reguli la t) apoi doar o mulțime conectată există după îndepărtarea predicatelor exemplu, produse de linia non-recursivă.

Un caz special important sînt închiderile tranzitive.

Dovadă : Notați că un strămoș al unui program reducător nu folosește altă informație adițională alta decît apariția sistemelor în formații din timpul evaluării unei relații derivate. În conformitate cu aceasta corespunde cu un algoritm de evaluare de la stînga la dreapta, cum e descris în [26].Cum e arătat în [26] ( lema 4.1 ) asemenea algoritm e suficient pentru evaluarea predicatului derivat, dacă a fost definit folosind repetarea unilaterală. Trebuie să folosim un program logic adițional ( LPc ) pentru a evalua complet predicatul recursiv.

Pentru a defini valorile variate ale orientării pe mulțime a unui program reducător, folosim relația de ordonare definită de un set dat de linii bP-SIP.

Definiția 12 ( relația de ordonare ) Similar cu realația care a fost definită de linii P-SIP, o mulțime de linii bP-SIP definește relația asupra literalilor bazei.

Această relație definește echivalența de clasă înter diferiți literali unde Pi Pj și

Pj Pi conduce la Pi Pj, Pi și Pj sînt în aceiași clasă de echivalență.

Aceste clase de echivalență vor fii folosite la definirea gradului de orientare pe mulțime a unui program reducător.

Definiția 13 ( Programe orientate pe mulțime în întregime ). Un program reducător orientat pe mulțime în întregime e un program reducător, unde fiecare clasă de echivalență () definită de , include literali doar de la un predicat al bazei.

Exemplul 7 Considerăm iarăși aceiași generație stabilă de programe descrisă în exemplul 4. Avem trei clase de echivalență definite de linii P-SIP, fiecare cu un element ( (u), (f), (d) ).

Definiția 14 ( Programe reducătoare orientate pe mulțime legate )

Un program reducător orientat pe mulțime legat e un program reducător unde cel puțin o clasă de echiavalență definită de are mai mult de un membru dar avem mai mult de o clasă de echivalență și nu e nici o relație de echivalență care să includă toate relațiile bazei.

Dacă pentru fiecare clasă de echivalență toate prediacatele bazei incluse sînt alocate pe același nod, atunci este necesar doar un număr de mesaje legate între noduri diferite ( ca în cazul orientării pe mulțime completă ).

Exemplu 8 Aceiași generație de programe instabilă folosită ăn exemplul 3 are doar două clase de echivalență ((ud), (f ) ).

Definiția 15 ( programe reducătoare orientate pe mulțime nelegate ). Un program

orientat pe mulțime nelegat e un program reducător care are cel puțin o clasă de echivalență ce include literali la fiecare predicat al bazei.

Teorema 2 Programele recursive non-lineare ( programe care au mai mult de un sub-scop care e mutual recursiv cu capul literal are întotdeauna programe orientate pe mulțime nelegate dacă definește strategia de trecere a informației ce folosește linii de comandă SIP.

Dovada : Considerați următorul program non-liniar din aceiași generație

sg ( X, Y ) : – f ( X, Y ).

sg ( X, Y ) : – u ( X, X1 ), sg ( X1, X2 ), b ( X2, Y2 ), sg ( Y2, Y1 ) : –

d( Y1, Y ).

?– sg ( X, Y ), X = a.

Folosind liniile P-SIP evidente, putem arăta că toate predicatele bazei sînt într-o clasă echivalentă. Cum acest program e prototipul pentru o reprezentare simplă non-liniară, repetări mai complexe permit de asemenea doar programele reducătoare orientate pe mulțime.

Reducători generalizați

Cum am descris în secțiunea anterioară, e avantajos să construiești reducători esențiali. Asemenea programe reducătoare nu au nevoie de un pas de evaluare finală a relațiilor reduse, căci am găsit toate răspunsurile deja ( prin operațiile algebrei operaționale ). Din nefericire strămoșii esnțiali ai reducătorilor nu sînt posibili decît pentru o clasă foarte mică de programe logice ( închideri tranzitive ).

Similar cu bazele de date distribuite non- recursive unde putem evita buclele în cadrul reducătorilor totali prin așa numita semi-unire generalizată, putem extinde noțiunea de reducători pentru a face posibili reducătorii esențiali pentru o clasă mai mare de programe.

Aceasta implică trimiterea mai multor informații în jur dar salvează pasul de evaluare finală a evaluării interogării. În contrast cu [19], atributele adăugate stochează structuri de dervațiiale interogărilor folosind indici și numărători și nu argumente din alte relații de bază.

Depinzînd de ce metodă e folosită putem construi reducători generalizați pentru diferite clse de linii recursive.

Numărătoarea reducătorilor se poate efectua aciclic, programele recursive liniare cu o linie recursivă.

Contrarii reducătorilor generalizați sînt capabili să proceseze programe recursive non-liniare, aciclice, cu mai mult de o linie

În general informația adițională de care e nevoie crește repetărilor folosite

într-un program logic. Dacă vrem să rezolvăm un caz general, trebuie să numărăm următoarele proprietăți :

Adîncimea repetării ;

Numărul de linii aplicate ;

Numărul de apariții ale predicatului recursiv extins ;

Detectarea ciclului ;

Pentru a adapta metodele pentru procesarea distribuită în cadrul nostru de lucru, diferența principală de observat este că, contorizatorii obișnuiți sînt atașați la predicatele recursive ( vezi [13] și [9] ), în timp ce ei trebuie să fie atașați seturilor de date ale relațiilor bază reduse în cazuri distribuite.

În următoarea secțiune vom descrie implementarea reducătorilor generalizați folosind un index de contorizare adițional pentru a genera reducători esențiali pentru linii lineare. Extensia la alte structuri de date și alte metode de indexare ca acelea folosite de metoda generalizată de contorizare par a fii mai cinstite, dar au nevoie de argumente de contorizare ami complexe. Rămîne de văzut totuși dacă repetarea mai complexă permite evaluarea bazată pe reducător, orientată pe mulțime.

A.Linii de comandă liniare

Definim liniile SIP de contorizare a precedenților ( liniile c P-SIP )similar cu liniile b P-SIP, pentru a construi programe reducătoare ( minimizatoare ) pentru progarmele logice liniare. Diferența principală va fii argument contorizator adi’ional ]n liniile de comandă. Ca șii liniile bP-SIP liniile cP-SIP includ doar relațiide bază sau constrîngerea iterogării.

Algoritmul 4 Transformarea unei linii P-SIP într-o linie cP-SIP :

Mulțimile coadă Ti ale tuturor liniilor P-SIP cu un predicat de bază ce are un cap literal vor fii substituite cu închiderile lor tranzitive clasure (Ti). Oricum vom adăuga un contorizator adițional care se schimbă după cum urmează :

Se adaugă un argument de numărare la fiecare literal din liniile P-SIP, folosind aceiași instanțiere în toți literalii unei linii P-SIP.

Extindera literalilor recursivi cum e descris în algoritmul 2 pentru liniile bP-SIP. Schimbă argumentul contorizator după cum urmează ( vom folosi funcția succesor S(n ) pentru a incrementa sau decrementa contorizatorul : )

Dacă înlocuim capul literal hb(b, s ( N )) cu o mulțime coadă

și argumentul contorizator e decrementat în fiecare din noii literali în N, exceptînd în literalii corespunzători constrîngerii interogării.

B. Dacă înlocuim hb(b, s ( N )) cu constrîngerea interogării,

argumentul contorizator al literalului constrîngător e fixat la N=0

Dacă înlocuim capul literal hf(f, N ) cu o mulțime coadă,

Argumentul constrîngător e incrementat în fiecare din noii literali ai lui s ( N ).

Asemenea mulțime de linii cP-SIP pot fii atunci transformate în mod evident într-un program reducător cu întîietate de contorizare în notașia Prolog. Răspunsul la interogare poate fii găsit prin luarea proiecției potrivite asupra seturilor de date cu argumentul de contorizare s(0) ( vezi [27], [12] ).

În timp ce programele reducătoare generalizate au aceleași caracteristici orientate pe mulțime ca și programele bazate pe reduceri anterioare, acestea sînt esențiale pentru o clasă mai largă decît proramele reducătoare cu întîietate. În particular avem următoarea teoremă :

Teorema 3

Programele reducătoare de contorizare generalizate cum sînt definite de Algoritmul 4, sînt esențiale pentru programele lineare recursive arbitrare.

Dovada

Algoritmul 4 folosește același principiu de bază ca și metoda de contorizare descrisă în [27]. Scopul acestui algoritm de transformare a fost deja arătat ca fiind mulțimea de linii recursive lineare.

Se poate remarca , că această asemănare între metoda de contorizare pentru evaluarea subsegvențială ( ca cea descrisă în [27] ) și programul nostru reducător pentru contorizare pentru un mediu distribuit arată aplicabilitatea ușoară a principilui contorizării și pentru baze de date distribuite ( cel pușâțin pentru interogări recursive liniare ). În contradicție, metoda setului magic trebuie schimbată substanțial pentru a duce la prioritatea programelor reducătoare prezentate în această lucrare.

1 ) Linii stabile liniare :

Exemplul 9 Următorul exemplu arată un reducător esențial pentru aceiași generație stabilă de program și programul logic ca și liniile P-SIP corespunzătoare sînt aceleași ca în exemplul 4. Cum reducătorul e esențial în interogarea finală Qc, constă doar în două selecțiuni și poate fii derivat din linia P-SIP pentru sgfbf ( X, 0 ).

Programul logic :

sg ( X, Y ) : – f ( X, Y ).

sg ( X, Y ) : – u ( X, X1 ), sg ( X1, Y1 ), d( Y1, Y ).

?– sg ( X, Y ), X = a.

liniile cP-SIP :

ubf ( X, X1, s ( N ) ) ← sg bbf( X, s( N ) ) ← (X = a, N = 0 )

← ubf ( _, X, N )

fbf ( X, Y, s ( N ) ) ← sg bbf( X, s( N ) ) ← (X = a, N = 0 )

← ubf ( _, X, N )

dbf( Y1, Y, N ) ←sg fbf( Y1, N ) ← dbf( _, Y1, s(N) )

← fbf( _, Y1, s(N) )

programul reducător de contorizare :

ubf( X, Y, s(N) ) : – ( X = a, N = 0 ), u ( X, Y ).

ubf( X, Y, s(N) ) : – ubf( _, X, N ), u ( X, Y ).

fbf ( X, Y, s ( N ) ) : –( X = a, N = 0 ), f ( X, Y ).

fbf ( X, Y, s ( N ) ) : – ubf( _, X, N ), f ( X, Y ).

dbf( X, Y, N ) : – fbf ( _, X, s ( N ) ), d ( X, Y ).

dbf( X, Y, N ) : – dbf ( _, X, s ( N ) ), d ( X, Y ).

programul final :

Qc : answer (query (a,Y) ) :– dbf ( _, Y, s ( 0 ) ).

answer (query (a,Y) ) :– fbf ( _, Y, s ( 0 ) ).

2 ) Linii de comandă

Exemplul 10 Acest exemplu arată un reducător de contorizare esențial pentru problema aceleiași generații non-stabile. Programul logic și liniile corespunzătoare P-SIP sînt aceleași ca în exemplul 3, interogarea finală Qc e derivată ca în exemplul anterior.

Programul original

sg ( X, Y ) : – f ( X, Y ).

sg ( X, Y ) : – u ( X, X1 ), sg ( X1, Y1 ), d( Y1, Y ).

?– sg ( X, Y ), X = a.

liniile cP-SIP :

ubf ( X, Y, s ( N ) ) ← sg bbf( X, s( N ) ) ← (X = a, N = 0 ).

← dfb( X, _, N ).

ufb ( X, Y, N )← sg fbf( Y, N ) ← fbf ( _, Y, s ( N ) ).

← dbf( _, Y, s( N ) ).

fbf ( X, Y, s ( N ) ) ← sg bbf( X, s( N ) ) ← (X = a, N = 0 ).

← dfb( X, _, N ).

ffb ( X, Y, s ( N ) ) ← sg bfb( Y, s( N ) ) ← ubf( _, Y, N ).

dbf ( X, Y, N )← sg ffb( Y, s ( N ) ) ← ffb ( X, _, s ( N ) ).

← ufb( X, _, s ( N ) ).

dfb ( X, Y, s ( N ) ) ← sg bfb( Y, s( N ) ) ← ubf( _, Y, N ).

programul reducător de contorizare :

ubf ( X, Y, s ( N ) ) : – (X = a, N = 0 ), u ( X, Y ).

ubf ( X, Y, s ( N ) ) : – dfb( X, _, N ), u ( X, Y ).

dfb ( X, Y, s ( N ) ) : – ubf( _, Y, N ), d ( X, Y ).

fbf ( X, Y, s ( N ) ) : – (X = a, N = 0 ), f ( X, Y ).

fbf ( X, Y, s ( N ) ) : – dfb( X, _, N ), f ( X, Y ).

ffb ( X, Y, s ( N ) ) : – ubf( _, Y, N ), f ( X, Y ).

ufb ( X, Y, N ) : – fbf( _, Y, s( N ) ), u ( X, Y ).

dbf ( X, Y, N ) : – ffb( X, _, s( N ) ), d ( X, Y ).

ufb ( X, Y, N ) : – dbf( _, Y, s( N ) ), u ( X, Y ).

dbf ( X, Y, N ) : – ufb( X, _, s( N ) ), d ( X, Y ).

Qc : answer ( sg(a,Y) ) :– dbf ( _, Y, s ( 0 ) ).

answer ( sg(a,Y) ) :– fbf ( _, Y, s ( 0 ) ).

V. Evaluare terminare și costuri

Folosind conceptele folosite în această lucrare vom distinge 2 faze de execuție :

1 ) În prima fază de evaluare relațiile reduse sînt calculate în mod

distribuit, în acord cu programul reducător

Aceasta corespunde cu evaluarea semi-unire într-o bază de date relațională convențională. În timpul acestui calcul, doar proiecțiile de care au nevoie relațiile reduse sînt trimise în jur.

2 ) După terminarea programului reducător, relațiile reduse sînt

transferate unui nod comun. Acolo e rulată o strategie de prelucrare a interogării recursivă și non-distribuită pe relațiile reduse.

Vom descrie procesele paralele de evaluare a programelor logice în cîteva noduri. În mod adițional, introducem protocolul de terminare pentru aceste procese, care au cîteva avantaje față de strategiile existente. În final comparăm costul strategiei noastre de evaluare cu fluxul de date și algoritmii secvențiali, și arătăm o analiză detaliată a costurilor pentru aceste metode, în același exemplu.

A. Topologia comunicațiilor

Conform programului reducător, o topologie de comunicație e stabilită la Începutul calculării. Nodurile alimentatoare transmit rezultatele la relația lor redusă cu nodurile consumatoare ce au nevoie de aceste rezultate. Trimiterea unor asemenea rezultate e făcută cît de orientată pe mulțime se poate, pentru a reduce numărul de mesaje și pentru a mări spre maxim mărimea lor. Oricum strategia următoare de execuție, incluzînd protocolul de terminare e valid și pentru transferul orientat pe seturi de date al rezultatelor.

Definiția 16 ( Graful comunicației ) Graful comunicației descrie topologia comunicării unei rețele. Fiecare legătură de comunicație e reprezentată printr-o muchie direcționată de la nodul transmițător la cel consumator.

Facem următoarea presupunere despre transportul mesajelor în rețea : Dacă un mesaj mi e trimis mai devreme ca un mesaj mj pe aceiași cale de comunicare atunci mi e primit mai repede decît mj în toate cazurile.

Pentru a găsi nodurile care inițiază protocolul de terminare definim noțiunea de arbori de comunicare pe intervale și noduri consumatoare terminale.

Definișia 17 ( Arborii de comunicare pe intervale ) Pentru aconstrui un arbore de comunicare pe intervale Încpînd cu un transfer nodal împotriva muchiilor grafului de comunicare. Dacă o muchie duce la un nod deja prezent în arborele secvențial, e șters și construcția arborelui se termină în acest punct.

Definiția 18 ( mulțimile consumatoare terminale ) Mulțimea consumatoare terminală e mulțimea minimă de noduri care sînt rădăcinile unei mulțimi de arbori de comunicație secvențiali acoperind toate nodurile rețelei.

Protocolul de terminare e început de procesul de terminare, legat de procesul de evalare a unui nod consumator terminal după ce procesul de evaluare nu aduce seturi noi de date pentru o perioadă de timp stabilită înainte. acest lucru nu especificat în procedurile de terminare din secțiunea B, dar poate fii implementată ușor cu un fel de mecanim time-out.

Arborele de comunicare secvențială nu e construit statistic vorbind înaintea evaluării (deși arborii posibili au nevoie să fie considerați că determină o mulțime consumatoare finală ). În timpul protocolului de terminare, arborii sînt construiți în mod dinamic folosind o structură de date potrivită pentru detecția ciclului.

B. Evaluarea și terminarea

Protocolul de terminare implementat duce la două tipuri diferite de procese. Principalul tip de proces “ evaluator “ rulează în fiecare nod. Prelucrează ambele seturi de informații noi și mesajele de protocol.Un proces special adițional “inițiator” rulează pe fiecare nod consumator terminal care inițiază protocolul terminație.

În cele ce urmează, descriem structurile de date și variabilele definite în procesul evaluator. Procesul inițiator folosește același tip de date versiuni prescurtate ale lor .

Timestamp : identifică unic un mesaj protocol

Waiting : într-un set de date ( sender timestaup ), care e folosit să stocheze cererile secvențiale finish ?Structură de date ( s,ts) e inclusă în primirea unei cereri finish ? și ștearsă după ce transmis răspunsul la sender ( Trimițător ). Mesajele protocol aparținînd cererilor deja șterse sînt descărcate.

Previous _messages : e o mulțime de timestamps ce e folosită în verificarea ciclilor. Dacă un al doilea mesaj finish ? cu același timestamp e întînlită se răspunde idle în orice caz. Acest lucru e posibil ca un răpuns Busy ! la prima va masca orice mesaj idle trimis.

Recipient : e o structură de date ca cea de tip array care monitorizează fiecare cerere finish? dacă primește răspunsuri de la nodurile dimensionatoare înainte de a transmite mesajul finish? la ele. Dacă un mesaj extraordinar idle! e primit, trimițătorul său e îndepărtat din recipient [ts]. Dacă recipient [ts] devine gol și cererea finish? e încă secvențială poate răspunde cu idle!

Presupunem că un proces privește un set nou de date și evaluează programul său logic în prima parte a buclei de prelucrare a mesajelor. De aceea procesează doar noi mesaje protocol, dacă e nefolosit în prezent. Dacă trebuie să proceseze noi seturi de date sau trimite un mesaj busy ! înainte de a fii primit toate mesajele idle ! de la alimentatorii săi, răspunde busy!, nu contează ce mesaj de răspuns e primit apoi.

procedure evaluator ;

loop

select

accept new_tuples ( s : sender, t : tuples ) ;

process_tuples( t ) ;

if new_results ( self ) then

begin

send_new_tuples_to_consumers ;

for each ( i, ts ) in waiting do

send ( i, “busy!” )

Waiting : = Ø

End

End ( * accept * )

or

accept protocol_message (s : sender, ts : timestamp, t : tipe ) ;

case t of

“finished?” :

if ts previous_messages

then send ( s, idle ! )

else

begin

recipient [ ts ] : = all_descendants ( self );

if recipient [ ts ]= Ø

then send ( s, idle ! )

else

begin

Waiting : = waiting + ( s, st );

Previous_messages : = previous_messages +[ts];

For each n in recipient[ts] do

Send ( n, “finished?” )

End

End ;

“idle!”;

if ( i,ts ) waiting

then

begin

recipient [ ts ] : = recipient [ ts ] – [s] ;

if ( recipient [ ts ]= Ø )

then

begin

send ( s, idle ! ) ;

waiting : =waiting – ( i, ts );

end

end ;

“busy!” :

if ( i,ts ) waiting

then

begin

send ( i, “busy! “ ) ;

waiting : =waiting – ( i, ts );

end

end ( *case * )

end ( *accept * )

end ( *select * )

end ( *loop * )

O prelucrare adițională “ inițiator” e responsabilă pentru pornirea protocolului de terminare. După inițierea protocolului de terminare prin trimiterea “ finish? “ la sursa nodurilor sale, așteaptă pentru răspunsuri. Bucla sa de așteptare e executată sau după primirea tuturor mesajelor speciale “idle “ sau a unui mesaj busy !. Procedura finală e executată dacă protocolul de terminare reușește. Ce s-a făcut exact depinde de mediu. Dacă protocolul de terminare reușește calcularea e finalizată în toată partea rețelei controlată de nodul consumator terminal.

Cîteva straturi pot fi folosite în rețea, pentru a folosi negația sau pentru a folosi negația sau pentru a simplifica serializarea evaluării în diferite componente puternice. În acest caz, protocolul terminator rulează serial în diferite straturi.

procedure inițiator ;

get_timestamp( curr_ts ) ;

recipient : =all_descendants ( self ) ;

for each n in recipient do

send ( n, “finished?”) ;

pozitive_end : = false ;

negative_end : = false ;

repeat

accept protocol_message ( s:sender, ts : timestamp, t : type ) ;

case t of

“ idle” :

if ts=curr_ts

then

begin

recipient : = recipient – [s] ;

if ( recipient = Ø )

then pozitive_end : = true ;

end ;

“busy!”:

if ts=curr_ts

then negative_end : = true ;

end ( * case * )

end ( * accept * )

until positive_end or negative_end ;

if positive_end

then end_procedure ;

În [20], un algoritm de terminare e descris în contextul unei strategii distribuite orientate pe structuri de date pentru a evalua interogările recursive. În timp ce cîteva din ideile sale sînt similare cu ale noastre, următoare le diferențe principale pot fi observate între acești doi algoritmi de terminare :

Algoritmii secvențiali în [20] sînt definiți doar pentru componente tari ceea ce e un caz special pentru definiția noastră ( folosind straturi adecvate )

Arborele secvențial e implementat statistic în timp ce al nostru e implementat dinamic de detecția ciclului. Aceasta face algoritmul nostru mai adaptabil la condițiile de încărcare și influențează și posibilitatea folosirii protocolului într-o fază ( vezi mai jos )

Datorită presupunerii că mesajele sînt livrate în ordinea în care sînt transmise și construcția dinamică a arboririlor de comunicare secvențiali folosind detecția ciclu, putem folosi un protocol într-o fază pentru terminare, în timp ce [20] are nevoie de un protocol în două faze.

C. Compararea diferitelor strategii de execuție

În această sub-secțiune, comparăm diferite strategiide execuție cu cea bazată pe reducere . În secțiunea 1) descriem diferențele principale ale strategiilor de optimizare într-un mediu distribuit și non-distribuit. Secțiunea 2) compară în mod specific abordările descrise în [20] cu abordarea noastră.

Evaluarea distribuită și non-distribuită.În prelucrarea interogărilor recursive putem distinge între metode ce folosesc evaluarea dinamică și statică. Metodele de prelucrare a interogărilor de sus în jos, pot fii văzute ca evaluatori dinimici pentru că determină în timpul procesării, subscopuri recursive necesare. metodele de prelucrare ca metoda setului magic, poate fii văzută ca evaluatori statici , pentru că determină mulțimea subscopurilor necesare, înainte de evaluare. Printre alte lucruri evaluarea statică are ăn general mai multe posibilități pentru optimizarea orientată pe mulțime și ăn multe cazurimai puțin depășite.

O distincție similară poate fii făcută în cazul prelucrării interogărilor recursive distribuite. Evaluarea fluxului de date orientat pe seturi de informație [20] determină în mod dinamic semi-unirile necesare ale relațiilor bazei prin trimiterea argumentelor legătură la nodurile potrivite pentru selectarea seturilor de date necesare și timiterea rezultatelor înapoi.

Optimizarea semi-unire explicită cum l-am descris în această lucrare, încearcă să calculeze relațiile reduse necesare ( prin evaluarea programelor reducătoare ) înainte de prelucrarea interogării originale asupra relațiilor reduse.

Avantajul principal datorat abordării semi-unire e abilitatea de exploatare a comportamentului orientării pe mulțime cu optimizarea semi-unirii explicite. Cantitatea de prelucrări orientate pe mulțime e oricum dependentă de structura programului logic. O clasă evidentă în care calculul bazat pe reducător ar terbui să fie folosite în clasa interogărilor lineare.

Folosind tehnicile semi-unire descrise în acestă lucrare, putem reduce relațiile de bază înaintea prelucrării relației recursive. Depinzînd de clasa programului logic și tehnicile semi-unire folosite ( reducători anteriori sau generalizați ) salvăm comunicația aerian prin prelucrare orientată pe mulțime, dar plătim posibilele măriri ale costului de calcul. Oricum, prelucrarea orintată pe mulțime reduce comunicațiile și privirile aeriene în contrast cu prelucrarea orientată pe seturi de date.

Optimizarea semi-unire în bazele de date convenționale suferă uneori din cauza faptului că nu pot reduce în totalitate relațiile bază ; aceasta apare și cu metodele bazate pe reducere, pentru cele mai multe programe logice. Folosind programele reducătoare precedente, reducția întreagă ssau esențială poate fii garantată doar de închiderea tranzitivă a tipurilor de interogări. Aceasta oglindește diferențele teortice de limbaj, dintre gramaticaobișnuită (corespunzînd cu închiderea tranzitivă ) și contextul gramaticii libere. Pe de altă parte, reducătorii generali sînt capabili să reducă în întregime programe recursive arbitrar lineare în timpul informației adiționale pe care o poartă. Calculul bazat pe reducători generalizați, chiar compară favorabil în timpul evaluării non-distribuite căci nici un calcul nu trebuie făcut în cazurile distribuite. Construcția relațiilor reduse generalizate produce deja rezultate pentru interogarea originală pînă la operațiile de algebră liniară.

2) Calculul bazat pe reducere și flux de date : O metodă folosind evaluarea fluxului de date orientat pe seturi de date a fost prezentată în [20] (DFG) ; cu această metodă selecția seturilor de date necesare e făcută în cursul evaluării. Aceasta poate fii văzută ca, corespunzînd la o evaluare dinamică de semi-unire, care este amestecată cu evaluarea relațiilor recursive.

Comparînd calculul nostru reducător generalizat (GSJ) la o evaluare orientată pe flux de date a liniilor lui [20], chiar mai puține date trebuie să fie transformate ; mai mult transferurile de date sînt orientate pe mulțime. Bineînțeles, reducătorii de contorizare descriși sînt aplicabili doar pentru o clasă restrînsă de linii comparabil cu [20].

Fie SJ reprezentantul abordării noastre semi-unire, GSJ reprezintă semi-unirea generalizată și DGF reprezintă abordarea curgerii de date din [20]. Însumat avem diferențele calitative următoare :

Suprascrierea mesajului al multor mesaje mici ( DFG ) e mai mare decît acelea ale cîtorva mari (SJ)

Interogările bazei de date orientate pe seturi de date (DGF) sînt mai puțin eficiente decît interogările stocate total în loturi

Setul de mesaje. Seturi de date transferate (DGF) e în general mai mic decît reducțiile de bază proiectate (SJ) folosind reducătorii cu întîietate.

Metoda reducătorilor generalizată (GSJ) reduce supra-sarcina comunicațiilor comparativ cu abordarea (DGF), în timp ce încă permite prelucrarea orientată pe mulțime.

Datorită calculului reducției semi-unire adițională, suprasarcina datorită calculului operațiilor bazei de date e de obicei mai mare în (SJ) decît în (DFG). Suprasarcina datorită reducătorilor generalizați (GSJ) este comparabilă cu cea a lui ( DFG ).

Pentru unele structuri de date ( structuri de date obișnuite vezi [27] ) abordarea semi-unire (SJ) au un avantaj adițional datorită posibilității optimizării globale (determinînd ordinea execuțiilor de unire ale relațiilor reduse ). Deși optimizarea globală poate fii integrată în strategiile de sus în jos (vezi [24]) rămîne să fie investigat dacă poate să fie folosită similar într-un mediu distribuit. Mai multe evaluări cantitative ale costurilor de execuție cu cele două abordări sînt lăsate pentru lucrările viitoare.

VI. Lucrări relatate anterior

Datorită naturii interdisciplinare a acestei lucrări, lucrări relatate anterior aparțin cîtorva cîmpuri, în special în cel al prelucrării interogărilor recursive, evaluarea paralelă și distribuită a interogărilor.

Prototipul tehnicilor de prelucrare a prelucrării interogărilor recursive “ sus – jos “, e metoda setului magic, care a fost scrisă prima dată în [12] și [13]. Descrierea strategiilor trecerii de informație secundară în acestă lucrare au fost inspirate de definiția folosită în [13] și poate fii o specializare a acestor definiții originale, oricum cu alt scop ( reducerea distribuției relațiilor de bază înaintea calculării relațiilor recursive ).

Variante ale metodei setului magic au fost descrise în multe alte lucrări. În timp ce căteva extensii sau ocupat cu interogări mai complexe decît cele liniare, două alte lucrări au simplificat ideea de set magic pentru a produce completări ( [28], [29] ) . Ideea folosită în aceste lucrări a fost să micșoreze complexitatea setului magic de linii pentru a minimiza suprascrierea calculului. Această regularizare a liniilor setului magic a fost dizertată prima oară în [28] și implementată în [29]. Programele reducător cu întîietate implementează o idee similară ( împărțirea predicatelor recursive în legături și părți libere ) pentru a permite prelucrarea orientată pe mulțime și să calculeze setul magic complet (pe cît posibil ) înainte de calculul relațiilor recursive.

Pe de altă parte, am adoptat cîteva idei din aria optimizării interogărilor distribuite, în special din teoria semi-unirii [22], [23] și semi-unirile generalizate.

O abordare mai veche a definirii semi-unirii magice a fost descrisă în [18]

În această lucrare o operație nouă algebrică ( semi-unire magică ), a fost definită și folosită pentru reducerea semi-unire aliniilor de comandă lineare, recursive și stabile [30]. Generalizăm această lucrare în paginile acestea pentru linile arbitrare recursive DATALOG, folosind o abordare logică pare mai potrivită pentru recursivitatea generală.

Lucrări anterioare au propus arhitecturi paralele pentru evaluarea interogărilor logice [31], dar paralelismul afost folosit pentru sporirea vitezei de primire de la o bază de date mare de pe un singur site. Modelele de fluxuri de date ale calculelor au fost propuse și în [20] ,dar în acea abordare fluxul calculelor a fost dictat de structura scopurilor și a linilor de comandă ce se cereau calculate ; o abordare similară e luată în [32]. În loc de asta, în strategiile de execuție a bazelor de date distribuite ar trebui dictate de actuala distribuție a datelor.

Lucrări recente [32], [34] au adresat calculul paralel al interogărilor cu format special ( cum ar fii închideri tranzitive sau căi mai scurte ) prin fragmente sau setări folosind o tehnică numită abordarea setului deconectat. Alte lucrări privind calculul paralel al interogărilor de închidere tranzitive includ [35], [36]

Prelucrarea paralelă folosind un număr mare de prelucrători a fost descrisă în [37] și [38] . Aceste lucrări sînt axate pe complexitatea paralelă teoretică a programelor recursive. Programe incluse în clasa de complexitate Ncrulează în timp logaritmic dar cer polinomial mulți prelucrători în mulțimea bazei de date. Notați că lucrarea noastră e diferită de majoritatea lucrărilor anterioare despre prelucrarea interogărilor distribuite, care încearcă să paralelizeze evaluarea unui program logic prin împărțirea muncii între mulți prelucrători depinzînd de programul logic. Această lucrare e orientată spre execuția distribuită aunui program logic într-un mediu da bază de date distribuită, unde distribuția e mai mult sau mai puțin dată de alocarea relațiilor bazei în diferite noduri . Deci calcularea noastră e mai mult distribuție de date decît distribuție de evaluare.

Lucrări recente [39], [40], [41] au încercat să acopere zona din mijloc, folosind un număr mare dar constant de prelucrători.

Unul din scopurile principale ale acestei lucrări este să investigheze partiționarea instalării liniilor de comandă în evaluarea de jos în sus, pentru a atinge evaluări paralele non-redundante cu nu prea mare supra sarcină a comunicațiilor. În contrast cu abordarea fragmentelor noastre și / sau relațiilor bazei pot fii distribuite unei strategii date de paralelizare și numărul de prelucrători disponibili.

În sfîrșit munca în comunitatea Prolog a condus la cîteva introduceri paralele de Prolog, multe descrise în [42] . Similar cu sistemele convenționale Prolog , se evaluează pe evaluarea sus-jos, orientată pe seturi de date a programelor logice.

VII Concluzii

Am studiat execuția interogărilor prin relații logice definite recursiv într-un mediu distribuit. Începînd cu conceptele de optimizare folosit în bazele de date distribuite non-recursiv am dezvoltat o optimizare și o strategie de execuție făcînd evaluarea interogărilor recursive cît de orientate pe mulțime se poate. Programele reducătoare cu întîietate și generalizate au fost descrise și proprietățile lor formale discutate. O strategie de evaluare a fost desemnată să implementeze algoritmii descriși.

Cum sîntem preocupați cu mulții mari de date, multe din rezultate primesc posibilități pentru prelucrări orientate pe mulțimi în asemenea mediu distribuit. Considerăm prelucrarea orientată pe seturi de date nu destul de eficientă pentru un asemenea mediu și definim clase ce pot fii complet legate evaluînd orientat pe mulțime. Tehnicile noastre s-au mutat de la ideea inițială a transformării tehnicilor de optimizare semi-unire, care sînt bine definite pentru bazele de date distribuite, în baze de date distribuite recursiv.

În timp ce într-o fixare non-distribuită eficiența poate fii maximizată doar pentru forme restrînse de recursivitate, acesta este în mod evident cazul și pentru mediul distribuit, unde vrem să evităm și prelucrarea setului de date în același timp și transmiterea relațiilor întregi. Am arătat că liniile de comandă lineare pot fii optimizate orientate pe mulțime ; în cadrul liniilor de comandă liniare, liniiile stabile au mai mult potențial pentru prelucrarea orientată pe mulțime decît cele nestabile. Închiderile tranzitive tip definiție (recursivitate unilaterală) permit reducătorilor esențiali și deci o comunicație cu mulțime redusă ca și suprasarcina calculului.

Noțiunea de programe reducător generalizate ( folosind indici similari cu aceia folosiți în variate metode de contorizare ) produc calculări eficiente și pentru tipuri de interogări mai complexe. Vom urmării acest aspect mai detaliat în următoarea noastră lucrare, deși nu credem că evaluarea unei interogări complet generale e relevantă și producerea unei analize solide cantitativ a costurilor prin devoltarea unui simulator de metode variate comparate în secțiunea 5. 32. Altă extensie interesantă e comparația unei implementări paralele de Prolog și metode folosite să paralelizeze sau să distribuie prelucrarea interogărilor într-un mediu bază de date.