Data Exchange Introduzione Data exchange & data integration: caratteristiche e differenze Il...

Data Exchange

Introduzione

Data exchange & data integration: caratteristiche e differenze

Il problema del data exchange

Soluzioni universali

Core di una soluzione universale

Query answering

Composing schema mappings

07/07/2008

1

Seminari di ingegneria del software

Introduzione: Il problema dell’interoperabilità dei dati2

I dati possono essere: In posti differenti In formati differenti (relazionale, XML, …).

Esistono due approcci differenti al problema:

Data Integration

Data Exchange

07/07/20082Seminari di ingegneria del software

Data Exchange: visione d’insieme3

Il Data Exchange è un problema vecchio e ricorrente. Phil Bernstein – 2003 “Il Data exchange è il più vecchio problema sui database”

Prima applicazione: EXPRESS: IBM San Jose Research Lab – 1977

EXtraction, Processing, and REStructuring System per trasformare dati tra database gerarchici.

Applicazioni odierne: Data Warehousing, ETL (Extract-Transform-Load); XML Publishing, XML Storage, …



Data exchange & data integration : caratteristiche e …

Data integration :

- tripla (S, G, M)-Due approcci per M. LAV e GAV

Data exchange:

- Quadrupla (S, T, Σst , Σt)

07/07/2008Seminari di ingegneria del software 5

Data exchange & data integration : … differenze

• Scopo principale

• Vincoli

• Query answering (certain answers)

Il problema del Data Exchange6

Source S Target T

Schema Mapping M = (S, T, Σ) Source schema S, Target schema T Asserzioni Σ specificano le relazioni tra S eT.

Obiettivo: Trasformare una istanza source I in una istanza target J, in modo che

<I, J> soddisfi le specifiche Σ di M.

IJ

Σ


Soluzioni7

Definizione: Schema Mapping M = (S, T, Σ)Se I è un’istanza source, allora una soluzione per I è un’istanza target J tale che <I, J > soddisfi Σ.

Fatto: In generale, per un’istanza source I, Può non esistere alcuna soluzione oppure Possono esistere più soluzioni; in particolare, possono esistere infinite soluzioni


Schema Mappings: Problemi8

Problema decisionale: Data una istanza source I, esiste una soluzione J perI? Problema funzionale: Data una istanza source I, costruire una soluzione J per I, assodato che

esista

Schema S Schema T

I J

Σ


Data Exchange con Tgds e Egds9

Gli schema mappings di un problema di Data Exchange che verranno presi in considerazione sono composti da: Source-to-target tgds Target tgds Target egds

Tuple-generating dependencies (tgds) Equality-generating dependencies (egds)


Dipendenze source-to-target10

La relazione tra source e target è data da formule della logica del primo ordine chiamate:

Source-to-Target Tuple Generating Dependencies (s-t tgds)

(x) y (x, y), dove (x) è una congiunzione di atomi sul source; (x, y) è una congiunzione di atomi sul target.

Esempio:

(Student(s) Enrolls(s,c)) t g (Teaches(t,c) Grade(s,c,g))


Dipendenze source-to-target11

s-t tgds generalizzano le specifiche più importanti del data integration:

Generalizzano LAV (local-as-view) :

P(x) y (x, y), dove P è un source schema. Generalizzano GAV(global-as-view) :

(x) R(x), dove R è un target schema.


Dipendenze target12

Oltre alle dipendenze source-to-target, vanno considerate anche le dipendenze target: Target Tgds : T(x) y T(x, y)

Dept (did, dname, mgr_id, mgr_name) Mgr (mgr_id, did) (dipendenza di inclusione sul target)

Target Equality Generating Dependencies (egds): T(x) (x1=x2)

(Mgr (e, d1) Mgr (e, d2)) (d1 = d2) (condizione di chiave sul target)


Data Exchange13

Schema Mapping può essere visto come una quadrupla:

M = (S, T, Σst , Σt ), dove

Σst è un insieme di source-to-target tgds Σt è un insieme di target tgds e target egds

Source Schema S

Target Schema T

Σst

I J

Σt


Data Exchange14

Fatto: Data una istanza source I, possono esistere più soluzioni.

