Automatizovaný návrh pravidel pro integraci dat a sémantický web

Motivace Návrhy mapování, míry Výsledky a shrnutí

Automatizovaný návrh pravidel pro integraci dat a sémantický web Zdeňka Linková, Martin Řimnáč Ústav informatiky AV ČR, v.v.i.

Znalosti 2008 Bratislava 13.-15.02. 2008

Zdeňka Linková, Martin Řimnáč

Automatizovaný návrh pravidel pro integraci dat a sémantický w


1

Motivace Integrace dat pomocí pohledů Automatická integrace dat Formalismus pro datový zdroj

2

Návrhy mapování, míry Globální matice úložiště Mapování Pravidlo ekvivalence Pravidlo hierarchie

3

Výsledky a shrnutí Využití měr Závěr




Integrace dat pomocí pohledů Automatická integrace dat Formalismus pro datový zdroj

Integrace dat

Web jako studnice dat mnoho zdrojů (stále progresivně rostoucí) (částečně) redundantní popis

Integrace dat umožňuje data z lokálních zdrojů prezentovat pomocí jednoho zdroje matrializovaně virtuálně - pomocí pohledů Mediační systémy





Integrace dat pomocí pohledů

Úlohy v procesu integrace dat: schema matching schema mapping: LAV (Local As View) GAV (Global As View) GLAV (Global Local As View)

zpracování dotazů: query rewriting





Automatická integrace dat 1

Manuální návrh integrace dat návrh pravidel - človek na základě své intrepretace schématů práce s mnoha daty možnost omylu, důvěryhodnost třetích stran

2

(Semi)automatický návrh pravidel na základě dat návrh kandidátů jako (ohodnocené) doporučení pro návrháře jako nejlepší možný odhad

ohodnocení kandidátů - kosinové fuzzy míry lexikální analýza strukturální analýza ....





Formalismus - datový zdroj Formalismus binárních matic 1

Matice úložiště Φ = [φij ], φij =

2

1 pokud ei → ej ∈ I 0 jinak

Matice funkčních závislostí 1 Ω = [ωij ], ωij = 0

pokud Ai → Aj ∈ F jinak

Vztah (transformace) Ω = ∆T Φ∆

Φ′ = Φ ⊙ ∆Ω∆T

pomocí matice aktivních domén atributů 1 pokud ei = (Aj , v⋆ ) ∈ E ∆ = [δij ], δij = 0 jinak Zdeňka Linková, Martin Řimnáč




Příklad



    Φ=    

1 0 0 1 0 1 0

0 1 0 0 1 1 0

0 0 1 0 1 0 1

0 0 0 1 0 1 0 

0 0 0 0 1 0 1

0 0 0 0 0 1 0

Město 1 0 0   Stát Ω= 1 1 0 1 1 1 Měna 


0 0 0 0 0 0 1

         

Město, Praha Město, Košice Město, Bratislava Stát, ČR Stát, Slovensko Měna, CZK Měna, SSK ~y = Φ~x



Globální matice úložiště Mapování Pravidlo ekvivalence Pravidlo hierarchie

Virtuální globální matice úložiště Centralizovaně ΦS =

X

ΓSl ΦSl ΓT Sl

∀Sl ∈S ΓS . . mediátor elementů mezi ΦS a ΦS l


l




Virtuální globální matice úložiště Centralizovaně ΦS =

X

ΓSl ΦSl ΓT Sl


l

Decentralizovaně 2

6 6 6 ΦS = 6 6 4

Φ1 Ψ21

Ψ12 Φ2

. . . Ψ|S |1

··· ··· .

···

. . ···

3 Ψ1|S | Ψ2|S | 7 7 7 7 7 5 Φ|S |

Ψij . . mediátor elementů mezi ΦS a ΦS i


j




Virtuální globální matice úložiště Centralizovaně X

ΦS =

ΓSl ΦSl ΓT Sl


l

Decentralizovaně 2

6 6 6 ΦS = 6 6 4

Φ1 Ψ21

Ψ12 Φ2

. . .

··· ··· .

