Data Exchange
1
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
Seminari di ingegneria del software
07/07/2008
Introduzione: Il problema dell’interoperabilità dei dati
2
 I dati possono essere:


In posti differenti
In formati differenti (relazionale, XML, …).
 Esistono due approcci differenti al problema:

Data Integration

Data Exchange
Seminari di ingegneria del software
2
07/07/2008
Data Exchange: visione d’insieme
3
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, …
Seminari di ingegneria del software
3
07/07/2008
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)
Seminari di ingegneria del software
4
07/07/2008
Data exchange & data integration : … differenze
• Scopo principale
• Vincoli
• Query answering
(certain answers)
Seminari di ingegneria del software
5
07/07/2008
Il problema del Data Exchange
6
Σ
Source S
Target T
I


J
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.
Seminari di ingegneria del software
6
07/07/2008
Soluzioni
7
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
Seminari di ingegneria del software
7
07/07/2008
Schema Mappings: Problemi
8
Σ
Schema S
Schema T
I
J
 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
Seminari di ingegneria del software
8
07/07/2008
Data Exchange con Tgds e Egds
9
 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)
Seminari di ingegneria del software
9
07/07/2008
Dipendenze source-to-target
10
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))
Seminari di ingegneria del software
10
07/07/2008
Dipendenze source-to-target
11
 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.
Seminari di ingegneria del software
11
07/07/2008
Dipendenze target
12
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)
Seminari di ingegneria del software
12
07/07/2008
Data Exchange
13
Σst
Σt
Target Schema
Source Schema
T
S
J
I
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
Seminari di ingegneria del software
13
07/07/2008
Data Exchange
14
 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)}
Seminari di ingegneria del software
14
X, Y, …
07/07/2008
Soluzioni universali
15
 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
Seminari di ingegneria del software
15
07/07/2008
Soluzioni universali
16
Σ
Schema S
Schema T
I
Soluzione universale
J
h2
h1
h3
J2
J1
Omomorfismi
J3
Soluzioni
Seminari di ingegneria del software
16
07/07/2008
Esempio
17
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
Seminari di ingegneria del software
17
07/07/2008
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.
Seminari di ingegneria del software
18
07/07/2008
Trovare le soluzioni universali
19
 Se esiste una soluzione, una soluzione universale canonica può essere trovata
utilizzando la procedura chase.
 PROCEDURA CHASE
si 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.
Seminari di ingegneria del software
19
07/07/2008
Trovare le soluzioni universali
20
 CHASE STEP
Sia 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’.
Seminari di ingegneria del software
20
07/07/2008
Trovare le soluzioni universali
21
 SEQUENZA CHASE
Una sequenza chase di K con Σ è una sequenza (finita o infinita) di chase steps
Ki di,hi → Ki+1, con i=0,1,…., con K=K0 e d i una dipendenza in Σ.
 CHASE FINITO
Un 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 .
Seminari di ingegneria del software
21
07/07/2008
Teorema: chase e soluzioni universali
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.
Seminari di ingegneria del software
22
07/07/2008
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.
Seminari di ingegneria del software
23
07/07/2008
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)}
Seminari di ingegneria del software
24
07/07/2008
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
Seminari di ingegneria del software
25
07/07/2008
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.
Seminari di ingegneria del software
26
07/07/2008
Soluzioni universali: Weakly Acyclic Set
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
Seminari di ingegneria del software
27
07/07/2008
Soluzioni universali: Weakly Acyclic Set
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).
Seminari di ingegneria del software
28
07/07/2008
Soluzioni universali: Weakly Acyclic Set
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.
N0 U …. U Ni-1.
*
(R,A)
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.
Seminari di ingegneria del software
29
07/07/2008
Soluzioni universali: Weakly Acyclic Set
Quanti valori possono essere copiati da un nodo in Nj a un nodo in Ni con j != i ?
(R,A)
N0 U …. U Ni-1.
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.
Seminari di ingegneria del software
30
07/07/2008
La più piccola soluzione universale: il CORE
Soluzioni 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’.
Universal solution
2. !∃ un omomorfismo da G’ a qualche altro
J
sottografo proprio di G’.
homomorphism
core(J)
 G è un core se è un core di se stesso.