Esempio: Relazione source E(A,B), relazione target H(A,B)

Σ: E(x,y) z (H(x,z) H(z,y))

Istanza source I = {E(a,b)}

Soluzioni: possono esisterne infinite! J1 = {H(a,b), H(b,b)} costanti:

J2 = {H(a,a), H(a,b)} a, b, …

J3 = {H(a,X), H(X,b)} labeled nulls:

J4 = {H(a,X), H(X,b), H(a,Y), H(Y,b)} X, Y, …


Soluzioni universali15

Le soluzioni universali sono le migliori soluzioni per un problema di Data Exchange. Sono considerate le soluzioni più generali, non contengono nè più nè meno

di quanto richiesto dalle specifiche. Hanno un omomorfismo verso tutte le altre soluzioni Const: insieme dei valori che compaiono nell’istanza source Var (labeled nulls): insieme infinito di valori tali che: Var ∩ Const = {} Omomorfismo h: J1 → J2 tra istanze target:

h(c) = c, per ogni costante in Const Se P(a1,…,am) è in J1,, allora P(h(a1),…,h(am)) è in J2


Soluzioni universali16

Schema S Schema T

IJ

Σ

J1J2

J3

Soluzione universale

Soluzioni

h1 h2 h3Omomorfismi


Esempio17

Relazione source S(A,B), relazione target T(A,B)

Σ : E(x,y) z (H(x,z) H(z,y))

Istanza source I = {H(a,b)}

Alcune possibili soluzioni: J1 = {H(a,b), H(b,b)} non è universale

J2 = {H(a,a), H(a,b)} non è universale

J3 = {H(a,X), H(X,b)} è universale

J4 = {H(a,X), H(X,b), H(a,Y), H(Y,b)} è universale


Soluzioni universali: proprietà18

Unicità sull’equivalenza omomorfica: Se J e J’ sono universali per I, allora sono omomorficamente equivalenti.

Assumiamo che Σst sia un insieme di tgds. Siano I, I’ due istanze del source schema, J una soluzione universale per I, e J’ una soluzione universale per I’. Allora Sol(I) ⊆ Sol(I ) se e solo se c’è un omomorfismo h: J’→ J. ′Di conseguenza, Sol(I) = Sol(I ) se e solo se J e J’ sono omomorficamente ′equivalenti.


Trovare le soluzioni universali19

Se esiste una soluzione, una soluzione universale canonica può essere trovata utilizzando la procedura chase.

PROCEDURA CHASEsi comincia con un’istanza <I, > ∅si applica il chase a <I, > applicando le dipendenze in Σ∅ st e Σt fintantoché sono applicabili. Questa procedura può:

fallire non terminare,

.. ma se termina è garantito che l’istanza risultante soddisfa tutte le dipendenze e che, per di più, è una soluzione universale.



CHASE STEPSia K un’istanza:(tgd) Sia d una tgd φ(x) → ∃yψ(x, y).

Sia h un omomorfismo da φ(x) a K tale che non esista un’estensione di h a un omomorfismo h’ da φ(x) ψ(∧ x, y) a K. Sia K’ l’unione di K con l’insieme dei fatti ottenuti: (a) estendendo h ad h’ in modo tale che ad ogni variabile in y sia assegnato un nuovo labeled null; (b) prendendo l’immagine degli atomi di ψ sotto h’. Diciamo che K d,h → K’.

(egd) Sia d un egd φ(x) → (x1 = x2). Sia h un omomorfismo da φ(x) a K tale che h(x1) != h(x2). Distinguiamo ora due casi:

- Se sia h(x1) che h(x2) sono in Const, fallimento- Altrimenti, sia K’ come K in cui identifichiamo h(x1) e h(x2) come segue:

- se uno è una costante, allora il labeled null è rimpiazzato dovunque dalla costante;- Se sono entrambi labeled nulls, allora ognuno è rimpiazzato dovunque dall’altro. Diciamo che K d,h → K’.



SEQUENZA CHASEUna sequenza chase di K con Σ è una sequenza (finita o infinita) di chase stepsKi di,hi → Ki+1, con i=0,1,…., con K=K0 e d i una dipendenza in Σ.

CHASE FINITOUn chase finito di K con Σ è una sequenza chase finita:

Ki di,hi → Ki+1, con 0 ≤ i < m , con il requisito che: (a) Km =⊥ oppure (b) non c’è dipendenza d i in Σ e non c’è omomorfismo h i tale che d i possa essere applicato a Km con h i .



Th. Si assuma una configurazione di Data Exchange in cui Σst consiste in tgds e Σt consiste in tgds e egds.1.Sia <I,J> il risultato di un qualche chase finito di <I, > ∅ con Σst ∪ Σt. Allora J è una soluzione universale.2.Se esiste un qualche chase finito di <I, > ∅ che fallisce con Σst ∪ Σt allora non esiste soluzione.

La dimostrazione fa uso del seguente lemma:

Lemma. sia K1 d,h → K2 un chase step dove K2!= ⊥. Sia K un’istanza tale che: (i) K soddisfa d e (ii) esiste un omomorfismo h1 : K1 → K. Allora esiste un omomorfismo h2 : K2 → K.

Teorema: chase e soluzioni universali


Dimostrazione teorema: La dimostrazione del teorema si basa sul precedente lemma e sull’osservazione che l’ “identity mapping” è un omomorfismo da <I, > a <I, J’> per ogni ∅soluzione J’.

1.Dimostrazione parte 1: <I,J> soddisfa Σst ∪ Σt . Sia J’ una soluzione arbitraria. <I,J’> soddisfa Σst ∪ Σt . L’identity mapping id: <I, >∅ → <I, J’> è un omomorfismo. Dal lemma, si ottiene un omomorfismo h:<I,J>→ <I,J’>. Quindi, J è universale.

2.Dimostrazione parte 2: chase step fallisce d deve essere un egd di Σt, detto φ(x) → (x1 = x2), e

h : φ(x) → J è un omomorfismo tale che h(x1) e h(x2) sono due costanti distinte c1 e c2.

Per assurdo si supponga che esista una soluzione J’. Omomorfismo identità id:<I, >∅ → <I, J’> implica, dal lemma, l’esistenza

dell’omomorfismo g: :<I, J>→ <I, J’>. Quindi, g ◦ h : φ(x) → J’ è un omomorfismo J’ soddisfa d deve essere il caso in cui g(h(x1)) = g(h(x2)) e quindi g(c1) =

g(c2). Gli omomorfismi sono identità su Const, quindi c1=c2, che è una contraddizione.

Teorema: chase e soluzioni universali

Esempio (chase infinito)24

S: DeptEmp(dpt_id, mgr_name, eid)T: Dept(dpt_id, mgr_id, mgr_name), emp(eid, dpt_id). Σst = { DeptEmp(d, n, e) → M.∃ Dept(d,M, n) ∧ Emp(e, d) } Σt = { Dept(d, m, n) → D.∃ Emp(m,D),

Emp(e, d) → M N.∃ ∃ Dept(d,M,N) }I = {DeptEmp(CS,Mary, E003) }

Applicando il chase < I, > ∅ con Σst si ottiene l’istanza target: J1 = {Dept(CS,M,Mary), Emp(E003, CS)}

J ={Dept(CS,M,Mary), Emp(E003, CS), Emp(M,D), Dept(D,M’,N’), . . . }

D’altro canto, una soluzione finita esiste. Due soluzioni (nessuna delle quali universale) sono ad esempio:

J’ ={Dept(CS,E003,Mary), Emp(E003, CS)}J’’ ={Dept(CS,M,Mary), Emp(E003, CS), Emp(M,CS)}



Soluzioni universali: Full tgds

I full tgds sono dei tgds senza variabili esistenzialmente quantificate, nella forma:

T(x) T(x), dove T(x) e T(x) sono congiunzioni di atomi target

Esempio (full tgd) H(x,z) H(z,y) H(x,y) C(z)

E’ stato provato che ogni sequenza chase con un insieme Σ di full tgds ha lunghezza finita.Inoltre, ogni insieme di egds può essere aggiunto a Σ senza influenzare questo risultato.

Tuttavia, .. non sono molto utili in pratica


Soluzioni universali: Weakly Acyclic Set

La nozione di WAS (Weakly Acyclic Set) include:-Insiemi di full tgds - insiemi aciclici di dipendenze di inclusione