Ψ|S |1

···

. . ···

3 Ψ1|S | Ψ2|S | 7 7 7 7 7 5 Φ|S |

Ψij . . mediátor elementů mezi ΦS a ΦS i

T i

Ψij = ΓS ΓS


j

j




Mapování na úrovni elementů 1

Binární Ψkl =

[ψijkl ]; ψijkl

=

1 pokud ei z Sl odpovídá ej z Sk 0 jinak






Binární Ψkl =

2

[ψijkl ]; ψijkl

=


Vážené  E  µ (ei , ej ) pokud ei z Sl odpovídá ej z Sk kl kl Ψkl = [ψij ]; ψij = s jistotou µE (ei , ej )  0 jinak






Binární Ψkl =

2

[ψijkl ]; ψijkl

=


Vážené  E  µ (ei , ej ) pokud ei z Sl odpovídá ej z Sk kl kl Ψkl = [ψij ]; ψij = s jistotou µE (ei , ej )  0 jinak

3

Triviální návrh mapování 1 pokud ei = (AI , v ) ∧ ej = (AJ , v ) kl kl ′ Ψkl = [ψij ]; ψij = 0 jinak Zdeňka Linková, Martin Řimnáč




Mapování na úrovni atributů 1

Binární Πkl =

[πijkl ]; πijkl

=

1 pokud Ai z Sl odpovídá Aj z Sk 0 jinak






Binární Πkl =

2

[πijkl ]; πijkl

=


Vážené Πkl = [πijkl ]; πijkl

 A  µ (ei , ej ) pokud Ai z Sl odpovídá Aj z Sk = s jistotou µA (ei , ej )  0 jinak






Binární Πkl =

2

[πijkl ]; πijkl

=


Vážené Πkl = [πijkl ]; πijkl

 A  µ (ei , ej ) pokud Ai z Sl odpovídá Aj z Sk = s jistotou µA (ei , ej )  0 jinak

Mapování atributů versus elementů Ψkl = Ψ′kl ⊙ ∆Sl Πkl ∆T Sk Zdeňka Linková, Martin Řimnáč

Πkl = ∆T Sl Ψkl ∆Sk




Cosinové míry - Pravidlo ekvivalence

Předpoklad: podobné atributy budou mít podobné (aktivní) domény

Cosinová míra: πij =

|DαSk (Ai ) ∩ DαSl (Aj )| |DαSk (Ai ) ∪ DαSl (Aj )|





Cosinové míry - Pravidlo ekvivalence

Předpoklad: podobné atributy budou mít podobné (aktivní) domény

Cosinová míra: πij =

|DαSk (Ai ) ∩ DαSl (Aj )| |DαSk (Ai ) ∪ DαSl (Aj )|

Symetrie ekvivalence Πkl = ΠT lk





Výběr kadidátů 1 0 0 1 0 1 0

0 1 0 0 1 1 0

0 0 1 0 1 0 1

0 0 0 1 0 1 0

1 6 0 Φ2 = 6 4 1 0

0 1 0 1

1 0 1 0

3 0 1 7 7 0 5 1

2

6 6 6 6 Φ1 = 6 6 6 4

2

0 0 0 0 1 0 1

0 0 0 0 0 1 0

0 0 0 0 0 0 1

7 7 7 7 7 7 7 5

město, Praha město, Košice město, Bratislava stát, ČR stát, Slovensko měna, CZK měna, SSK

země , země , hlavní hlavní

Česká republika Slovensko město , Praha město , Bratislava

3

Mediátor: 

ˆ 12 =  Π

0 1 3

0

2 3



0  0

preference pravidel s maximální podporou Ai ∼ Aj µA (Ai , Aj ) 2 hlavní město ∼ město 3 1 země ∼ stát 3 Zdeňka Linková, Martin Řimnáč




Cosinové míry - Pravidlo hierarchie Cosinová míra: πij =

|DαSk (Ai ) ∩ DαSl (Aj )|


|DαSk (Ai )|





|DαSk (Ai ) ∩ DαSl (Aj )| |DαSk (Ai )|