Esempio.
S: E(x,y)
Σst : E(x,y)  ∃ z (H(x,z) H(z,y))
I = { E(a,b) }.
T: H(x,y)
Σt = Ø.
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
Seminari di ingegneria del software
31
•
07/07/2008
La più piccola soluzione universale: il CORE
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.
Complessità.
Il problema nella sua generalità è intrattabile.
ma…
- CORE IDENTIFICATION (DP-complete)
- CORE RECOGNITION (coNP-complete)
…
Seminari di ingegneria del software
32
07/07/2008
08/07/2008
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.
Seminari di ingegneria del software
33
07/07/2008
Query Answering
34
Σ
Schema S
q
Schema T
I
J
Definizione: Le risposte certe di una query q su T su I
certain(q,I) =
Seminari di ingegneria del software
∩ { q(J): J è una soluzione per I }.
34
07/07/2008
Risposte certe
35
q(J1)
q(J2)
q(J3)
certain(q,I)
certain(q,I) =
Seminari di ingegneria del software
∩ { q(J): J è una soluzione per I }.
35
07/07/2008
Trovare le risposte certe
36
 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.
Seminari di ingegneria del software
36
07/07/2008
Trovare le risposte certe
37

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 soluzione
t 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.
Seminari di ingegneria del software
37
07/07/2008
Risposte certe e soluzione universale
38
q(J1)
q: unione di query congiuntive
q(J2)
q(J3)
q(J)
certain(q,I)
q(J)
Soluzione universale J per I
certain(q,I) insieme di tuple senza null di q(J).
Seminari di ingegneria del software
38
07/07/2008
Esempio
39
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.
Seminari di ingegneria del software
39
07/07/2008
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.
Seminari di ingegneria del software
40
07/07/2008
Risposte certe e disuguaglianze
41
 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.
Seminari di ingegneria del software
41
07/07/2008
Risposte certe e core
42
 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).
Seminari di ingegneria del software
42
07/07/2008
Risposte certe universali
43
 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).
Seminari di ingegneria del software
43
07/07/2008
Trovare le risposte certe universali
44
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.
Seminari di ingegneria del software
44
07/07/2008
Risposte certe universali e core
45
q: esistenziale
q(J1)
q(J3)
q(J2)
q(core(J))
q(J)
u-certain(q,I)
Soluzione universale J per I
u-certain(q,I) = insieme di tutte le tuple senza null di q(core(J)).
Seminari di ingegneria del software
45
07/07/2008
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>
Seminari di ingegneria del software
46
Inst(M12) ° Inst(M23)?
07/07/2008
Composing Schema Mapping
Composing s-t tgds
Punto chiave: chiusura dei linguaggi sotto la composizione
12
Σ12
23
Σ23
12  23
Σ13
Insieme finito di
full tgds
Insieme finito di
full tgds
Insieme finito di
full tgds
Insieme finito di
full tgds
Insieme finito di s-t
tgds
Insieme finito di s-t
tgds
Insieme finito di s-t
tgds
Insieme finito di
full tgds
Insieme infinito di
s-t tgds
P-time (att)
Singola s-t tgds
Insieme finito di
full s-t tgds
Non definibile
--
Insieme finito di s-t Insieme finito di s-t Formula esist. 2
tgds
tgds
ordine
Seminari di ingegneria del software
47
Composition
Query
P-time
NP
07/07/2008
Composing Schema Mapping
Second-order tgds
Def: Sia S uno schema sorgente e T uno schema target. Una second-order tuplegenerating 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) ) )
Seminari di ingegneria del software
48
07/07/2008
Composing Schema Mapping
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
Seminari di ingegneria del software
49
07/07/2008
Composing Schema Mapping
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)
Seminari di ingegneria del software
50
07/07/2008
Grazie per l’attenzione !!!
Seminari di ingegneria del software
51
07/07/2008