Università degli studi di
Modena e Reggio Emilia
Facoltà di Ingegneria - Sede di Modena
Corso di Laurea in Ingegneria Informatica
Elaborazione di interrogazioni
in un sistema a mediatore:
Fusione dei dati
Con Risoluzione di conflitti
Relatore
Chiar.mo Prof. Sonia Bergamaschi
Tesi di Laurea di
Marco Mattioli
Correlatore
Prof. Ing. Domenico Beneventano
Controrelatore
Prof. Ing. Paolo Tiberio
Sommario
• Il modello a mediatore
• La qualità dei dati e la risoluzione dei conflitti
- Funzione di risoluzione
• L’interrogazione di database autonomi
- Full Disjunction
- Algoritmi risolutivi
Il Modello a Mediatore
Approccio MOMIS
MEDIATORE
MOMIS
Lista di auto dai
cataloghi FIAT e
Wolkswagen
rispondenti alla
richiesta
Usando un motore di ricerca internet
Informazioni
FIAT
pagine web
FIAT
Informazioni
Volkswagen
pagine web
Volkswagen
...
...
Altre
Pagine
Motore
di ricerca
query
Voglio comprare un’auto con il motore tra i 1600 e i 2000cc, con un
costo minore di 18000
Il Modello a Mediatore
• L’utente esegue le richieste su uno SCHEMA GLOBALE
• Il mediatore seleziona le fonti locali e traduce, la richiesta per renderla
comprensibile dalle fonti locali (MAPPING TABLE)
• Ogni richiesta tradotta viene spedita alla rispettiva fonte locale ed eseguita
• I risultati vengono raccolti e tradotti per lo schema globale
•Approccio GAV: ogni attributo della classe globale è mappato
in almeno una classe locale.
•Le classi locali sono autonome: i dati potrebbero
contenere delle inconsistenze.
I Conflitti nei Dati
•Genericamente: quando una entità presenta
aspetti inconsistenti o contrastanti.
•In ambito relazionale: quando i valori di uno o più attributi
comuni di tuple che vanno fuse hanno valori discordanti.
Esempio:
Comune
USL
Carta
Identità
Nome
Indirizzo
Carta
Identità
Nome
Indirizzo
22222
M. Rossi
Via
Indipendenza 26
22222
M. Rossi
Via
F.lli Rosselli 35
55555
L. Verdi
Viale
Vittorio Veneto 30
55555
L. Verdi
Viale
Vittorio Veneto 30
•Conflitto su Indirizzo nella prima tupla. Come comportarsi?
I Conflitti nei Dati
• Non fornire in uscita le informazioni conflittuali (L. Bertossi, J. Chomicki 2003)
Carta identità
Nome
Indirizzo
55555
L. Verdi
Viale Vittorio Veneto 30
• Fornire in uscita anche tutti i valori conflittuali (D. Lembo, M. Lenzerini 2002)
Carta identità
Nome
Indirizzo
22222
M. Rossi
Via Indipendenza 26,
Via F.lli Rosselli 35
55555
L. Verdi
Viale Vittorio Veneto 30
• Fornire in uscita un solo valore per ogni conflitto (F. Naumann 2000)
(risoluzione dei conflitti)
Carta identità
Nome
Indirizzo
22222
M. Rossi
f (Via Indipendenza 26,
Via F.lli Rosselli 35)
55555
L. Verdi
Viale Vittorio Veneto 30
La Qualità nei Dati
•Utile per la selezione delle fonti (F. Naumann 1998)
•Utile per risolvere i conflitti (H. J. Lenz, F. Naumann, M. Neiling 2003)
Fonte più affidabile
Dato probabilmente corretto
• Concetto non ben definito
- Numerosi parametri (>60) e metodi per calcolarla.
- L’importanza dei parametri varia in base all’applicazione ed all’utente
Esempi:
*Tempo di risposta
*Consistenza
*Completezza
*Accuratezza
*Aggiornamento
La Funzione di Risoluzione
Dati:
R1,…,Rn: insieme di relazioni
X1,…,Xn: valori assunti da R1…Rn per l’attributo A
D+: D   . Dove D è il dominio di A
Allora si definisce funzione di risoluzione la funzione:
frA= frA( X1,…,Xn) : D+n  D+
frA =

