rezumat teza de doctorat

UNIVERSITATEA DIN BUCURETI FACULTATEA DE MATEMATIC I INFORMATIC

TEZ DE DOCTORAT GESTIUNEA INFORMAIEI

DISTRIBUITE REZUMAT

CONDUCTOR TIINIFIC PROF. UNIV. DR. IOAN TOMESCU

DOCTORAND ASIST. UNIV. GABRIELA MIHAI

BUCURETI 2010

INTRODUCERE

Centralizarea i descentralizarea sunt dou tendine opuse care au marcat alternativ evoluia sistemelor informatice. Tehnologia sistemelor de baze de date distribuite mbin dou domenii aparent opuse din punct de vedere al prelucrrii datelor: sistemele de baze de

date i reelele de calculatoare. Sistemele de baze de date asigur integrarea informaiilor i centralizarea lor, astfel

nct s permit controlul accesului la aceste informaii. Tehnologia reelelor de calculatoare promoveaz un mod de lucru descentralizat. Bazele de date distribuite reprezint unul dintre

compromisurile cele mai profitabile, pstrnd avantajele ambelor abordri. Trebuie avut n vedere c obiectivul cel mai important n tehnologia bazelor de date este integrarea informaiilor, nu centralizarea acestora. Se poate realiza integrare fr centralizare, iar acest fapt este posibil prin tehnologia bazelor de date distribuite.

Bazele de date distribuite sunt colecii de baze de date corelate logic ntre ele care rezid pe mai multe calculatoare interconectate printr-o reea de comunicaie (zsu i Valduriez 1999). Din perspectiva utilizatorului final baza de date distribuit apare ca o baz de date unic. Bazele de date distribuite ofer sistemelor informaionale o serie de avantaje, ce permit managerilor locali libertatea de a prelucra informaiile, astfel nct s rezolve necesitile departamentului pe care l conduc i reduc impactul provocat de eventualele defeciuni ale sistemului. De asemenea, prin crearea unor baze de date mai mici, n diferite locaii, se asigur prevenirea pierderii datelor.

Datorit problemei critice privind performana, procesarea cererilor este o arie de interes att n contextul bazelor de date centralizate, ct i n cazul sistemelor distribuite. Problema procesrii cererilor este mult mai complex n mediile distribuite, deoarece un numr mare de parametri pot afecta performana acestora. n sistemele cu multe staii, timpul de rspuns poate fi foarte mare mai ales n cazurile n care cererea implic operaii

de join pe tabele de dimensiuni mari. Este evident c n cazul bazelor de date distribuite un rol deosebit de important l reprezint partea de configurare a reelei de calculatoare.

Introducere

2

Datorit dezvoltrii susinute a calculului paralel i distribuit, realizarea i analiza

unor noi reele de interconectare pentru sistemele paralele i distribuite reprezint un subiect

principal de studiu. Actualele tehnologii de comunicaie fac posibil conectarea unor sisteme

de calcul ce conin un numr mare de procesoare folosind reele de interconectare

de mare vitez.

Un sistem distribuit este o colecie de sisteme de calcul independente care pentru un

singur utilizator apare ca un singur sistem de calcul (Tanenbaum i Van Steen 2007). Exist dou aspecte ale acestei definiii: din punct de vedere hardware sistemele de calcul sunt

independente, iar din punct de vedere software utilizatorul vede ntregul sistem ca pe un singur sistem de calcul.

Att n cazul sistemelor de baze de date, ct i n cazul sistemele de calcul, exist

cteva elemente importante care au motivat trecerea de la centralizare la distribuire.

Avantajele eseniale care au determinat utilizarea distribuirii sunt urmtoarele: obinerea autonomiei locale - deoarece sistemele distribuite permit organizarea

descentralizat a informaiilor, utilizatorii dintr-un nod al reelei pot avea control

local asupra datelor stocate n acea locaie; posibilitatea partiionrii autoritii i a

responsabilitii n sistemele informaionale este unul dintre motivele eseniale care

au determinat trecerea la sistemele distribuite;

creterea performanelor - ntr-un sistem distribuit accesul la informaii este

mbuntit prin posibilitatea de execuie n paralel a sarcinilor; deoarece fiecare

staie prelucreaz doar o poriune a aplicaiei, disputele asupra folosirii resurselor

(CPU, I/O) nu sunt att de intense ca n cazul sistemelor centralizate; mai mult, stocarea datelor n mai multe locaii permite execuia n paralel a sarcinilor, astfel

micorndu-se timpul de execuie a acestora;

creterea fiabilitii - sistemele distribuite pot reduce impactul provocat de

eventualele cderi ale componentelor reelei de comunicaii prin folosirea mai multor

copii ale datelor n locaii diferite; cderea unui nod din sistem sau ntreruperea unei

legturi de comunicaie poate determina ca anumite noduri s devin inaccesibile,

dar aceasta nu presupune inoperabilitatea total a sistemului; chiar dac anumite date

nu sunt accesibile, sistemul distribuit poate asigura servicii limitate;

Introducere

3

partajabilitatea informaiilor - organizaiile care ntreprind activiti distribuite geografic stocheaz de obicei informaiile ntr-o form distribuit; n general, dac

sistemul informatic nu este distribuit, atunci acesta nu poate permite folosirea n comun a datelor sau a resurselor; sistemele distribuite fac posibil partajarea informaiilor, accesul la acestea fiind permis tuturor utilizatorilor;

scalabilitatea sistemului - fa de sistemele centralizate, sistemele distribuite sunt

mult mai uor de adaptat la creterea complexitii i dimensiunii aplicaiei; pe msur ce necesitile cresc, se pot aduga staii noi n reea, mrind simultan i

fiabilitatea sistemului;

scderea costurilor - costurile de comunicaie se reduc simitor dac sistemele

distribuite geografic permit partiionarea aplicaiilor i procesarea local a informaiilor; de asemenea, un sistem distribuit poate determina scderea costurilor pentru echipamentele hardware; n general, costurile sunt mult mai reduse dac se organizeaz un sistem cu mai multe procesoare mici care este echivalent ca putere cu

unul care are un procesor foarte mare.

n luarea deciziei de utilizare a sistemelor distribuite trebuie avute n vedere i problemele pe care aceste tipuri de sisteme le pot genera:

complexitatea - problemele generate de utilizarea unui sistem distribuit sunt cu mult

mai complexe dect cele ale sistemelor centralizate; pe lng problemele aprute n

cazul sistemelor centralizate acestea includ o serie de probleme specifice mediului distribuit;

distribuia controlului - acest aspect a fost prezentat anterior ca un avantaj pe care l ofer mediile distribuite; totui, distribuirea poate crea probleme de sincronizare i de coordonare a proceselor; de aceea, trebuie adoptate politici adecvate pentru a putea preveni apariia acestor probleme;

securitatea - unul dintre cele mai importante beneficii ale utilizrii sistemelor centralizate este asigurarea controlului de acces la date; n cazul mediilor centralizate

securitatea poate fi controlat cu uurin dintr-un punct central;

dificultatea schimbrii - dac o companie a investit ntr-un sistem centralizat, atunci implementarea unui sistem distribuit nu are sens; n prezent, nu exist instrumente

Introducere

4

sau metodologii pentru convertirea unui sistem centralizat ntr-unul distribuit; costurile de pregtire a personalului i cele pentru achiziionarea componentelor software sau hardware adecvate pot fi mult prea mari pentru ca modificarea s fie justificat din punct de vedere economic;

costurile - sistemele distribuite necesit componente hardware adiionale (de exemplu, mecanisme pentru comunicaii) i componente software complexe, acestea mrind costurile de configurare a bazelor de date distribuite; n plus, este necesar angajarea de personal suplimentar pentru ntreinerea nodurilor reelei i pentru procesarea datelor de la aceste niveluri.

n consecin, problemele determinate de utilizarea unui sistem distribuit au o complexitate sporit fa de cele specifice unui sistem centralizat. n plus, aceast complexitate mrit poate genera probleme noi, influenate n mare parte de trei factori:

inexistena copiilor de siguran ale datelor la nivelul mai multor noduri din reea;

neasigurarea unor mecanisme care s determine propagarea modificrilor asupra datelor la nivelul fiecrei copii a acestora;

ngreunarea sincronizrii copiilor.

O reea de interconectare poate fi modelat printr-un graf G = (V;E). Vrfurile grafului reprezint nodurile reelei, iar muchiile grafului corespund liniilor de comunicaie. Dac comunicaia dintre noduri se realizeaz ntr-o singur direcie, atunci graful este orientat. n caz contrar, modelul este cel al unui graf neorientat. Graful care modeleaz reeaua de interconectare reprezint topologia reelei.

