Interogarea World-Wide-Web-ului

Există surse de date, ca de pildă World-Wide-Web-ul, pe care am dori să le interogăm ca baze de date, dar care nu pot fi constrânse de o schemă. Majoritatea interogărilor web-ului folosesc tehnici de regăsire a informației pentru a găsi pagini după conținut. Există însă puține posibilități de formulare a interogărilor în vederea exploatării structurii web-ului și, deoarece aceasta nu este conformă cu nici un model de date standard, este necesară o metodă de descriere a acestei structuri.

Modelul de date semistructurat a fost propus în vederea satisfacerii acestei necesități. Ideea centrală în modelul semistructurat este de a reprezenta datele sub forma unui graf etichetat. Structura documentelor hipertext este capturată interpretând arcele grafului drept legături. O reprezentare posibilă este cea introdusă în proiectul UnQL[1]. Etichetele arcurilor pot fi atât valori (de tip întreg, șir de caractere și alte tipuri de bază, precum și de tip de date abstract, ca video, audio, etc.) cât și nume de atribute (Film, Titlu, Regizor, Actor), etc. modelând de exemplu cunoscuta bază de date cinematografică [2].

Există numeroase limbaje de interogare pentru modelul semistructurat. Toate aceste limbaje sunt construite pe baza ideii de expresii asociate căilor (path expressions). Acestea sunt expresii regulate ce exprimă căi generice în graful etichetat, permițând astfel traversarea grafului și colecționarea tuturor etichetelor ce satisfac o anumită condiție de selecție. Dacă, de exemplu, condiția de selecție este „eticheta este un șir de caractere, și arcul său este adiacent unui arc etichetat actor”, atunci rezultatul acestei interogări va conține numele tuturor actorilor din baza de date (printre altele).

Limbajele semistructurate pot fi clasificate în două categorii, după strategia de calcul adoptată. Prima categorie, dezvoltată oarecum ad-hoc, se bazează pe modelarea grafurilor în modelul relațional și apoi pe interogarea lor într-un limbaj relațional de tip SQL.

Câteva exemple prezentate în literatură sunt [3], [4], [5], [6], [7]

A doua categorie pornește de la un limbaj bazat pe o noțiune formală de calcul cu date semistructurate: limbajul UnQL este reprezentantul acestei categorii [1]. Acest limbaj pornește de la „recursivitatea structurală”, forma naturală de recursivitate asociată cu tipul de date grafuri etichetate. Datorită bazei sale teoretice, UnQL este capabil de restructurări complexe, „în adâncime”, spre deosebire de limbajele din prima categorie, care se limitează la scoaterea la suprafață a datelor din graf, fără însă a crea noi structuri.

Această capacitate de restructurare stă la baza proiectului STRUDEL[8] care propune limbajul StruQL de gestiune a sit-urilor de web. Un alt avantaj al bazei teoretice a limbajelor UnQL și StruQL este posibilitatea efectuării optimizărilor specifice acestui nou model de date. Limbajele din prima categorie pot beneficia doar de optimizările specifice modelului relațional, deci dezvoltate pentru alt model de date și în consecință nu atât de folositoare.

Integrarea surselor de date eterogene

Integrarea datelor provenind din surse eterogene (cu scheme disparate sau, mai grav, modelate diferit), este un domeniu de cercetare care, deși consacrat de mai bine de un deceniu, continuă să rămână în centrul atenției multor cercetători. Cercetarea în acest domeniu este motivată de absența unui model de date atotcuprinzător, fapt ce îngreuiază dezvoltarea de software care convertește date între două modele diferite.

O complicație adițională este reprezentată de faptul că majoritatea datelor stocate electronic nu se află în baze de date convenționale, ci în sisteme de fișiere, programe de bibliotecă, de poștă electronică, foi de calcul etc., care prezintă capacități de interogare limitate.