se i Xi = 
Xi
se !i|Xi 
g(X1,…,Xn)
Dove g(X1,…,Xn) : D+n  D+
altrimenti
La Funzione di Risoluzione
• g(X1…Xn) preposta a risolvere i conflitti.
- deve essere commutativa
- Si possono identificare tre categorie, a seconda del tipo di attributo
*Funzioni per attributi numerici (media, mediana, somma)
*Funzioni per attributi non numerici (concatena, più corto, più lungo)
*Funzioni per ogni tipo di attributo (max qualità, random, fonte stabilita)
•Si possono distinguere due tipi di funzione di risoluzione:
-Funzione di risoluzione standard
risolve i conflitti utilizzando i valori dell’attributo da risolvere
-Funzione di risoluzione generalizzata
si serve anche dei valori di altri attributi dello schema
Es.: attributo “prezzo” utilizza attributo “data”
Grafi ed Ipergrafi
• Grafi secondo Galindo-Legaria
- i nodi rappresentano le relazioni
- gli archi rappresentano i join tra le relazioni
• Ipergrafi secondo Fagin
- i nodi rappresentano gli attributi
- gli iperarchi rappresentano le relazioni
Un iperarco può congiungere un numero qualsiasi di nodi
Esempio di grafo
Esempio di ipergrafo
Full Disjunction
• Operatore in grado di calcolare l’outerjoin di n relazioni
• Preserva tutte le possibili connessioni tra i fatti
Esempio:
L1
L2
L3
A
B
B
C
A
C
1
10
20
200
1
100
2
20
30
300
3
300
select *
from (L1 full outer join L2 on L1.B=L2.B)
full outer join L3 on (L2.C=L3.C or L1.A=L3.A)
Metodo basato
sull’OR
L1.A
L1.B
L2.B
L2.C
L3.A
L3.C
1
10


1
100
2
20
20
200




30
300
3
300
Gli Algoritmi SOJO e PSOJ
•
•
•
•
•
Calcolano la full disjunction
Utilizzano il natural outerjoin come unico operatore
Fanno l’ipotesi di omogeneità semantica
SOJO (Sound Ordering of OuterJoin) ideato da Ullman
PSOJ (Pseudo Sequence of OuterJoin) da utilizzare in ambito MOMIS
Principali differenze
a.
b.
c.
d.
SOJO (Ullman 1996)
basato su ipergrafi
funziona correttamente solo per
ipergrafi -aciclici
ogni relazione compare una ed
una sola volta nella sequenza di
join
necessita di un ordinamento per
le relazioni
a.
b.
c.
d.
PSOJ
basato su grafi
funziona correttamente per
ogni tipo di grafo/ipergrafo
ogni relazione può comparire
più volte nella sequenza di
join
non necessita di
ordinamento
Il Natural Outerjoin
• Funzionamento simile al full outerjoin
• Proietta il risultato sull’unione degli schemi
• Computa l’equijoin su tutti gli attributi comuni
Esempio:
R
S
A
C
B
C
3
7
5
7
4
9
6
8
A
B
C
R.A
R.C
S.B
S.C
3
5
7
3
7
5
7
4

9
4
9



6
8


6
8
Natural Outerjoin
Full Outerjoin
Le Modifiche al PSOJ
• Rimozione del vincolo di omogeneità
semantica
- Funzione di risoluzione
- Necessità di un ordinamento
- Fallimento in alcuni casi
• E’ necessario che gli attributi di join siano compattati
 Natural Outerjoin (non standard SQL92)
 Full Outerjoin + Funzione di risoluzione sugli attributi di join
L’Algoritmo PSOJ Modificato
•
Input:
- R = {R1, … , Rn} su S (G)
- JM = {Fij : i<j , i = 1,…,n-1 ; j = 2,…,n}
- F = {fr1,…,frm}
•
Output:
- Full Disjunction
•
Operatore di join: full outerjoin
Procedimento:
• Poni F0 = JM , Ro = R , NR= n. relazioni
• for (i=0; i< NR;i++)
seleziona Ri 
R i+1 =
Ri
{Ri =►◄f= Ri’ : Ri’ 
calcola tutti i join in
 R
R i , Ri’ ≠ Ri , f = OJCi(Ri , Ri’ ) ≠ null}
R i+1
R i+1
 tupla di R
 attributo di join j della tupla
applica la funzione di risoluzione frj (associativa)
 tupla della relazione
 attributo j della tupla
