Lichid: sufletul unei noi baze de date grafice, partea 2

Coautori: Scott Meyer, Andrew Carter si Andrew Rodriguez

Nota editorului: Aceasta este a doua parte a unei serii de bloguri in doua parti. Partea 1 a descris modul in care datele graficului se raporteaza la graficul in memorie al structurilor utilizate in mod obisnuit ca modele (ca in „model-vizualizare-controler”) de catre aplicatii, modul in care datele graficului pot fi stocate intr-o baza de date relationala conventionala si de ce bazele de date relationale conventionale nu lucrati foarte bine la acest tip de date. In loc sa renuntam la modelul relational, in aceasta transa, vom arata modul in care datele graficului relational pot fi procesate eficient.

Grafice ca date relationale

In ultima postare, am inceput prin a discuta despre proiectarea LIquid intr-un mod direct, incepand de la vizualizarea programatorului aplicatiei, un grafic al obiectelor din memorie si rezolvand problemele pe masura ce le-am intalnit. Cu toate acestea, dupa ce am ajuns la un punct in care avem date de margine relationale (jurnalul graficului) si un indice inversat (obiectele), ne-ar putea dori sa analizam o abordare relationala conventionala a acestei probleme. De fapt, reprezentarea unui grafic ca o lista de adiacenta a muchiilor intr-un sistem relational tabular este usoara:

Exista avantaje evidente in adoptarea acestei forme restranse a modelului relational tabular standard, inclusiv:

1. Utilizarea modelului relational bine studiat: este dificil de argumentat ca teoria multimilor si logica de ordinul intai ar trebui considerate daunatoare sau ceva de evitat. Modelul relational a avut un succes practic enorm si din motive foarte bune.

2. Fara NULL: muchiile exista sau nu. Sistemul nu este obligat sa atribuie semnificatie ceva de genul Edge („x”, „age”, NULL), deci nu este nevoie de logica trinara incorporata. Aplicatia trebuie sa spuna in mod explicit ce intentioneaza (0, MAXINT, …) atunci cand apar valori nule din cauza disjunctiei in interogari.

3. Fara probleme de normalizare: aceste date sunt in forma a cincea normala. Nu exista nicio modalitate prin care utilizatorul sa exprime denormalizarea.

4. Portabilitate usoara a datelor: astazi, este dificil sa mutati datele dintr-o baza de date in alta. Nu exista o codificare standard pentru un set de tabele. Pentru tabelele unice, in cazul nostru specific (muchiile exprimate ca tripluri de siruri), schimbul de date este usor: CSV si foi de calcul sunt formate obisnuite de schimb de tabele.

Aceasta forma de codificare a graficelor de lista de adiacenta este simpla, bine cunoscuta si este disponibila de zeci de ani. Deci, din nou, „De ce nu am terminat?” Practic, doua motive:

1. Performanta slaba: Sistemele traditionale de baze de date relationale, bazate pe un arbore static al operatiilor de algebra relationala aplicate stocarii sortate, se comporta ingrozitor pe aceasta schema. Pentru un planificator de interogari statice bazat pe statistici la nivel de tabel, unirile de sine sunt intens problematice.

2. SQL: SQL (o algebra relationala de implementare) este extrem de incomod de utilizat pentru construirea de aplicatii. Este detaliat, compune incomod si in mod natural returneaza numai rezultate care pot fi exprimate ca un singur tabel. In mod colocvial, aceasta incomoditate este cunoscuta sub numele de „nepotrivire impedanta obiect-relationala” sau mai rau, daca vorbitorul a suferit printr-o intalnire adversa recenta cu acesta.

Sarcina noastra de lucru si, in general, o sarcina de lucru foarte obisnuita, este navigarea: inspectarea unei portiuni mici dintr-un grafic foarte mare. In timp ce subgraful afisat pe o pagina de browser este mic in raport cu dimensiunea graficului general, are o structura complicata, deoarece fiintelor umane le place sa stie ce este interesant despre obiectul pe care il privesc. Interogarea declarativa care recupereaza subgraful necesar pentru afisarea unei pagini va avea de obicei zeci sau sute de constrangeri de margine, auto-imbinari cu tabelul de margini din acest model de date. In mod inevitabil, cea mai mare parte a evaluarii interogarilor pentru astfel de interogari se transforma in sondare aleatorie a tabelului de margini.