Sia Σ un insieme di tgds, costruiamo il grafo delle dipendenze:

1.Esiste un nodo per ogni (R,A) dove R è un simbolo di relazione e A un attributo di R;

2.Si aggiungono gli archi come segue: per ogni per ogni tgd φ(x) → y ψ(x, y) in Σ e per ogni x che occorre in ψ e per ∃ ogni occorrenza di x in φ in (R, Ai):

a. Si aggiunge un arco (R, Ai) (S, Bj) ( se non esista già) per ogni x in ψ in posizione (R,Bj). b. Si aggiunge un arco speciale (R,Ai) (T,Ck) ( se non esiste già) per ogni y in ψ in posizione (T, Ck) •

DEF. Σ è weakly acyclic se il grafo delle dipendenze non contiene cicli attraverso archi speciali.



Esempio:

S : DeptEmp(dpt_id,mgr_name,eid)T : Dept(dpt_id, mgr_id, mgr_name) ; Emp(eid, dpt_id)

Σst = { DeptEmp(d, n, e) → ∃M.Dept(d,M, n) Emp(e, d) }∧Σt = { Dept(d, m, n) → D.Emp(m,D), ∃ Emp(e, d) → M N.Dept(d,M,N) }∃ ∃ Non è weakly acyclic!!

Esempio:

Σ’t = { Dept(d, m, n) → Emp(m, d),Emp(e, d) → M N.Dept(d,M,N) }∃ ∃

OK



Th. Sia Σ l’unione di un weakly acyclic set of tgds con un insieme di egds, e sia K

un’istanza. Allora esiste un valore polinomiale nella dimensione di K che limita la

lunghezza di ogni sequenza chase di K con Σ.

DIM. Per ogni nodo (R,A) (posizione) Siano:

-Σ senza egds;- incoming path: ogni percorso che finisce in (R, A);- rank: numero max di archi speciali su ogni incoming path- r: il massimo di rank(R, A)- p: il numero di nodi nello schema- partizioniamo i nodi in N0, N1, …., Nr con Ni insieme dei nodi con rank =i;-n il numero totale di valori distinti che appartengono all’istanza K. - K’ qualsiasi istanza ottenuta da K dopo qualche arbitraria sequenza di chase.

Lemma. per ogni i esiste un polinomio Qi, tale che il numero di valori distinti che occorrono in tutti i nodi (R,A) di Ni, in K’, è al più Qi(n).



DIM. (per induzione) Lemma

Passo Base: (R, A) è in N0 Q0(n) = n;

Passo induttivo: un valore può occorrere in un nodo di Ni, in K’, per:1. È stato copiato da qualche nodo in Nj con j != i, durante un chase step.2. È stato generato come nuovo valore (labeled null) durante un chase step.

Quanti valori possono essere generati nel Caso (2)?Sia (R,A) un nodo in Ni.

Induttivamente, il numero di valori distinti che possono esistere in tutti i nodi in N0 U …. U Ni-1 è limitato da P(n) = Q0(n) + …. + Qi-1(n). Sia d il numero max di archi speciali che entrano in un nodo. Il numero totale di nuovi nodi: (P(n))d x D, dove D è il numero di dipendenze in Σ. Considerando tutti i nodi in Ni: G(n) = pi x (P(n))d x D con pi è il numero di nodi in Ni. Considerando che lo schema e Σ sono fissi, G è polinomiale.

N0 U …. U Ni-1. * (R,A)



Quanti valori possono essere copiati da un nodo in Nj a un nodo in Ni con j != i ?

N0 U …. U Ni-1.(R,A)

Quindi il numero massimo è limitato dal numero totale di valori in N0 U …. U Ni-1 che è P(n).

Ricapitolando Qi(n) = n + G(n) + P(n)Notare che i <= r(costante)

Ne consegue che il numero totale di tuple che possono esistere in K’ è al più (Q(n)) •

Corollario: Si assuma una configurazione di Data Exchange in cui Σst sia un insieme di tgds e Σt l’unione di un weakly acyclic set of tgds con un insieme di egds. L’esistenza di una soluzione può essere controllata in tempo polinomiale. Se la soluzione esiste, allora una soluzione universale può essere trovata in tempo polinomiale.