Ultima observație a reprezentat punctul de plecare al proiectului Tsimmis [9][10] de la Stanford. Proiectul Tsimmis își propune integrarea atât a surselor de date care sunt conforme cu modelele de date standard (relațional, orientat pe obiecte), cât și a surselor de date cu capacități de interogare limitate. Aceste surse neconvenționale sunt împachetate în așa-numiți „wrappers” (ambalaje). Un astfel de ambalaj asigură interfața între sursa de date cu capacități de interogare limitate și aplicația care o interoghează. Aplicația trimite către sursa interogări într-un limbaj expresiv cum ar fi SQL sau OQL și așteaptă rezultatul într-un format numit OEM (Object Exchange Model).

OEM folosește grafuri etichetate, ca structură de date, care capturează majoritatea datelor folosite în aplicații de baze de date. În același timp, toate celelalte structuri de date pot fi codificate ca grafuri OEM.

Rolul ambalajului constă în:
• interceptarea interogării și identificarea acelor părți ale acesteia care pot fi efectuate de către sursă,
• translatarea acestor părți în limbajul specific sursei,
• recepționarea și prelucrarea rezultatelor intermediare în vederea reconstituirii rezultatului interogării originale,
• codificarea rezultatului final în formatul OEM și transmiterea acestuia către aplicație.

Evident, dacă interogarea originală este prea complexă, este posibil să nu poată fi efectuată pornind de la capabilitățile limitate ale sursei. Ambalajul detectează această situație și anunță sursa că nu îi poate satisface cererea. Cu cât crește capacitatea de evaluare a interogărilor în cadrul ambalajului (de exemplu, capacitatea de a efectua operații de tip join, proiecții, selecții, etc.), cu atât se extinde clasa de interogări pe care le poate satisface combinația sursă-ambalaj.

Un proiect similar, cu scopul interogării surselor de date structurate din web este [13].

Cititorul a remarcat desigur similaritatea dintre modelul OEM și cel semistructurat. Într-adevăr, Lore [11],[12] este un sistem de interogare a datelor semistructurate, foarte similar cu UnQL, utilizând un model de date inspirat de OEM.

Navigare în Internet

În anumite situații este avantajos să privim bazele de date convenționale ca fiind semistructurate. Un exemplu este activitatea de navigare în Internet.

În general, utilizatorul nu poate interoga o bază de date fără a-i cunoaște schema. Din nefericire însă, aceasta este adeseori greu de înțeles, datorită mărimii exagerate (zeci de tabele, de exemplu) și a terminologiei opace, nestandard, folosite de către proiectanții bazei de date.

Descifrarea schemei ar fi considerabil ușurată de facilitatea de a interoga datele având doar o înțelegere parțială a structurii lor. De exemplu, în cazul bazei de date cinematografice din World-Wide Web[2], următoarele interogări ar fi de folos:

În care atribut găsim șirul de caractere „Casablanca”?
Există în baza de date întregi mai mari decât 216?
Ce obiecte din baza de date au un atribut al cărui nume începe cu „act”?

Și în acest domeniu, modelul semistructurat se dovedește a fi folositor. Spre deosebire de modelele de date convenționale, care diferențiază între schema (tipul, structura) și instanța (valoarea) datelor, modelul de date semistructurat reprezintă cele două tipuri de informație în mod uniform, permițând interogarea lor simultană. Din acest motiv, datele semi-structurate se numesc și autodescriptive.

[1] prezintă un elegant limbaj de interogare care permite exprimarea concisă a acestor interogări.

Cubul de date și OLAP

Sistemele de suport pentru decizii (Decision support systems) sunt utilizate de către companiile moderne pentru integrarea într-o bază de date centrală numit㠄data warehouse” (magazia centrală de date), a datelor provenind din baze de date mici operaționale folosite în diferite domenii de activitate/filiale ale companiei.

