Seminario di Ingegneria del
software
Studio della composizione di
servizi attraverso l’uso di tecniche
del data integration
Autore: Paolo Urbano
Docente: Giuseppe De Giacomo
•
A View Integration Approach to Dynamic Composition of Web Services
Snehal Thakkar, Craig Knoblock and José Luis Ambite
Workshop on Planning for Web Services, The 13th International Conference
on Automated Planning & Scheduling (ICAPS 2003), Trento, Italy, 2003.
•
A Data Integration Approach to Automatically Composing and Optimizing
Web Services
Snehal Thakkar, José Luis Ambite and Craig A. Knoblock
In Proceeding of 2004 ICAPS Workshop on Planning and Scheduling for Web
and Grid Services, June 2004.
•
Composing, optimizing, and executing plans for bioinformatics web services,
Snehal Thakkar, Jose Luis Ambite, and Craig A. Knoblock.
VLDB Journal, Special Issue on Data Management, Analysis and Mining for
Life Sciences, 14(3):330--353, Sep 2005.
•
Retrieving and Semantically Integrating Heterogeneous Data from the Web.
Martin Michalowski, José Luis Ambite, Craig A. Knoblock, Steve Minton,
Snehal Thakkar, and Rattapoom Tuchinda
IEEE Intelligent Systems., Vol. 19, No. 3, 2004, pp. 72-79.
Introduzione
• Il potenziale dei web services può essere sfruttato solo se si effettua
la composizione dei servizi.
• In questo approccio vediamo i web services come sorgenti di dati.
• I primi tre articoli fanno uso di tali principi: i primi due illustrano le
idee fondamentali e il terzo è un esempio di applicazione al dominio
bioinformatico.
• La composizione completamente automatica di servizi, in risposta
ad una query utente arbitraria, rimane un problema aperto.
A View Integration Approach to Dynamic
Composition of Web Services (/1)
• Scopo: generare un piano d’integrazione universale di web service
per rispondere alle query utente.
• Il Mediatore è l’oggetto che costruisce il piano d’integrazione.
• Il Mediatore tradizionale accetta in input una specifica query utente
q e la riformula come combinazione di query alle sorgenti per
rispondere a q, utilizzando un algoritmo di riformulazione di query.
• In questo articolo modifichiamo l’inverse rule algorithm per produrre
un web service integrato che possa rispondere ad un range di query.
A View Integration Approach to Dynamic
Composition of Web Services (/2)
Esempio conduttore:
Ogni web service è rappresentato come un predicato:
CitytoCounty(city’, state’, county)
LAProperty(address’, city, value)
NYProperty(address’, city’, county, value)
YellowPages(name’, city’, state, address, phone)
Gli attributi apostrofati sono richiesti come input del servizio, sugli altri non vi è nessun
tipo di restrizione.
Query utente:
Trova il valore fiscale delle proprietà di tutte le ubicazioni ‘Burger King’
nella città di ‘Torrance’ nello stato della California (‘CA’).
A View Integration Approach to Dynamic
Composition of Web Services (/3)
• Passi fondamentali:
1) Query utente  Insieme di query datalog
2) Insieme di query datalog  Theseus
Theseus è un meccanismo di esecuzione di query che permette il
parallelismo delle operazioni e l’invio di un flusso di dati tra i vari
componenti del piano d’integrazione generato.
A View Integration Approach to Dynamic
Composition of Web Services (/4)
Predicati del Mediatore:
Location(locid, address, city, county, state)
Value(locid, value)
Business(name, locid, phone)
Definizione delle sorgenti (approccio LAV):
R1: LAProperty(address, city, value):Location(locid, address, city, county, state) ^ Value(locid, value) ^
county = ‘LA’^ state = ‘CA’
R2: NYProperty(address, city, county, value):Location(locid, address, city, county, state) ^ Value(locid, value) ^
state = ‘NY’
A View Integration Approach to Dynamic
Composition of Web Services (/5)
R3: YellowPages(name, address, city, state, phone) :- Business(name,
locid, phone)^ Location(locid, address, city, county, state)
R4: CitytoCounty(city, state, county):Locations(locid, address, city, county, state)
A View Integration Approach to Dynamic
Composition of Web Services (/5)
• La fase 1 consiste nell’invertire le definizioni delle viste per ottenere
quelle delle relazioni globali sulle sorgenti:
Per ogni definizione V(X) :- S1(X1),…,Sn(Xn), dove X e Xi si riferiscono
all’insieme di attributi nelle relazioni e nelle viste
corrispondenti, l’Inverse
Rule Algorithm genera n regole del tipo: Si(Xi’) :- V(X), dove la differenza tra gli
insiemi X’ e X è che in X’ ci possono essere simboli di funzione.
R1: LAProperty(address, city, value):Location(locid, address, city, county, state) ^ Value(locid, value) ^
county = ‘LA’^ state = ‘CA’