La più piccola soluzione universale: il CORESoluzioni universali multiple: qual è la migliore? Quale utilizzare? CORE

Def. Sia G = (N, A) un grafo. Un sottografo G’ = (N’, A’) è il core di G se:1. ∃ un omomorfismo da G a G’.2.! ∃ un omomorfismo da G’ a qualche altro

sottografo proprio di G’.

G è un core se è un core di se stesso.

Esempio. S: E(x,y) T: H(x,y)Σst : E(x,y) ∃ z (H(x,z) H(z,y)) Σt = Ø. I = { E(a,b) }.

Soluzioni universali:J1 = {H(a,X), H(X,b)} è il core.J2 = {H(a,X), H(X,b), H(a,Y), H(Y,b)} è una sol univ •

Universal solution J

core(J)

homomorphism

07/07/2008Seminari di ingegneria del software 32 08/07/2008Seminari di ingegneria del software 32

La più piccola soluzione universale: il CORE

Complessità.Il problema nella sua generalità è intrattabile.

ma…

- CORE IDENTIFICATION (DP-complete)- CORE RECOGNITION (coNP-complete)

…

Prop. Sia (S, T, Σst, Σt) uno schema mapping:

1.Tutte le soluzioni universali hanno lo stesso core.2.Il core di una soluzione universale è la più piccola soluzione universale.


La più piccola soluzione universale: il CORE

..in certi setting il core di una soluzione universale può essere calcolato in tempo polinomiale:

-∑st un insieme di s-t tgds e ∑t un insieme di egds.

- Algoritmo Greedy ( semplice ma utilizza l’istanza sorgente )

- Algoritmo Blocks ( più complessa ma utilizza solo l’istanza target)

- ∑st un insieme di s-t tgds e ∑t un insieme di weakly acyclic tgds con arbitrarie egds.

Query Answering34

Schema S Schema T

IJ

Σ q

Definizione: Le risposte certe di una query q su T su I

certain(q,I) = ∩ { q(J): J è una soluzione per I }.


Risposte certe35

certain(q,I)

q(J1)

q(J2)q(J3)

certain(q,I) = ∩ { q(J): J è una soluzione per I }.


Trovare le risposte certe36

Th: Si assuma che M = (S,T,Σst ∪ Σt) sia uno schema mapping tale che Σst sia un insieme di tgds source-to-target e Σt sia un insieme di target egds e target tgds. Sia q un unione di query congiuntive sullo scherma target T (Si ricorda che una query congiuntiva è una formula del primo ordine nella forma wχ(x,w), dove χ(x,w) è una congiunzione di atomi).

1. Se I è un’istanza source e J è una soluzione universale per I, allora certainM(q, I)= q(J)↓, dove q(J)↓ è l’insieme di tutte le tuple di q(J) senza null, ovvero tutte le tuple t in q(J) tali che ogni valore in t sia una costante di Const.

2. Sia I un’istanza source e J una soluzione tale che per ogni query congiuntiva q su T, si ha che certain(q, I) = q(J)↓. Allora J è universale.

Quindi, certain(q,I) è computabile in tempo polinomiale in |I|:1. Computare una soluzione universale canonica J in tempo polinomiale;2. Valutare q(J) e rimuovere le tuple con i null.


Trovare le risposte certe37

Dimostrazione

1. Sia q una query di arità k che è l’unione di query congiuntive e sia t una k-tupla di costanti dall’istanza source I. t appartiene a certain(q,I), t appartiene a q(J), con J soluzionet appartiene a q(J)↓ t consiste solamente di costanti. Inoltre esistono un termine φ(x) in q e un omomorfismo g : φ(x) → J tale che g(x) = t. Sia J’ una soluzione arbitraria. J è una soluzione universale c’è un omomorfismo h : J → J’. Allora h ◦ g è un omomorfismo da φ(x) a J’. Gli omomorfismi sono identità sulle costanti, per cui h(g(x)) = h(t) = t. Quindi t appartiene a q(J’).

2. Sia q^j la query congiuntiva canonica associata a J (ad esempio, la query congiuntiva booleana ottenuta prendendo la congiunzione di tutti i fatti di J nei quali i labeled null sono sostituiti da variabili esistenzialmente quantificate).

