Nana Mbinkeu Rodrigue Carlos 1 DB Group @ unimo OTTIMIZZAZIONE DI QUERY IN MOMIS Università degli...

Nana Mbinkeu Rodrigue Carlos1

DB

Gro

up @

uni

mo

OTTIMIZZAZIONE DI QUERYOTTIMIZZAZIONE DI QUERY IN MOMIS IN MOMIS

Università degli studi di Modena e

Reggio Emilia

Relatore:Prof. Sonia Bergamaschi

Correlatore: Prof: Domenico Beneventano

Anno Accademico 2004-2005

Candidato:Rodrigue C. Nana Mbinkeu


DB

Gro

up @

uni

mo

SommarioSommario

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


DB

Gro

up @

uni

mo

IntroduzioneIntroduzione

DBrelational

ApplicationDBobject

DBSemi-Structured

Agenzie di Viaggi

hotel Siti Orari dei Voli

FileText

Filetext

FileText

InformazioniPaese

Meteo

SQL

tuple OQLoggetti

XQueryXML

Motori di ricerca HTML API instanze

?

Dove trascorrere le vacanze quest’estate ?


DB

Gro

up @

uni

mo

Sistemi di integrazione dati basati su Sistemi di integrazione dati basati su mediatoremediatore

DBMSrelational

ApplicationDBMSobjet

DBMSSemi-Structured

Agenziedi Viaggi

Gli Hotel Siti Oraridei Voli

Filetext

Filetext

Filetext

Meteo

SQL

tuples XML texti API instances

?

Mediatore

Wrapper Wrapper Wrapper Wrapper Wrapper

SQLOQL

tuple objet API instanzeMotoridiricerca

textiXQueryXML

Informazioni Paese


DB

Gro

up @

uni

mo

MOMIS: Integrazione semantica dei datiMOMIS: Integrazione semantica dei dati

Global Virtual View(GVV)

Source Source Source

LocalSchema

LocalSchema

LocalSchema

Mapping

Query


DB

Gro

up @

uni

mo

Mapping Table Mapping Table

from L1 full join L2

Join Attribute

on (T_L1.COMPANY_ID = T_L2.COMPANY_ID)

Join Conditions

FullDisjunction

L1.company L2.company

COMPANY_ID COMPANY_ID COMPANY_ID

SUBCONTR SUBCONTR

CAPITAL_STOCK CAPITAL_STOCK

REGION REGION REGION

ADDRESS ADDRESS ADDRESS

...Select COMPANY_ID,

precedence(T_L1.ADDRESS, T_L2.ADRESS) as Address, T_L2.SUBCONTRACTOR, …

Resolution Functions

Precedence(L1,L2)

G


DB

Gro

up @

uni

mo

Full Disjunction : FJFull Disjunction : FJ

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

FJ : operazione di full join tra n classi locali


DB

Gro

up @

uni

mo

OTTIMIZZAZIONEOTTIMIZZAZIONE 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


DB

Gro

up @

uni

mo

Query Globale

Forma algebrica

naive semplificata

oppure Sostituzione dell’operatore di full outerjoin. Eliminazione delle classi locali : riduzione di

“Push” delle proiezioni e selezioni.

Obiettivo dell’ottimizzazioneObiettivo dell’ottimizzazione


DB

Gro

up @

uni

mo

Semplificazione dell’outerjoin: stato dell’arteSemplificazione 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)


DB

Gro

up @

uni

mo

Semplificazione dell’outerjoin: estensioneSemplificazione dell’outerjoin: estensione

Introduzione Proprietà duale: NOT NULL PROJECTIONEliminazione delle tuple nulle dalla risposta

naive

ottimizzata


DB

Gro

up @

uni

mo

Esempio di semplificazione Esempio di semplificazione

La query viene riscritta in algebra relazionale come segue:

Mapping table


DB

Gro

up @

uni

mo

Esempio caso B2Esempio caso B2


DB

Gro

up @

uni

mo

Cosa succede nel sistema MOMIS?Cosa succede nel sistema MOMIS?versione naive

Caso B2

Versione ottimizzata


DB

Gro

up @

uni

mo

Piano generale di semplificazionePiano generale di semplificazione


DB

Gro

up @

uni

mo

Riduzione degli schemi sugli attributi di Riduzione degli schemi sugli attributi di proiezioneproiezione


DB

Gro

up @

uni

mo

Esempio di applicazione dell’algoritmoEsempio di applicazione dell’algoritmo

versione senza riduzione schemi

Versione con riduzione schemi


DB

Gro

up @

uni

mo

Riduzione degli schemi in una queryRiduzione degli schemi in una query


DB

Gro

up @

uni

mo

Combinazione delle due tecnicheCombinazione delle due tecniche

Risultato (I)

Risultato (II)


DB

Gro

up @

uni

mo

Conclusione e Sviluppi FuturiConclusione 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

Nana Mbinkeu Rodrigue Carlos 1 DB Group @ unimo OTTIMIZZAZIONE DI QUERY IN MOMIS Università degli...

Documents

Transcript of Nana Mbinkeu Rodrigue Carlos 1 DB Group @ unimo OTTIMIZZAZIONE DI QUERY IN MOMIS Università degli...