není symetrické







není symetrické vyjma kombinací pravidel vedoucích na cykly: A j ⊏ A k ⊏ A i : A i , A i ∈ A l , A k ∈ Ak







není symetrické vyjma kombinací pravidel vedoucích na cykly: A j ⊏ A k ⊏ A i : A i , A i ∈ A l , A k ∈ Ak Pro kombinaci ekvivalence a hierarchie - preference σij∼ = πijkl · πjilk σij⊏ = πijkl · (1 − πjilk ) Zdeňka Linková, Martin Řimnáč




Výběr kadidátů 1 0 0 1 0 1 0

0 1 0 0 1 1 0

0 0 1 0 1 0 1

0 0 0 1 0 1 0

1 6 0 Φ2 = 6 4 1 0

0 1 0 1

1 0 1 0

3 0 1 7 7 0 5 1

2

6 6 6 6 Φ1 = 6 6 6 4 2

0 0 0 0 1 0 1

0 0 0 0 0 1 0

0 0 0 0 0 0 1

7 7 7 7 7 7 7 5

město, Praha město, Košice město, Bratislava stát, ČR stát, Slovensko měna, CZK měna, SSK

země , země , hlavní hlavní

Česká republika Slovensko město , Praha město , Bratislava

3

Hierarchie: 

 Π⊏ 12 = Π⊏ 21

=

0 2 3

1 2

0 2 2



0  0

0 1 2

0 0 0

preference pravidel s maximální podporou z2 z2 z2 z2 z1 z1

: : : : : :

hlavní město ⊏ z1 : město hlavní město ∼ z1 : město stát ∼ z1 : země stát ⊏ z1 : země země ⊏ z2 : stát město ⊏ z2 : hlavní město


2 3 2 9 1 4 1 4 1 4 1 9

⊕ ⊖ ⊕ ⊖ ⊖ ⊖



Využití měr Závěr

Použití měr - dotaz - ekvivalence Dotaz na Prahu 2

6 6 6 6 6 6 6 6 6 ΦS = 6 6 6 6 6 6 6 6 6 4 ~ x0 = ~ x1 =

0 1 0 0 1 1 0

0 0 1 0 1 0 1

0 0 0 1 0 1 0

0 0 0 0 1 0 1

0 0 0 0 0 1 0

0 0 0 0 0 0 1

0 0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0

0 0 0 0

0 0 0

0 0 0 0

0

0 0 0 0

0 0 0 0

1 0 1 0

0 1 0 1

1 0 1 0

2 3

0 [1 [1

0 0

2 3

0 0

0 1

1 3

0 0 0 0

z1 :město, z2 :hlavní město z1 :stát, z2 :země z1 :měna

2 3

1 0 0 1 0 1 0

0 1 2 3 1 3 1 3

1

0 0

0 1

1 3

0 0

1 1

Praha ČR Česká Republika CZK


3 0 0 7 7 2 7 3 7 0 7 7 7 0 7 7 0 7 7 0 7 7 0 7 7 7 1 7 7 0 5 1

město, Praha město, Košice město, Bratislava stát, ČR stát, Slovensko měna, CZK měna, SSK země , země , hlavní hlavní

Česká Republika Slovensko město , Praha město , Bratislava

0] 0] 1+1 = 2 1 1 1




Použití měr - dotaz - ekvivalence Dotaz na hlavní město Praha 0 1 0 0 1 1 0

0 0 1 0 1 0 1

0 0 0 1 0 1 0

0 0 0 0 1 0 1

0 0 0 0 0 1 0

0 0 0 0 0 0 1

0 0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0

0 0 0

0 0 0 0

0

0

0 0 0 0

0 0 0 0

0 0 0 0

1 0 1 0

0 1 0 1

1 0 1 0