Daca tabelul este implementat printr-o structura sortata, o forma a arborelui B este aproape universala in sistemele relationale tabulare, sondarea aleatorie este O (log (N)), iar N si factorii constanti implicati sunt mari. 

Concret, la scara terabyte, un copac B imuabil va avea probabil cel putin trei niveluri, doar primul fiind relativ fierbinte in memoria cache L1. O singura sonda va necesita doua cautari binare, probabil necasate, cu usurinta zeci de cache L3 lipsesc pentru a materializa o singura margine. Mutabilitatea va inrautati aceasta performanta. In schimb, structurile de index pe care le descriem in „Indexarea nanosecundelor de date grafice cu Hash Maps si VLists” (prezentare) vor face o sonda pentru o singura margine, fie in 2, fie in 3 rate L3. 

Faptul ca datele graficului social sunt frecvent distorsionate, cele mai mari fan-out-uri fiind cu multe ordine de marime mai mari decat media, exacerbeaza diferenta de performanta intre stocarea sortata si stocarea hash. Intr-un index sortat, gasirea dimensiunii unui set de rezultate fara a se materializa efectiv va necesita o a doua cautare binara. In practica, este dificil sa se decida cand merita efectuata a doua cautare binara. Intr-un index bazat pe hash, dimensiunea unui set poate fi stocata in tabelul de hash de nivel superior, disponibil in 1 L3 miss. Detectarea inclinarii inainte de a experimenta efectele sale adverse este ieftina si usoara.

Trecand atentia noastra de la stocare la evaluarea interogarilor, constatam ca algebra relationala este ineficienta, atat ca specificatie declarativa, cat si ca masina de executie. Luati in considerare urmatoarea interogare grafica simpla despre competente si angajatori din reteaua cuiva de gradul doi:

Ca notatie, acest lucru este greoi. Sintaxa singura este o problema rezolvabila. Cu toate acestea, observati redundanta in iesire: perechi precum (Java, Oracle) sau (a1, b1) apar de mai multe ori, chiar daca exista doar o margine subiacenta. Acest produs fals fals din tabelul de rezultate este o problema fundamentala. Atat datele, cat si rezultatul dorit de utilizator sunt in forma de grafic. Reprezentand un grafic ca un tabel de tupluri de legaturi variabile fortele incruciseaza produsele, doua dintre ele in acest exemplu foarte simplu. In teorie, aceasta este doar o problema de protocol provocata de utilizarea SQL a unui singur tabel pentru rezultatele interogarii – una pe care am putea-o remedia returnand randuri potrivite din mai multe tabele in loc de doar una. Cu toate acestea, in practica, sistemele relationale tabulare utilizeaza intr-adevar algebra relationala pentru a evalua interogarile si, prin urmare, produsele incrucisate false sunt de fapt o preocupare de eficienta.

Din pacate, acesta nu este sfarsitul vestii rele pentru algebra relationala. Interogarile in forma de grafic – cele cu constrangeri circulare intre variabile – se dovedesc a fi importante, constrangerile triunghiulare sau in forma de diamant fiind o sarcina obisnuita. Lucrarile recente referitoare la „Algoritmi de imbinare optima in cel mai rau caz” au aratat ca „orice algoritm bazat pe planurile traditionale de selectare-proiect-imbinare tipic utilizate intr-un RDBMS este asimptotic mai lent decat optimul pentru anumite interogari”, cu o simpla imbinare triunghiulara fiind exemplul conducator.

