Approcci Basati su Grafi

In precedenza abbiamo introdotto le pipe e commentato brevemente alcu- ni studi basati su tale concetto. Nel contesto della composizione di servizi Web e creazione di mashup, possiamo immaginare che le dipendenze di in- put/output esistenti tra gli elementi di un modello a pipe possano essere modellate come un particolare grafo orientato in cui ciascun arco collega un nodo al suo successore (una catena di nodi). In un caso simile, in qualche modo si sta assumendo che un servizio sia in grado di soddisfare totalmente le richieste del suo successore. Tuttavia possiamo pensare di estendere il caso appena descritto ad uno scenario (tipico nella composizione di servizi) in cui l’input di un servizio venga soddisfatto da pi`u servizi o addirittura in cui il risultato di un servizio rappresenti l’input di pi`u servizi. Analogamente a quanto fatto in precedenza, `e naturale pensare di modellare una situazione del genere con un grafo orientato, stavolta con un numero maggiore di archi rispetto al caso precedente e con una struttura generica, dunque diversa dalla struttura a catena descritta in precedenza.

“Dato un repository di descrizioni di servizi e una query con i requisiti del servizio richiesto, nel caso in cui non esista un servizio corrispondente, il problema della composizione coinvolge la creazione automatica di un grafo aciclico diretto di servizi che possono essere composti per ottenere il servizio desiderato” [62]. La precedente affermazione lascia intuire come i grafi sia- no alla base dell’approccio adottato in [62]. In particolare il problema della composizione viene affrontato avvalendosi di grafi diretti aciclici (DAG) che

possono includere delle pre e post-condizioni. Una particolarit`a di questo studio `e che la fase di scoperta di servizi viene vista come un caso particolare di composizione (composizione di un unico servizio) e dunque viene affronta- ta usando la stessa metodologia utilizzata per la composizione.

Lo studio in questione pertanto basa il suo approccio su DAG con condizio- ni, risolve il problema della composizione attraverso un algoritmo efficiente e scalabile che scopre e seleziona automaticamente servizi (semantici) per soddisfare i requisiti espressi. Inoltre, una volta trovata la composizione ap- propriata, viene generata in maniera automatica una descrizione OWL per il nuovo servizio in modo da poterlo riutilizzare in ricerche future senza doverlo creare nuovamente da zero.

L’algoritmo che crea il grafo che modella il servizio composito si basa sull’e- liminazione progressiva dei servizi che non vengono ritenuti utili ai fini della composizione. La struttura generale dell’algoritmo `e la seguente:

• si inizia prendendo in considerazione i parametri espressi nella specifica della composizione;

• si selezionano tutti e soli i servizi presenti nel repository che prendono in input un sottoinsieme dei parametri disponibili fino a questo momento (parametri della specifica);

• l’input disponibile a questo passo `e dato dall’unione dei parametri della specifica e degli output dei servizi selezionati. Quindi si selezionano degli altri servizi considerando la disponibilit`a di input corrente; • il procedimento continua finch´e l’output espresso nella specifica non `e

• l’ultimo passo `e finalizzato alla rimozione di servizi ridondanti, ovvero che non contribuiscono alla costruzione dell’output richiesto.

Come accennato, una volta ottenuta la composizione di servizi si provvede a produrre una descrizione semantica in OWL del nuovo servizio, che permet- ter`a di eseguire il servizio stesso e pubblicarlo nel repository per futuri utilizzi e ricerche. La metodologia elaborata `e implementata in uno strumento per la composizione di servizi, che `e stato utilizzato per la generazione automatica di flussi di lavoro nell’ambito della bioinformatica.

Un ulteriore studio in cui i grafi costituiscono l’elemento centrale della metodologia adottata `e [50], in cui viene definito il concetto di “Enhanced Service Dependency Graph” (SDG+). [50] `e stato concepito nell’ambito della risoluzione del problema della composizione automatica di servizi della WS- Challenge, una competizione sulla composizione automatica di servizi orga- nizzata dalla conferenza annuale CEC/EEE. L’approccio parte dal concetto (sviluppato in uno studio precedente) di Grafo delle Dipendenze tra Servizi (SDG), un grafo che modella tutte le possibili dipendenze di input/output di un insieme di servizi. Dunque attraverso l’analisi di un grafo cos`ı costrui- to `e possibile individuare rapidamente quali servizi sono in grado di fornire l’input a un servizio dato e analogamente a quali servizi potr`a essere inviato l’output di un servizio dato. Una struttura di questo tipo `e estremamente utile nell’ambito della composizione di servizi, sia per la sua immediatezza, sia per la completezza di informazione, infatti ricordiamo che molto spesso l’obiettivo di un mashup o di un servizio composito `e espresso proprio in termini dell’input fornito e dell’output richiesto. L’idea di espandere il con-

cetto di SDG nasce dall’osservazione che l’espressivit`a di un simile grafo `e limitata da diversi aspetti quali l’impossibilit`a di rappresentare dipendenze tra interfacce di servizi e istanze, la mancanza di quantificatori per esprimere relazioni tra attributi o la rappresentazione di tutte le dipendenze in maniera implicita. Il primo passo dello studio in questione `e dunque l’estensione degli SDG attraverso i seguenti meccanismi:

• aggiunta di quantificatori che permettano di esprimere relazioni tra gli attributi (del tipo uno a uno, uno a molti, ecc...);

• aggiunta di un meccanismo per la rappresentazione esplicita di dipen- denze;

• introduzione di due livelli di dipendenze: a livello astratto e a livello di istanza.

Una volta costruito il SDG+ relativo ad un insieme di servizi, la ricerca di una composizione che soddisfi i requisiti richiesti equivale alla ricerca di una catena di servizi nel SDG+. Per individuare tale catena viene utilizzato un algoritmo basato su quello originalmente utilizzato sugli SDG.