Individuazione delle classi locali coinvolte

Per ogni Basic Query generata, bisogna determinare l'insieme ottimo di classi locali a cui inviare le Local Query . Per poter eseguire correttamente questo passaggio é necessario utilizzare entrambi i tipi di conoscenza individuati in fase di integrazione degli schemi.

1. Analisi della Basic Query
   Il testo della Basic Query viene analizzato per individuare tutti gli attributi globali in esso contenuti.
   Una generica Basic Query puó essere schematizzata come segue:

    SELECT <select-list>
    FROM Gi
    WHERE <where-clause>
   

   Dove <select-list> e' un insieme di attributi globali: $f(GA(G_i))$ , mentre <where-clause> e' un'espressione booleana, sempre funzione degli attributi globali, giá posta in forma normale congiuntiva $(b(GA(G_i)))$. Viene individuato l'insieme Q di attributi globali contenuti nella <select-list> e nella <where-clause>:
   $Q = \{q_1,q_2,\ldots,q_N\}$   , con$Q \subseteq \ GA(MT(G_i))$    per cui vale:
   $\forall q_i \in Q, q_i \in (GA($<select-list>$)) \lor (GA($<where-clause>$))$
   Consideriamo ad esempio la query seguente:

    Q_1: select name,dept
         from University_Person
         where faculty = 'CS'
         and (pay >2000000)
   

   Per la query Q_1 viene determinato l'insieme $Q = \{\texttt{name, dept, \ faculty, pay}\}$, che costituisce il punto di partenza per i passi successivi.

2. Individuazione della Classe Virtuale Target
   A questo punto bisogna utilizzare la Gerachia Estensionale $GE(G_i)$, associata alla Globale $G_i$, per stabilire la Classe Virtuale Target, cioe' la Classe Virtuale che contiene all'interno della propria intensione tutti gli attributi Q della query.
   In realtá viene determinato un insieme di classi virtuali, in quanto piú di una classe puó avere i requisiti visti in precedenza, si determina quindi un insieme iniziale di classi virtuali $V_in$.
   $VC_{in} = \{V_{ji} \in GE(G_i): Q \subseteq int(Vji) \}$
   Nell'esempio vengono selezionate: $VC_{in} = \{ C4, C7, C9, C11 \}$ Da questo insieme iniziale, vengono selezionate le classi virtuali con estensione massima, quelle cioé che contengono il maggior numero di Base Extension.
   $VC_{opt} = \{V \in VC_{in}: est(V) >= est(V_h), \forall V_h \in VC_{in}\}$
   Nell'esempio si ottiene: $VC_{opt} = \{C11\}$.
3. individuazione delle Base Extension
   Nel caso in cui le Classi Virtuali siano piú di una bisogna considerare l'unione delle base extension, in caso contrario l'insieme $BE_{in}$ di Base Extension iniziali é determinato automaticamente dall'estensione della Classe Virtuale. Nell'esempio $VC_{opt} = \{C11\}$ e quindi $BE_{in} = est(C11) = \{1,2,6,7\}$ In generale la formula seguente:
   $BE_{in} = \bigcup_{V \in VC_{opt}} est(V)$

4. Selezione delle Classi Locali
   Individuate le Base Extension sono note automaticamente anche le classi da interrogare.Relativamente alla nostra query di esempio Q_1, inizialmente le base extension selezionate sono: $\{1,2,6 e 7\}$, esaminando la tabella riportata in Figura , dalle colonne delle base extension in questione si evince che le classi locali alle quali accedere risultano essere :
   $CL = \{ \mbox{\texttt{University\_Worker, School\_Member, CS\_Person,\\ \ University\_Student}} \}$ .
