Correspondencia de grafos RDF
Claudio Gutiérrez
Julio Águila
Introducción

¿Cómo determinar si dos archivos RDF
representan lo mismo?
 Problema: pueden representar el mismo
modelo pero este puede estar declarado en
orden distinto.
 Utilidad: determinar equivalencia entre
modelos representados (mismo significado)
Ejemplo
<rdf:RDF
xmlns:rdf=“http://www.w3.org/1999/02/22-rdf-syntax-ns#”
xmlns:t=“http://example.org/brothers#”
xmlns:base=“http://example.org/brothers” >
<rdf:Description t:name=“John”>
<t:child t:name=“Robert”/>
<t:child t:name=“Jeremy”/>
<t:child t:name=“Terry”/>
</rdf:Description >
</rdf:RDF >
Ejemplo
<rdf:RDF
xmlns:rdf=“http://www.w3.org/1999/02/22-rdf-syntax-ns#”
xmlns:t=“http://example.org/brothers#”
xmlns:base=“http://example.org/brothers” >
<rdf:Description t:name=“John”>
<t:child t:name=“Jeremy”/>
<t:child t:name=“Terry”/>
<t:child t:name=“Robert”/>
</rdf:Description >
</rdf:RDF >
Ejemplo
_:a3 <http://example.org/brothers#name> “Robert”
_:a1 <http://example.org/brothers#name> “John”
_:a1 <http://example.org/brothers#child> _:a9
_:a1 <http://example.org/brothers#child> _:a3
_:a9 <http://example.org/brothers#name> “Terry”
_:a6 <http://example.org/brothers#name> “Jeremy”
_:a1 <http://example.org/brothers#child> _:a6
_:a3 <http://example.org/brothers#name> “Jeremy”
_:a6 <http://example.org/brothers#name> “Terry”
_:a1 <http://example.org/brothers#name> “John”
_:a1 <http://example.org/brothers#child> _:a9
_:a1 <http://example.org/brothers#child> _:a3
_:a9 <http://example.org/brothers#name> “Robert”
_:a1 <http://example.org/brothers#child> _:a6
John
Robert Terry Jeremy
Ejemplo
_:a1 <#name> “John”
_:a1 <#child> _:a9
_:a9 <#name> “Terry”
_:a1 <#child> _:a3
_:a3 <#name> “Robert”
_:a1 <#child> _:a6
_:a6 <#name> “Jeremy”
_:a1 <#name> “John”
_:a1 <#child> _:a9
_:a9 <#name> “Robert”
_:a1 <#child> _:a3
_:a3 <#name> “Jeremy”
_:a1 <#child> _:a6
_:a6 <#name> “Terry”
Ejemplo
<#name>
“John”
“Terry”
_:a9
<#child>
<#name>
_:a1 <#name> “John”
_:a1 <#child> _:a9
_:a9 <#name> “Terry”
_:a1 <#child> _:a3
_:a3 <#name> “Robert”
_:a1 <#child> _:a6
_:a6 <#name> “Jeremy”
_:a1 <#child>
_:a3 <#name>
“Robert”
<#child>
_:a6
<#name>
“Jeremy”
Ejemplo
<#name>
“John”
“Robert”
_:a9
<#child>
<#name>
_:a1 <#child>
_:a1 <#name> “John”
_:a1 <#child> _:a9
_:a9 <#name> “Robert”
_:a1 <#child> _:a3
_:a3 <#name> “Jeremy”
_:a1 <#child> _:a6
_:a6 <#name> “Terry”
<#child>
_:a6
_:a3 <#name>
“Jeremy”
<#name>
“Terry”
Ejemplo
“Terry”
<#name>
“John”
<#name>
_:a9
“John”
_:a9
<#child>
<#name>
_:a1 <#child>
<#child>
<#name>
_:a1
<#child>
_:a6
_:a3 <#name>
“Jeremy”
<#child>
_:a6
<#child>
“Robert”
_:a3 <#name>
<#name>
“Jeremy”
“Robert”
<#name>
“Terry”
Algoritmo de fuerza bruta
IF |V1| = |V2| SET n = |V1|
SINO no son isomorficos
REPEAT
GEN MAPPING DE V1 2 V2
IF CHECK EDGES
es isomorfico
BREAK
n! combinaciones
O(n2 )
Algoritmo con clasificación de nodos
IF |V1| = |V2| SET n = |V1|
SINO no son isomorficos
CLASIFIQUE G1 & G2 SEGÚN INVARIANTE
grado de los nodos
otros
FOREACH CLASS C
IF |V1,c| = |V2,c| ASOCIE C con una clase en G2
SINO no son isomorficos
REPEAT
GEN MAPPING DE V1 2 V2
IF CHECK EDGES
es isomorfico
BREAK
Clasificación de nodos por adyacencia
2
3
A
2
B
A
F
C
B
2
F
D
3
3
C
4
D
3
4
E
E
2
2
INVARIANTE=GRADO
{ [A,E,F],[B,C],[D] }
3
2
1
2
Clasificación de nodo iterativa
IF |V1| = |V2| SET n = |V1| SINO no son isomorficos
CLASIFICAR nodos de V1 & V2 en una sola clase
REPEAT
REPEAT // reclasificación
FOREACH NODO RECLASIFIQUE
Adyacencia con otras
clases y con nodos de
la misma
IF CADA CLASE TIENE 1 ELEMENTO
RETURN es isomorfico;
Biyección por
IF NOT ASOCIAR POR CARD. DE CLASE
cardinalidad
RETURN no es isomorfico;
IF (NEW.CLASIFICACION = OLD.CLASIFICACION | |
EXISTE CLASE CON CARDINALIDAD <= COTA)
BREAK;
USANDO LA CLASE CON CARD. MENOR
Cardinalidad máxima para
fuerza bruta
FUERZA BRUTA SOBRE Cmin
IF CHECK NODES
G1 = G1 – Cmin; G2 = G2 - Cmin
Clasificación de nodo iterativa
2
3
A
1.- {A,B,C,D,E,F}
B
F
C
D
3
2
2.- { [A,E,F],[B,C],[D] }
3.- { [A],[E,F],[B,C],[D] }
4
E
2
A=(0,0,2,0)
B=(1,1,0,1)
C=(1,1,0,1)
D=(0,2,2,0)
E=(0,0,1,1)
F=(0,0,1,1)
SELECT
Clasificación de nodo iterativa
2
F
2
3
A
E1
B
E4
E5
E2
C
3
3
E7
E
2
B
E1
2
E6
D
E3
E8
F
E5
4
E4
C
3
E6
E2
2
A
D
E3
E8
4
E7
E
2
Isomorfismo de Grafos a Través
de Subgrafos de Mayor Longitud
•Si dos Grafos son Isomorficos, entonces los
subgrafos de mayor longitud también lo son.
(Transitividad e Inducción).
•El tiempo en calcular el subgrafo de mayor longitud
es menor que el tiempo total involucrado en
determinar si dos grafos son isomorficos.
•El objetivo es determinar los subgrafos de los grafos
A y B, si los subgrafos(A) y subgrafo(B) son iguales
entonces existe una gran probabilidad de que A y B
sean iguales.
Algoritmo
• El objetivo es utilizar una heurística con información
en los arcos de los grafos.
•Para ello debe existir un prepocesamiento de los grafos.
•El prepocesamiento supone una asignación numérica
de los vértices y de los arcos.
•No debería de existir problemas de colisiones.
Algoritmo
DESCOMPOSITION(B)
1.
2.
3.
4.
5.
let B={G1,G2} and D(B)=0
Smax,G1=
Smax,G2=
Smax,G1=descompose(G1, Smax,G1, v1,G1)
Smax,G2=descompose(G2, Smax,G2,v1,G2)
Algoritmo
DESCOMPOSE(G, Smax,v)
S'max=0
2.
suc=sucesores(G,v)
3.
DephtMarkVertice(G,v)
4.
CicleMarkVertice(G,v)
1.
for all suc of v
6.
(a) If(!IsDepthVerticeMark (G,vi))
7.
(b ) If(!IsCicleVerticeMark (G,vi))
8.
(b.1) S'max= DESCOMPOSE(G, Smax, vsuc)
9.
(c) if Smax< S'max
10.
(c.1) Smax=S'max
11.
(d) else continue
12. CicleDesmarkVertice(G,vi)
13. return(Smax)
1.
Algoritmo
MATCHING_SUBGRAPHS(S’, S)
1.
if(S’.lp== S.lp && S’.tcs== S.tcs.&& S’.tcg==S.tcg && S’.E== S.E)
2.
(a) for all V  S1
3.
(a.a) if ((S’.et1(v)== S.et1(v)  S’.et2(v)== S.et2(v)) &&S’.a(v)== S.a(v) &&
S’.e(v)== S.e(v))
4.
(a.b) continue
5.
(a.c) else return false
6.
return true
7.
else return false
Ejemplo
Tarea por realizar
•Modificar la estructura a lista enlazada
•Realizar las pruebas
Conclusiones
•Es posible usar algoritmos clásicos de
isomorfismos de grafos para comparar grafos
RDFcon nodos blancos.
• Dado que el uso standard de RDF no presenta
casos patológicos donde los algoritmos
anteriores no funcionen, en promedio el
desempeño es satisfactorio.
Descargar

Iterative.