LIquid foloseste un evaluator de interogare dinamic bazat pe costuri, bazat pe satisfacerea constrangerilor aplicate unui grafic de constrangeri de margine. In acest context, „dinamic” inseamna ca planul de interogare nu este cunoscut cand incepe evaluarea. Intr-un evaluator traditional de interogare SQL, planul de interogare (un arbore al operatorilor de algebra relationala) este complet determinat inainte de inceperea evaluarii. In contrast, evaluatorul LIquid stabileste consistenta traseului subgrafului rezultatului prin satisfacerea in mod repetat a celei mai ieftine constrangeri ramase. Pentru calculele costurilor, evaluatorul se bazeaza in mare masura pe accesul in timp constant pentru a stabili dimensiunile din index. Vom descrie evaluatorul interogarii in detaliu intr-o lucrare viitoare; deocamdata, sa spunem doar ca credem ca problemele de performanta asociate in mod traditional cu un model de date grafic relational sunt rezolvabile.

Acest lucru ne face sa avem nevoie doar de un limbaj de interactiune relational cu o sintaxa succinta, compozabila. Astfel, poate:

Cele de mai sus sunt aceeasi interogare, compusa din doua subinterogari.

In timp ce Datalog are o lipsa de implementari de rezistenta industriala, este extrem de bine studiat, utilizat in mod obisnuit in studiul bazelor de date relationale. Pentru a adapta Datalog in scopurile noastre, trebuie doar sa solicitam ca relatiile Edge sa fie singura forma care poate fi afirmata. Toate regulile trebuie sa se reduca in cele din urma la Edges.

Forma rezultatelor interogarii poate fi selectata de utilizator: tabelul traditional al legarilor variabile ale capului de regula ca in SQL sau marginile reale utilizate pentru a satisface interogarea. In afara de fortarea posibila a produselor incrucisate dupa ce au fost indeplinite constrangerile, alegerea rezultatelor tabulare nu are niciun impact asupra evaluarii interogarii. Cu toate acestea, daca ceea ce are nevoie utilizatorul este un rezultat complex, in forma de grafic, cum ar fi in mod natural produs de o interogare complexa, compusa, atunci este important un mod eficient de a-l consuma. Rezultatele tabulare si produsele incrucisate false sunt esenta nepotrivirii impedantei obiect-relationala. Returnarea rezultatelor interogarii ca subgraf (un set de margini) permite raspunsuri la interogari complexe in mod arbitrar intr-o singura operatie consecventa.

Acum avem o baza de date relationala in memorie cu indexuri bazate pe hash si Datalog ca limbaj de interogare, cu un planificator de interogari dinamic bazat pe satisfactia constrangerilor. Am terminat deja? Nu chiar. In raport cu graficele obiect sau SQL, ne lipseste schema. Toate valorile sunt doar siruri. Mai rau, nu avem cum sa insistam ca anumite relatii sa fie unice – de exemplu, ca o entitate ar trebui sa aiba un singur nume. Fara unicitate fortata, nu exista nicio modalitate de a mapa un grafic intr-un tabel normalizat. Considera:

In general, oamenii au un singur nume si o zi de nastere. Pentru aceasta interogare, un singur tabel este o valoare excelenta de returnare. Cu toate acestea, daca graficul permite mai multe nume sau date de nastere pe o entitate, va trebui sa extindem produsul incrucisat si utilizatorul va trebui sa se normalizeze manual.

Tabelele sunt comune si utile, iar utilizatorii necesita in mod rezonabil aceasta mapare. Ceea ce trebuie sa reparam aceasta valoare implicita este o modalitate de a descrie capetele unei margini: tipul scalar (cum se interpreteaza sirul literal care identifica varful) si constrangerea cardinalitatii (cate muchii incidente) pentru subiect si obiect. Ca si in catalogul SQL, care descrie tabele, codificam aceasta descriere a muchiilor ca date grafice, astfel incat graficul sa se autodescrie:

Spunem „putea” pentru ca este un pic ciudat sa ii cerem utilizatorului sa defineasca identitati suplimentare pentru metadatele subiectului si obiectului, „nume_sub” si „nume_obj”. Acest lucru va fi remediat in prezent.

