Nella fase del parsing, la query in MW-SQL `e tradotta nella rappresentazione interna del piano di esecuzione descritta precedentemente. Il parser considerato funziona in maniera standard, come quello dei compilatori di altri linguaggi ad alto livello (vedi [1]). In particolare si tratta di un parser top-down a discesa ricorsiva per la grammatica descritta nel paragrafo 4.4. Il parser `e costruito automaticamente con un apposito strumento (vedi par. 7.1), e utilizza un lookahead di cinque token per eliminare il nondeterminismo sulla scelta tra pi`u produzioni.
Eventuali errori pervenuti durante il parsing (errori di lessico o di sintassi) inter- rompono il processo e vengono mostrati all’utente nell’interfaccia.
Per generare la rappresentazione interna del piano durante il parsing usiamo la tecnica standard:
• ad ogni simbolo non-terminale della grammatica generante il linguaggio MW- SQL si associa un qualche tipo di struttura dati, in modo tale che quando il parser riconosce un simbolo non-terminale produce un’istanza del tipo della struttura dati associata;
• ad ogni regola di derivazione corrisponde una funzione per calcolare l’istanza da produrre utilizzando le istanze prodotte dai non-terminali della parte destra della regola in questione.
Si utilizzano le seguenti associazioni fra simboli non-terminali e tipi di dati: - Query: un albero di operatori (l’albero corrispondente alla query); - FromWhere: un sottoalbero dell’albero degli operatori;
- Const: un intero;
- Natural: un intero senza segno;
- Condition: un sottoalbero composto da una catena aperta di operatori unari σ;
- Select List: un insieme di attributi;
- Source: un sottoalbero di operatori (ad esempio il source 1.Light diventa il sot- toalbero composto dalla sola foglia 1.Light);
- Source List e Aggr List: insieme di sottoalberi (che include un sottoalbero di operatori per ogni source della lista);
5.3. PARSING DELLA QUERY E COSTRUZ. DELLA RAPPR. INTERNA 65
Figura 5.2: L’albero di parsing completo di una semplice query in MW-SQL, mostra- ta in alto a destra. Per alcuni simboli non-terminali nell’albero abbiamo specificato con delle lettere in rosso la struttura dati prodotta con il riconoscimento di quel sim- bolo non-terminale. In particolare: A `e il piano di esecuzione risultante dal parsing della query, B `e un sottoalbero, C’`e un sottoalbero incompleto composto da un solo nodo restrizione col figlio non specificato, D ed E sono sottoalberi composti da una sola foglia ciascuno ed F e G sono insiemi di sottoalberi.
- Var: un identificatore (una stringa);
- B Source: un identificatore di nodo della rete di sensore (un intero); - Field: un nome di un attributo (una stringa);
- Area: una struttura dati apposita per rappresentare un’area rettangolare. Per brevit`a, omettiamo di riportare la maggior parte delle funzioni associate ad ogni regola di produzione (vedi fig. 5.2 per un esempio).
Una caratteristica importante del nostro sistema `e il trattamento del caso dei sim- boli non-terminali Source List e Aggr List. Come si vede dalla grammatica queste liste sono composte da source, aree e variabili. Il corrispondente insieme di sot- toalberi viene composto unendo tutti i contributi di ogni elemento della lista, in particolare:
• per i source singoli si aggiunge il sottoalbero corrispondente;
• per le aree si aggiungono tutti i sottoalberi ciascuno composto da un nodo foglia corrispondente ad ogni nodo della rete di sensore dentro l’area;
• per le variabili si aggiungono tutti i sottoalberi dell’insieme associato al cor- rispondente sorgente virtuale.
Quando bisogna trasformare un insieme di sottoalberi in un singolo sottoalbero, tutti i sottoalberi dell’insieme verranno uniti tramite una serie di operatori binari: nella figura 5.3 a tale proposito `e mostrato un esempio con la giunzione. In tal caso quando il parser riconosce il simbolo non-terminale Source List costruisce l’insieme di sei sottoalberi mostrati nella figura in basso a sinistra ed ottenuti come unione dei contributi dei quattro elementi della lista:
• A `e un source singolo che produce un albero composto da una sola foglia; • B `e un’area che racchiude due nodi della rete che hanno il fotometro richiesto; • C `e un sorgente virtuale, precedentemente definito come una coppia di source
col comando CREATE mostrato in cima nella figura; • D `e una inner query che produce un albero di due nodi.
Quando il Source `e riconosciuto con la regola Source::= <JOIN><OPEN> Source List <CLOSE>, ad esso `e associato l’albero in basso a destra ottenuto incollan- do insieme i sei sottoalberi con alcuni operatori binari di giunzione. Nell’esempio questo passaggio `e effettuato applicando l’ottimizzazione topologica per minimizzare le distanze tra i nodi della rete che dovranno comunicare (vedi par. 6.1). Da notare che ad esempio, i due sottoalberi 4.A e σc(4.T ) pur provenendo da parti diverse
della query, sono situati sotto la stessa giunzione e che le due foglie del sorgente virtuale pippo non sono vicini nell’albero finale. Invece, nel caso della regola di produzione Source::=<AVG><OPEN> Aggr List<CLOSE>, il corrispondente insieme di sottoalberi `e trasformato in un singolo sottoalbero tramite una serie di operatori binari relativi ad aggregati di media spaziale. Un’altra trasformazione di un insieme di sottoalberi in un unico albero, si ha per il non-terminale FromWhere per l’esempio mostrato nella figura 5.2.
Ci sono molte alternative per trasformare un insieme di sottoalberi in un singolo sottoalbero, che determinano sequenze diverse di comunicazione tra nodi. Tra queste ce ne saranno alcune pi`u convenienti: quelle che fanno comunicare fra loro nodi vicini. In questa fase si pu`o attuare dunque un’ottimizzazione preliminare, che chiamiamo ottimizzazione topologica, per trovare una buona soluzione (descritta nel par. 6.1 del capitolo sull’ottimizzazione).
Alcuni esempi di risultato della costruzione della rappresentazione interna a partire da una query saranno mostrati nel paragrafo 7.4.