Negli ultimi anni si è registrato un crescente interesse nei confronti dell’integrazione delle informazioni sulle reti P2P, con riferimento all’accesso, alla raccolta e alla combinazione dei dati memorizzati su ciascuna peer della rete.
Ciò ha contribuito ad accrescere l’importanza della figura del mediator, attraverso la quale si snodano le attività di ricerca per il calcolo delle query.
Nei nostri sistemi P2P, i termini appartenenti ad una peer sono organizzati gerarchicamente e in relazione con i termini memorizzati sulle altre peer.
Prima di definire formalmente il comportamento della rete, abbiamo fissato alcuni concetti fondamentali che ci permetteranno di individuare le informazioni necessarie per il calcolo delle query.
Ogni peer ha una propria tassonomia costituita da un insieme di termini organizzati gerar- chicamente attraverso delle relazioni di sussunzione.
Definizione 1. Una tassonomia è una coppia (T, p ) nella quale T è una terminologia, ossia un
insieme finito e non vuoto di nomi o termini, mentre p è una relazione riflessiva e transitiva su T che modella le inclusioni, o sussunzioni, fra i termini.
Se a e b sono termini dell’insieme T (a, b ∈ T) e a p b allora diciamo che b sussume a e a è sussunto da b (esempio:Databases p Informatics).
Se due termini sono equivalenti allora: a p b e b p a, in simboli a ~ b (esempio: Computer Science ~Informatics).
Obj è l’insieme di tutti gli oggetti che definiscono il dominio del sistema, ossia la somma di tutti gli elementi memorizzati localmente in ciascuna peer.
Definizione 2. Data una terminologia T, una stored interpretation per T è una funzione
I: T 2Obj che associa ad ogni termine di T un sottoinsieme, possibilmente non vuoto, dell’insieme Obj .
Definizione 3. Una simple source S è definita da: una tassonomia (TS, p ) e da una stored
interpretation IS per la terminologia TS.
L’esempio riportato nella Figura 2.1 mostra una simple source che ha come dominio un insieme di file audio. Gli oggetti sono raggruppati per generi musicali e i loro identificatori sono rappresentati da numeri naturali. Le associazioni che legano i termini agli oggetti sono descritte da frecce tratteggiate, le sussunzioni fra i termini da frecce, mentre le equivalenze da linee. Nell’esempio, gli oggetti 1 e 3 appartengono all’interpretazione, ossia la stored interpretation, del termineLive, I(Live)= {1, 3}.
Il termine Rock sussume Metal (Metal pRock), il quale è sussunto dal termine Genre
(Rock p Genre) e il termine Rock è equivalente al termineRocky (Rock ~ Rocky).
Definizione 4. Se T è una terminologia, allora una query su T è una stringa definita dalla
seguente grammatica: q ::= t | q q′ | q V q′ | q ¬ q′ | (q) dove t è un termine dell’in- sieme T (t∈T) e q, q′ sono query (q,q′∈QT).
Indichiamo con QT l’insieme delle query formulate sulla terminologia T e con IT l’insieme degli
Affinché, un’interpretazione possa essere significativa e corretta deve rispettare la seguente proprietà: se t p t′ allora I(t) ⊆ I(t′).
Definizione 5. Un’interpretazione I è un modello per la tassonomia (T, p ) se per ogni coppia t,
t′ ∈ T dove t p t′, è verificata la seguente relazione: I(t) ⊆ I(t′).
La stored interpretation della simple source della Figura 2.1 non è un modello per la sua tassonomia, infatti, la relazioneMetal p Genre non è rispettata, in quanto:
I(Metal) ={1} ⊄ I(Genre) = {2}.
Per risolvere questo problema, senza alterare le interpretazioni di ciascun termine, possiamo estendere I all’insieme I , dove I è un’interpretazione definita nel seguente modo:
I (Genre) = I(Genre) ∪ I(Rock) ∪ I(Rocky) ∪ I(Jazz) ∪ I(Metal).
Figura 2.1 Rappresentazione grafica di una simple source
Rocky Metal Rock Live Jazz Studio 1 2 3 Genre Recording oggetti termini ~ interpretazione
Definizione 6. Data un’interpretazione I per la terminologia T, il modello di T generato da I,
corrisponde alla seguente formula: (t) = U { I(s) | s p t,s ∈ Τ}.
Per poter definire un criterio di minimalità dell’insieme, è necessario ordinare l’insieme di tutte le possibili interpretazioni della terminologia T, utilizzando una relazione binaria d’inclusione. Date due interpretazioni: I , I , entrambe definite sulla terminologia T, I è minore o uguale di I , in simboli I ≤ I , se I(t) ⊆ I (t) per ogni termine t ∈ T.
La relazione binaria ≤ soddisfa: la proprietà riflessiva, transitiva e antisimmetrica, quindi è un ordinamento parziale sull’insieme delle interpretazioni. La Proposizione 1 stabilisce che nell’insieme dei modelli della tassonomia di (T, p ) esiste un unico modello minimale.
Proposizione 1. Data una source (T, p , I) allora è l’unico modello minimale della tassonomia
(T, p ) con ≤ I.
Definizione 7. Data una simple source Si con terminologia T, una stored interpretation I e una
query q ∈ QT, la risposta alla query q calcolata sul nodo Si (answer query), che indicheremo
con ansi(q), è definita in modo induttivo dalla combinazione delle seguenti formule:
1. ansi(t) = (t) ∀t ∈T
2. ansi(q q′) = ansi(q)∩ansi(q′)
3. ansi(q V q′) = ansi(q) ∪ansi(q′)
4. ansi(q ¬q′) = ansi(q) \ ansi(q′).
Dopo aver definito tutti gli elementi delle simple source, possiamo formalizzare i mediator e le articulated source, partendo dalla definizione delle articolazioni.
Definizione 8. Un’articolazione pij tra la tassonomia (Ti, pi) e la tassonomia (Tj , pj) è un
insieme non vuoto di coppie (ti, tj) in simboli tj pijti, con ti∈Tie tj∈Tj.
Se tj pijti allora il termine tj è articolato con il termine ti. Le articolazioni sono associazioni tra i
Possono essere definite manualmente oppure automaticamente, seguendo due differenti tecniche d’implementazione: model-driven e data-driven.
Model_driven è un modello teorico nel quale sono descritte le eterogeneità e le differenze strutturali, funzionali e semantiche della coppia di terminologie su cui sono definite le articolazioni. Il suo processo di articolazione dei termini viene implementato utilizzando degli specifici software tools.
L’approccio data-driven, a differenza di model-driven, può essere implementato in maniera automatica e focalizza la propria attenzione sulle tecniche d’indicizzazione dei dati, memo- rizzando gli oggetti condivisi in due database associati ad ogni coppia di source i cui termini sono articolati fra loro, implementando articolazioni fra: singoli termini, query, insiemi di termini e query, senza collegare intere tassonomie.
Applicando quest’approccio ai modelli semantici possiamo riscontrare limitazione nelle performance della rete. Infatti, se le source dispongono di una copiosa collezione d’oggetti condivisi da entrambe le tassonomie e se esistono delle false correlazioni fra i termini, il sistema ha dei malfunzionamenti e un incremento del tempo d’esecuzione.
Definizione 10. Un’articulated source M su k source S1, …, Sk è definita da:
1. una simple source, con tassonomia (TM, pM) e stored interpretation IM di TM
2. un insieme { aM,1, …, aM,k } in cui ogni aM,i è un’articolazione che lega i termini della
tassonomia (TM, pM) con i termini della tassonomia (Ti, pi).
Se la stored interpretation dell’articulated source è un insieme vuoto, in simboli I(t) =∅per ogni termine t ∈ TM, allora la source è un mediator. Viceversa, se la stored interpretation non è vuota
e l’insieme delle articolazioni è vuoto la source è una simple source.
Definizione 11. L’insieme N = {S1, … , Sn}, è una rete di articulated source, se N è un insieme
non vuoto di articulated source disgiunte, nelle quali ogni source Si è articolata con l’insieme
N = N /{Si}, ossia l’insieme delle source di N eccetto la source Si.
A ogni termine t ∈ ΤΜ sono associate delle informazioni sulla source che contiene la termi-
La Figura 2.2 mostra una rete di articulated source composta da: due simple source (S3 e S4), un
mediator (S2) e un’articulated source (S1).
Figura 2.2 Una rete di articulated source
La rete N = {S1, …, Sn} può essere rappresentata attraverso una simple source SN, composta da:
una terminologia TN e una stored interpretation IN, ottenute dall’unione di tutte le terminologie e
delle stored interpretation delle source del sistema, con l’aggiunta di una relazione di sussunzione totale ,ottenuta dalla chiusura transitiva dell’unione di tutte le sussunzioni locali e delle articolazioni della rete.
DB S2 = (T2, p2, a2,1 ,a2,3, a2,4) S1 = (T1, p1, I1, a1,2, a1,3) S3 = (T3, p3, I3) S4 = (T4, p4, I4) S1 S2 S3 S4 DB DB
– TN=
U
n i 1= Ti – IN =U
n i 1= Ii – = (U
n i 1= i)*dove i = pi ∪ ai,1 ∪… ∪ ai,n e A* è la chiusura transitiva della relazione binaria A.
Quest’assunzione permette di definire una network query su T, nella quale gli utenti risolvono localmente le interrogazioni propagandole alle source della rete.
Le risposte locali possono appartenere a source remote oppure a source direttamente articolate con la source di partenza, combinando le risposte associate ai termini appartenenti alle differenti terminologie della rete.
L’insieme delle risposte alla network query q, o network answer, coincide con l’insieme ansN(q), calcolato sul modello di T generato da I. In accordo con la Definizione 7, network
answer è uguale al seguente insieme:
(t) =
U
{ I(t′)| t′ t }∀termine t definito in q.Definizione 12. Data una rete di articulated source definita dall’insieme N = {S1, …, Sn} e un
termine t ∈TN, dove TN è unione di tutte le terminologie della rete, le entrate di t in N, ossia
l’insieme E(t), sono definite nel seguente modo:
E(t) = {t}∪ {t′ ∈ Τ | ∃ t′′∈ Τ : t′ pij t′′ t , con i, j indici delle source di N}
La notazione: t′pij t′′ t significa che t′ pij t′′ e t′′ t. Per ogni termine t, l’insieme E(t)
include il termine t e tutti i termini articolati con t e memorizzati nelle varie source della rete, compresi: i termini direttamente articolati e quelli articolati attraverso uno o più termini intermediari.
Consideriamo l’esempio riportato nella Figura 2.3, che descrive la tassonomia di una rete di articulated source composta da tre source e da un insieme di articolazioni. Le entrate del termine
c coincidono con l’insieme E(c) = {c, a3, b3, b1}. I termini a3 e b3 sono articolati con c in accordo con le sussunzioni: pc,a e p . Il termine b1, è una sussunzione remota del termine c,c,b
infatti è articolato con a3, ossia uno dei termini direttamente sussunti da c, in accordo con la sussunzione pa,b.
Figura 2.3 Rete composta da 3 articulated source
Se consideriamo una rete N = {S1,…,Sn} e associamo un indice a ogni terminologia della rete,
possiamo definire una funzione g(t) che restituisce l’indice della terminologia che contiene il termine t definita nel seguente modo: g(t) = j se t∈Tj.
Proposizione 3. Per ogni termine t appartenente alla terminologia della rete N = {S1,…,Sn}, la
sua network answer è uguale all’insieme: ansN(t) = U { ansg(t )(t) | t ∈E(t)}.
c b1 b2 b4 b3 a1 a2 a3 Sb Sc Sa {1,2} {3} {4} {5} {8} {6} {7,9}
Quest’ultima proposizione presuppone che ogni source della rete conosca le occorrenze di tutte le articolazioni e le tassonomie delle altre source, in modo tale da poter computare le entrate di ciascun termine. Quest’assunzione è fattibile solo per le architetture Client-Server e per i sistemi P2P ibridi, nei quali è possibile fissare un ordinamento fra le source connesse alla rete.
Per definire un metodo compatibile con le architetture P2P pure, dobbiamo trasformare le entrate in entrate locali, partizionando la conoscenza della rete. Per questo motivo, ogni source dispone di un insieme d’informazioni che gli permettono di derivare le entrate delle altre source, ossia le source articolate con la source di partenza.
Definizione 13. Data una source Si appartenente alla rete N = {S1,…,Sn} e un termine t∈Ti, le
entrate locali di t sulle source della rete N, ossia l’insieme e(t), sono tutti i termini appartenenti all’insieme:
e(t) = {t}∪
U
ni 1=
{e(t′)|t′ i t, t ∉Ti}
Possiamo definire l’insieme in funzione dell’indice della terminologia:
ei(t) = {t} ∪
U
n
i 1=
{ eg(t )(t | t' it, t ∉Ti}.
Nello specifico dell'esempio della Figura 2.3, le entrate locali del termine c sono calcolate nel seguente modo:
ec(c) = {c}∪eb(b3) ∪ea(a3) ⇒
eb(b3) = {b3}, ea(a3) = {a3}∪eb(b1) , ec(b1) = {b1}∪ec(c)⇒
ec(c) = {c, b3, a3, b1}∪ec(c).
ec(c) è una funzione F, con dominio e codominio sulla terminologia della rete. E’ uguale a:
F(X)
def
= λX.{c,b3, a3, b1}∪ X.
I suoi punti fissi sono le soluzioni della funzione. F è monotona rispetto all’ordinamento parziale completo (2T, ⊆), questo implica che la funzione abbia un unico minimo punto fisso (l’elemento minimale dell’insieme ossia il minimo dei suoi maggioranti), che nel nostro esempio è l’insieme {c, b3, a3, b1}.
Dato un termine ti∈ Τi, il suo indice è l’insieme H(ti) ={t′∈ Τ | t′ i*ti , t′ ∉Ti} sottoinsieme
di e(ti). Possiamo definire le entrate locali del termine tiin funzione dei suoi indici, applicando la
seguente formula:
e(tk) ={tk}∪
U
{ e(t′) | t′∈H(tk)} ∀tk∈E(ti)che può essere scritta nel seguente modo:
e(tk) = Ak ∪
U
{ e(t′)|t′∈Bk} dove Ake Bk sono insiemi di termini scelti opportunamente. Nello specifico dell'esempio della Figura 2.3:Η(c) = {b3, a3},Η(b3) =∅, H(a3) = {b1}, H(b1) = {c}⇒
e(c) = {c}∪e(b3)∪e(a3), e(b3) = {b3}, e(a3) = {a3}∪e(b1), e(b1) = {b1}∪e(c)⇒ e(c) = {c, b3, a3, b1}
Sulla base degli assegnamenti che abbiamo definito precedentemente, possiamo modificare la definizione di e(tk), utilizzando gli insiemi Ake Bk.
0 k
A = {tk} Bk0 =H(tk)
In modo induttivo possiamo estendere le definizioni degli insiemi Ake Bkper i > 0, e ottenere le seguenti formule: – Aki+1 = Aki ∪ Bki – Bki+1 = Bki ∪
U
{ H(t) | t ∈Bki} – e(tk) = (A
k ∪ Bk) ∪U
{ e(t′)|t′∈Bk ∪U
Bk t′′∈ H(t′′) }.Quest’ultima definizione converge all’insieme B* che coincide con il minimo punto fisso del calcolo computazione delle entrate di ciascun termine della rete. E’ uguale a Bm, ossia al più piccolo insieme per il quale Bm = Bm+1. I termini della rete sono finiti, di conseguenza il calcolo di B* converge a |E(t)|, ossia l’insieme delle entrate globali di ciascun termine. Al caso pessimo |E(t)| è uguale all’insieme di tutti i termini della rete, questo è un caso limite che si verifica nel momento in cui: per ogni coppia di termini, esiste un’articolazione che li collega.
Proposizione 4. Per ogni termine t appartenente alla terminologia della rete N ={S1,…,Sn},
E(t) = LFP(e(t)) = A*, dove LFP(F) rappresenta il minimo punto fisso di F su (2T, ⊆ ).
La Tabella 2.1 mostra le computazioni A* e B* del termine tk= c (vedi esempio Figura 2.3).
i Aki i k B 0 {c} {b3, a3} 1 {c, b3, a3} {b3, a3, b1} 2 {c, b3, a3, b1} {b3, a3, b1, c} 3 {c, b3, a3, b1} {b3, a3, b1, c} Tabella 2.1 Computazioni A* e B*
I due insiemi convergono per m = 2. Infatti:Bk2 =