C13. XML Design

Date Semistructurate, 2012-2013

C13. DS

• XML Design

• Unul din principalele obiective in schema design bun este evitarea redundantelor de date: stocarea de date redundante poate duce nu numai la date ne-consistente si nevoia de spatiu de stocare mai mare, dar si la costuri mai mari de transfer si manipulare => o buna proiectare a schemei XML

• Uneori, documentele XML sunt scrise „de ocazie”, fara o foarte buna analiza sau structura documentelor poate evolua in timp si aduce dependente necunoscute la inceput. Astfel, asemenea documente XML pot intra intr-un proces de re-design, rafinare de schema

• Redundantele datelor. Ca si in cazul BD relationale, redundatele pot duce la anomalii in cazul operatiilor de adaugare, modificare sau stergere. De asemenea, redundante pot sa apara in cazul unor dependente functionale „anormale” de-a lungul cailor dintr-un document XML

C13 - DS

• Notiunea de dependenta functionala (DF) este foarte importanta in proiectarea BD relationale, dar si a documentelor XML. Vezi normalizarea relatiilor. Totusi, teoria, regulile de la 1NF, 2NF, 3NF, 4NF, BCNF, 5NF, nu sunt direct aplicabile in datele semistructurate:

– datele semistructurate au structura mai complexa; de exemplu: un document XML poate sa includa constrangeri de cardinalitate (vezi XSD), care nu se gasesc in modelul relational;

– o instanta de document XML contine si informatie de structura, si date, si trebuie sa respecte o schema (vezi DTD, XSD); totusi, doua instante diferite pot avea structura diferita (vezi partile optionale);

– in structurile relationale se efectueaza comparatii pe valori atomice; in documente XML este posibil sa fie necesar sa se efectueze comparatii pe ierarhii de elemente;

– tratarea atributelor multi-valoare in structurile relationale este o operatie inutila in documente semistructurate / XML in particular.

C13 - DS

• Observatie: Doua noduri n1 si n2 sunt considerate egale ca valoare daca ele contin valori atomice egale sau daca ele contin alte sub-obiecte, egale ca valoare doua cate doua, n1 =v n2 (egalitate pe structura ierarhica)

• Observatie: Constrangere de cheie straina – similar bazelor de date relationale.

• Fie D o schema XML (un DTD, de exemplu).

C13 - DS

• NF-SS

• Exemplu de DTD:

<!ELEMENT department (course+)<!ATTLIST department name ID #REQUIRED><!ELEMENT course (student*)><!ATTLIST course

cid ID #REQUIREDtitle CDATA #IMPLIED>

<!ELEMENT student (grade?)><!ATTLIST student

sid ID #REQUIREDname CDATA #REQUIREDage CDATA #IMPLIED>