applica la funzione di risoluzione frj
Restituisci
R NP
Esempio di applicazione
dell’algoritmo PSOJ
F2,4
F1,2
F
F
1,4
1,2
F1,2 (R F
R
F
)]
R
F
R
)
[(R
2
1,2
22
1,4
2
4 2,4 RR
1
R1
1
(R1
(R4
R2)
R2)
FF
2,4
2,4
F1,3
F1,4
F
1,4
F1,3
F3,4
R
R4
4
F
F3,4
F2,3
F2,4
F1,3
1,3
2,3 R )]
(R
[(R3
R2) F
2
4
F3,4
4,3
F2,3
(R3
R3
R
3
R2)
Esempio di applicazione
dell’algoritmo PSOJ
[(R3
F2,3
R2)
F3,4
(R4
F2,4
R2)]
F1,3
F1,2
[(R1
R2)
F1,4
(R4
F2,4
R2)]
Conclusioni
• Come procedere al calcolo della full disjunction?
Gradi di Ciclicità degli Ipergrafi
Per i grafi la nozione di ciclicità è standard:
Un grafo è ciclico se esiste un percorso che ha inizio e termine sullo stesso nodo
Per gli ipergrafi sono stati introdotti vari gradi di ciclicità:
• -ciclicità
• -ciclicità
• -ciclicità
• Berge-ciclicità
Si ha che:
Berge-aciclicità  -aciclicità  -aciclicità  -aciclicità
Per la nostra trattazione sono importanti i concetti di -ciclicità e -ciclicità
-ciclicità e -ciclicità
Schema -ciclico
Schema -ciclico
I Limiti dell’Algoritmo
Il limite dell’algoritmo sono gli ipergrafi -ciclici e -aciclici, ma utilizzando il
full outerjoin invece che il natural outerjoin la situazione è diversa.
Gli ipergrafi sono progettati per l’operatore di natural outerjoin
e quindi su join basati su tutti gli attributi comuni alle relazioni.
I -cicli portano al fallimento dell’algoritmo solo se sono formati da attributi
di join; quindi alcuni ipergrafi -ciclici possono essere affrontati dall’algoritmo,
a seconda delle condizioni di join.
Riefinendo gli ipergrafi usando come nodi solo gli attributi di join
e come iperarchi solo gli attributi di join delle relazioni quanto detto finora
vale anche per il full outerjoin.
La Motivazione dell’Ordinamento
L’algoritmo si basa sul concetto che:
FD(Li,Lj) = Li=Fij=Lj
Essendo la full disjunction una relazione:
FD(FD(Li,Lj),FD(Li,Lk)) = FD(Li,Lj)=Fjk=FD(Li,Lk)
Queste uguaglianze valgono se e solo se:
Li=Fij=Lj = LiFijLj  Li  Lj
che vale se e solo se Li ed Lj non hanno tuple sussunte.
L’ipotesi di consistenza dei join assicura la validità della proprietà per le relazioni
base, ma non viene assicurato niente per i passaggi successivi.
Perché ciò avvenga è necessario preservare tale ipotesi attraverso un ordinamento.
L’Ordinamento da Utilizzare
Dato un grafo G=(V,E) con V={R1,…,Rn} e E={(Ri,Rj) | Ri,Rj V, Fij  NULL}
si definisce nodo ammissibile un nodo Ri V se, essendo RJ=Rj1,…,Rjn
l’insieme di tutti i nodi collegati direttamente a Ri, esiste un percorso di
G=(V,E) con V=V - {Ri} e E={(Ri,Rj) | Ri,Rj V, Fij  NULL} che colleghi
tutti i componenti di RJ tra loro. Si definisce G l’insieme di tutti i nodi
ammissibili del grafo G.
Dato un grafo G=(V,E) con V={R1,…,Rn} e E={(Ri,Rj) | Ri,Rj V, Fij  NULL}
e dato l’insieme di tutti i nodi ammissibili di G, si definisce funzione di ricerca
fric(G) una funzione che, dato G, restituisce l’insieme V V tale che:
V={Ri  G | (Ri,Rj)  E, Rj | (Rj,Rk)  E,
Fjk  ((S(Ri)  S(Rj)) - (S(Ri)  S(Rj)))= }
con Ri  Rj  Rk  V
L’Ordinamento da Utilizzare
E’ necessario cercare un ordinamento un’unica volta, dati gli schemi delle relazioni
e le condizioni di join.
Non esiste sempre un ordinamento, ma se esiste va ricercato prima tra i nodi
che ad ogni passo hanno join che coinvolgono il maggior numero di attributi.
Esempio:
Grafo non risolubile
Grafo risolubile
Le Modifiche dell’Algoritmo
• Nei grafi non totalmente connessi per evitare la disconnessione
si prendono per primi i nodi con un numero minore di connessioni
FALSO
esempio:
Soluzione:
Si può usare un nodo se e solo se dopo la sua eliminazione esiste un percorso
che congiunga tutti i nodi a cui questo è direttamente connesso.
Dato un grafo G ed un nodo Li G, l’utilizzo del nodo Li non disconnette G
se e solo se
 Lj  Fij  NULL  Lk  Fjk  NULL, Fik  NULL
con i  j  k
dove Fij indica la condizione di join tra le fonti Li e Lj.
Le Modifiche dell’Algoritmo
• La condizione di join “False” viene vista come un qualsiasi join ed affrontata
con l’operatore di outerjoin.
ERRATO
“False” indica che l’insieme degli oggetti contenuti nelle due classi è disgiunto.
Un join produrrebbe un prodotto cartesiano, creando congiunzioni che non
devono esistere.
Soluzione
• Trattare le condizioni di join “False” come assenti
oppure
• Utilizzare l’operatore di outerunion
Le Modifiche dell’Algoritmo
• Nel caso di grafi completamente connessi non è necessario un ordinamento.
ERRATO
Esempio:
La Riscrittura della Query
Query globale: Q
Query locale per la classe L: QL
1. Normalizzazione della query Q
Si riscrive Q nella forma Qd=C1Cn dove Ci=P1Pn
con Pi predicati atomici
2. Scrittura della condizione where per QL:
Tutti i fattori di Qd che possono essere ricercati in L
3. Scrittura della condizione residua di Q
Tutti i fattori non compresi in tutte le condizione where locali
4. Scrittura della select list di QL
Per ogni classe locale L gli attributi:
della select list di Q + di join per L + della condizione residua
Tutti gli attributi devono essere tradotti tramite la mapping table.
La query globale viene riformulata tramite la full disjunction
basata sulla join table e tramite la condizione residua
La Riscrittura e la Funzione di
Risoluzione Generalizzata
L1
L2
prezzo
data
codice
prezzo
data
codice
40
9/2
11111
50
10/2
11111
43
1/1
22222
42
10/1
22222
select *
from G
where prezzo<45 and data>1/2
select *
from Li
where prezzo<45 and data>1/2
tuple risultanti da L1
tuple risultanti da L2
prezzo
data
codice
prezzo
data
codice
40
9/2
11111



Non ci sono conflitti: la tupla di L1 costituisce il risultato restituito
La Riscrittura e la Funzione di
Risoluzione Generalizzata
select *
from Li
select *
from G
tuple restituite da L1
tuple restituite da L2
prezzo
data
codice
prezzo
data
codice
40
9/2
11111
50
10/2
11111
43
1/1
22222
42
10/1
33333
Conflitto di prezzo su 11111. Si sceglie il valore più aggiornato.
Conflitto di data su 11111. Si sceglie il valore più elevato.
tuple restituite da G
prezzo
data
codice
50
10/2
11111
43
1/1
22222
42
10/1
33333
La Riscrittura e la Funzione di
Risoluzione Generalizzata
select *
from G
where prezzo<45 and Data>1/2
select *
from G
tuple restituite da G
tuple restituite da G
prezzo
data
codice
prezzo
data
codice
40
9/2
11111
50
10/2
11111
43
1/1
22222
42
10/1
33333
I risultati della prima esecuzione non sono un sottoinsieme dei risultati della seconda
e quindi sono errati. Le condizioni di selezione poste su attributi che usano funzioni
di risoluzione generalizzate devono fare parte esclusivamente della clausola residua,
senza considerare che siano o meno mappate su tutte le classi locali, e non devono
essere spedite alla classi locali.
La Riscrittura e la Funzione di
Risoluzione Generalizzata
select *
from G
where prezzo<45 and Data>1/2
tuple restituite da L1
select *
from Li
where Data>1/2
tuple restituite da L2
prezzo
data
codice
prezzo
data
codice
40
9/2
11111
50
10/2
11111
tuple restituite da G
G
prezzo
data
codice
50
10/2
11111
prezzo<45
prezzo
data
codice