IR1: Location( f1locid(a, ci, v), a , ci, ‘LA’, ‘CA’) :- LAProperty(a, ci, v)
IR2: Value(f1val(a, ci, v), v) :- LAProperty(a, ci, v)
A View Integration Approach to Dynamic
Composition of Web Services (/6)
La Fase 2 consiste nel trasformare l’insieme di regole datalog
prodotte dalla Fase 1, unitamente alla query utente, nel linguaggio
di Theseus:
costruzione di moduli;
ogni modulo rappresenta un’operazione;
ogni operazione prende in input e restituisce in output un insieme
di relazioni
InRel(name’, city’, state’,
value)
Corrisponde all’esecuzione
della inverse rule
Business(n, f1bus(n, a, ci, s, p), p):YellowPages(n, ,a, ci, s, p)
Corrisponde all’esecuzione
delle inverse rule IR1 e IR2
Tutti i web service sulle
tasse delle proprietà sono
interrogati in parallelo.
A View Integration Approach to Dynamic
Composition of Web Services (/7)
Problema:
• Il Mediatore deve generare un nuovo piano d’integrazione per ogni
query utente, anche se, per esempio, cambiano solo i valori delle
costanti.
Idea:
• Il Mediatore diventa un generatore di web service:
accetta una query utente e genera un web service capace di
rispondere ad una classe di query, alla quale apparitene anche
la query data.
A View Integration Approach to Dynamic
Composition of Web Services (/8)
• Generalizzazione di una query:
Le tecniche per generalizzare le query si basano, generalmente,
sulle combinazioni degli attributi sui quali generalizzare.
Qui viene utilizzata una “generalizzazione completa”, cioè una
generalizzazione su tutti i parametri, la query diventa:
‘Trova i valori fiscali di tutte le proprietà di una certa attività in una data
città di un certo stato.’
A View Integration Approach to Dynamic
Composition of Web Services (/9)
Problema derivante dall’uso di questa tecnica:
• Il piano generato potrebbe inviare troppe richieste a molte sorgenti
di dati.
Idea: Tuple – Level Filtering Algorithm
Con questa tecnica, ogni sorgente viene interrogata solamente per
l’informazione presente nella sorgente stessa.
A View Integration Approach to Dynamic
Composition of Web Services (/10)
Risultano quindi necessarie due modifiche all’Inverse Rule
Algorithm:
• Le costanti vengono trattate come variabili per generalizzare la
query (il piano risultante avrà la capacità di interrogare sia il web
service relativo alle proprietà della contea di Los Angeles, sia quello
relativo allo stato di New York).
• Le sorgenti vengono interrogate solo con input validi (Il Los Angeles
web service verrà interrogato solo per le proprietà di Los Angeles e
Il New York web service solamente per quelle di Newy York); le
interrogazioni alle sorgenti vengono filtrate utilizzando i vincoli
presenti nelle definizioni delle sorgenti.
A View Integration Approach to Dynamic
Composition of Web Services (/11)
Risultato:
Numero minore di interrogazioni e interrogazioni più ‘sensate’:
• Per una specifica query, solo uno dei web service sulle tasse delle
proprietà viene effettivamente interrogato;
• Le interrogazioni sono filtrate oltre che dalle operazioni di select,
anche da interrogazioni ad altre sorgenti che contengono
informazioni che permettono di risparmiare ulteriormente.
Il Mediatore, a partire
dal programma
datalog, costruisce il
piano d’integrazione
che viene eseguito
da Theseus.
L’informazione sulle
Tasse è ottenuta
facendo uso anche
del web service
CityToCounty
Il Mediatore restituisce
all’utente l’URL del
nuovo servizio generato
A Data Integration Approach to Automatically
Composing and Optimizing Web Services(/1)
• La novità sostanziale di questo articolo è rappresentata
dall’implementazione di metodi per ottimizzare l’esecuzione della
composizione di web service
• Oltre al funzionamento del Tuple – Level Filtering Algorithm, per
ridurre il numero di richieste ai web service, sarànno utilizzate delle
interrogazioni aggiuntive per ottimizzare ulteriormente l’esecuzione.
A Data Integration Approach to Automatically
Composing and Optimizing Web Services(/2)
Oltre alle descrizioni delle sorgenti, vengono fornite al sistema, dall’esperto
del dominio, le dipendenze funzionali, nel nostro caso, per esempio,
consideriamo la dipendenza funzionale:
<address, city, state>  <value>
Avremo in input al Mediatore:
FR1: equals(value, value’) :BusinessProperties(name, addr, city, county,
state, zip, phone, value)^
BusinessProperties(name’, addr’, city’, county’,
state’, zip’, phone’, value’)^
equals(addr, addr’)^
equals(city, city’)^
equals(state, state’)
FR2: equals(x, z) :- equals(x, y) ^ equals(y, z)
A Data Integration Approach to Automatically
Composing and Optimizing Web Services(/3)
Consideriamo il programma datalog generato dal sistema:
PR1: Q1(name, addr, city, cty, st, zip, ph, val):YellowPages(name, zip, city, st, addr, ph)^
name = <name>^
LAProperty(addr, city, zip, val)
PR2: Q1(name, addr, city, cty, st, zip, ph, val):YellowPages(name, zip, city, st, addr, ph)^
name = <name>^
TNProperty(addr, city, cty, zip, val)
Il Tuple Level – Filtering Algorithm fornisce al programma i valori dei
parametri per effettuare le operazioni di filtraggio.
A Data Integration Approach to Automatically
Composing and Optimizing Web Services(/4)
Passi fondamentali del Tuple – Level filtering Algorithm:
• Analizza la lista delle chiamate di sorgente:
•
Per ogni definizione di sorgente esamina i vincoli:
1)
Se il valore dell’attributo coinvolto è presente nel corpo
di una Inverse Rule inserisce il vincolo di filtraggio
2)
Altrimenti inserisci una ‘sensing operation’ per
recuperare il valore del parametro
A Data Integration Approach to Automatically
Composing and Optimizing Web Services(/5)
1) L’algoritmo fa uso di vincoli di uguaglianza e di ordinamento
per ridurre l’ampiezza delle query:
TR1: Q1(name, addr, city, cty, st, zip, ph, val):YellowPages(name, zip, city, st, addr, ph)^
name = <name>^
st = ‘CA’^
LAProperty(addr, city, zip, val)
TR2: Q1(name, addr, city, cty, st, zip, ph, val):YellowPages(name, zip, city, st, addr, ph)^
name = <name>^
st = ‘TN’^
TNProperty(addr, city, cty, zip, val)
A Data Integration Approach to Automatically
Composing and Optimizing Web Services(/6)
2) Il Mediatore può chiamare altri servizi per recuperare i valori degli
attributi richiesti: sensing operation
Il programma datalog ottimizzato include la chiamata al servizio
CityToCounty per produrre il vincolo: County = ‘Los Angeles’
SR1: Q1(name, addr, city, cty, st, zip, ph, val):YellowPages(name, zip, city, st, addr, ph)^
name = <name>^ st = ‘CA’^
CitytoCounty(city, st, cty)^cty = ‘Los Angeles’^
LAProperty(addr, city, zip, val)
SR2: Q1(name, addr, city, cty, st, zip, ph, val):YellowPages(name, zip, city, st, addr, ph)^
name = <name>^st = ‘TN’^
TNProperty(addr, city, cty, zip, val)
A Data Integration Approach to Automatically
Composing and Optimizing Web Services(/7)
Risultati sperimentali
Query:
‘Richiesta di creare un web service che accetta il nome di
un’attività e fornisce la lista delle ubicazioni di tali attività e i loro
valori fiscali’
Input #tuple
PagGialle
356
#tuple
Tennesse
#tuple
California
#tuple
Los
Angeles
Inverse
Rule
T-L
Filtering
With
Sensing
17
10
4
8747 sec
92 sec
88 sec
A Data Integration Approach to Automatically
Composing and Optimizing Web Services(/8)
• L’applicazione delle tecniche di ottimizzazione descritte ha ridotto il
tempo di esecuzione di due ordini di grandezza.
• In generale, il Tuple – Level Filtering Algorithm, con o senza sensing
operation, è notevolmente efficace nei domini dove più attributi
possono essere utilizzati per ridurre le richieste a differenti web
service. Per esempio: integrare l’informazione proveniente dai
giornali locali o dai produttori di automobili.
Composing, optimizing, and executing plans
for bioinformatics web services(/1)
• Questo articolo descrive un’applicazione dei risultati precedenti al
dominio bioinformatico.
• Consiste nella composizione automatica di piani d’integrazione
parametrizzati per web service di tipo informativo:
il sistema crea un piano d’integrazione che accetta i valori dei
parametri forniti in input, recupera ed integra l’informazione dai web
service rilevanti e restituisce il risultato all’utente.
• I valori dei parametri di input non sono noti al tempo di
composizione del piano.
Composing, optimizing, and executing plans
for bioinformatics web services(/2)
Dominio: ci sono diversi web service, che modellano l’informazione
sui vari tipi di proteine e sulle interazioni tra le proteine stesse:
Composing, optimizing, and executing plans
for bioinformatics web services(/3)
• Query: creare un web service che accetta l’identificatore di una
proteina, interroga le sorgenti rilevanti e restituisce l’informazione
all’utente sulla sequenza della proteina stessa e le informazioni sulle
proteine con le quali interagisce direttamente o indirettamente:
Le entità Protein e Protein – Protein Interaction sono entità virtuali
Composing, optimizing, and executing plans
for bioinformatics web services(/4)
Composing, optimizing, and executing plans
for bioinformatics web services(/5)
Domain Rule: permette
di esprimere la
chiusura transitiva
della relazione
Protein – Protein
Interaction,per non
perdere l’informazione
sull’interazione indiretta
tra le proteine.
Composing, optimizing, and executing plans
for bioinformatics web services(/6)
Applicazione dell’Inverse Rule Algorithm:
In questo caso la
corrispondenza tra le
definizioni di sorgente
e le regole inverse
è 1 a 1 (in generale,
è 1 a n).
Composing, optimizing, and executing plans
for bioinformatics web services(/7)
• Il Mediatore combina la query utente, le regole inverse rilevanti e la
domain rule per generare un piano universale, capace di rispondere
alla classe di query alla quale appartiene anche quella iniziale:
Nel piano sono presenti anche
le sorgenti
MMProtein e MMProtein Interaction,
anche se non servono alla
query iniziale.
A questo punto diventa necessario
ottimizzare l’esecuzione del piano
d’integrazione generato per rimuovere
le richieste inutili alle sorgenti
(il valore dei parametri è noto solo
a tempo di esecuzione).
Composing, optimizing, and executing plans
for bioinformatics web services(/8)
Applicazione delle tecniche di ottimizzazione:
• Consideriamo la richiesta di creare un web service che accetta
l’identificatore di una proteina e il valore taxonid (un valore che
rappresenta il tipo di proteina) e trova tutte le interazioni protein –
proteina.
• L’algoritmo utilizza i vincoli sull’attributo taxonid ed aggiunge i vincoli
di filtraggio prima di interrogare il web service:
Composing, optimizing, and executing plans
for bioinformatics web services(/9)
Aggiunta di una ‘sensing operation’:
• L’algoritmo interroga la sorgente SS per ottenere i valori dei
parametri non ancora noti
Composing, optimizing, and executing plans
for bioinformatics web services(/10)
• Siccome sussiste l’ipotesi di ‘mondo aperto’, le risposte alle query
potrebbero non essere complete, diventa, quindi, necessario
recuperare le tuple eventualmente perse:
In questo modo non vi sono tuple in meno
rispetto al risultato della query iniziale.
Per garantire la correttezza
della tecnica utilizzata, non ci
devono essere nemmeno tuple in più
rispetto al risultato della query originaria:
il Tuple – Level Filtering Algorithm
verifica le ‘condizioni di compatibilità’
prima di interrogare una sorgente
aggiuntiva, tra le quali vi è il vincolo
che il risultato della query ottimizzata
sia un sottoinsieme di quello della query originale.
Composing, optimizing, and executing plans
for bioinformatics web services(/11)
• Piano effettivamente eseguito dal sistema:
viene inserita una richiesta alla sorgente DipProtein (sensing
operation) e successivamente il vincolo taxonid = 9606 (filtering
operation) prima delle richieste ai web service riguardanti le
proteine.
Composing, optimizing, and executing plans
for bioinformatics web services(/12)
Conclusioni:
• Grazie alla modularità del lavoro svolto, i vari strumenti sviluppati
possono essere utlizzati indipendentemente gli uni dagli altri:
Theseus come meccanismo di esecuzione dei piani generati;
Tuple – Level Filtering Algorithm, con o senza sensing operation, per
ottimizzare l’esecuzione dei piani;
L’inverse Rule Algorithm come algoritmo di riformulazione di query.
Composing, optimizing, and executing plans
for bioinformatics web services(/13)
Sviluppi futuri
• Strategie per stabilire efficientemente come determinare i vincoli
utilizzati per generalizzare la query utente.
• Modellare in maniera automatica il nuovo web service generato
dalla richiesta dell’utente come sorgente di dati nel dominio del
mediatore (questo può essere ottenuto rappresentando il nuovo web
service tramite la struttura della query).
• Facilitare l’integrazione intelligente di web service differenti.
Retriving and semantically integrating
heterogeneous data from the web(/1)
Questo articolo utilizza le idee chiave degli studi precedenti e fornisce
strumenti complessi d’integrazione semantica dei dati.
Concetti chiave dell’articolo:
• Realizzazione di tecnologie in grado di integrare i dati descritti in
ontologie diverse, per esempio le immagini e i dati strutturati.
• Riconoscere quando più oggetti in differenti siti rappresentano lo
stesso oggetto nel mondo reale.
Retriving and semantically integrating
heterogeneous data from the web(/2)
• Building Finder integra le immagini provenienti dal satellite e i dati
strutturati e semistrutturati di varie sorgenti online utilizzando il
semantic web.
• L’utente può interrogare una vista integrata di queste sorgenti e
richiedere a Building Finder di sovrapporre accuratamente le
informazioni riguardanti edifici e strade alle immagini del satellite.
Retriving and semantically integrating
heterogeneous data from the web(/3)
• I dati raccolti sono eterogenei anche in termini di come
l’applicazione accede alle sorgenti:
alle immagini del satellite tramite Microsoft’s web service TerraService, alle strade tramite US Census Bureau’s Tigerline file(un
database dell’università della california del sud);
inoltre accede all’informazione presente in Los Angeles Property Tax
Information Web Site e a Yahoo Yellow Page Web Site.
• L’utente può utilizzare Building Finder per mezzo di un’interfaccia
che fa uso di agenti che interrogano l’applicazione con RDF Data
Query Language (RDQL) ed ottenendo i risultati in RDF.
Retriving and semantically integrating
heterogeneous data from the web(/4)
Strumenti per l’integrazione di dati efficiente:
1)
Tecniche di apprendimento automatico per convertire i siti
tradizionali e i database in web services.
2)
Record Linkage System per consolidare i dati presenti in sorgenti
diverse che si riferiscono alla stessa entità.
3)
Mediatore che fornisce accesso uniforme ai dati.
4)
Sistema di esecuzione di query efficiente.
Retriving and semantically integrating
heterogeneous data from the web(/5)
(1)
Wrapping delle sorgenti online:
•
E’ necessario poiché l’ampiezza e la profondità delle query non favoriscono
l’uso di sistemi di immagazzinamento dei dati localmente.
Le pagine web sono scritte in HTML quindi estrarre i dati diventa un lavoro
complicato perché i tag non possiedono una semantica ben precisa.
I wrapper devono ‘imparare’ ad estrarre i dati rilevanti cercando un percorso
che li conduca ai dati d’interesse: possiamo utilizzare una tecnica di
ragionamento automatico chiamata Wrapper Rule Learning; per esempio,
per estrarre i nomi delle persone possiamo notare che il dato è presente
dopo <HTML>Name:<b> e prima di </b>.
•
•
Retriving and semantically integrating
heterogeneous data from the web(/6)
(2)
Record Linkage System:
•
Rispondere al problema: gli stessi oggetti possono esistere in formati
differenti e la ricerca di un oggetto può restituire risultati multipli.
Active Atlas individua gli attributi comuni di oggetti, apparentemente diversi,
per identificare un matching tra gli oggetti stessi:
- seleziona una sorgente primaria per il nome dell’entità e fornisce un
mapping tra tale sorgente ed ogni altra che fornisce un nome differente.
Il sistema può imparare che ‘Rep’, in una sorgente, è comunemente usato
come abbreviazione di ‘Republic’, che una sorgente utilizza spesso
acronimi, che un’altra rappresenta le persone con ‘Nome e Cognome’,
mentre un’altra ancora con ‘Cognome e Nome’.
Uso congiunto di un sistema di consolidamento di oggetti e di un mediatore:
il mediatore, in questo caso, serve ad individuare automaticamente quali
sorgenti secondarie interrogare nel caso in cui il sistema di consolidamento
di oggetti non possa determinare se due oggetti si riferiscono alla stessa
entità.
•
•
Retriving and semantically integrating
heterogeneous data from the web(/7)
(3)
Il Mediatore:
Prometheus
Obiettivo: fornire un accesso unico alle varie sorgenti di dati.
L’utente invia una query attraverso l’interfaccia oppure formula una RDQL
query, e il Mediatore restituisce il risultato all’interfaccia.
Retriving and semantically integrating
heterogeneous data from the web(/8)
A)
B)
C)
I tre componenti principali di Prometheus:
Modello di dati
Riformulazione di query
Convertitore Datalog  Theseus
Retriving and semantically integrating
heterogeneous data from the web(/9)
A) Il Modello dei dati:
Building Finder usa i predicati di dominio Street, Image e Building.
L’utente può interrogare il sistema attraverso l’uso di questi predicati
(definiti secondo l’approccio GAV)
Retriving and semantically integrating
heterogeneous data from the web(/10)
B)
Riformulazione di query:
alla ricezione della query, Prometheus unisce la query al modello
del dominio e genera un programma Datalog in grado di
rispondere alla query.
C)
Convertitore:
Prometheus converte il programma Datalog per farlo eseguire a
Theseus.
Retriving and semantically integrating
heterogeneous data from the web(/11)
4)
Esecuzione efficiente di query
Cause di inefficienza:
• presenza di sorgenti multiple;
• ritardi di rete e/o dovuti alla capacità delle sorgenti di
elaborare le richieste;
• vincoli di precedenza tra le sorgenti di dati.
Retriving and semantically integrating
heterogeneous data from the web(/12)
Parallelismo orizzontale e verticale in Theseus:
•
orizzontale: esecuzione decentralizzata, gli operatori (le
funzioni) lavorano indipendentemente gli uni dagli altri.
•
verticale: gli operatori si attivano appena il loro input diviene
disponibile e passano il risultato agli altri operatori in modalità
pipeline.
Attivazione degli operatori per il recupero dell’informazione riguardante
le tasse sulle proprietà e le informazioni sugli edifici:
Retriving and semantically integrating
heterogeneous data from the web(/13)
Confronto tra quest’approccio rispetto a quello basato sul
datawarehousing spesso utilizzato nel semantic web:
• il sistema accede a dati sempre ‘freschi’ (nel datawarehousing i dati
potrebbero essere modificati prima del ciclo di aggiornamento del
warehouse)
• l’applicazione è più scalabile: i dati disponibili sul web crescono
molto e diventa difficile ospitarli localmente
• cambiare l’ontologia del mediatore e le definizioni delle sorgenti
(approccio GAV) è più facile piuttosto di ricostruire il datawarehouse.
Retriving and semantically integrating
heterogeneous data from the web(/14)
Applicazione possibile:
Gestione dei disastri: Building Finder potrebbe, in tale eventualità,
risultare utile per ottenere informazioni sulle aree affette, inclusi i
nomi delle strade e degli edifici.
Sviluppi futuri:
Integrare le sorgenti utilizzando tecniche Object Oriented, ragionando
sulle classi, come in OWL e RDF, piuttosto che limitarsi alle regole
Datalog.
Sensing source e binding pattern
Entrambi le tecniche possono essere utilizzate per recuperare i
valori degli attributi mancanti.
Confronto diventa tra l’applicazione delle sensing operation e i
risultati teorici sul binding pattern.
Analisi e dimostrazione della validità:
•
del Tuple – Level Filtering
•
del binding pattern
Compatibilità di una sorgente
Teorema
Dato un piano d’integrazione Q, generato utilizzando l’algoritmo
dell’Inverse Rule in risposta ad una query utente, il Tuple – Level
Filtering produce un nuovo piano d’integrazione Q’, contenente filtri
e sensing operation, tale che Q=Q’.
Dimostrazione
date le definizioni delle sorgenti:
e consideriamo le seguenti query:
• caso 1:
la tupla [X, Z] appartiene alla prima regola di Q’
allora deve appartenere anche alla sottoformula
• caso 2:
la tupla [X, Z] appartiene alla seconda regola di Q’
allora anch’essa deve appartenere anche alla sottoformula
• caso1:
Supponiamo che esistono Y’, Z’ tali che
Allora se [X, Z] appartiene a
Dovrà appartenere anche alla seconda regola di Q’
• caso 2:
Supponiamo che esistono Y’, Z’ tali che
Allora se [X, Z] appartiene a
Dovrà appartenere anche alla prima regola di Q’.
• caso 3:
Supponiamo che esistono Y’, Z’ tali che
sviluppiamo la definizione di SS, si ha che
Per la definizione di SF, inoltre:
Allora,
• caso 3…continua:
Tuttavia, la VI condizione della verifica della compatibilità della
sorgente deve essere anch’essa soddisfatta
Ma allora esiste una tupla che appartiene al corpo della prima query e
non alla seconda.
Assurdo.
Il Tuple – Level Filtering non modifica la semantica della query utente.
c.v.d.
Computing Complete Answers to Queries in
the Presence of Limited
Access Patterns
• Studio della stabilità di varie classi di query
Una query è stabile se la sua risposta completa può essere
calcolata per ogni database costituito dalle relazioni della query
stessa.
• Studio della fattibilità di una query e cerchiamo di metterla in
relazione con la stabilità.
L’ordine dei sottogoal di una query è fattibile, se per ogni
sottogoal nell’ordine, le variabili di input o sono costanti o sono
presenti in un sottogoal precedente.
Una query è fattibile se ha un ordine fattibile dei suoi sottogoal.
Esempio di query fattiblie e stabile
Binding adornament di r ed s: ‘bf’
Fattibilità  Stabilità
Lemma:
Una query congiuntiva fattibile è stabile.
Dimostrazione
• Sia Q una CQ che abbia un ordine fattibile dei suoi sottogoal
g1(X1), …gn(Xn).
• Costruzione di un “piano lineare”: calcolare la sequenza di n
relazioni supplementari I1, ...In, tali che la relazione Ii è la relazione
ottenuta dopo che i primi i-1 sottogoal sono stati eseguiti.
continua….
Fattibilità  Stabilità
• Provare che questo piano calcola effettivamente ANS(Q, D):
supponiamo che ogni tupla appartenente ad ANS(Q, D) viene
dalle tuple t1, …tn delle relazioni g1, ..gn, rispettivamente.
Per ogni j=1..n, la tupla
è inclusa nella relazione supplementare
senza variabili irrilevanti (quelle che non appaiono nei
sottogoal successivi o nella testa della query).
Accediamo al j-esimo sottogoal rispettando il suo biinding
pattern (query fattibile) per ottenere la tupla
Otteniamo anche la relazione supplementare n-esima.
Corollari
• Una query congiuntiva è stabile se ha una query equivalente fattibile
• Se una query congiuntiva ha una query equivalente minimale
fattibile, allora la query è stabile
Stabilità  Fattibilità
Lemma:
se la query minimale equivalente ad una query conguntiva non è
fattibile, allora la query non è stabile.
Costruzione di D1 e di D2.
La query non è fattibile quindi almeno un sottogoal rispondibile
UCQ
• Se applichiamo il nostro studio all’unione di query congiuntive
(UCQ) otteniamo:
Sia Q un unione di query congiuntive su relazioni con binding
pattern, Q è stabile se e solo se, per ogni query, la query
minimale equivalente a Q è stabile.
Stabilità di query Datalog
Vediamo un esempio:
Flight(F, T)
una relazione (binding adornament ‘bf’) che rappresenti i voli
nonstop da F a T.
Definiamo la relazione reachable:
RGG: Rule Goal/Graph
Costruiamo l’RGG associato al goal reachable:
Esempio di RGG fattibile
RGG: Rule Goal/Graph
• Costruiamo l’RGG associato al goal reachable, dopo aver invertito
l’ordine dei sottogoal della regola r2:
Esempio di RGG non fattibile
Condizione sufficiente
Il problema di determinare la stabilità di un programma datalog è
indecidibile (anche l’equivalenza di query datalog è indecidibile)
Ci dobbiamo accontentare una condizione sufficiente:
Se un insieme di relazioni con binding pattern ha un RGG fattibile
rispetto ad un query goal, allora la query è stabile
Conclusioni
Questi risultati teorici sono una certificazione del fatto che è
ragionevole utilizzare le tecniche sul binding pattern per ottenere
risposte complete durante il recupero di dati dalle sorgenti. Lo
stesso obiettivo, del resto, che volevamo raggiungere quando
utilizzavamo sorgenti ausiliarie (sensing source) nel Tuple – Level
Filtering per recuperare il valore degli attributi mancanti.