Data integration: differenze tra le versioni

Versione delle 20:37, 6 dic 2016

Versione delle 20:40, 6 dic 2016

Riga 53:

La teoria dell'elaborazione di query in un sistema di data integration systems è comunemente espressa utilizzando interrogazioni congiuntive [[Linguaggio di interrogazione|interrogazioni]] e [[Datalog]], un linguaggio di [[programmazione logica]] puramente dichiarativo.<ref name="reffive">{{cite conference | author=[[Jeffrey D. Ullman]] | title=Information Integration Using Logical Views | booktitle=ICDT 1997 | year=1997 | pages=19–40 | url=http://www-db.stanford.edu/pub/papers/integration-using-views.ps}}</ref> Si può liberamente pensare ad una [[query]] come una funzione logica applicata alle relazioni del database come "<math>f(A,B)</math> dove <math>A < B</math>". Se una tupla o insieme di tuple è sostituito nella regole e la soddisfa (cioè la rende vera), allora consideriamo quella tupla parte dell'insieme di risposte alla query. Mentre il linguaggi formali in stile [[Datalog]] esprimono queste query sinteticamente e senza ambiguità, anche le query [[SQL]] comuni contano come query congiuntive.

In termini di integrazione dei dati, il "contenimento delle query" raoppresentarappresenta un'importante proprietà delle query congiuntive. Una query <math>A</math> contiene un'altra quuery <math>B</math> (in simboli <math>A \supset B</math>) se i risultati di <math>B</math> sono un sottoinsieme dei risultati di <math>A</math> per ogni database. Le due query sono dette equivalenti se gli insiemi risultanti sono uguali per ogni database. Questo è importante perché in entrambi i sistemi GAV e LAV, un utente pone query congiuntive su uno schema virtuale rappresentato da un insieme di [[Vista (basi di dati)|viste]], o query congiuntive [[Vista materializzata |materializzate]]. L'integrazione si propone di riscrivere le query rappresentate dalle viste al fine di rendere i loro risultati equivalenti o al massimo contenuti nella richiesta del nostro utente. Ciò corrisponde al problema di rispondere a interrogazioni usando le viste.<ref name="refsix">{{cite conference | author=[[Alon Y. Halevy]] | title=Answering queries using views: A survey | booktitle=The VLDB Journal | year=2001 | pages=270–294 | url=http://www.cs.uwaterloo.ca/~david/cs740/answering-queries-using-views.pdf}}</ref>

Nei sistemi GAV, un progettista scrive il codice del mediatore per definire la riscrittura delle query. Ogni elemento nella query dell'utente corrisponde a una regola di sostituzione proprio come ogni elemento nello schema globale corrisponde a una query sulla sorgente. L'elaborazione delle query espande semplicemente i sotto-obiettivi della query dell'utente secondo le regole specificate nel mediatore, perciò la query risultante è probabile che sia equivalente. Mentre il progettista fa la maggior parte del lavoro in anticipo, alcuni sistemi GAV come [http://www-db.stanford.edu/tsimmis/ Tsimmis] comportano la semplificazione del processo di descrizione del mediatore.

Nei sistemi LAV, le query vengono sottoposte a un processo più radicale di riscrittura perché non esiste alcun mediatore che allinei le query dell'utente con una semplice strategia di espansione. Il sistema di integrazione deve eseguire una ricerca sullo spazio delle possibili query al fine di trovare la riscrittura migliore. La riscrittura risultante potrebbe non essere una query equivalente, ma massimamente contenuta, e le tuple restituite incomplete. {{Dal | 2009}} l'algoritmo MiniCon <ref name="refsix" /> è l'algoritmo capofila nella riscrittura di query per i sistemi di data integration LAV.

In generale, la complessità di riscrittura delle query è [[NP-completo]].<ref name="refsix" /> Se lo spazio delle riscritture è relativamente piccolo questo non rappresenta un problema — anche per sistemi di integrazione con centinaia di sorgenti.