<!ELEMENT grade (#PCDATA)>

C13 - DS

• Reprezentare grafica schema:

• Fig. 1.

C13 - DS

• Schema semistructurata D = (E, A, B, P, R, r), unde:– E este o multime de tipuri obiect (etichete de noduri)– A este o multime de atribute, A disjunct de E (etichete de atribute)– B este o multime de tipuri de baza (integer, string, boolean, s.a.)– P este o functie de la E la definitia de tip de obiect (object type definition),

care este o expresie o1_w1, ..., ok_wk, unde oi este obiect din E sau B, iar wi este multiplicitatea din {*, +, ?, 1} (multimea de noduri fiu a unui obiect)

– R este o functie definita pe E cu valori in power set of A (multimea de atribute a unui obiect)

– r din E este tip obiect al radacinii.• Daca o este din E, atunci o(a1, ..., am; o1_w1, ..., on_wn) este o, multimea

de atribute si multimea de obiecte continute in o (sub-elemente).

• Altfel spus: E – elemente, A – atribute, B – tipuri, P – relatie subordonare (element + children sau element + tip), R – relatie care defineste multimea atributelor pentru un element, r – nodul radacina

C13 - DS

• Exemplu:

• E= {department, course, student, grade};• A = {cid, title, sid, name, age};

• P(department) = course+ R(department) = {name}• P (course) = student* R(course) = {cid, title}• P (student) = grade R(student) = {sid, name, age }• P (grade) = string • r = department

C13 - DS

• Data tree (T) pentru o schema data D = (E, A, B, P, R, r) este dat de T = (V, lab, obj, att, val, root), unde:– V este o multime finita de noduri– lab este o functie de etichetare, definita pe V cu valori in E A B– obj este o functie partiala de la V cu valori secvente de elemente din V;

daca v V, o E si lab(v) = o, atunci obj(v) = <v1, ..., vn>, lab(vi) = oi_wi => multimea de noduri fiu

– att este o functie partiala de la V X A la V, unde v V, a A, att(v, a) = v’, ddaca lab(v) = o, lab(v’) = a, o E, v’ V, a R(o) => multimea de atribute

– val – functie partiala care are ca rezultat valoare atomica; v V, atunci val(v) = s, unde s B sau s A

– root este nodul din V care este radacina lui T, lab(root) = r.

• => T = o instanta a schemei D

C13 - DS

• Def: Oricare n din arbore, D sau T, PathD(n) sau PathT(n) este calea de la radacina la n.

• Observatie: Doua noduri n1 si n2 sunt considerate egale ca valoare daca au aceeasi eticheta, contin valori atomice egale sau daca ele contin alte sub-obiecte, egale ca valoare doua cate doua, n1 =v n2.

• Def: Fie T1 si T2 doua data tree peste acelasi schema D = (E, A, B, P, R, r), si X E A. T1 si T2 agree on X, T1 =v T2, daca exista t1 T1[X] si t2 T2[X] a.i. t1 =v t2.

• Obs: In BDR, fie o relatie R si un set de atribute X, din R. Doua tuple “agree on X” daca proiectiile lor pe X sunt egale.

• Def: Fie D = (E, A, B, P, R, r), S o multime de data tree pentru D, X E A, Y E A. Y este dependent functional extins (EFD) fata de X, X -> Y, daca oricare T1 si T2 din S, si T1 si T2 agree on fiecare componenta a lui X, atunci T1 si T2 agree on Y. [Wu]

• (practic, valoarea pentru X determina valoarea pentru Y, ca in BDR)

C13 - DS

• Fig. 2.

C13 - DS

• Fig. 3.

C13 - DS

• Exemple EFD:

• Exemplu: In fig. 3. – {/warehause/state/store/book/ISBN} -> {/warehause/state/store/book/title}

• => daca exista doua noduri book cu aceleasi valori pentru ISBN, atunci au si valorile title egale.

• Exemplu: In fig. 2.– cursuri, studenti – exista doua noduri student cu acelasi sid si cu aceleasi

valori ale atributelor name si age => {/department/course/student/sid} -> {/department/course/student/name, /department/course/student/age}

C13 - DS

• Alte definitii:

• Daca X -> Y si exista X’ X a.i. X’ -> Y atunci X -> Y este numit EFD partial. Altfel, este numit complet (full).

• Daca X -> Y si Y X atunci X -> Y este numit EFD trivial.

• Daca X -> Y si /X/Y este cale in D atunci X -> Y este numit EFD coerent. Altfel, este numit EFD incoerent.

• Daca X -> Y si exista Z E A, Y -> Z, NOT Y -> X atunci Z este dependent functional tranzitiv de X, via Y.

C13 - DS

• Exemplu:

– course.cid,student.sid -> student.name

– student.sid -> student.name

• unde (1) este EFD partial si (2) este EFD complet.

C13 - DS

• Observatie: EDF-urile incoerente produc asa-numitele anomalii de cale care indica o grupare nu tocmai buna a informatiei (nu reflecta bine relatiile din realitatea modelata in ierarhia documentului).

• Exemplu: Fig. 4.

C13 - DS

• Observatie: EDF-urile incoerente produc asa-numitele anomalii de cale care indica o grupare nu tocmai buna a informatiei (nu reflecta bine relatiile din realitatea modelata in ierarhia documentului).

• Exemplu: Fig. 4.

C13 - DS

• Exemplu: In fig. 2:– (1) course.@cid -> student.@sid– (2) student.@sid -> student.@age– si NOT (student.@sid -> course.@cid)

• => age este dependent tranzitiv fata de course, via student.

• Observatie: Dependentele tranzitive sunt cauza anomaliilor de actualizare (age se repeta pentru un student – la fiecare curs pe care si l-a ales => actualizarea varstei trebuie efectuata pentru toate aparitiile).

C13 - DS

• Chei• (Cheie definita pe baza unei scheme si a EFD-urilor)

• Fie o schema D. Fie un obiect de tip complex O(a1, ..., am; o1, ..., on) (atribute si sub-obiecte – simple sau complexe). Fie K o submultime nevida (a1, ..., ap; o1, ..., oq) a.i. oi sunt obiecte atomice, simple. K este cheie daca:– O este radacina lui D. K este cheie candidat a lui O ddaca K -> O si nu

exista K’ K a.i. K’ -> O.– O nu este radacina lui D. Fie PathD(O) = O0/O1/ ... /Ov-1, v>0, Pk Kv-1,

unde Kv-1 este cheia parintelui lui O (Ov-1). KO = Pk K este cheia lui O ddaca (Pk, K) -> O, si nu exista o submultime KO’ KO a.i. KO’ -> O.

• Daca KO contine doar elemente si / sau atribute ale lui 0 => cheie absoluta; altfel – cheie relativa (pentru a-l identifica, foloseste si ceva din parinti).

C13 - DS

• Exemplu: Fie o schema pentru structura unei carti, cu calea /books/book[@isbn]/chapter[@number]/section[@number]

– Kbook = book.@isbn (cheie absoluta – nu depinde de nimic din nodurile parinte)

– Kchapter = book.@isbn/chapter.@number (cheie relativa)

– Ksection = book.@isbn/chapter.@number/section.@number (cheie relativa)

• Exemplu: student.@sid = cheie absoluta

C13 - DS

• Pentru a aduce o schema D in NF-SS:

– radacina trebuie sa aiba cheie;

– (*) daca O1 este tip sub-obiect a lui O, KO KO1 = sau KO KO1, unde KO este cheia lui O, iar KO1 este cheia lui O1.

– plus, sa se elimine EFD-urile partiale, tranzitive si anomaliile de cale.

C13 - DS

• Reguli de normalizare

• R1. Se elimina dependentele functionale tranzitive.

• Daca exista: O obiect in schema D, si componenta Y a lui O care este tranzitiv dependent de o cheie KO a lui O a.i. KO -> X, X -> Y si NOT X -> KO si X KO = .

• Atunci D poate fi restructurat ca:– se duplica X si formeaza un nou nod Z

– se muta Y si toti fiii lui (tot sub-arborele lui Y) sub Z

– X se transforma in cheie straina in O, catre Z.

C13 - DS

• Exemplu:• In fig. 2:• (1) department.@name -> course.@cid• (2) course.@cid -> department• (3) course.@cid -> course.@title• (4) course.@cid -> student.@sid• (5) course.@cid, student.@sid -> grade• (6) student.@sid -> student.@name, @age• Din (4) si (6) – tranzitiv dependenta si NOT student.@sid -> course.

Dar course.@cid student.@sid = => se foloseste regula de mai sus pentru a descompune student in student1(sid, grade) si student2(sid, name, age), unde student1 ramane fiu a lui course, iar student2 este mutat ca fiu al nodului radacina al arborelui XML. student1.@sid este cheie straina catre student2.@sid.

C13 - DS

• Fig. 2., din nou:

C13 - DS

• Fig. 2., plus dependente tranzitive eliminate:

C13 - DS

• R2. Se elimina anomaliile de cale.

• Fie D si un EFD incoerent O1.X1,..., On.Xn -> Y, unde Y este un obiect sau atribut, si exista o cale P care contine O1, ..., On, Y. Calea P se descompune in P1 si P2 – vezi exemplul urmator.

• Aceasta regula este folosita pentru a elimina anomaliile de cale si dependentele partiale, plus over-nesting. Ideea este de a pastra obiecte / atribute cat mai aproape de proprietarul lor (de cel care le determina).

• Solutie – promovarea lui Y (se muta la un nivel superior in arborele XML).

C13 - DS

• Exemplu: In fig. 4.(a):

– (1) teacher.@tid,time -> ClassRoom

– (2) teacher.@tid, time -> subject

D nu este in NF-SS deoarece

contine aceasta anomalie de cale.

Calea teacher/classroom/subject/time

se imparte in caile

teacher/time/ClassRoom

si teacher/time/subject

(vezi fig. 4.(b)).

C13 - DS

• Exemplu: In fig. 4.(a):

– (1) teacher.@tid,time -> ClassRoom

– (2) teacher.@tid, time -> subject

C13 - DS

• 3. Se elimina dependentele partiale.

• Fie un tip obiect O in schema D. Fie X o multime de attribute / sub-elemente prime ale lui O (X KO), si Y setul de atribute / sub-elemente a lui O. Fie O1 un tip sub-obiect a lui O. Daca (KO -X) -> O1 si nici o submultime X’ X nu satisface aceasta proprietate, atunci D este restructurat astfel:– 1. (KO Y – X) raman singurele atribute / sub-elemente ale lui O, iar O1

ramane sub-obiect;– 2. Se creeaza un nou tip obiect O2 care este componenta directa a lui O;– 3. Se muta restul componentelor lui O (plus descendentii lor) sub O2.

C13 - DS

• Exemplu:

• In fig. 5.(a), fie:– O.@A, O.@B -> D,

– O.@A, O.@B -> O2,

– O.@A -> O1,

– O.@A -> E,

– cheia lui O este {A, B}.

• Schema nu este in NF-SS deoarece exista dependenta partiala O.@A(, O.@B) -> O1.

• Astfel, se creeaza un tip obiect O3 cu descendentii O2 si B, D, E (vezi fig. 5.(b)).

• Deoarece exista EFD incoerent O.@A -> E, se promoveaza E ca fiu direct a lui O (vezi fig. 5.(c)).

C13 - DS

• Fig. 5.

C13 - DS

• Fig. 6. Exemplu:– (1) O.@K, O.@A -> O1

– (2) O.@K, O.@B -> O2 – si cheia lui O este KO = {K, A, B}.

C13 - DS

• O metoda de detectare a dependentelor functionale in documentele semistructurate:

• Exemplu: presupune toate nodurile existente!!!

C13 - DS

• Se construiesc toate tuplele posibile care ar fi obtinute prin transformarea acestei structuri XML in tabel: (stud := student)

dept.name, course.cid, course.title, stud.sid, stud.name, stud.age, stud.grade

CS cs4221 DB Design s01 Jack 21 A-CS cs4221 DB Design s02 Tom 20 A...CS cs5220 Data Mining s01 Jack 21 B+...

• =>• course.cid -> course.title• course.title -> course.cid• dept.name, course.cid -> course.title• student.sid -> student.name, student,age• ...

• Observatie: Trebuie ca documentul sa contina suficient de multe date pentru o determinare aproximativ buna a dependentelor functionale.

C13 - DS

• Exemplu:

<!ELEMENT jocuri (jo+)><!ELEMENT jo (sport+)>

<!ATTLIST jo @an ID #REQUIRED><!ELEMENT sport (denumire, clasament+)>

<!ATTLIST sport sportid CDATA #REQUIRED><!ELEMENT denumire (#PCDATA)><!ELEMENT clasament (sportiv*)>

<!ATTLIST clasament pozitie CDATA #REQUIRED><!ELEMENT sportiv (nume, tara)>

<!ATTLIST sportiv sportivid CDATA #REQUIRED><!ATTLIST sportiv localitate_jo CDATA #REQUIRED><!ATTLIST sportiv sport_practicat CDATA #REQUIRED><!ATTLIST sportiv pers_best CDATA #REQUIRED>

<!ELEMENT nume (#PCDATA)><!ELEMENT tara (#PCDATA)>

C13 - DS

• Exemplu:

• Banca– Client

• @Codclient, CNP, Nume, Adresa, Telefon• Cont

– @Nrcont– Sold

» @Luna, @An, @Valuta, Valoare– Imputernicit

» CNP, Nume, Adresa, Telefon– Angajat

» @codAngajat, Nume, Mail

C13 - DS

• Bibliografie:

• Xiaoying Wu, Tok Wang Ling, Sin Yeung Lee, Mong Li Lee, Gillian Dobbie, NF-SS: A Normal Form for Semistructured Schema, LCNS, Springer Berlin / Heidelberg, Vol. 2465, 2002, pp. 292-305.

• Marcelo Arenas, Leonid Libkin, A Normal Form for XML Documents, ACM Transactions on Database Systems, Vol. 29(1), 2004, pp. 195-232.

• Yu, C., Jagadish, H.V., XML Schema Refinement through Redundancy Detection and Normalization, The VLDB Journal, Vol. 17, Issue 2, 2008, pp. 203-223.

C13 - DS