n aceast lucrare subiectul gestiunii informaiei distribuite va fi abordat din cele dou perspective discutate anterior: a grafurilor care permit modelarea reelei de interconectare, respectiv a bazelor de date.

Din punct de vedere logic lucrarea cuprinde dou pari, una dedicat teoriei grafurilor, iar cealalt bazelor de date. Fiecare parte este structurat pe dou capitole.

Primele dou capitole ale lucrrii trateaz dou probleme de etichetare a anumitor clase de grafuri. Este vorba de etichetarea L(2; 1), respectiv etichetarea radio a grafurilor. Aceste dou tipuri de etichetri pe care le-am abordat n lucrare sunt utile n rezolvarea unei probleme practice, i anume atribuirea de frecvene corespunztoare fiecrei staii radio dintr-un sistem fr a se produce interferene.

Introducere

5

Fie G un graf conex de diametru d i p un numr ntreg pozitiv, astfel nct

1 p d. Se numete p - etichetare radio a grafului G o funcie f care atribuie vrfurilor

grafului G numere ntregi pozitive (etichete, culori) astfel nct:

d(u; v)+ j f (u) f(v) j p + 1;

oricare ar fi u i v dou vrfuri distincte ale grafului G i d(u; v) distana dintre acestea.

Dac funcia f este o p - etichetare radio a grafului G, atunci se noteaz cu rcp(f)

valoarea etichetei maxime atribuit prin funcia f vrfurilor grafului G. Numrul rcp(G)

reprezint cel mai mic numr rcp(f), oricare ar fi f o p - etichetare radio a grafului G.

n funcie de valoarea numrului p se obin diferite forme de etichetri radio. De exemplu, dac p = 1, atunci problema se reduce la colorarea clasic a grafurilor. Problema

colorrii grafurilor const n atribuirea unei etichete (culori) fiecrui vrf din graf, astfel nct vrfurile adiacente s nu primeasc aceeai etichet. n acest caz, numrul rc1(G) este denumit numrul cromatic al grafului G i este notat cu (G).

n primul capitol al tezei am abordat problema etichetrii L(2; 1) a grafurilor. Acest tip de etichetare se obine pentru p = 2. Problema const n atribuirea unui numr ntreg

pozitiv fiecrui vrf al grafului, astfel nct etichetele vrfurilor adiacente s difere prin cel puin 2, iar etichetele vrfurilor aflate la distan 2 s difere prin cel puin 1. n acest caz, numrul rc2(G) este notat cu (G), aceast afirmaie fiind adevrat dac etichetarea

ncepe cu valoarea minim 1. Deoarece n cazul etichetrii L(2; 1) eticheta minim este

considerat 0, se obine de fapt (G) = rc2(G) 1.

n prima seciune a capitolului este inclus o retrospectiv a celor mai importante rezultate obinute pn n prezent privind acest tip de etichetare. Urmtoarele dou seciuni reprezint contribuii personale. Iniial, sunt determinate valorile exacte ale numerelor

asociate grafurile totale ale grafurilor bipartite complete. Acest rezultat este extins

pentru grafurilor totale ale grafurilor multipartite complete.

Al doilea capitol prezint problema d - etichetrii radio a unui graf G, unde d

reprezint diametrul grafului. Aceast etichetare este numit simplu etichetare radio, iar numrul rcd(G) se numete numr radio i este notat rn(G). Ca i n cazul primului capitol,

prima seciune cuprinde definiiile i notaiile de baz, respectiv unele dintre cele mai importante rezultate obinute pn n prezent. Urmtoarele trei seciuni ale capitolului includ

Introducere

6

contribuii personale, fiind determinate valorile numerelor radio pentru anumite clase de grafuri (subdiviziunile 2-uniforme ale grafului roat Wn , subdiviziunile k -uniforme ale grafului roat Wn, graful floarea soarelui SFn i graful mCn + K1).

Urmtoarele dou capitole sunt dedicate bazelor de date relaionale. Pentru definiiile, notaiile i terminologia specific bazelor de date relaionale se face referire la (Popescu 1996), (Popescu 2001) i (Dollinger i Andron 2004).

Modelul relaional a fost conceput i dezvoltat de Codd ((Codd 1970), (Codd 1990)), fiind un model formal de organizare conceptual a datelor, destinat reprezentrii legturilor dintre date i bazat pe teoria matematic a mulimilor i logic matematic. Modelul relaional este alctuit numai din relaii i prin urmare orice interogare asupra bazei de date este tot o relaie. Codd a definit acest model cu o deosebit rigoare matematic, furniznd un

mijloc performant de studiu al proprietilor logice ale unui sistem de baze de date. Un model relaional este caracterizat de trei elemente: structura relaional a datelor,

operatorii relaionali ce acioneaz asupra structurii i regulile de integritate ce trebuie respectate de model. Din punct de vedere formal, datele sunt organizate n relaii (tabele), relaiile reprezint mulimi de tupluri (linii), tuplurile sunt caracterizate de atribute (coloane), iar atributele aparin unor domenii (tipuri de date). La nivel fizic, aceste elemente devin fiierele, nregistrrile, cmpurile, respectiv tipurile de date.

Mulimea atributelor unei relaii R definete schema relaional a relaiei respective.

Dac relaia R este caracterizat de atributele A1; A2; :::; An, atunci schema relaional a

relaiei R va fi notat cu R(A1; A2; :::; An).

Operatorii modelului relaional definesc operaiile care se pot efectua asupra relaiilor, n scopul realizrii funciilor de prelucrare asupra bazei de date. Modelul relaional

ofer dou mulimi de operatori pe relaii, i anume algebra relaional i calculul relaional. Operatorii algebrei relaionale sunt fie operatorii tradiionali pe mulimi (union, intersect, product, difference), fie operatori relaionali speciali (select, project, join, division).

Accesarea informaiilor stocate ntr-o baz de date se realizeaz folosind interogri

SQL. Pentru a nu afecta performana sistemului, interogrile SQL trebuie optimizate, astfel nct s produc rezultatul dorit cu un cost ct mai mic. Unul dintre cei mai costisitori operatori relaionali este operatorul join (compunere).

Introducere

7

n capitolul al treilea al tezei este tratat operatorul outer join cu toate cele trei forme ale acestuia (left, right i full). Aceast seciune conine contribuii personale. Algoritmii clasici de procesare a operaiilor de join sunt modificai astfel nct s permit procesarea diverselor forme ale operatorului outer join. Sunt realizate o serie de teste asupra acestor algoritmi pentru a putea decide care dintre acetia reprezint o alegere bun pentru a procesa o operaie de outer join ntr-un anumit context. n lucrare sunt incluse exemple care ruleaz n cazul unor baze de date centralizate. n schimb, algoritmii au fost testai i pe medii distribuite, rezultatele obinute fiind relativ asemntoare. Evident, n cazul bazelor de date distribuite un rol deosebit de important l joac alegerea modului de distribuire a datelor (replicare total, replicare parial, tipul de fragmentare al relaiilor orizontal primar, orizontal derivat, vertical sau mixt), a topologiei reelei, a modalitii de gestiune a problemelor de sincronizare a replicilor de date, a politicilor de securitate etc.

Ultimul capitol al tezei reprezint o dorin fireasc de a implementa, a testa i a optimiza anumite aplicaii din teoria grafurilor folosind tehnologii specifice sistemelor de gestiune a bazelor de date. Acest fapt presupune c graful este stocat ntr-o baz de date. Au existat mai multe motive care au stat la baza acestei decizii:

majoritatea aplicaiilor pot fi proiectate folosind structuri de grafuri; aplicaiile actuale pot utiliza cantiti foarte mari de date al cror volum este n

continu cretere;

se dorete distribuirea datelor astfel nct s se obin toate avantajele configurrii unui sistem de baze de date distribuite;

sunt necesare faciliti de configurare a aplicaiilor client/server etc. n acest scop a fost configurat o baz de date care s permit ncrcarea, stocarea i

prelucrarea unor grafuri de dimensiuni mari. De asemenea, au fost implementai algoritmii specifici arborilor i grafurilor. Capitolul include contribuii personale. Sunt propui algoritmi care permit rezolvarea ctorva probleme: distane n grafuri; lanuri de cost minim n grafuri; centrul grafului. Aceste probleme au fost rezolvate att folosind metodele specifice programrii pe obiecte, ct i metode specifice bazelor de date. Testele realizate au demonstrat c pe lng o serie de alte avantaje, sistemele de gestiune a bazelor de date dispun de faciliti suplimentare care permit obinerea unui timp de execuie mai bun n cazul modelelor de grafuri ce au fost generate pentru teste.

CAPITOLUL I

Etichetarea L(2,1) a grafurilor

Dorind s rezolve problema asignrii frecvenelor, Yeh mpreun cu Griggs au

