DB Group @ unimo
Università degli studi di Modena e
Reggio Emilia
OTTIMIZZAZIONE DI QUERY
IN MOMIS
Relatore:
Prof. Sonia Bergamaschi
Candidato:
Rodrigue C. Nana Mbinkeu
Correlatore:
Prof: Domenico Beneventano
Anno Accademico 2004-2005
1
DB Group @ unimo
Sommario

Introduzione ai sistemi a mediatori ed al sistema MOMIS

Definizione del Problema: Ottimizzazione di Query di full join in MOMIS

Ottimizzazione del full join : stato dell’arte

Applicazione ed estensione delle tecniche di ottimizzazione del full join

Conclusione e Sviluppi Futuri
2
DB Group @ unimo
Introduzione
Dove trascorrere le vacanze quest’estate ?
SQL
tuple
DB
relational
Agenzie di
Viaggi
OQL
DB
object
hotel
oggetti
Motori
XQuery
XML di ricerca
DB
Semi-Structured
Siti Orari
dei Voli
HTML
API
File
File
File
Text
text
instanze
Application
Text
Informazioni
Paese
Meteo
3
DB Group @ unimo
Sistemi di integrazione dati basati su mediatore
Mediatore
SQL
Wrapper
SQL
DBMS
relational
Agenzie
di Viaggi
tuples
tuple
Wrapper
OQL
DBMS
objet
Gli Hotel
objet
Wrapper
XML
XQuery
Wrapper
Motori
di
ricerca
Wrapper
texti
texti
API
API
DBMS
Semi-Structured
File
File
textFile
text
text
Siti Orari
dei Voli
Informazioni
Paese
instanze
instances
Application
Meteo
4
DB Group @ unimo
MOMIS: Integrazione semantica dei dati
Global Virtual View
(GVV)
Query
Mapping
Local
Schema
Local
Schema
Local
Schema
Source
Source
Source
5
DB Group @ unimo
Mapping Table
Join Conditions
Join Attribute
Resolution Functions
Precedence(L1,L2)
G
COMPANY_ID
SUBCONTR
CAPITAL_STOCK
REGION
ADDRESS
L1.company
COMPANY_ID
L2.company
COMPANY_ID
SUBCONTR
CAPITAL_STOCK
REGION
REGION
ADDRESS
ADDRESS
...
Select COMPANY_ID,
precedence(T_L1.ADDRESS, T_L2.ADRESS) as Address,
T_L2.SUBCONTRACTOR,
…
from L1 full join L2
Full
Disjunction
on (T_L1.COMPANY_ID = T_L2.COMPANY_ID)
6
DB Group @ unimo
Full Disjunction : FJ

FJ : operazione di full join tra n classi locali

Dove



= {L1, L2, …, Ln} sono le classi locali
JC(Li,Lj) condizione di join tra Li e Lj
Attualmente nel Query Manager del sistema MOMIS è implementata tale
operazione
7
DB Group @ unimo
OTTIMIZZAZIONE

Problema:
Ottimizzazione di FJ, ovvero di interrogazioni contenenti l’operatore di full
join.

Stato dell’arte:
Poche tecniche proposte per ottimizzare il full join, rispetto alle numerose
tecniche proposte ed implementate per l’operatore di join

Proposta della tesi:
Estendere le tecniche di ottimizzazione al caso specifico di FJ, ovvero di
interrogazione con full join tra classi locali sulla base delle seguenti ipotesi:

Tutte le classi locali sono connesse tramite join condition

Omogeneità semantica: assenza di conflitti

Join consistenti: associatività dell’operatore di full outer join
8
DB Group @ unimo
Obiettivo dell’ottimizzazione
Query Globale
Forma algebrica
naive
semplificata
 Sostituzione dell’operatore di full outerjoin.
oppure
 Eliminazione delle classi locali : riduzione di
 “Push” delle proiezioni e selezioni.
9
DB Group @ unimo
Semplificazione dell’outerjoin: stato dell’arte
Reject Null [ Galindo-Legaria & Ronsenthal, 1997 ]
Un predicato P Reject Null su A se è valutato FALSE quando A è NULL (┴)
P=(A > 1 and C > 2)
10
DB Group @ unimo
Semplificazione dell’outerjoin: estensione
Introduzione Proprietà duale: NOT NULL PROJECTION
Eliminazione delle tuple nulle dalla risposta
naive
ottimizzata
11
DB Group @ unimo
Esempio di semplificazione
Mapping table
La query viene riscritta in algebra relazionale come segue:
12
DB Group @ unimo
Esempio caso B2
13
DB Group @ unimo
Cosa succede nel sistema MOMIS?
versione naive
Versione ottimizzata
Caso B2
14
DB Group @ unimo
Piano generale di semplificazione
15
DB Group @ unimo
Riduzione degli schemi sugli attributi di proiezione
16
DB Group @ unimo
Esempio di applicazione dell’algoritmo
versione senza riduzione schemi
Versione con riduzione schemi
17
DB Group @ unimo
Riduzione degli schemi in una query
18
DB Group @ unimo
Combinazione delle due tecniche
Risultato (I)
Risultato (II)
19
DB Group @ unimo
Conclusione e Sviluppi Futuri


Ottimizzazione delle Query in MOMIS:
ottimizzazione algebrica delle query contenenti operatori di full join

Applicazione ed estensioni di tecniche a casi specifici

Ottimizzazioni sono molto significative, in quanto consentono sia di ridurre il
numero di classi coinvolte nell'interrogazione sia di sostituire il full outerjoin con
operazioni di join.
Sviluppi Futuri:

Studio delle proprietà rilassando alcune ipotesi

Implementazione nel Query Manager di MOMIS
20