Datele astfel acumulate sunt analizate în timp real (OLAP: On-Line Analitical Processing) pentru a asista conducerea companiei în luarea deciziilor strategice de dezvoltare [14] (de exemplu, analizând vânzările unui anumit produs pe trimestru și zonă geografică, se poate stabili o nouă strategie de marketing pentru acest produs). Datele din magazia centrală de date sunt modelate sub forma unui (hiper)cub de date multidimensional [15]) care poate fi analizat la nivelul subcuburilor de granularitate arbitrară. Subcuburile se obțin prin agregarea cuburilor din care provin.

De exemplu, prin însumarea vânzărilor trimestriale pentru fiecare zonă, cubul de date tridimensional reprezentând vânzările pe trimestru și zona geografică poate fi redus la un subcub bidimensional (plan) reprezentând vânzările pe zona geografică. Agregarea este o operație costisitoare, efectuarea ei eficientă pe un volum mare de date reprezentând țelul principal al cercetării în acest domeniu ([16],[17],[18],[19]).

Noi modele tranzacționale

În mod tradițional, tranzacțiile modelează unități de lucru atomice și izolate, efectuate asupra datelor sistemului de gestiune a bazelor de date.

Izolarea tranzacțiilor nu permite crearea tranzacțiilor complexe, mari, din tranzacții simple. Acest model a avut succes atâta vreme cât tranzacțiile efectuau un număr mic de operații simple asupra datelor cu structură simplă.

Din păcate, modelul tranzacțiilor simple nu satisface cerințele aplicațiilor complexe, în care tranzacțiile trebuiesc combinate și coordonate pentru a colabora la realizarea unui scop complex. Aplicații ca proiectarea asistată de calculator, automatizarea activității de birou, controlul producției, gestiunea activităților necesită noi modele tranzacționale, noi metode de gestiune a tranzacțiilor, și noi limbaje de specificare a tranzacțiilor. Limbajele tranzacționale sunt limbaje de nivel înalt, de obicei inspirate din logica cu predicate de ordinul întâi.

Dacă limbajele tradiționale specificau interogări și actualizări, noile limbaje tranzacționale se concentrează asupra relației dintre tranzacții, exprimând dependențe de tipul „tranzacția T2 nu poate porni înainte ca T1 să se termine”, sau „T2 poate începe dacă T1 întoarce o valoare mai mare ca 25”. [20] prezintă o clasificare și analiza detailată a noilor limbaje tranzacționale.

Un excelent exponent al noii generații de limbaje tranzacționale este Transaction Datalog [21], un limbaj deductiv care menține în același timp toate proprietățile tranzacțiilor clasice, cum ar fi: persistență, atomicitate, izolare, terminare și rollback (revenire).

Limbajul este însoțit de un model teoretic natural și de o teorie sigură pentru demonstrații, permițând astfel demonstrarea echivalenței între diverse expresii din acest limbaj. Acest fapt este crucial pentru optimizare - care constă din înlocuirea unei planificări cu o alta echivalentă din punct de vedere al efectului său asupra datelor, dar mai eficientă din punct de vedere al costului execuției. Mai mult, faptul că putem demonstra că efectul unei tranzacții complexe asupra setului de date este sau nu cel scontat, asigură consistența datelor.

Optimizări

Optimizarea limbajelor de interogare a bazelor de date nu este un domeniu nou, ci dimpotrivă, există încă de la apariția acestora. Datorită importanței sale, acest domeniu va fi întotdeauna „la mod㔠în cercetarea bazelor de date.

Apariția unui nou model de date atrage după sine o efervescență în activitatea de cercetare a posibilităților de optimizare a limbajului de interogare asociat noului model. Referințele bibliografice introduse în secțiunea anterioară prezintă și primele încercări de optimizare a noilor limbaje de interogare.

Bibliografie