propus noiunea de etichetare L (2 ; 1) a unui graf simplu (Yeh 1990), (Griggs i Yeh 1992). Etichetarea L (2 ; 1) a unui graf const n atribuirea unui numr ntreg pozitiv fiecrui vrf al

grafului, astfel nct etichetele vrfurilor adiacente s difere prin cel puin 2, iar etichetele

vrfurilor aflate la distan 2 s difere prin cel puin 1. Acest concept generalizeaz noiunea de colorare, deoarece colorarea vrfurilor unui

graf corespunde etichetrii L (1 ; 0). Numrul L (2 ; 1)

al unui graf G, notat cu (G ), este cel

mai mic numr k pentru care graful G permite o etichetare L (2 ; 1) cu etichete mai mici

dect k .

Problema atribuirii unei frecvene corespunztoare fiecrei staii radio fr a se produce interferene poate fi formulat ca o problem de etichetare a unui graf, aplicnd condiii care depind de distanele dintre vrfuri. Etichetarea L (2 ; 1) poate fi numit

etichetare la distan 2, deoarece constrngerile se aplic vrfurilor care se afl la distan 2.

Griggs i Yeh au demonstrat c orice graf cu gradul maxim are o etichetare

L (2 ; 1) pentru care valoarea este cel mult 2 + 2

(Griggs i Yeh 1992). Chang i Kuo au determinat o margine superioar mai mic pentru numrul , aceasta fiind 2 +

(Chang i Kuo 1996). Griggs i Yeh au conjecturat c 2 este cea mai bun limit superioar a valorii , pentru orice graf G care are gradul maxim 2, aceast margine fiind valid

pentru grafurile care au diametrul 2

(Griggs i Yeh 1992). Problema etichetrii L (2 ; 1) a fost tratat n multe articole (Chang i Kuo 1996),

(Georges, Mauro i Whittlesey 1994), (Griggs i Yeh 1992), (Liu i Yeh 1997), (Shao, Yeh i Zhang 2008), (Yeh 1990). n cele mai multe dintre aceste lucrri este determinat valoarea pentru clase particulare de grafuri. Determinarea valorii s-a demonstrat a fi o problem

NP-dificil (Griggs i Yeh 1992).

Capitolul 1 Etichetarea L(2,1) a grafurilor

9

n prima parte a capitolului este introdus noiunea general de etichetare L (d 1 ; d 2 )

i sunt amintite cteva dintre rezultatele remarcabile gsite pn n prezent n cazul acestui

tip de etichetare. n continuare este tratat cazul particular L (2 ; 1). n urmtoarele dou pri ale acestui capitol sunt incluse rezultatele pe care le-am obinut pentru grafurile totale ale

grafurilor bipartite complete, respectiv pentru grafurile totale ale grafurilor multipartite

complete. Pentru aceste clase de grafuri am determinat valorile exacte ale numerelor

asociate. Am demonstrat c n aceste cazuri conjectura Griggs i Yeh este adevrat. De asemenea, am furnizat o margine superioar mai bun a valorilor corespunztoare acestor

clase grafuri.

Pentru terminologia i notaiile de baz utilizate n teoria grafurilor se face referire la

monografia (Harary 1969).

1.1. Noiuni introductive

Fie G un graf conex cu mulimea vrfurilor V (G ). Pentru oricare dou vrfuri

distincte u i v ale grafului G, notm cu dG (u; v ) distana dintre acestea. De asemenea,

notm cu (G) gradul minim al grafului G i cu (G) gradul su maxim.

n situaiile n care referirea la graful G este evident se vor folosi notaiile directe d(u; v ), , respectiv :

1.1.1. Etichetarea L(d1,d2) a grafurilor

Acest tip de etichetare reprezint generalizarea noiunii de etichetare L (2 ; 1).

Definiie. Pentru numerele ntregi pozitive k , d1 i d2, o etichetare k L (d1 ; d2) a unui

graf G este o funcie f : V (G ) ! f0 ; 1; 2 ; : : : ; kg definit astfel nct:

jf (u ) f (v )j d i ; daca dG (u; v ) = i; unde i 2 f1 ; 2g :

Definiie. Numrul L(d1 ; d2) al unui graf G, notat cu d1 ;d2 (G), reprezint cel mai mic

numr k pentru care graful G admite o etichetare k L (d1 ; d2).


10

Problema etichetrii L (d 1 ; d 2 ), unde d1 d2 1, a reprezentat subiectul multor

articole. n continuare sunt date cteva dintre cele mai importante rezultate privind acest tip de etichetare, obinute pn n prezent.

Proprieti generale

Aceste proprieti provin fie din definiii, fie pot fi gsite n cteva articole (Griggs i Yeh 1992), (Chang, Ke, i alii 2000), (Georges i Mauro 1995) i (Georges i Mauro 1994).

Fie H un subgraf al grafului G. Atunci d1 ;d2 (H ) d1 ;d2 (G), unde d1 d2. De

remarcat este faptul c aceast proprietate nu este adevrat dac d1 < d2. De exemplu,

graful K1;n este subgraf al grafului Kn+1, dar 0;1(K 1;n) = n 1 > 0;1(Kn+1) = 0 . n schimb, dac H este un subgraf indus, atunci inegalitatea este adevrat pentru orice d1 i

d2. Dou vrfuri u i v sunt adiacente (distana dintre acestea este 1) n G dac i numai dac u i v sunt adiacente n H. Dac dG (u ; v ) = 2, atunci dH (u; v ) 2. Aceasta verific

afirmaia anterioar.

Dac G este un graf care are gradul maxim 1, atunci d;1(G) + d 1.

Mai mult, dac d;1(G) = + d 1 i d 2 , atunci f (x) = 0 sau f (x ) = + d 1

pentru orice etichetare f de tip L (d ; 1) i orice vrf major x . Un vrf major este un vrf care are gradul maxim .

Pentru orice graf G i pentru oricare trei numere ntregi pozitive d1, d2 i c , se

obine c cd1;cd2 = cd1 ;d2.

Dac G este un graf cu cel puin o muchie, atunci

limd!1

d+1;1(G)

d;1(G)= 1.

1.1.2. Etichetarea L(2,1) a grafurilor

Definiie. Etichetarea L (2 ; 1) a unui graf G este o funcie f : V (G ) ! Z+

care satisface

urmtoarele condiii:

jf (u ) f (v )j 2 ; daca dG (u; v ) = 1

jf (u ) f (v )j 1 ; daca dG (u; v ) = 2 :


11

Definiie. Numrul L (2 ; 1) al unui graf G, notat cu (G ), este cel mai mic numr pentru

care G

admite o etichetare L (2 ; 1) astfel nct maxff (v ) : v 2 V (G )g = k .

n continuare sunt prezentate cteva dintre cele mai importante rezultate referitoare la numerele ale anumitor tipuri de grafuri.

Teorem. (Griggs i Yeh 1992) (i). Dac G este un graf de ordin n, atunci (G ) n + (G ) 2.

(ii). Pentru orice graf G, (G ) 2 + 2 . (iii). Dac G este un graf care are diametrul , atunci (G ) 2 .

Chang i Kuo au redus limita superioar n cazul (ii) la 2 + (Chang i Kuo 1996). Apoi, Kral i Skrekovski au redus aceast limit la 2 + 1

(Kral i Skrekovski 2003). Limita superioar 2 din relaia (iii) este cea mai bun atunci cnd 2 f2 ; 3 ; 7g. Se cunoate c un graf cu diametrul pentru care jV (G ) j = 2 + 1 exist doar dac

2 f2 ; 3 ; 7 ; 57g

(Bondy i Murty 1976). Deoarece diametrul are valoarea

2 , toate

etichetele grafului trebuie s fie distincte. Astfel, rezult c (G ) jV (G ) j 1 = 2 . Pe

de alt parte, din (iii) se obine c (G ) 2 : Rezult c (G ) = 2 doar dac 2 f2 ; 3 ; 7 ; 57g. Dac = 2, atunci se obine graful C5. Dac = 3, atunci se obine

graful lui Petersen. Graful pentru care = 7 este numit graful Hoffman-Singleton (Bondy i Murty 1976).

Conjectur. (Griggs i Yeh 1992) Pentru orice graf care are gradul maxim 2, exist inegalitatea (G ) 2 .

Teorem. (Shao, Yeh i Zhang 2008)

(T(Kn)) =

8>>>>>:

4; daca n = 2

7; daca n = 3n

2

; daca n 4:


12

1.2. Etichetarea L(2,1) a grafurilor totale ale grafurilor ,

Definiie. Graful total al unui graf G, notat T (G), este graful ale crui vrfuri corespund

vrfurilor i muchiilor grafului G, dou vrfuri din T (G ) fiind adiacente dac i numai