[0 [ 32 [ 23

0 0 0

0 0 0

0 1 1

6 6 6 6 6 6 6 6 6 ΦS = 6 6 6 6 6 6 6 6 6 4 ~ x0 = ~ x1 = ~ x2 =

2 3

1 0 0 1 0 1 0

2

2 3

2 3

0 0 0

0 0 2 3


1 3

0 0 0 0 0

0 0 2 3

2 3 1 3 1 3

1

1 3

0 0 0

1 1 1

Praha ČR Česká Republika CZK


3 0 0 7 7 2 7 3 7 0 7 7 7 0 7 7 0 7 7 0 7 7 0 7 7 7 1 7 7 0 5 1

město, Praha město, Košice město, Bratislava stát, ČR stát, Slovensko měna, CZK měna, SSK země = Česká Republika země = Slovensko hlavní město = Praha hlavní město = Bratislava

0] 0] 0] 1 + 0.66 = 1.66 0.66 1 0.66




Použití měr - dotaz - ekvivalence Dotaz na město Košice 2

6 6 6 6 6 6 6 6 6 ΦS = 6 6 6 6 6 6 6 6 6 4 ~ x0 = ~ x1 = ~ x2 =

2 3

1 0 0 1 0 1 0

0 1 0 0 1 1 0

0 0 1 0 1 0 1

0 0 0 1 0 1 0

0 0 0 0 1 0 1

0 0 0 0 0 1 0

0 0 0 0 0 0 1

0 0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0

0 0 0 0

0 0 0

0 0 0 0

0

0 0 0 0

0 0 0 0

1 0 1 0

0 1 0 1

1 0 1 0

2 3

0 [0 [0 [0

1 1 1

2 3

0 0 0

0 0 0

1 3

0 0 0 1 1


0 0 0 1 3 1 3 1 3

1

0 1 1

0 0 0

1 3

0 1 3 1 3

Košice Bratislava Slovensko SKK


0 0 0

3 0 0 7 7 2 7 3 7 0 7 7 7 0 7 7 0 7 7 0 7 7 0 7 7 7 1 7 7 0 5 1

město, Praha město, Košice město, Bratislava stát, ČR stát, Slovensko měna, CZK měna, SSK země = Česká Republika země = Slovensko hlavní město = Praha hlavní město = Bratislava

0] 0] 1] 3

1 0.33 1.33 1




Použití měr - dotaz - Hierarchie Dotaz na město Košice 2 1 6 0 6 0 6 6 1 6 6 6 0 6 1 ΦS = 6 6 6 0 6 6 0 6 6 6 0 4 0 0 ~ x0 = ~ x1 = ~ x2 =

[0 [0 [0

0 1 0 0 1 0 1

0 0 1 0 1 0 1

0 0 0 1 0 1 0

0 0 0 0 1 0 1

0 0 0 0 0 1 0

0 0 0 0 0 0 1

0 0 0 0 0 0 0

0 0 0 0 0 0

1 0 0 0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0

0 0 0 0

0 0 0 0

1 0 1 0

0 1 0 1

1 0 1 0

1 1 1

0 0 0

0 0 0

z1 :město z2 :hlavní město z1 :stát, z2 :země z1 :měna

1 2

1

1 2

0 0 0 1 1

0 0 0

0 1 1

Košice Bratislava Slovensko SKK


0 0 0

1 2

0 1 2 1 2

0 0 0

0 0 1 0 0 0 0

3

7 7 7 7 7 7 7 7 7 7 7 7 0 7 7 7 1 7 5 0 1

město, Praha město, Košice město, Bratislava stát, ČR stát, Slovensko měna, CZK měna, SSK země , země , hlavní hlavní

Česká Republika Slovensko město , Praha město , Bratislava

0] 0] 1] 2

1 0.50 1.50 1




Reálná data





Závěr Možnost (semi)automatického návrhu integračních pravidel Využití měr při návrhu ověření navržených pravidel na datech

při dotazování 1 2

rozhodnutí při nekonzistenci (preference) ochrana lokálního zdroje před ostatními (reputace)

Pravidla vhodnost uvažovat hierarchii - nutnost dalších testů polynomiální složitost jednoznačné přiřazení při disjunktnosti globálních domén atributů



Automatizovaný návrh pravidel pro integraci dat a sémantický web

Recommend Documents