Adaptive query processing for result completeness in the presence of duplicate values
Roald Lengu · 2007
Secondo J. M. Juran, uno dei fondatori delle management and quality theories, i dati sono detti di alta qualita se possono essere utilizzati in modo appropriato per operations, decision making and planning. Il termine Quality of Data (QoD) quindi, si riferisce ad un aspetto multi-dimensionale che esprime una caratteristica intrinseca dei dati offerti, come opposto all’omologo Quality of Service, che si riferisce ad una caratteristica intrinseca di un certo servizio offerto. Si consideri ad esempio uno scenario in cui vogliamo fare il join di due insiemi di tuple su un attributo del primo che condivide lo stesso dominio con un attributo del secondo. Per esempio, si considerino due insiemi: una lista di fermate di autobus, chiamato LBT , in cui ogni fermata viene annotata con l’indirizzo della strada in cui si trova (per esempio diverse linee di Londra, come l’autobus 92, potrebbero avere una fermata annotata con 10 Downing Street); una lista di attrazioni turistiche, chiamato LTA, con i corrispondenti indirizzi (per esempio, Office and home of the prime minister potrebbe essere annotata con 10 Downing St). Si noti che 10 Downing Street e 10 Downing St rappresentano lo stesso oggeto reale e sono quindi dei valori mutuamente duplicati. Il termine duplicato, si riferisce a delle rappresentazioni simili, ma strettamente diverse, della stessa entita (oggetto) reale, in letteratura chiamati anche duplicati fuzzy [CGM05]. Uno dei rischi della presenza dei duplicati e che la completezza del risultato, un aspetto del QoD, potrebbe non essere raggiunta senza ricorso a misure speciali. Nell’esempio di prima, se l’utente volesse trovare quali autobus potrebbe usare per andare a una qualsiasi attrazione turistica, la coppia (92, Office and home of the prime minister) dovrebbe fare parte del risultato, ma in presenza di duplicati questo non potra succedere. Rispondere in maniera efficace ed efficiente alla presenza dei duplicati e essenziale se si spera che il settore di data provision dovrebbe diventare un settore robusto e industrialmente avanzato come quello di service provision. Molta ricerca e gia stata svolta nell’ambito di come un provider dovrebbe risolvere i problemi causati dalla presenza dei duplicati (vedi survey [BS06, EIV07]), pero la maggior parte di questo lavoro consiste in attivita di profiling e di filtraggio offline dei dati, che avvengono in una fase precedente alla generazione dei data product finali distribuiti al consumatore. Da questo punto di vista, una classica contromisura nell’esempio precedente, sarebbe quella di standardizzare le rappresentazioni degli indirizzi. Percio, prima di integrare i due insiemi, noi potremmo gia avere diagnosticato che LTA usa delle abbreviazioni, ed invece LBT usa le forme complete per rappresentare gli indirizzi. In questo caso, si potrebbe applicare una trasformazione ad LBT per farle usare le stesse abbreviazioni di LTA risolvendo il problema offline. In molti casi pero, prendere delle contromisure offline potrebbe non essere vantaggioso o possibile. Potrebbe non essere vantaggioso perche la misura di perturbazione (che e la proporzione dei duplicati nell’insieme) potrebbe essere molto piccola per giustificare una fase preliminare computazionalmente costosa e il conseguente ritardo introdotto nel servizio di data provision. Potrebbe, addirittura non essere possibile, per esempio in scenari di data streaming, dove al provider non viene data l’opportunita di fare data profiling per riconciliare i dati prima della loro consumazione dalla query che genera i prodotti finali contrattati dal consumatore. Anche in casi in cui gli input non fossero degli stream, questi potrebbe appartenere ad una terza parte che le mette a disposizione solo sotto richiesta (come per esempio e normale in scenari di mashup di integrazione on-the-fly) eliminando l’opportunita di disporre di un tempo preliminare per ridurre o eliminare la perturbazione da parte del provider. Sono quindi poche le situazioni in cui si potrebbero effettuare delle operazioni computazionalmente costose di data profiling e data cleaning offline da parte dei provider sui dati che distribuiscono ai loro consumatori. Si noti che la probabilita di avere dei duplicati e alta, soprattutto in quegli scenari, come nel nostro esempio, quando non sembra che questi siano dovuti a degli errori, ma ai risultati di diverse decisioni di design. Nel caso di integrazioni dinamiche on-the-fly (come succederebbe nel nostro caso, se la lista delle fermate e quella delle attrazioni turistiche fossero accedute via web service durante una richiesta ad-hoc da parte di un utente di un sito web), non sarebbe possibile eliminare questo rischio con una misura preventiva perche la scelta degli insiemi e degli attributi da usare e difficile da prevedere nel caso generale. In questa tesi, proponiamo una classe diversa di contromisure che sono appropriate per contesti dinamici piu generici. Noi ci restringiamo al caso in cui i dati sono stati ottenuti come risultato di un join. Dopodiche descriviamo una tecnica di elaborazione di query adattativa (AQP) che permette al provider di confrontare le minacce proferite alla completezza dei dati. La tecnica rileva la presenza inattesa di duplicati nella distribuzione dei valori di un attributo di un insieme che condivide lo stesso dominio con un altro attributo di un altro insieme. La novita piu importante del nostro metodo e che questo cerca di applicare delle contromisure durante la creazione di un data product, invece di applicarle offline come e solito fare, e solo se c’e evidenza che queste servono veramente, invece di farle per default, come e solito fare. In particolare, per garantire la completezza dei risultati in presenza di duplicati, la nostra soluzione usa delle tecniche di rimpiazzamento di operatori in piani di esecuzione pipeline [EFP06] e di join approssimati [CGK06] come segue: l’occorrenza di duplicati in almeno uno degli input del join puo causare uno switch da join esatto a join approssimato, e possibilmente uno reverse switch se i duplicati non vengono piu rilevati. A grandi linee la strategia e la seguente 1. usare un join esatto in presenza di duplicati compromette la completezza dei risultati, 2. usare un join approssimato neutralizza la minaccia provocata dalla presenza dei duplicati, ma risulta computazionalmente piu costoso. Nella nostra soluzione, noi monitoriamo l’esecuzione del join e consideriamo la possibilita di fare lo switch tra join esatto ed approssimato come risposta all’evidenza che la presenza dei duplicati sta minacciando la completezza del risultato, ma teniamo in considerazione i costi computazionali in modo da tenere basso l’overhead di applicare questa contromisura. Quindi, invece di applicare le contromisure come un passo fisso (e quindi pagando un costo computazionale fisso), il nostro metodo fornisce ai provider la possibilita di applicare tali contromisure secondo un approccio di when-needed ed if-required. Oltre alla sua rilevanza pratica, il nostro contributo illustra la versatilita delle tecniche di AQP [DIR07]. Molto spesso, delle tecniche di AQP sono state usate per garantire degli standard di QoS (soprattutto in piani di esecuzione parallela delle query [DIR07]). Questa tesi dimostra che tecniche di AQP possono essere applicate anche a problemi di QoD, in questo caso, alla completezza del risultato in presenza di duplicati. I primi due capitoli di questa tesi (1 e 2) danno una panoramica del lavoro gia svolto nel settore e introducono alcune nozioni preliminary. Queste nozioni vengono ulteriormente usate nei capitoli successivi (3–7) per spiegare il nostro specifico contributo nell’area. I principali contributi di questa tesi sono: symmetric set hash join (sshjoin), un nuovo algoritmo approssimato ed incrementale per eseguire operazioni di join in presenza di duplicati; una nuova tecnica di AQP per garantire QoD; una instanziazione dell’approccio generico, in cui una strategia adattativa viene usata per garantire la completezza del risultato; l’adattamento di un insieme di modelli probabilistici per rilevare la presenza di duplicati negli stream di input al join, insieme ad un confronto teorico e sperimentale della loro efficacia; un’analisi costo-beneficio della nostra strategia adattativa tramite un insieme di risultati sperimentali.