Tipurile scalare, cum ar fi lichid / nod, lichid / sir sau lichid / int determina reguli de analiza cu care identitatea corespunzatoare trebuie sa se conformeze pentru ca scrierea sa aiba succes. Identitatile pot si au mai multe scopuri:

La fel ca in exemplul de mai sus, utilizatorul este de asteptat sa dezambiguizeze in interogare, daca este necesar. Implementarea bazei de date este gratuita pentru a exploata informatiile de tip, de exemplu prin indexarea sortata sau cuantificata sau stocarea imediata a numerelor intregi mici.

In timp ce multe relatii sunt reprezentate in mod natural ca un subiect-predicat-obiect triplu: mama, nume, autor, exista si multe care nu sunt, cum ar fi un mandat de angajare (persoana, companie, data de incepere) sau un spectacol de film al unui actor (actor, rol, film). Pentru relatiile ternare, le-am putea forta in Edge-ul existent facand ca unul dintre varfuri sa duca o dubla functie ca predicat: „Harrison Ford Han-Solo’d in Star Wars”, dar acesta este un hack unic care nu generalizati la relatiile n-ari.

Un model de date grafice ar trebui sa permita „muchii compuse” n-ari arbitrare sa se comporte la fel ca muchiile simple, ca relatii unice care exista sau nu. Avand in vedere ca muchiile pot fi folosite cu blandete, este tentant sa incepem o solutie prin construirea unor relatii n-ari din margini:

Observati ca putem folosi identitatea relativa generata, cid, la fel ca orice alt nod. Aici, indicam ca acest spectacol de film a fost o descoperire. In termeni relationali tabulari, o margine compusa se comporta exact ca o cheie primara compusa.

Deoarece compusii sunt cunoscuti pentru implementarea bazei de date, baza de date este libera pentru a optimiza relatiile compuse. De fapt, o simpla generalizare a structurilor de index descrise la inceputul acestei scrieri va permite accesul marginilor si atributelor compuse care se refera la ele la fel de repede ca marginile atomice. Implementarea bazei de date poate optimiza extra hopul. Efectiv, obtinem expresivitatea si performanta unui grafic de proprietati fara a fi nevoie ca utilizatorul sa defineasca sau sa opereze proprietati special.

Instantele FilmPerf se comporta „ca niste varfuri”, deoarece marginile pot face referire la ele si „ca niste margini”, deoarece pot fi sterse. Uneori avem nevoie de relatii compuse care se comporta doar „ca varfuri”. Vrem doar o valoare scalara cu o structura interna interogabila:

Astfel de compusi de varf ne permit sa codificam structuri de arbori arbitrare direct in date grafice, care sunt pe deplin accesibile aceleasi masini de interogare Datalog utilizate pe un grafic obisnuit.

In general, compusii definesc „identitatea relativa”, o notiune care se dovedeste a fi surprinzator de utila. In special, il folosim pentru a defini „partea subiectului” si „partea obiectului” unei margini in schema predicatului. Definitia reala a DefPred arata cam asa:

Acest lucru ne permite sa avem identitati relative distincte pentru un predicat: „partea subiectului”, sm si „partea obiectului”, om, fara a deranja utilizatorul sa vina cu identificatori unici pentru ei.

Vecinii cei mai apropiati ai lichidului 

Sa definim ce am construit. O „baza de date grafica” este o implementare a modelului relational cu urmatoarele proprietati:

1. Toate relatiile sunt egale si de prima clasa. Desi este o forma utila de index pentru modele de acces previzibile, folosirea tabelelor ca model de date fizice are ca rezultat inechitati de indata ce exista mai multe tabele. Tuplurile exprimate intr-un singur tabel fizic sunt mult mai performante decat cele exprimate prin alaturarea a doua sau mai multe tabele. In cele din urma, lipsa suportului de domeniu in sistemele relationale tabulare face ca intentiile utilizatorului cu privire la posibilele imbinari sa fie opace. Intr-o baza de date cu grafice, existenta unei margini exprima exact intentia utilizatorului.