[1] Peter Buneman, Susan Davidson, Gerd Hillebrand, Dan Suciu, „A Query Language and Optimization Techniques for Unstructured Data”, „Proceedings of ACM-SIGMOD International Conference on Management of Data”, Montreal, Canada,June, 1996, pages 505-516
[2]„The internet movie database”
[3] S. Abiteboul, D. Quass, J. McHugh, J. Widom, J. Weiner, The lorel query language for semistructured data, Journal of Digital Libraries,Vol 1 number 1, 1997
[4] L. V. S. Lakshmanan, F. Sadri, I. N. Subramanian,„A declarative language for querying and restructuring the world-wide-web”,Post-ICDE IEEE Workshop on Research Issues in Data Engineering (RIDE-NDS'96),New Orleans, February,1996
[5] A. O. Mendelzon, G. A. Mihaila, T. Milo, „Querying the world Wide Web”, Proc. PIDS '96, December, 1996
[6] M. P. Consens, A. O. Mendelzon, „Expressing Structural Hypertext Queries in Graphlog”, Proc. 2nd ACM Conference on Hypertext, Pittsburgh, November, 1989
[7] S. Cluet, G. Moerkotte,„Query processing in the schemaless and semistructured context”, INRIA, 1997
[8] Mary Fernandez, Daniela Florescu, Jaewoo Kang, Alon Levy, Dan Suciu, „STRUDEL: A Web Site Management System”,Proc. of the 16th ACM SIGMOD Symposium on Principles of Database Systems,Tucson, Arizona, May, 1997
[9] Sudarshan Chawathe, Hector Garcia-Molina, Joachim Hammer, Kelly Ireland, Yannis Papakonstantinou, Jeffrey Ullman, Jennifer Widom, „The {TSIMMIS} Project:{Integration} of Heterogenous Information Sources”, October, 1994, Tokyo, Japan,„Proceedings of the Information Processing Society of Japan Conference”
[10] Yannis Papakonstantinou, Hector Garcia-Molina, Jennifer Widom, „Object Exchange Across Heterogenous Information Sources”,„Proceedings of IEEE International Conference on Data Engineering”, March, 1995, 251—260
[11]J. McHugh, S. Abiteboul, R. Goldman, D. Quass and J. Widom,„Lore: A database management system for semistructured data”,Stanford University Database Group, February,1997
[12] S. Abiteboul, D. Quass, J. McHugh, J. Widom, J. Weiner,The lorel query language for semistructured data,Journal of Digital Libraries,Vol 1 number 1, 1997
[13] A. Levy, A. Rajaraman, J. J. Ordille, „Querying Heterogeneous Information Sources Using Source Descriptions”,Proc. 22nd International Conference on VLDB, Mumbai, India, 1996,
[14] Arbor Software, „Multidimensional Analysis: Converting Corporate Data into Strategic Information”,White Paper
[15] J. Xenakis, editor,„Mutlidimensional Databases”,Application Development Strategies, April, 1994
[16] J. Gray, A. Bosworth, A. Layman, H. Pirahesh,„Data Cube: A Relational aggregation Operator Generalizing Group-By, Cross-Tab and Sub-Totals”, Microsoft, MSR-TR-95-22
[17] A. Gupta, V. Harinarayan, D. Quass, Aggregate Query Processing in Data Warehousing Environments, Proc. of the 21st International VLDB Conference,P 358-369,1995
[18] V. Harinarayan, A. Rajaraman, J. Ullman, „Implementing Data Cubes Efficiently”,Proc. ACM SIGMOD, Montreal, Canada, June, 1996
[19] J. R. Smith, „Dynamic Assembly of Views in Data Cubes”, Proc. of the International VLDB Conference (to appear), New York, USA, 1998
[20] A. J. Bonner, M. Kifer, „An overview of transaction logic”, Theoretical Computer Science, vol 133, pp 205-265,October, 1994
[21] A. J. Bonner, „Transaction Datalog: a Compositional Language for Transaction Programming”, Proc. 6th International Workshop on Database Programming Languages, Estes Park, Colorado, August, 1997