dac acestea corespund n graful G unor vrfuri adiacente, unor muchii adiacente sau unor

vrfuri i muchii incidente.

n aceast seciune se vor considera grafurile bipartite complete Kn;m pentru care n m, cu bipartiia vrfurilor V (Kn;m ) = V1 [ V2, unde mulimile V1 i V2 sunt disjuncte i jV 1 j = n , iar jV2 j = m .

1.2.1. Proprieti ale grafurilor totale ale grafurilor Kn,m

Lem. (Mihai 2010) Dac G este graful total T (Kn;m), atunci

j V (G ) j = n + m + nm

j E(G) j = 3nm+ n

m

2

+m

n

2

.

1.2.2. Numerele asociate grafurilor totale (,)

Lem. (Mihai 2010) Dac G este graful total T (Kn;m), atunci gradul minim al complementului su este

(G) = nm 1 + n m:

Teorem. (Mihai 2010)

(T (Kn;m)) =

8>>>:

4; daca n = m = 1

2m+ 1; daca n = 1; m 2

nm+ n+m 1; daca m n 2:


13

Corolar. (Mihai 2010)

(T (Kn;m)) 1

42 + 1; pentru orice m n 2:

1.3. Etichetarea L(2,1) a grafurilor totale ale grafurilor ,,,

n aceast seciune se vor considera grafurile multipartite complete Kn1;n2 ;:::;np

pentru care n1 n2 ::: np.

Se va considera multipartiia V (Kn1;n2 ;:::;np) = V1 [ V2 [ ::: [ Vp , unde mulimile

V1; V2; :::; Vp sunt disjuncte i jVij = ni pentru toi 1 i p. De asemenea, se va nota cu xik

al k -lea vrf din mulimea , unde 1 i p i 1 k ni.

1.3.1. Proprieti ale grafurilor totale ale grafurilor ,,,

Se observ cu uurin c dac notm cu n = jV (Kn1 ;n2;:::;np)j, atunci rezult c

n =X

1ip

ni.

Lem. (Mihai i Marinescu-Ghemeci (a)) Dac xik i xikx

jt sunt vrfuri ale grafului T (Kn1 ;n2;:::;np ), unde 1 i 6= j p;

1 k ni; 1 t nj, atunci

d(xki) = 2(n ni)

d(xkixt

j) = 2n ni nj :

Lem. (Mihai i Marinescu-Ghemeci (a)) Dac G este graful total T (Kn1 ;n2;:::;np ), atunci

jV (T (Kn1;n2;:::;np))j = n +X

1i


14

Lem. (Mihai i Marinescu-Ghemeci (a)) Dac G este graful total T (Kn1 ;n2;:::;np ), atunci

Lem. (Mihai i Marinescu-Ghemeci (a)) Graful total T (Kn1 ;n2;:::;np )

are diametrul

diam(T (Kn1;n2;:::;np)) =

8>>:

(d + 1)2

4+ 1; daca n este impar

d(d+ 2)

4+ 1; daca n este par:

Liu a obinut o margine inferioar a numerelor radio asociate arborilor, respectiv

arborilor care au cel mult un vrf cu gradul mai mare dect 2 . De asemenea, Liu a

caracterizat grafurile care ating aceste limite (Liu 2008). n 2001 Chartrand, Erwin, Zhang i Harary au obinut cteva rezultate care sunt

incluse n urmtoarele patru teoreme.

Teorem. (Chartrand, Erwin, i alii 2001)

rn(Kn) = n:

Graful stea, notat Sn cu n 2, este arborele cu n+ 1 vrfuri K1;n. Numrul radio

al acestui tip de graf este dat de urmtoarea teorem.


rn(Sn) = n+ 2; unde n 2:


rn(Kn1 ;n2;:::;nk) = n1 + n2 + : : :+ nk + k 1:

Capitolul 2 Etichetarea radio a grafurilor

18


(i) Dac G este un graf conex de ordin n care are diametrul 2, atunci n rn(G) 2n 2.

(ii) Pentru orice pereche de numere ntregi k i n, cu n k 2n 2, exist un graf conex G de ordin n care are diametrul

2, astfel nct rn(G) = k: Teorem. (Chartrand, Erwin, i alii 2001)

rn(Wn) =

8>>>:

4; pentru n = 3

7; pentru n = 4

n+ 2; pentru n 5:

Grafurile gear sunt extensii ale grafurilor roat. Graful n-gear Gn este obinut din graful roat Wn, insernd cte un vrf de grad 2 ntre fiecare dou vrfuri ale ciclului. Deci, graful n-gear Gn este un graf obinut din graful roat W2n, pstrnd spiele la pas 2.

Numrul radio al grafului Gn, avnd n 4, este dat de urmtoarea teorem.

Teorem. (Fernandez, i alii) rn(Gn) = 4n+ 2; pentru n 4:

Graful crm Hn este obinut din graful roat Wn, atand un vrf de grad 1 fiecrui vrf de pe ciclul roii.

Teorem. (Tomescu i Rahim)

rn(Hn) =

8>>>:

13; pentru n = 3

21; pentru n = 4

4n+ 2; pentru n 5:

2.2. Numrul radio al subdiviziunilor 2-uniforme ale lui Wn

n aceast seciune vom determina numrul radio al subdiviziunilor 2-uniforme ale grafului roat Wn, notate cu Wn;3.

Graful Wn;k este o subdiviziune (k 1) - uniform a grafului Wn i este obinut

din graful roat Wn, insernd k 1

vrfuri ntre fiecare 2 vrfuri ale ciclului.


19

Astfel, graful Wn;k este obinut din graful Wkn, pstrnd spiele la pasul k, pentru

n 2 i k 2. Folosind aceast definiie, rezult c graful roat Wn este Wn;1 i graful

n-gear Gn este Wn;2:

Graful Wn;k are nk + 1

vrfuri (n

vrfuri de grad 3, n(k 1) vrfuri de grad 2 i

un vrf de grad n) i n(k + 1) muchii. Pentru graful Wn;k se obine

diam(Wn;k) = 2

k

2

+ 2, pentru n 3 i k 3:

Teorem. (Mihai, Marinescu-Ghemeci i Tomescu (a))

rn(Wn;3) 5n+ 2; pentru n 3:

Teorem. (Mihai, Marinescu-Ghemeci i Tomescu (a))

rn(Wn;3) = 5n+ 2; pentru n 4:

Teorem. (Mihai, Marinescu-Ghemeci i Tomescu (a)) rn(W3;3) = 20.

2.3. Numrul radio al subdiviziunilor uniforme ale lui Wn

n aceast seciune vom determina numrul radio al tuturor subdiviziunilor (k 1) - uniforme ale grafului Wn, notate Wn;k.

Teorem. (Mihai i Marinescu-Ghemeci (b)) Dac n i k sunt dou numere ntregi astfel nct k 3 i n k + 1, atunci are

loc urmtoarea inegalitate:

rn(Wn;k) 2n

k

2

2+nk+2:

Teorem. (Mihai i Marinescu-Ghemeci (b)) Fie n i k dou numere ntregi astfel nct k 3 i n k + 1. Atunci se obine

rn(Wn;k) = 2n

k

2

2+ nk + 2:


20

Teorem. (Mihai i Marinescu-Ghemeci (b)) Fie n i k dou numere ntregi astfel nct n; k 3 i n k. Pentru k impar exist inegalitatea

rn(Wn;k) 2n

k

2

2+ nk + 2 + 2(

k n

2n

+ 1)(k n(

k n

2n

+ 1)) +

+ k + 1 n:

Pentru k par avem

rn(Wn;k) 2n

k

2

2+ nk + 2 + 2(

k + 1 n

2n

+ 1)

(k + 1 n(

k + 1 n

2n

+ 1)):

2.4. Numrul radio al unor grafuri nrudite cu graful Wn

n aceast seciune vom determina valorile exacte ale numerelor radio asociate unor tipuri de grafuri nrudite cu graful roat Wn. Iniial este tratat cazul grafului mCn +K1, iar

apoi cazul grafului floarea soarelui SFn.

2.4.1. Numrul radio al grafului mCn + K1

Graful mCn +K1, cu m; n 2, const din m cicluri de lungime n i un vrf

central care este conectat cu toate vrfurile ciclurilor. De remarcat este faptul c pentru

m = 1 se obine graful Cn +K1, care este graful roat Wn. Pentru m = 2 se obine graful

2Cn + K1, care este denumit roat dubl.

Graful mCn +K1 are mn + 1 vrfuri (mn vrfuri de grad 3 i un vrf de grad mn) i 2mn muchii.

De asemenea, se obine c

diam(mCn +K1) = 2; pentru m;n 2:

Pentru a determina numerele radio asociate acestui tip de graf este utilizat rezultatul

de mai jos. De remarcat este faptul c n cazul numerelor radio a fost utilizat o etichetare ce presupune c eticheta minim are valoarea 1 (n loc de 0).


21

Teorem. (Mihai i Marinescu-Ghemeci (c)) Numrul radio al grafului mCn +K1, cu n;m 2, este

rn(mCn +K1) = mn+ 2:

2.4.2. Numrul radio al grafului floarea soarelui

Graful floarea soarelui este un graf nrudit cu graful roat. Graful n-floarea soarelui,

notat SFn, este obinut din graful roat Wn, unind fiecare pereche de vrfuri adiacente ale

ciclului printr-un lan de lungime 2. De aceea, se consider graful roat Wn cu vrful

central x i x1; x2; : : : ; xn vrfurile cilului Cn. Graful SFn se obine din Wn, adugnd n

vrfuri noi y1; y2; : : : ; yn i unind prin muchii vrful yi de vrfurile xi, respectiv xi+1,

pentru fiecare 1 i n, indicii fiind considerai modulo n plus 1. Un exemplu de astfel

de graf este dat n Figura 2.4.3.

Graful SFn are 2n + 1 vrfuri:

n vrfuri de grad 5;

n vrfuri de grad 2;

un vrf de grad n.

De asemenea, se observ cu uurin c SFn are 4n muchii.

Teorem. (Mihai i Marinescu-Ghemeci (c)) Fie n

un numr ntreg astfel nct n 6. Atunci

rn(SFn) 4n+2:

Teorem. (Mihai i Marinescu-Ghemeci (c)) Dac n 6, atunci numrul radio al grafului SFn este

Teorem. (Mihai i Marinescu-Ghemeci (c)) rn(SF3) = 8:

Remarc. (Mihai i Marinescu-Ghemeci (c)) rn(SF4) = 15:

rn(SF5) = 16:

CAPITOLUL III

ALGORITMI EFICIENI PENTRU PROCESAREA OPERATORILOR RELAIONALI N BAZE DE DATE

Deoarece comenzile SQL sunt cele mai des utilizate pentru a accesa baza de date, crearea de interogri eficiente poate determina o cretere substanial a performanei sistemului. Modul n care sunt scrise comenzile SQL are cel mai mare impact asupra performanei bazei de date. De multe ori, o mic schimbare ntr-o interogare SQL poate spori sau ncetini considerabil execuia acesteia. Un script SQL este bun dac utilizeaz toate caracteristicile disponibile ale bazei de date pentru a realiza sarcina ct mai rapid i cu ct mai puine resurse ale sistemului.

O bun performan a sistemului reprezint echilibrul dintre efectivitatea i eficiena

codului aplicaiei versus resursele de sistem disponibile. Utiliznd fire de execuie i procesoare multiple, o aplicaie cu o singur baz de date poate folosi toate resursele din ntreg sistemul.

nainte de a ncepe optimizarea comenzilor SQL, trebuie s se decid ce comenzi se vor optimiza. n general, se optimizeaz comenzile a cror execuie dureaz foarte mult sau comenzile care sunt executate destul de rapid, dar sunt repetate de multe ori. Optimizarea acestor tipuri de comenzi va determina o mbuntire a utilizrii resurselor sistemului.

Unul dintre cei mai costisitori operatori relaionali din bazele de date l reprezint

operatorul join. Pentru a optimiza eficient o comand SQL care utilizeaz operatori join trebuie s se in cont de ordinea de execuie a join-urilor, astfel nct la fiecare pas s fie obinute ct mai puine nregistrri ce vor fi utilizate n urmtoarea operaie de join. De asemenea, alegerea metodei de procesare a join-ului astfel nct aceasta s fie adecvat numrului de tupluri care ntr n join i rezultatului dorit, reprezint un pas important al etapei de optimizare.

Capitolul 3 Algoritmi eficieni pentru procesarea operatorilor relaionali n baze de date

23

Pn acum civa ani, cele mai multe sisteme de baze de date relaionale utilizau

pentru implementarea operatorului join diverse forme ale algoritmilor Nested Loops i Sort Merge. Algoritmul Nested Loops reprezint o alegere bun dac cel puin una dintre relaiile

participante la join are dimensiune redus, iar algoritmul Sort Merge este util pentru procesarea join-ului care implic relaii de dimensiuni mari (Graefe 1999). ncepnd din anul 1984, n mediile de cercetare a crescut interesul asupra algoritmului Hash Join, fiind

create mai multe variante ale acestuia. n prezent, algoritmul Hash Join este utilizat frecvent pentru a procesa eficient operaiile de join (Chen, i alii 2003).

Operatorul outer join este important pentru cuplarea informaiilor care sunt stocate n dou sau mai multe relaii ce au un atribut comun. Pentru dou relaii care ntr n join, se ntmpl frecvent ca tuplurile din prima relaie s nu aib un tuplu corespondent n cea de-a

doua relaie. Utiliznd diverse forme ale operatorului outer join (left, right, full), un tuplu al unei relaii poate aprea n rezultat chiar dac nu satisface condiia de join. n aceast seciune sunt create extensii specifice operatorului outer join ale celor mai cunoscui algoritmi de procesare a join-urilor (Nested Loops, Sort Merge i Hash Join). Partea experimental care urmeaz ncearc s determine care dintre aceti algoritmi este cel mai

eficient pentru a procesa o operaie outer join n anumite condiii iniiale. Operatorul outer join combin tupluri din dou sau mai multe relaii care au un

atribut n comun. n mod formal, dac R i S sunt dou relaii ce au n comun atributul A, atunci:

operatorul left outer join (R R.A = S.A S) reprezint un join n care sunt incluse i tuplurile din relaia R pentru care nu exist un tuplu corespondent n relaia S (tuplul care lipsete din relaia S este completat cu valori null);

operatorul right outer join (R R.A=S.A S) reprezint un join n care sunt incluse i tuplurile din relaia S pentru care nu exist un tuplu corespondent n relaia R (tuplul care lipsete din relaia R este completat cu valori null);

operatorul full outer join (R R.A=S.A S) reprezint un join n care sunt incluse att tuplurile din relaia R pentru care nu exist un tuplu corespondent n relaia S, ct i

tuplurile din relaia S pentru care nu exist un tuplu corespondent n relaia R

(tuplurile care lipsesc dintr-una dintre relaii sunt completate cu valori null).


24

n primele trei seciuni ale capitolului se prezint implementarea n pseudo-cod a algoritmilor creai pentru a procesa operaia de outer join (Mihai 2004). Datele de intrare sunt reprezentate de dou relaii, R i S, care au n comun atributul A. Datele de ieire reprezint rezultatul operaiei de outer join a celor dou relaii, dup atributul A. Pentru partea experimental a fost creat o baz de date relaional Oracle9i cu dou tabele, R (X NUMBER(20), Y VARCHAR2(25)), A NUMBER(10)) i S (A NUMBER(10), Z VARCHAR2(15)) (Mihai 2004). Tabelele nu sunt sortate i nici nu au indeci declarai pe atributul de join A. Algoritmii creai au fost implementai n Visual C++ 6.0 i au fost compilai cu utilitarul Oracle9i Pro C/C++. Afiarea rezultatului a cuprins toate coloanele celor dou tabele. Timpul de rspuns a fost msurat n secunde. Algoritmii au fost testai pe un computer AMD Athlon(tm) XP 2600+, 1.92 GHz, 512 RAM, cu sistem de operare Microsoft Windows XP Professional Version 2002, Service Pack 2.

n figurile din aceast seciune sunt utilizate urmtoarele notaii: NL pentru algoritmul Nested Loops, SM pentru algoritmul Sort Merge, HJ pentru algoritmul Hash Join i HJW pentru algoritmul Hash Join care utilizeaz date deja meninute n partiii hash. De asemenea, s-a utilizat notaia SP pentru utilitarul SQL*PLUS Oracle9i. Notaia NrT X reprezint numrul de tupluri al relaiei X. Un exemplu pentru operatorul left outer join s-a realizat un experiment n care testele au fost realizate n ipoteza n care tabelele au aceeai dimensiune iniial, iar la fiecare pas de testare dimensiunea acestora crete cu acelai numr de tupluri. Figura urmtoare cuprinde rezultatele obinute n aceste ipoteze.

NrT 700 1200 2200 7200 10000 20000 50000 100000 500000 1000000

NL 21 61 205 2202 4326 16925 106e3 424e3 1031e5 4246e5 SM 0 0 1 3 6 13 33 59 143 420 HJ 2 3 5 14 17 38 90 126 555 1004

HJW 0 0 0 1 1 2 17 23 167 501 SP 0 0 1 3 5 9 22 46 125 380


25

Pentru a se putea analiza eficiena celor trei algoritmi prezentai anterior, s-au

realizat aceleai teste, n aceleai condiii i pentru utilitarul Oracle9i SQL*PLUS. Aa cum rezult din experimente, cu acest utilitar doar ntr-un singur caz s-a obinut un timp mai bun

fa de ceilali algoritmi propui (Mihai 2004). Se poate observa c pentru tabele de dimensiuni reduse, oricare dintre algoritmii luai

n considerare constituie o alegere bun, n acest caz timpul de rspuns fiind de cteva

secunde. O situaie aparte luat n considerare este cea a algoritmului Hash Join. Algoritmul

Hash Join W reprezint o implementare a algoritmului Hash Join care utilizeaz partiii deja create i populate cu date anterior procesrii operatorului outer join. De exemplu, un tabel poate fi partiionat n partiii corespunztoare cheii hash, definit n algoritmul Hash Join. n acest caz, un tuplu nou va fi inserat direct n partiia corespunztoare cheii hash. Testele

demonstreaz c n anumite ipoteze pentru algoritmul Hash Join W se obine cel mai bun

timp de rspuns, fiind urmat de algoritmul Sort Merge. De asemenea, pentru tabelele de

dimensiuni mari testele indic faptul c algoritmul Nested Loops reprezint cea mai

costisitoare alegere.

CAPITOLUL IV

GRAFURI N BAZE DE DATE

Grafurile furnizeaz o structur natural de reprezentare a modelului de date n cazul

multor aplicaii. Vrfurile grafului reprezint obiectele modelului, iar muchiile acestuia

relaiile dintre obiecte. Cteva exemple de actualitate care se bucur de un real interes sunt

reelele de calculatoare, infrastructurile de transport, reelele de telefonie, reelele de

socializare, reelele moleculare, WWW etc.

Cele mai cunoscute forme de reprezentare ale unui graf n memorie sunt matricea de

adiacen i lista de adiacen. n cazul primei metode un graf de ordin este memorat prin utilizarea unei matrice booleene ptratice de ordin , n care liniile i coloanele reprezint

vrfurile, iar valorile matricei indic dac exist sau nu muchie ntre vrfurile respective.

Dezavantajul memorrii unui graf prin matricea de adiacen este dat de faptul c multe dintre elementele acesteia sunt nule, deci utilizarea memoriei este nejustificat.

n cazul reprezentrii grafului prin liste de adiacen, pentru fiecare vrf al grafului se menine lista vecinilor si. Aceast metod are avantajul c utilizeaz mai puin spaiu de alocare n memorie.

Dac graful este stocat ntr-o baz de date reprezentarea acestuia folosind matricea

de adiacen nu reprezint o soluie viabil din dou motive:

numrul de coloane ale unui tabel este limitat (de exemplu, numrul absolut de coloane pentru un tabel Oracle este limitat la 1000, dar acest numr poate fi mrit

dac se utilizeaz coloane de tip tablou imbricat sau vector); pentru a putea aduga sau elimina un vrf din graf este necesar utilizarea unei

comenzi LDD.

De asemenea, reprezentarea grafului prin liste de adiacen implic operaii

costisitoare asupra bazei de date (tabele cu coloane de tip colecii, XML etc.).

Capitolul 4 Grafuri n baze de date

27

Vectorul de muchii reprezint o alt alternativ de reprezentare a unui graf, aceast

metod fiind util atunci cnd graful este meninut ntr-o baz de date relaional. n acest caz, o metod corect de stocare a grafului, respectnd regulile de proiectare conceptual a

modelului, presupune existen a dou tabele. Tabelul varfuri menine vrfurile grafului i informaii asociate acestora, iar tabelul muchii codurile vrfurilor ntre care exist muchie n

graf, respectiv informaii utile despre muchii. De exemplu, dac modelul reprezint

infrastructura rutier a unei zone geografice, atunci ne va interesa ntre ce orae exist drum

rutier, care este distana ce trebuie parcurs pentru a putea ajunge dintr-un ora n altul, care sunt rutele alternative i dintre acestea care este cel mai scurt drum. Un alt exemplu poate fi

reprezentarea unei reelele de socializare (de exemplu, Facebook, Twitter). n acest caz vrfurile reprezint persoane, iar muchiile relaii ntre persoane. Pentru fiecare persoan ne

intereseaz anumite caracteristici (vrst, liceu, facultate, hobby etc.).

Dac graful este orientat, atunci nu este necesar implementarea unor constrngeri

suplimentare. n cazul grafurilor neorientate de dimensiuni mari, datorit volumului mare de informaii ce trebuie stocate n baza de date este de preferat s nu se menin ambele arce

ntre aceleai dou vrfuri. Adic, dac vrfurile x i y sunt adiacente, atunci n tabelul

muchii poate fi inserat doar una dintre perechile (x; y) sau (y; x). Este evident c trebuie s

ne asigurm c n tabel nu poate fi introdus aceeai muchie de mai multe ori. Pentru

implementarea acestei constrngeri am abordat mai multe metode alternative, iar cea optim

a fost pstrat pentru testele finale.

Pentru a putea contura o imagine de ansamblu asupra facilitilor aduse de metoda

stocrii grafului ntr-o baz de date, am implementat o serie de proceduri i funcii specifice

operaiilor de baz asupra arborilor, ct i asupra grafurilor. Trebuie specificat faptul c

pentru fiecare operaie am utilizat iniial algoritmii clasici de programare. Am observat c n

aceste condiii varianta de stocare a grafului ntr-o baz de date este util doar dac timpul de

execuie nu reprezint un factor predominant. n a doua etap de dezvoltare, am obinut rezultatele dorite folosind facilitile aduse de tehnologia specific bazelor de date. n plus, a fost studiat comportamentul aplicaiilor create n funcie de diferite versiuni ale Oracle

Database Server (Oracle 9i, Oracle 10g, Oracle 11g).


28

Modulele utilizate de aplicaia final au fost implementate folosind dou tehnologii:

baze de date relaionale (Oracle Database Server 11g); programare orientat obiect (C# Framework 2.0).

Grafurile pe care s-au testat aplicaiile au fost generate aleator folosind MathLab

R2010a. Numrul de muchii ale grafurilor generate reprezint 80% - 85% din numrul total

de muchii posibile (cazul grafului complet). n continuare sunt tratate cteva probleme cu aplicaii practice imediate. Aplicaia C#

utilizeaz algoritmi clasici de rezolvare a acestora. Autorul propune o abordare din

perspectiva bazelor de date, folosind n acest sens facilitile furnizate de sistemele de

gestiune a bazelor de date.

4.1. Distane n grafuri

Distana ntre vrfurile x i y ale unui graf neorientat i conex G reprezint

lungimea minim a lanurilor dintre x i y n

G.

Din punct de vedere arhitectural aplicaia cuprinde urmtoarele module:

resetare graf;

ncrcare graf;

determinare distan dintre oricare dou vrfuri din graf;

ncrcare informaii ntr-o structur de stocare.

Pentru a determina distanele dintre oricare dou vrfuri ale unui graf a fost utilizat metoda parcurgerii n lime. n cazul arborilor problema se poate rezolva utiliznd standardul SQL:1999 care permite cereri recursive (Melton i Simon 2002). Marii productori de sisteme de gestiune a bazelor de date au preluat aceast facilitate i au propus diferite forme de implementare a acesteia. De exemplu, Oracle ofer o form de recursivitate cunoscut sub denumirea de cereri ierarhice. O comand SELECT care utilizeaz clauzele START WITH i CONNECT BY permite parcurgerea n lime a unui

arbore a crui rdcin este specificat. n cazul grafurilor care conin cicluri (deci nu sunt arbori) aceast comand eueaz.


29

O metod de rezolvare a acestei probleme este utilizarea clauzei WITH. Aceasta a fost introdus de standardul SQL:1999 i implementat prima dat n Oracle 9i Release 1. Versiunile ulterioare (Oracle 10g, Oracle 11g) aduc faciliti noi privind lucrul cu date ierarhice: posibilitatea de detectare a existenei ciclurilor i de marcare a acestora, utilizarea

opiunilor de parcurgere n adncime, respectiv n lime etc. n aceast seciune este tratat cazul grafurilor neorientate de dimensiuni mari. Pentru

determinarea distanelor au fost alese trei strategii (algoritm clasic, algoritm propus de autor, cereri recursive). Cele trei strategii au fost implementate i testate.

Deoarece strategia propus de autor a obinut cel mai bun timp de execuie, aceasta a

fost utilizat n testele finale.

Pentru calculul distanelor grafurilor meninute n baza de date a fost aleas Strategia

2, adic implementarea algoritmului propus de autor. Implementarea algoritmului clasic a fost realizat n C#. Timpul de execuie al

acestei aplicaii a fost comparat cu cel obinut folosind librriile Open-Source QuickGraph. n urma testelor realizate pentru tipurile de grafuri luate n considerare a rezultat c aplicaia implementat de autor a obinut timpi de execuie mai buni. De aceea, n continuare aceast aplicaie a fost comparat cu Strategia 2.

Rezultatele testelor realizate sunt ilustrate n Figura 4.1.3.

Metoda/Graf G1 G2 G3 G4 G5

Baze de Date 00:00:00.031 00:00:00.593 00:00:08.096 00:01:19.576 00:12:12.515

C# 00:00:00.013 00:00:01.407 00:00:52.766 00:14:18.411 03:46:09.195

Nr. distane 45 4.950 31.125 124.750 499.500

Aa cum rezult din graficul anterior, meninerea grafurilor testate ntr-o baz de date

este o soluie cu mult mai bun dect metoda clasic. De exemplu, n cazul grafului G5 care

are 1000 de vrfuri i 424732 de muchii algoritmul propus de autor i rulat pe versiunea

Oracle 11g a procesat i a nregistrat toate distanele n mai puin de dou minute, n timp ce

aplicaia implementat de autor n C# Framework 2.0 a obinut acelai rezultat n

aproximativ patru ore.


30

4.2. Lanuri optime n grafuri

n aceast seciune se consider c fiecare muchie a grafului are o pondere pozitiv. Pentru dou vrfuri x i y ale unui graf neorientat i conex G dorim s obinem lanurile

care au ca extremiti cele dou vrfuri i costul cel mai mic (suma ponderilor muchiilor lanului este minim).

Din punct de vedere arhitectural aplicaia cuprinde urmtoarele module:

resetare graf;

ncrcare graf;

determinare lanuri optime dintre oricare dou vrfuri din graf;

ncrcare informaii ntr-o structur de stocare.

Pentru a determina lanurile optime dintre oricare dou vrfuri ale unui graf a fost

folosit o variant modificat a algoritmului propus de autor n seciunea anterioar.

Pentru determinarea lanurilor optime alternative ntre oricare dou vrfuri ale unui graf stocat ntr-o baz de date a fost utilizat implementarea algoritmului propus de autor. Aplicaia realizat n C# reprezint implementarea algoritmul Dijkstra.

Tabelul urmtor ilustreaz performanele celor dou implementri.

Metoda/Graf G1 G2 G3 G4 G5

Baze de Date Lanuri optime

Lanuri create

00:00:00.016 00:00:02.138 00:00:32.861 00:05:40.044 01:23:12.430

49 8.972 80.954 557.993 4.193.729

270 380.290 5.652.007 46.929.703 367.934.564

C# 00:00:00.004 00:00:03.118 00:01:45.295 00:28:04.272 08:55:27.120

De remarcat este faptul c algoritmul propus de autor obine toate lanurile optime alternative dintre dou vrfuri. De exemplu, pentru graful G5 algoritmul determin 367.934.564 lanuri posibile i dintre acestea alege 4.193.729 lanuri optime. Astfel, pentru oricare dou vrfuri date se pot obine toate lanurile optime alternative dintre acestea.


31

4.3. Centrul grafului

S presupunem c trebuie implementat un sistem care s permit gestiunea

informaiilor distribuite necesare unei anumite aplicaii i c soluia aleas este utilizarea

unei baze de date distribuite. Aceasta presupune existena mai multor server-e de baze de

date interconectate printr-o reea de comunicaii. Un model realizabil n practic este cel al

unei baze de date distribuite replicate parial. Aceasta presupune c doar pentru anumite

pri ale bazei de date sunt meninute copii pe mai mult de o staie din sistem. Replicile de

date trebuie amplasate astfel nct traficul n reea, determinat de accesarea unei replici s

satisfac o anumit funcie de optimizare. n general replicarea determin probleme de sincronizare a copiilor. Astfel, existena unui numr prea mare de replici n sistem poate

determina performan redus.

O metod const n determinarea centrului grafului care modeleaz topologia reelei

i apoi plasarea replicilor de date n nodurile care fac parte din acest centru.

n continuare presupunem c toate server-ele din sistem au acelai cost de acces. n caz contrar algoritmii pot fi modificai astfel nct s in cont i de ponderile asociate

vrfurilor grafului.

Pentru aceasta trebuie introduse cteva noiuni specifice teoriei grafurilor.

Definiie. Excentricitatea unui vrf x al unui graf conex G se noteaz cu e(x) i reprezint

cea mai mare distan dintre vrful x i oricare alt vrf y al grafului.

e(x) = maxfd(x; y) : y 2 V (G)g

Definiie. Raza unui graf conex se noteaz cu (G) i reprezint minimul

excentricitilor vrfurilor sale.

(G) = minfe(x) : x 2 V (G)g

Definiie. Centrul unui graf conex G este format din acele vrfuri care au excentricitatea

egal cu raza grafului (au excentricitate minim). C(G) = fx 2 V (G) : e(x) = (G)g

Dac funcia de optimizare presupune amplasarea replicilor n reea astfel nct

accesarea unei replici s se fac trecnd printr-un numr minim de server-e intermediare,


32

atunci centrul grafului trebuie determinat relativ la distanele dintre vrfurile grafului. Deci,

n acest caz se poate utiliza algoritmul propus pentru calculul distanelor. Vom denumi

aceast funcie de optimizare f1

Dac funcia de optimizare trebuie s ia n calcul costurile asociate muchiilor grafului (cost trafic de date, vitez, timp, distan etc.), atunci centrul grafului trebuie determinat relativ la costul minim al lanurilor dintre vrfurile grafului. Pentru aceasta se poate utiliza algoritmul propus pentru obinerea lanurilor optime. n continuare ne vom referi la aceast funcie de optimizare folosind notaia f2

Este posibil s ne intereseze ambele funcii de optimizare a costurilor. n acest caz centrul grafului va fi determinat relativ la costul minim al lanurilor dintre vrfuri, dar vor fi

pstrate doar acele lanuri cu numr minim de muchii. n acest scop se poate utiliza o variant modificat a algoritmului propus pentru obinerea lanurilor optime. Vom denumi aceast funcie de optimizare .

Algoritmul propus de autor pentru determinarea centrului unui graf de dimensiuni mari utilizeaz una dintre cele trei funcii de optimizare date anterior.

f3

33

CONCLUZII I OBIECTIVE VIITOARE

Lucrarea trateaz problema gestiunii informaiei distribuite din dou perspective, cea

a grafurilor (topologia reelei de interconectare), respectiv cea a bazelor de date (stocarea informaiilor necesare n fiecare nod al reelei).

Prima parte a lucrrii cuprinde dou tipuri de probleme de etichetare a vrfurilor unui

graf, n condiiile unor restricii impuse ce sunt relative la distanele dintre acestea. O prim

problem este cea a etichetrii L(2; 1) pentru anumite clase de grafuri i determinarea

numerelor asociate acestora. O direcie viitoare const n determinarea numerelor

asociate grafurilor studiate n cazul etichetrii L(d1 ; d2) i obinerea unor rezultate generale.

Al doilea tip de etichetare studiat n lucrare l reprezint etichetarea radio a anumitor

clase particulare de grafuri. Determinarea numrului radio este o problem dificil n cazul

multor tipuri de grafuri. Pe viitor doresc s extind rezultatele obinute n aceast lucrare,

studiind alte clase de grafuri i ncercnd s obin proprieti generale pentru acestea.

O alt direcie viitoare const n continuarea studiului anumitor tipuri de indici

asociai grafurilor moleculare: indicele Randi (Mihai, Tomescu, Marinescu-Ghemeci 2009), indicele Wiener, indicele Hosoya, indicele Estrada etc.

A doua parte a lucrrii cuprinde dou capitole i este dedicat bazelor de date. Primul

capitol al acestei pri trateaz problema procesrii operatorului de join extern. n viitor doresc s urmez aceast direcie determinnd metode eficiente pentru procesarea altor tipuri

de operatori relaionali n situaia n care implementarea acestora trebuie realizat prin

module software alternative. Ultimul capitol al tezei trateaz problema stocrii grafurilor de dimensiuni mari

ntr-o baz de date. Doresc s extind aceast seciune cu o serie de algoritmi care s rspund

cerinelor aplicaiilor actuale ce utilizeaz grafuri de dimensiuni mari.

34

BIBLIOGRAFIE

Bodlaender H.L., Kloks T., Tan R.B., Leeuwen J.V., -coloring of graphs, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 1770 (395-406), 2000.

Bondy J.A., Murty U.S.R., Graph Theory with Applications, North-Holland, New York, 1976.

Calamoneri T., Petreschi R., L(h,1)-labeling subclasses of planar graphs, J. Parallel Distrib. Comput. 64 (414-426), 2004.

Chang G.J., Kuo D., The L(2, 1) - labeling on graphs, SIAM J. Discrete Math 9 (309-316), 1996.

Chang G.J., Ke W.-T., Kuo D., Liu D.D.-F., Yeh R.K., On L(d,1)-labelings of graphs, Discrete Math. 220 (57-66), 2000.

Chartrand G., Erwin D., Zhang P., A graph labeling problem suggested by FM channel restrictions, Bull. Inst. Combin. Appl. 43 (43-57), 2005.

Chartrand G., Erwin D., Zhang P., Harary F., Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (77-85), 2001.

Chen S., Ailamaki A., Gibbons P.B., Mowry T.C., Improving Hash Join Performance through Prefetching, School of Computer Science, Carnegie Mellon University Pittsburgh, 2003.

Chiang S.-H., On L(d,1)-labeling of Cartesian product of cycle and path, Master thesis, Department of Mathematics, Aletheia University, Tamsui, Taipei, Taiwan, 2004.

Codd E.F., A Relational Model of Data for Large Shared Data Banks, Communications of the ACM 13 (6): 377387, 1970.

Codd E.F., The Relational Model for Database Management (Version 2 ed.), Addison Wesley Publishing Company, 1990.

Bibliografie

35

Connolly T., Begg C., Strachan A., Database systems. A practical Approach to Design, Implementation, and Management (Second Edition), Addison-Wesley, 1998.

Dollinger R., Andron L., Baze de date i gestiunea tranzaciilor (reeditare), Editura Albastr, 2004.

Erwin D.J., Georges J.P., Mauro D.W., On labeling the vertices of products of complete graphs with distance constraints, Naval Res. Logist 52 (138-144), 2005.

Fernandez C., Flores A., Tomova M., Wyels C., The radio number of gear graphs, preprint available at front.math.ucdavis.edu/ 0809.2623, n.d.

Gallian J.A., A dynamic survey of graph labelings, Electronic J. of Combinatorics, 14 #DS6, 2007.

Georges J., Mauro D.W., Generalized vertex labelings with a condition at distance two, Congr. Numer. 109 (141-159), 1995.

Georges J., Mauro D.W., On the criticality of graphs labelled with a condition at distance two, Congr. Numer. 101 (3349), 1994.

Georges J., Mauro D.W., Whittlesey M., Relating path covering to vertex labelings with a condition at distance two, Discrete Math. 135 (103-111), 1994.

Georges J., Mauro D.W., Some results on - numbers of the products of complete graphs, Congr. Numer. 140 (141-160), 1999.

Georges J.P., Mauro D.W., Stein M.I., Labeling products of complete graphs with a condition at distance two, SIAM J. Discrete Math. 14 (28-35), 2000.

Graefe G., The Value of Merge-Join and Hash-Join in SQL Server, Proceedings of the 25th International Conference on Very Large Data Bases (250 - 253). Morgan Kaufmann Publishers Inc. San Francisco, CA, USA, 1999.

Griggs J.R., Yeh, R.K., Labeling graphs with a condition at distance two, SIAM J. Discrete Math. 5 (586-595), 1992.

Hale W. K., Frequency assignment: theory and applications, Proc. IEEE, 68 (1497-1514), 1980.

Bibliografie

36

Harary F., Graph Theory, Addison-Wesley, Reading, MA, 1969.

Jha P.K., Optimal L(2,1)-labeling of Cartesian products of cycle with an application to independent domination, IEEE Trans. Circuits and Systems-I 47 (1531-1534), 2000.

Jha P.K., Optimal L(2,1)-labeling of strong products cycle, IEEE Trans. Circuites and Systems-I 48 (498-500), 2001.

Jha P.K., Narayanan A., Sood P., Sundaram V., Sunder V., On L(2,1)-labeling of Cartesian product of cycle and path, Ars Combin. 55 (81-89), 2000.

Jin X.T., Yeh R.K., Graph distance-dependent labeling related to code assignment in computer networks, Naval Res. Logist. 52 (159164), 2005.

Jonas K., Graph coloring analogues with a condition at distance two: L(2,1)-labeling and list - labelings, Ph.D. Thesis, Department of Mathematics University of South

Carolina, SC, USA, 1993.

Klavzar S., Vesel A., Computing graph invariants on rotagraphs using dynamic algorithm approach the case of (2,1)-colorings and independence numbers, Discrete Appl. Math. 129 (449-460), 2003.

Kral D., Skrekovski R., A theorem about channel assigment problem, SIAM J. Discrete Math. 16 (426-437), 2003.

Kuo D., Yah J.-H., On L(2,1)-labeling of Cartesian products of path and cycles, Discrete Math. 283 (137-144), 2004.

Liu, D., Zhu, X., Multi-level distance labelings for paths and cycles, SIAM J. Discrete Math., 19 (610-621), 2005.

Liu D., Radio number for trees, Discrete Math., 308 (1153-1164), 2008.

Liu D., Xie M., Radio number for square of cycles, Congr. Numer., 169 (105 - 125), 2004.

Liu D., Zhu X., Multi-level distance labelings for paths and cycles, SIAM J. Discrete Math. 19, No. 3 (610-621), 2005.

Liu D., Yeh R.K., On distance-two labelings of graphs, Ars Combin. 47 (13-22), 1997.

Bibliografie

37

Melton J., Simon A. R., SQL:1999 - Understanding Relational Language Components, Academic Press, 2002.

Mihai (Florea) G., Performance analysis of the outer-join algorithms for relational database systems, Analele Universitii din Bucureti, 2005.

Mihai (Florea) G., Popescu I., Alecu A., Velcescu L., Programare avansat n Oracle9i, Editura Tehnic, 2004.

Mihai G., The L(2,1)-labeling on total graphs of complete bipartite graphs, Mathematical Reports 12(62), 4(351-357), 2010.

Mihai G., Marinescu-Ghemeci R., (a), The L(2,1)-labeling on total graphs of complete multipartite graphs, trimis pentru publicare.

Mihai G., Marinescu-Ghemeci R., (b), Radio number of uniform subdivisions of the wheel, trimis pentru publicare.

Mihai G., Marinescu-Ghemeci R., (c), Radio number of some wheel related graphs, Analele Universitii din Bucureti, acceptat pentru publicare.

Mihai G., Marinescu-Ghemeci R., Tomescu I. (a), Radio number of 2-uniform subdivisions of the wheel, Utilitas Mathematica, acceptat pentru publicare.

Mihai G., Tomescu I., Marinescu-Ghemeci R., (b), On dense graphs having minimum Randic index, ROMJIST 4(455-465), 2009.

zsu M.T., Valduriez P., Principles of Distributed Database Systems (2nd Edition), Prentice Hall, 1999.

Popescu I., Baze de date relaionale, Editura Universitii din Bucureti, 1996.

Popescu I., Modelarea bazelor de date, Editura Tehnic, Bucureti, 2001.

Shao Z., Yeh R.K., Zhang D., The L(2,1)-labeling on graphs and the frequency assignment problem, Applied Mathematics Letters 21 (37-41), 2008.

Shao Z.-D., Yeh R.K., The L(2,1)-labeling and operations of graphs, IEEE Trans. Circuits and Systems-I 52 (668-671), 2005.

Simovici D.A., Tenney R.L., Relational Database Systems, Academic Press, England, 1995.

Bibliografie

38

Tomescu I., Rahim M. T., Multi-level distance labelings for helm graphs, Ars Combinatoria, acceptat pentru publicare.

Wallis W.D., Magic graphs, Birkhauser, Boston, 2001.

Wang W.-F., Lih K.-W., Labeling planar graphs with conditions on girth and distance two,

SIAM J. Discrete Math. 17 (264275), 2003.

West D. B., An introduction to graph theory, Prentice-Hall, 1996.

Whittlesey M., Georges J., Mauro D.W., On the - number of and related graphs, SIAM J.Discrete Math. 8 (499-506), 2000.

Willets K., SQL Graph Algorithms, http://willets.org/sqlgraphs.html.

Yeh R.K., Labeling graphs with a condition at distance two, Ph.D. Thesis, Dept. of Math.,

Univ. of South Carolina, Columbia, SC, USA, 1990.

Yeh R.K., The edge span of distance two labelings of graphs, Taiwanese J.Math. 4 (675-683), 2000.

Yu C.T., Meng W., Binghamton S., Principales of Databases, Query Processing for Advanced Applications, Morgan Kaufmann Publishers, California, 1998.

Zhang P., Radio labelings of cycles, Ars Combin., 65 (21-32), 2002.

PRIMA PAGINA teza mea de doctorat - rezumat 1

rezumat teza de doctorat

Documents