2. Traversarea muchiilor este rapida si in timp constant. Daca totul este stocat sub forma de margini, vom face o multime de imbinari, in special auto-imbinari. Fiecare interogare cu rezultate intermediare mici se va transforma aproape sigur in acces aleatoriu.

3. Rezultatele interogarilor sunt un subgraf. Modelele de aplicatii sunt complexe, iar aplicatiile trebuie sa poata prelua modele complexe in mod arbitrar intr-o singura interogare cu o singura garantie de coerenta.

4. Evolutia schemei este in timp constant. Daca evolutia schemei (intr-adevar, adaugarea de noi predicate) necesita timp neconstant, atunci implementarea bazei de date trebuie sa pretinda ca functioneaza cu margini, mentinand in acelasi timp structuri sau tabele sub coperte.

Exista multe lucruri in lume care se numesc baze de date grafice, aproximativ impartite in trei familii:

1. RDF, SPARQL: magazine triple

2. Grafice de proprietati: Neo4J, Tao-ul Facebook, diverse implementari Gremlin

3. Extensiile SQL si SQL, cum ar fi suportul graficului SQL Server

In afara de # 3, niciunul dintre ei nu are relatii clare cu modelul relational. Niciuna dintre ele nu suporta margini compuse n-ari. Evaluarea interogarilor este fie bazata pe algebra relationala, fie imperativa (bazata pe traversare).

RDF este destul de apropiat de LIquid’s Edge in spirit, dar a introdus o mare complexitate. Triplele sunt asimetrice. De fapt, sunt quad-uri. Exista o eticheta de limba care este dificil de patrat atat cu codarea sirurilor Unicode, care este multilingva, cat si fara un sistem de tip (exista mai multe) care poate exprima constrangeri de cardinalitate precum: „un singur nume in orice limba”. SPARQL pare sa fi mostenit majoritatea afectiunilor SQL.

Graficele de proprietati introduc o a doua schema pentru proprietati si forteaza utilizatorul sa aleaga intre reprezentarea datelor ca margini sau ca proprietati ale nodurilor sau muchiilor. Un nod cu proprietati este practic un obiect si sufera de toate dezavantajele OODB-urilor. Codificarea evidenta a unui grafic de proprietati ca tabel de varfuri (cu proprietati) si un tabel de margini (cu proprietati) va forta doua cautari pentru orice interogare care implica proprietati de varfuri si margini.

In timp ce multe implementari de baze de date grafice sunt efectiv „in memorie RAM”, niciuna nu optimizeaza in mod explicit accesul aleatoriu cu indexare bazata pe hash sau exploateaza accesul rapid aleatoriu pentru a stabili dimensiunile in evaluarea interogarii. Nimic nu vizeaza interogari complexe sau accepta compozitia interogarii necesara pentru a face acest lucru cu usurinta.

Am definit ce este o baza de date cu grafice si am descris implementarea uneia care accepta limbajul de interogare Datalog. De asemenea, am sugerat cum sa indexam datele grafice pentru un acces rapid, in timp constant si cum sa construim un planificator de interogari dinamic bazat pe satisfactia constrangerii. Modelul de date al graficului este simplu si universal si are o schema auto-descriptiva care ne permite sa specificam cardinalitatea relatiei si domeniile valorice. Si, aceasta schema ne permite sa definim muchii compuse n-ari, pe care le putem folosi pentru a implementa grafice de proprietati. Deci, „De ce nu am terminat?”

Da, de fapt, am cam terminat.

Am mentionat ca LIquid este distractiv de utilizat?

Echipa LIquid

Multumim echipei LIquid de pe LinkedIn pentru multi ani de munca grea facand aceasta baza de date o realitate. In special: Bogdan Arsintescu, Roman Averbukh, Andrew Carter, Juan Colmenares, Ionut Constandache, Peter Li, Scott Meyer, Andrew Rodriguez, Siddharth Shah, Yiming Yang si Jiajun Yao.