5. Semplificazione del Query Plan
   Gli insiemi $BE_{in} e CL_{in}$ determinati devono essere ulteriormente semplificati per minimizzare il numero di query da inviare alle sorgenti. Questa semplificazione avviene in due momenti distinti:
   • Eliminazione di base extension:
     Puo succedere che non tutte le base extension contenute in $BE_{in}$ debbano essere ricostruite per ottenere la risposta minima, per valuare le eventuali ridondanze viene introdotto il concetto di dominazione:
     Definizione 6 (Dominazione)   Date due Base Extension $b_1$, $b_2$ ed un insieme di attributi A = {$a_1,$ $\dots,$ $a_n$ $\}$, si dice che $b_1$ domina $b_2$ rispetto ad A, se A è compreso nelle intensioni di entrambe e se le classi che compongono $b_1$ sono un sottoinsieme di quelle che formano $b_2$.

     $b_1$ domina $b_2$ rispetto ad A $\Leftrightarrow$
     $(A \subseteq int(b_1)) \land (A \subseteq int(b_2)) \land (C(b_1) \subset C(b_2))$

     Per ricostruire una base extension si deve effettuare il join tra tutte le classi locali che la compongono, ma le base extension rappresentano insiemi disgiunti di entità, quindi dal join tra le classi si ottiene in realtà un soprainsieme della base extension desiderata.

     Quindi si possono, anzi si devono, non prendere in considerazione le base extension dominate, ma si devono ricostruire solo quelle dominanti per evitare duplicazioni.
     Di conseguenza sfruttando la definizione precedente, si ottiene l'insieme di base extension dominate:

     $BE_{dom} = \{ b_2 \in B_{in}: \exists b_1 \in B_{in} \land b_1$    domina $b_2$    rispetto a $Q \}$
     Con questo primo passo di semplificazione si ottiene l'insieme ottimo di base extension:
     $BE_{opt} = BE_{in} - BE_{dom}$

     Per la query di esempio Q_1, l'insieme di base extension iniziali $BE_{in} = \{1,2,6,7\}$ viene semplificato in $BE_{opt} = \{6,7\}$, infatti, rispetto all'insieme di attributi della query, si vede che la 6 domina sia la 1 che la 2, mentre la 7 domina la 2. Dobbiamo quindi ricostruire solo la base extension 6 e 7.
     

     Scartando le base extension dominate da altre abbiamo notevolmente limitato le possibilità di duplicazioni, ma non le abbiamo eliminate del tutto. Nel caso infatti che due base extension ne dominino una terza, questa viene scartata, ma le altre due una volta ricostruite generano insiemi di entità parzialmente sovrapposti: la sovrapposizione è rappresentata proprio dall'estensione della base extension eliminata. Per ovviare a ciò è necessario tenere traccia ,nel query plan, di come unire le base extension per una determinata Basic Query: di default bisognerà effettuare una unione delle entità, ma se si presenta un caso come quello appena discusso bisognerà effettuare un outer join tra le base extension al fine di presentare una sola volta la porzione comune. Nel nostro esempio Q_1 entrambe le base extension selezionate dominano la 2, di conseguenza in fase di esecuzione devono essere fuse tramite un outer join.

   • Eliminazione di classi locali:
     una volta individuato l'insieme ottimo di base extension, ognuna di queste viene esaminata per ottenere il numero minimo di classi a cui accedere.Questa semplificazione del Query-Plan consente di diminuire il numero di Local Query da generare e potrebbe anche evitare l'accesso ad una sorgente.

     In una base extension potrebbe accadere che due classi locali siano estensionalmente equivalenti, se questo accade e nessuna delle due classi aggiunge informazioni rispetto all'altra puo' essere eliminata una delle due in modo indifferente.Se invece una classe contiene attributi della query non presenti nell'altra deve essere eliminata la seconda.

     Un'altro caso in cui é possibile minimizzare l'insieme di classi locali, si verifica quando due classi appartengono allo stesso DataBase ed esiste fra loro una relazione di specializzazione: se la sorgente é 'object' o se in ogni caso la classe specializzata contiene tutte le proprietá richieste, é possibile scrtare la superclasse. Nell'esempio introdotto, la base extension 6 prevede l'interrogazione delle seguenti classi locali $CL_{6}= \{ \mbox{\texttt{University\_Worker, \ CS\_Person}} \}$ , come si puo' vedere questo insieme non puó essere ulteriormente ridotto in quanto non ricorre uno dei due casi visti in precedenza. La base extension 7 prevede inizilamente $CL_7 = \{\mbox{ \texttt{University\_Worker, School\_Member, University\_Student}} \}$, in questo caso School_Member e University_Student risultano estensionalmente equivalenti e nessuna delle due aggiunge informazioni rispetto all'altra , quindi una delle due puó essere eliminata indifferentemente, ma eliminanado University_Student si evita di accedere alla terza sorgente, Tax_Position. L'insieme ottimo di classi a cui inviare le Local Query risulta essere: $CL = \{ \mbox{\texttt{University\_Worker, CS\_Person, University\_Student}} \}$.

     Prima di eseguire la fase di semplificazione delle classi locali, devono essere eventualmente aggiunti alla <$<$select-list$>$ della query, gli attributi aggiuntivi per la fusione delle base extension. Per due base extension da fondere in outer join, é necessario indiviaduare una chiave comune o, nel caso in cui il join diretto non sia possibile, una classe di collegamento. Per questo é necessario considerare, per determinare l'insieme ottimo delle classi locali, non solo gli attributi originari della query, ma anche eventuali attributi aggiuntivi necessari alla fusione.