Anali PAZU - Letnik 2, leto 2012, številka 1 2 Merjenje podobnosti (označenih) podatkovnih tabel Measuring similarity of (annotated) data tables Melita Hajdinjak Univerza v Ljubljani, Fakulteta za elektrotehniko / Tržaška cesta 25, 1000 Ljubljana E-Mail: melita.hajdinjak@fe.uni-lj.si * Avtor za korespondenco; Tel.: +386-1-4768-385; Fax: + 386-1-4768-316 Povzetek: V članku predlagamo mero podobnosti klasičnih relacij oziroma podatkovnih tabel. Dobimo jo kot posplošitev Egli-Milnerjeve urejenosti in Hausdorffove metrike. Ta mera omogoča, da primerjamo različne podatkovne tabele. Mero podobnosti klasičnih relacij poskušamo razširiti na D-relacije, imenovane tudi relacije s podobnostmi, ki posplošujejo veliko skupino označenih relacij. V splošni obliki takšne mere zdaj nastopa še funkcija, ki meri podobnost označb. Izpostavimo lastnosti, ki naj jim ta funkcija zadošča, in poiščemo ustrezno obliko funkcije v primeru nekaterih posebnih označevalnih domen. Ključne besede: relacijska algebra; mera podobnosti; označene relacije; De Morganov okvir; Egli-Milnerjeva urejenost; Hausdorffova razdalja Abstract: We propose a measure of similarity for classical relations or data tables. It is obtained as a generalization of the Egli-Milner ordering and the Hausdorff metric. This measure allows us to compare different data tables. We attempt to extend the measure from classical relations to D-relations, also called relations with similarities, which generalize a large group of annotated relations. The general form of such a measure now contains a function for comparing annotations. We expose some properties of the annotation- comparing function and find suitable candidates in the case of some special annotation domains. Keywords: relational algebra; similarity measure; annotated relation; De Morgan frame; Egli-Milner ordering; Hausdorff distance 1. Uvod Vračanje informacij, ki niso natančni odgovori na zastavljeno vprašanje, so pa relevantni oziroma blizu tistemu, kar je bilo vprašano, je splošna lastnost človeške komunikacije, znana kot sodelujoče odgovarjanje [1]. Ker poizvedovanja po netočnih, približnih informacijah klasična relacijska algebra ni sposobna modelirati, so bile predlagane številne posplošitve in razširitve tega najbolj priljubljenega podatkovnega modela. Članek temelji na označenih relacijah, imenovanih D-relacije, ki jih dobimo tako, da domene atributov razširimo z merami podobnosti [2]. 1.1. Klasične relacije Naj bodo i τ množice, relacijska shema   11 :: nn U= a τ , , a τ  pa preslikava, ki atributu i a priredi domeno i τ , torej ii U(a )= τ za 1, i= ,n  . Naj bo U-terica   11 :: nn t= a v , ,a v  preslikava, ki atributu i a priredi element ii v τ  , torej ii t(a )=v za 1, i= ,n  . Množico vseh U-teric imenujmo Tup U  . Označena relacija nad U imenujemo preslikavo oblike : Tup AU K  , ki vsaki U-terici priredi nek element izbrane domene K. Pišemo   A Rel U  . Klasična relacija, ki jo običajno pojmujemo kot množico U-teric in jo predstavimo s tabelo, je poseben primer označene relacije. Dobimo jo, če Anali PAZU - Letnik 2, leto 2012, številka 1 3 izberemo 0,1 K={ } in definiramo 1 A(t)= , če tA  , ter 0 A(t)= sicer. 1.2. D-relacije Naj bodo   01 i i i i i i i L = L , , , , ,¬  De Morganovi okvirji, tj. polne mreže z negacijo : i i i ¬ L L  , v katerih so končni infimumi distributivni glede na supremume. Naj bo De Morganova shema   11 :: nn D= a L , ,a L  preslikava, ki atributu i a priredi De Morganov okvir i L , torej ii D(a )=L za 1, i= ,n  . Naj bo   DU -terica   11 :: nn s= a l , ,a l  preslikava, ki atributu i a priredi element ii lL  . Množico vseh   DU -teric imenujmo   Tup DU  . Predpostavimo, da je na vsaki množici i τ definirana refleksivna mera podobnosti : i i i ρ i τ τ L  ,       1 i i i ρ i t a , t a = , kjer je 1 i največji element De Morganovega okvirja i L . Primeri takšnih refleksivnih mer podobnosti so:  enakost : 0,1 i i i = τ τ { }  , ki vrne 1 i , če sta elementa enaka, in 0 i , če sta različna,  mehka enakost : 0,1 i i i τ τ [ ]    , ki vrne mehko stopnjo enakosti obeh elementov,  metrika : 0, i i i max d τ τ [ d ]  , ki vrne razdaljo obeh elementov v metričnem prostoru. Označeno relacijo   : Tup Tup AU D U    , ki U-terico t preslika v   DU -terico     11 :: nn A t = a l , ,a l  , dobljeno s pomočjo mer podobnosti i ρ , imenujemo relacija s podobnostmi ali D- relacija. Pišemo     A Rel D U  . Hajdinjak in Bierman [2] sta pokazala, da lahko na tako označenih relacijah definiramo vse operacije klasične relacijske algebre (unijo, projekcijo, izbiro, spoj, razliko). Na začetku poizvedovanja sta U-terico, ki ni v podatkovni tabeli, označila z najmanjšim elementom,   11 0 :0 :0 nn = a , ,a  , U-terico, ki je v podatkovni tabeli, pa z največjim elementom,   11 1 :1 :1 nn = a , ,a  . Relacijsko algebro na D-relacijah sta poimenovala relacijska algebra s podobnostmi. Taka algebra pravilno modelira glavne primere označenih relacij, kot so klasične relacije, c-tabele, tabele dogodkov in mehke relacije [3]. 2. Podobnost relacij Problem, ki ga obravnava članek, izvira s področja sodelujočega odgovarjanja. Odgovore na isto poizvedbo, ki so lahko samo približni, bi radi primerjali med sabo in tudi določili njihovo relevantnost. 2.1. Podobnost klasičnih relacij Naj bo na vsaki množici i τ iz   11 :: nn U= a τ , , a τ  definirana mera podobnosti : i i i i ρ τ τ L  . Iščemo funkcijo       : Tup U ρ R e l U R e l U D U    , ki bo paru klasičnih relacij ali podatkovnih tabel   A,B Rel U  priredila njuno podobnost. Ker ima shema U v splošnem več različnih atributov, lahko delamo več različnih primerjav, zato smo predpostavili, da bo kodomena iskane mere U ρ množica   Tup DU  . Primerjavo vrednosti atributov U-teric v relacijah A in B omogočajo mere i ρ .  Če je i ρ enakost, ki slika v 0,1 i L ={ } , lahko za mero podobnosti relacij oziroma podatkovnih tabel (glede na atribut i a ) izberemo funkcijo, ki slika enaki množici v 1 in različni v 0.  Če je i ρ refleksivna relacija, ki slika v 0,1 i L ={ } , lahko za mero podobnosti relacij (glede na atribut i a ) izberemo Egli-Milnerjevo urejenost, v kateri sta dve množici v relaciji, če je vsak element prve množice v relaciji z nekim elementom druge množice in za vsak element druge množice obstaja nek element v prvi množici, ki je z njim v relaciji [4,5]. Pomembnost te urejenosti v podatkovnih modelih so prepoznali že Buneman, Jung in Ohori [6].  Če je ρi funkcija razdalje oziroma metrika, ki slika v 0, i max L =[ d ] , lahko za mero podobnosti relacij (glede na atribut i a ) izberemo Hausdorffovo metriko, kjer sta dve množici blizu ena drugi, če je vsak element ene množice blizu nekemu elementu druge množice. Hausdorffova razdalja je najdaljša pot, ki jo moramo prepotovati od izbrane točke v eni množici do druge množice [4,7]. Ta razdalja je zelo široko uporabna (npr. v geometriji fraktalov, numerični matematiki in pri razpoznavanju vzorcev). Anali PAZU - Letnik 2, leto 2012, številka 1 4 Zgoraj omenjene mere podobnosti posplošuje mera, ki sta jo na množicah že predlagala Hajdinjak in Bauer [4]. To mero sedaj prenesemo na klasične relacije. Definicija 1. [Mera podobnosti na klasičnih relacijah] Naj bosta   A,B Rel U  , kjer je   11 :: nn U= a τ , , a τ  . Naj bo : i i i i ρ τ τ L  mera podobnosti na množici i τ oziroma atributu i a , kjer je   01 i i i i i i i L = L , , , , ,¬  De Morganov okvir in   11 :: nn D= a L , ,a L  De Morganova shema. Na klasičnih relacijah nad shemo U definiramo naslednjo mero podobnosti:       : Tup U ρ R e l U R e l U D U    ,                     U i i,t A i,u B i i i i i,u B i,t A i i i ρ A , B a = ρ t a , u a ρ t a , u a          . Tudi neskončni infimumi ( i  ) in supremumi ( i  ) obstajajo, saj je i L De Morganov okvir, ki je polna mreža. Izrek 1. [Lastnosti mere U ρ ] Naj bo   11 :: nn D= a L , ,a L  De Morganova shema z   01 i i i i i i i L = L , , , , ,¬  , naj bo       : Tup U ρ R e l U R e l U D U    mera podobnosti na klasičnih relacijah nad U, naj bosta   A,B Rel U  in B {}  . Potem velja:   11 :1 :1 U n n ρ A , A = { a , , a } =  1 ,     11 :0 :0 U U n n ρ { } , B = ρ B , { } = { a , , a } =  0 . Vidimo, da ima mera podobnosti U ρ nekatere pomembne lastnosti. Vsaka relacija je najbolj podobna (1) sama sebi, kar velja tudi za prazno relacijo, in prazna relacija je popolnoma različna (0) od vsake neprazne relacije. Ti dve lastnosti sta še posebej pomembni, ko med poizvedovanjem pričakujemo vsaj sodelujoče odgovore, ki so lahko le približek dejansko iskanih informacij. Opazimo tudi, da iz   U ρ A , B =1 ne sledi nujno A=B . Hitro lahko preverimo, da če so mere podobnosti : i i i i ρ τ τ L  simetrične, tj. velja     ii ρ x , y = ρ y , x , je simetrična tudi mera U ρ , tj. tedaj velja     UU ρ A , B = ρ B , A . 2.2. Podobnost D-relacij Ko imamo relacije oziroma podatkovne tabele, ki niso označene le z 0 ali 1, na njihovo podobnost zagotovo vplivajo tudi označbe. Zdaj bomo torej morali primerjati vrednosti atributov in še označbe vrstic v tabelah. Iskana mera podobnosti, imenujmo jo D,U ρ , bo razširitev mere U ρ s funkcijami primerjave označb, : i i i i w L L L . Definicija 2. [Mera podobnosti na D-relacijah] Naj bosta     A,B Rel D U  , kjer je   11 :: nn U= a τ , , a τ  relacijska shema in   11 :: nn D= a L , ,a L  De Morganova shema z   01 i i i i i i i L = L , , , , ,¬  . Naj bo : i i i i ρ τ τ L  mera podobnosti na množici i τ oziroma atributu i a . Na D-relacijah definiramo naslednjo mero podobnosti:           : Tup D,U ρ R e l D U R e l D U D U    ,                       Tup Tup D,U i i,t U i,u U i i i i i i i ρ A , B a = ρ t a , u a w A t a , B u a                          Tup Tup i i,u U i,t U i i i i i i i ρ t a , u a w A t a , B u a         , kjer je : i i i i w L L L  neka funkcija primerjave označb, povezana z atributom i a . Do ustrezne oblike funkcije : i i i i w L L L  lahko pridemo preko posplošitev Egli-Milnerjeve urejenosti in Hausdorffove metrike. Upoštevati pa moramo tudi, da so edina matematična orodja, ki jih imamo na razpolago, da definiramo takšno funkcijo, operacije in konstante, ki jih ponujajo De Morganovi okvirji (to so infimum, supremum in negacija ter najmanjši in največji element).  Če je   0,1 0 1 i L = { }, , , , ,¬  Boolov De Morganov okvir, kjer je 01 ¬= in 10 ¬= , lahko definiramo   1 i w x,y = , če x= y , in 0 sicer.  Če je   0, 0, i max max L = [ d ],min,max,d , ¬ De Morganov okvir omejenih razdalj, kjer je max ¬x=d x  , imamo Anali PAZU - Letnik 2, leto 2012, številka 1 5 več povsem smiselnih možnosti, na primer   i w x,y = x y    ali kakšno drugo razdaljo na 0, max [ d ] . Če pa želimo zaradi kasnejše posplošitve v definiciji funkcije i w uporabiti le 0 in max min,max,d , ¬ , mnoge možnosti odpadejo. Zgornji predlog taksi metrike, na primer, uporablja funkciji razlika in absolutna vrednost, ki sta definirani na intervalu realnih števil 0, max [ d ] , v mnogih drugih mrežah pa ne.  Do podobne ugotovitve kot v prejšnjem primeru pridemo tudi v primeru mehkega De Morganovega okvirja   0,1 0 1 i L = [ ],max,min, , ,¬ , kjer je 1 ¬x= x  . Izpostavimo lastnosti, ki jih od funkcije i w pričakujemo:   1 ii w x,x = ,   00 i i i w ,x = ,   1 ii w ,x =x ,     ii w x,y =w y,x . Za mero D,U ρ pa pričakujemo, da ima podobne lastnosti kot mera U ρ , tj. da za     A,B Rel D U  in B {}  velja:   11 :1 :1 D,U n n ρ A , A = { a , , a } =  1 ,     11 :0 :0 D,U D,U n n ρ { } , B = ρ B , { } = { a , , a } =  0 ,     D,U D,U ρ A , B = ρ B , A , če so mere i ρ simetrične. Zavedati se moramo, da nam funkcije, ki zadošča želenim pogojem, v splošnem mogoče ne bo uspelo najti, da mogoče niti ne obstaja. V tem primeru bi lahko pogoje omilili, a pod pogojem, da bi funkcija i w razlike med označbami še vedno ustrezno kvantitativno vrednotila. Na primer, lahko bi dovolili   i i i w x,x =x ¬x  , kar je v splošnem lahko različno od 1 i , in posledično             Tup D,U i,t U i i i i ρ A , A = A t a ¬ A t a   , kar je "blizu" 1, če so   i w x,x "blizu" 1 i . 3. Zaključki Medtem ko mera podobnosti klasičnih relacij oziroma podatkovnih tabel predvsem omogoča, da ocenjujemo podobnost različnih podatkovnih tabel, lahko mero podobnosti D-relacij uporabimo za primerjavo različnih odgovorov na isto poizvedbo, izračun relevantnosti ali zamenljivosti eksaktnega in relaksiranega odgovora, vrednotenje razlik v tabelah iz časovno-odvisne zbirke ali sledenje spremembam v podatkovni tabeli [1,2]. V meri podobnosti D-relacij, D,U ρ , nastopa funkcija primerjave označb, ki je v meri podobnosti klasičnih relacij, U ρ , ni. V članku smo predlagali obliko funkcije primerjave označb le za nekatere specifične primere označevalnih domen D-relacij (to so Boolov De Morganov okvir, De Morganov okvir omejenih razdalj in mehki De Morganov okvir), splošne oblike pa nismo našli. Izpostavili smo lastnosti, ki naj bi za tako funkcijo veljale, ter se omejili na operacije in konstante, ki v funkcijskem predpisu lahko nastopajo. Na vprašanje splošnega funkcijskega predpisa zaenkrat nismo znali odgovoriti. Literatura 1. Minker, J. An Overview of Cooperative Answering in Databases. V zborniku konference International Conference on Flexible Query Answering Systems, Roskilde University, Danska, 1998, 282-285. 2. Hajdinjak, M.; Bierman, G. Extending Relational Algebra with Similarities. Mathematical Structures in Computer Science 2012, 22 (4), 686-718. 3. Green, J.; Tannen, V. Models for Incomplete and Probabilistic Information. IEEE Data Engineering Bulletin 2006, 29, 17-24. 4. Hajdinjak, M.; Bauer, A. Similarity Measures for Relational Databases. Informatica 2009, 33 (2), 135- 141. 5. Abramsky, S.; Jung, A. Domain Theory. Claredon Press: Oxford, Velika Britanija, 1994. 6. Buneman, P.; Jung, P.; Ohori, A. Using Powerdomains to Generalize Relational Databases. Theoretical Computer Science 1991, 9 (1), 23-55. 7. Rockafellar, R. T.; Wets, R. J.-B. Variational Analysis. Springer Verlag: Berlin, Nemčija, 2005. Anali PAZU - Letnik 2, leto 2012, številka 1 6