Si sa che certain(q^j, I) = q^j(J) ↓ = q^j(J), dove la prima uguaglianza deriva dall’assunzione su J, e la seconda deriva dal fatto che q^j è una query booleana. Quindi finchè q^j(J) = true, si ha che certain(q^j,I) = true. Inoltre, se J’ è una soluzione arbitraria, si ha che q^j(J’) = true. Questo implica l’esistenza di un omomorfismo h : J → J’. Quindi J è universale.


Risposte certe e soluzione universale38

q(J1)

q(J2)q(J3)

certain(q,I) insieme di tuple senza null di q(J).

q(J)certain(q,I)

q(J)

Soluzione universale J per I

q: unione di query congiuntive


Esempio39

Sia M uno schema mapping tale che:

Σst = {E(x, y) → ( z∃ )(H(x, z) H∧ (z, y))}Σt = .∅

Sia I l’istanza source che consiste semplicemente nel fatto E(1,2).Sia q(x) la query congiuntiva wH∃ (x,w). E’ facile verificare che

certain(q,I) = {1}. Prendiamo in considerazione la seguente soluzione universale per I:

J = {H(1, u),H(u, 2)}

Si può notare che q(J) = {1,u}, quindi eliminando i valori nulli si ottiene q(J)↓ = {1} = certain(q,I), come ipotizzato dal teorema.


Esempio (Query congiuntive con disuguaglianze)40

Sia M lo stesso schema mapping dell’esempio precedente:

Σst = {E(x, y) → ( z)(H(x, z) H(z, y))}∃ ∧Σt = .∅

Sia I l’istanza source che consiste semplicemente nel fatto E(1,1).Sia q(x) la query congiuntiva w (H(x,w) w!=x) . E’ facile verificare che ∃ ∧

certain(q,I) = {}. Prendiamo in considerazione la seguente soluzione universale per I:

J = {H(1, u),H(u, 1)}Si può notare che q(J) = {1,u}, quindi eliminando i valori nulli si ottiene q(J)↓ = {1} != certain(q,I), per cui il teorema non è soddisfatto.


Risposte certe e disuguaglianze41

Th: Si assuma che M = (S,T,Σst ∪ Σt) sia uno schema mapping tale che Σst sia un insieme di tgds source-to-target e Σt sia un insieme di target egds e un weakly acyclic set di target tgds.

1. Sia q un’unione di query congiuntive con al più una disuguaglianza per query congiuntiva. Allora le risposte certe di q sono computabili in tempo polinomiale.

2. Sia q un’unione di query congiuntive con disuguaglianze. Il problema delle risposte certe per q è un problema in coNP.

3. Computare le risposte certe di unioni di query congiuntive con disuguaglianze può essere un problema coNP-completo anche se l’unione consiste di due query congiuntive ognuna della quali abbia al massimo due disuguaglianze e il cui schema mapping non abbia condizioni target.


Risposte certe e core42

Si assuma che M = (S,T,Σst ∪ Σt) sia uno schema mapping tale che Σst sia un insieme di tgds source-to-target e Σt sia un insieme di target egds e target tgds. Si assuma anche che I sia un’istanza source per la quale esistano soluzioni universali. Sia J0 il core delle soluzioni universali per I. Sia q un unione di query congiuntive con disuguaglianze.

q(J0) q⊆ (J), per ogni soluzione universale J per I; q(J0)↓ = ∩ {q(J) : J è universale per I} certain⊆ (q, I).


Risposte certe universali43

Risposte certe: “Possibili mondi” = Soluzioni Risposte certe universali: “Possibili mondi” = Soluzioni universali

Definizione: Risposte certe universali di una query q su T su I

u-certain(q,I) = ∩ { q(J): J è una soluzione universale per I }.

Dalle definizioni segue che certain(q, I) u-certain⊆ (q, I) . Inoltre, se q è un’unione di query congiuntive e I è un’istanza source per la quale esiste soluzione universale, si ha che certain(q, I) = u-certain(q, I).


Trovare le risposte certe universali44

Schema mapping M = (S, T, st, t) tale che: st è un insieme di tgds source-to-target t è un insieme di target egds e target tgds. Sia q una query esistenziale su T. Se I è un’istanza source e J è una soluzione universale per I, allora u- certain(q,I) = l’insieme di tutte le tuple “senza null” in q(core(J)).

Si noti che l’unione di query congiuntive con disuaglianze è un caso speciale di query esistenziali.


Risposte certe universali e core45

q(J1)

q(J2)q(J3)

u-certain(q,I) = insieme di tutte le tuple senza null di q(core(J)).

q(J)u-certain(q,I)

q(core(J))

Soluzione universale J per I

q: esistenziale



Composing Schema Mapping

DEF. Scriviamo Inst(M) l’insieme di tutte le istanze <I, J> di M. Siano M12 = (S1, S2, Σ12 ) e M23 = (S2 , S3 , Σ23 ) due schema mappings tali che S1 , S2 , S3 non abbiano simboli relazionali in comune. Uno schema mapping M13 = (S1 , S3 , Σ13 ) è una composizione di M12 e M23 se Inst(M13) = Inst(M12) ° Inst(M23), ossia:

Inst(M13) = { <I1 , I3> | Exist I2 tale che <I1 ,I2> Inst(M12) e <I2 ,I3> Inst(M23) }

Proprietà:

- Equivalenza logica - Inst(12 ) Inst(23 ) è chiusa sotto l’isomorfismo

Composition Query: date due istanze I1 e I3 è <I1 ,I3> Inst(M12) ° Inst(M23)?



Composing s-t tgdsPunto chiave: chiusura dei linguaggi sotto la composizione

12

Σ12

23

Σ23

12 23

Σ13

Composition

Query

Insieme finito di full tgds



P-timeInsieme finito di full tgds

Insieme finito di s-t tgds




Insieme infinito di s-t tgds

P-time (att)

Singola s-t tgds Insieme finito di full s-t tgds

Non definibile --



Formula esist. 2 ordine

NP



Second-order tgds

Def: Sia S uno schema sorgente e T uno schema target. Una second-order tuple-

generating dependency (SO tgd) è una formula:

f1 … fm( (x1(1 1)) … (xn(n n)) ), dove:

-Ogni fi è un simbolo di funzione.

- Ogni i è un’intersezione di atomi da S ed uguaglianze di termini

- Ogni i è un’intersezione di atomi da T.

Esempio: f (e( Emp(e) Mgr(e,f(e) ) e( Emp(e) (e=f(e)) SelfMgr(e) ) )



SO-tgds - Proprietà:

- La composizione di SO tgds è definibile in un SO tgds

- Esiste un algoritmo per comporre SO-tgds

- Chasable

- Per gli schema mapping specificati da SO tgds, le certain answers di query congiuntive target sono calcolabili in tempo polinomiale



Computing – Algoritmo Compose

∑12 = Exists f ( e ( Emp(e) Mgr1(e, f(e) ) ) )∑23 = Exist e,m ( Mgr1(e, m) Mgr(e, m ) ) AND p.o. e ( Mgr1(e, e) SelfMgr(e) )

Input: due schema mappings M12=(S1, S2, ∑12) e M23=(S2 , S3 ,∑23) con ∑12 e ∑23 SO tgds.Output: una composizione M13 = (S1 , S3 , ∑13) dove ∑13 è un insieme di SO tgds.

- Dividere le SO tgds in ∑12 e ∑23.Es: C12 = Emp(e) (Mgr1(e, f(e)) C23 = Mgr1(e,m) Mgr(e,m) Mgr1(e,e) SelfMgr(e)- Componi C12 con C23

Es: P1 : Emp(e0) (e=e0) (m = f(e0)) Mgr1(e,m) P2 : Emp(e0) (e=e0) (e = f(e0)) SelfMgr(e)- Costruisce M13

Es: ∑13 = f ( e0 e m P1 e0 e P2)

-Return M13 = (S1, S3, ∑13)


Grazie per l’attenzione !!!

Data Exchange Introduzione Data exchange & data integration: caratteristiche e differenze Il...

Documents

Transcript of Data Exchange Introduzione Data exchange & data integration: caratteristiche e differenze Il...