Generalized Graph Pattern Matching
Full text
Gene alized G aph Pa e n Ma ching
Ped o Almag o-Blanco and Fe nando Sancho-Capa ini
Augus 15, 2017
1 In oduc ion
G aphs a e high exp essi e models and especially sui able o modelling highly
complex s uc u es, he numbe o applica ions ha use hem o modelling
bo h hei da a and he p ocesses ha manipula e has g own d ama ically in
ecen yea s.
The use o new concep ual s uc u es in eal-wo ld applica ions equi es he
de elopmen o new sys ems o s o e and que y such s uc u es in o de o allow
use s o access da a e ec i ely and e icien ly. As wi h all new echnologies, i
is s ill in he de elopmen phase and in sea ch o a se o s anda ds ensu ing a
con inued g ow h.
The g owing popula i y o G aph Da abases has led o he eme gence o
in e es ing p oblems ela ed o s o age and que y in hese sys ems. These
da abases ha e obus undamen als in e ms o basic in o ma ion managemen
(c ea ion, access, dele ion, and modi ica ion o indi idual elemen s o he s uc-
u e), bu hey lack s anda ds in some o he asks necessa y o he s o age and
e ie al o in o ma ion, like hose ela ed o mo e ad anced que y mechanisms.
Among he p oblems ela ed o hese que y p ocesses, he de ec ion o pa -
e ns is conside ed as one o he undamen al ones since i includes o he sub-
p oblems necessa y o ob ain powe ul que y sys ems, such as he sea ch o
subg aphs o minimum pa hs, o he s udy o connec i i y [18, 10].
In his pape we p esen Gene alized G aph Que y (GGQ), a p oposal o
ca y ou que ies in p ope y g aphs. GGQ ep esen s a obus logical ame-
wo k, making i especially use ul in g aph disco e y p ocedu es and gene alizing
o he mo e basic ools ha ha e been p o ed e y use ul on ela ed asks. In
addi ion, we will p esen a collec ion o ope a ions ha allow o ob ain complex
GGQs om simple ones, some hing e y use ul when au oma ing he cons uc-
ion o complex que ies.
2 G aph Pa e n Ma ching
G aph Pa e n Ma ching is an ac i e esea ch a ea since mo e han 30 yea s
and i s use ulness has been demons a ed in many a eas, om a i icial ision,
o biology, h ough elec onics, compu e -aided design, and analysis o social
ne wo ks, among o he s. Undoub edly, i s in e es has g own e en mo e as
g aph da abases has become a ool o s uc u ing and s o ing in o ma ion in
a ans e sal way in all a eas o knowledge. Fo his eason, he p oblem o
g aph pa e n ma ching expands, wi h sligh a ian s, ac oss di e en scien i ic
1
communi ies, showing ha is no a single p oblem de ined unde a common
o maliza ion, bu a se o ela ed p oblems.
The p ocess by which we check he p esence o a pa icula pa e n in a
pa icula se o da a is called pa e n de ec ion, and compu a ionally ep esen s
he se o mechanical p ocesses ha allow o e u n one (o all) he occu ences
o he pa e n.
The de ini ion o wha is mean by an occu ence o a pa e n in a g aph
a ies acco ding o how he pa e n is de ined. When i is gi en by a g aph
s uc u e (al hough no necessa ily using he same elemen a y se s o e ices
and edges as he g aph on which he que y is made) i is usual o associa e
he occu ence wi h he exis ence o iden i ica ions (pe haps no as s ong as
isomo phisms) be ween he pa e n and hose subg aphs in he da a ha espec
some imposed cons ain s [6].
Some classi ica ions ha we can p esen in e ms o he di e en possible
ways o ca y ou he de ec ion o pa e ns in g aphs a e: (a) S uc u al s.
Seman ic, (b) Exac s. Inexac , and (c) Op imal s. Ap oxima e [9].
One o he classi ica ion akes in o accoun he ela ion o be me by he
pa e n ega ding o he subg aphs ha a e conside ed i s occu ences. I allows
o di ide he di e en echniques o g aph pa e n ma ching in hose based
on Isomo phisms (an occu ence will be any subg aph ha is isomo phic o
he pa e n), G aph Simula ion [13] (an occu ence will be any subg aph o
which he e is a bina y ela ion be ween he elemen s o he subg aph and he
pa e n which espec s he ypes o he nodes and hei adjacencies), Bounded
Simula ion [8, 18, 13] (based on G aph Simula ion bu allowing o associa e
pa e n edges o pa hs) and Regula Pa e n Ma ching [7, 15, 4, 13] (Bounded
Simula ion wi h egula exp essions o pa e n edges).
Cu en ools ha allow que ying pa e ns in g aphs use ei he a decla a i e
language (such as Cyphe , SPARQL, o SQL), o an impe a i e language (wi h
G emlin as he clea es ep esen a i e). In he case o decla a i e languages, i
is esponsibili y o he sys em (ideally) o pe o m que ies op imiza ion. In he
case o impe a i e languages, he execu ion plan is esponsibili y o he use , so
hey usually p o ide lowe le el app oxima ions.
Nex , we b ie ly p esen some que y languages ha ha e been used o g aph
pa e n ma ching.
SQL (S uc u ed Que y Language) is a decla a i e language o accessing
Rela ional Da abase Managemen Sys ems (RDBMS). These ypes o da abases
we e designed o abula da a wi h a ixed schema, and wo k bes in con ex s
ha a e well de ined om he beginning and whe e he eco ds hemsel es a e
mo e impo an han he ela ionships be ween hem. Fo his eason, ying
o answe ques ions in ol ing many ela ionships be ween da a (as is usual in
g aph pa e n que ies) wi h a ela ional da abase in ol es nume ous and cos ly
ope a ions be ween ables, ha may become his op ion in ac able. In spi e o
his, SQL has he exp essi e capaci y necessa y o be able o exp ess mos o
g aph pa e n que ies, and because ela ional da abases ha e been he s o age
op ion chosen by mos p ojec s o decades, he i s g aph pa e n que y sys ems
used SQL que ies, such as Selec ion G aphs ha we will see la e .
SPARQL is a decla a i e que y language o da a s o ed in RDF o ma
[16] and is ecognized as a key echnology o he Seman ic Web, i s exp essi e
abili y o pe o m g aph pa e n ma ching is supe io o ha p o ided by SQL,
bu is s ill no in ui i e o a human use . SPARQL allows s uc u al, seman ic,
2
op imal, and exac que ies based on subg aph isomo phism. Al hough SPARQL
does no allow o any ype o G aph Simula ion o Regula Pa e n Ma ching,
language ex ensions such as PSPARQL [3] ha e been de eloped o que y RDF
da abases using pa e ns ha make use o egula exp essions. Thanks o he
s uc u e o he language, i is ela i ely easy o gene a e au oma ic que ies in
SPARQL and he e a e ools ha use i as a inal que y language.
G emlin is, a he same ime, a que y language o da abases and a g aph
o ien ed compu a ion sys em. As a language, G emlin is independen o he
unde lying da abase. I s syn ax allows o decla a i e and impe a i e que ies,
and easily exp ess complex que ies on g aphs. Each que y consis s o a sequence
o s eps ha pe o m a omic ope a ions on he da a s eam. G emlin allows
seman ic, exac , op imal que ies and is based on subg aph isomo phism. I is
possible o design o he que y languages o compile o G emlin language (eg,
SPARQL can be compiled o un on G emlin 1).
Selec ion G aphs a e mul i- ela ional pa e ns o exp ess SQL based que ies.
They ep esen he ounda ion o he mul i- ela ional decision ee induc ion al-
go i hm MRDTL [12] as well as o he mul i- ela ional au oma ic lea ning algo-
i hms [14]. The pu pose o selec ion g aphs is o be used in op-down disco e y
p ocedu es [11], hus ope a o s o modi y hem h ough small changes a e p o-
ided ha allow he cons uc ion o complex que ies in successi e s eps. As a
coun e pa , hey ha e he disad an age ha hese cons uc ions can no con-
ain cycles, limi ing he exp essi eness o que ies. Selec ion g aphs ep esen an
exac , op imal ype o g aph pa e n ma ching based on seman ic g aph isomo -
phism. In addi ion, being a g aphical ep esen a ion o SQL que ies, hey inhe i
he e iciency p oblems p esen ed by he sys ems based on his echnology. The
new p oposal we show in hese pages can be conside ed as a gene aliza ion o
some o he ideas ha p omo ed his p e ious app oach, a oiding some o hei
limi a ions.
Cyphe is a decla a i e que y language speci ically de eloped o wo k on
Neo4j g aph da abase 2. Cyphe is designed o be a human- iendly que y lan-
guage, close o bo h de elope s and end use s. Que y pa e ns in g aphs ha
a e usually ha d o exp ess in o he languages a e e y simple in Cyphe [2],
showing a high exp essi e capaci y [1]. Neo4j da abase closely ollows he p op-
e y g aph model, bu o ces he edges o be yped. Unlike G emlin, Cyphe is
no Tu ing comple e, so i has some limi a ions, and i is highe le el. Simple
Cyphe que ies ha e good pe o mance, bu when que ies ollow complex pa -
e ns hey can lead o a wo s pe o mance since i does no allow o indica e
he applica ion o de o he di e en condi ions. Cyphe allows s uc u al and
seman ic, op imal, exac , and based on subg aph isomo phism que ies. In ad-
di ion, i allows a ype o Regula Pa e n Ma ching in which he edges in he
pa e n a e p ojec ed on o pa hs o he g aph, and whe e cons ain s can be
imposed h ough exp essions ha make use o he disjunc ion ope a o and he
closu e o Kleene. One limi a ion om he academic poin o iew is ha i
lacks an associa ed o mal model, and some o i s ope a ions ha e no ye been
alida ed. Despi e his, because o i s excellen exp essi eness and accep able
pe o mance, and because i consumes he da a om a g aph da abase wi h a
widesp ead use, Cyphe has been he elec ion o implemen he es s o GGQ.
1h ps://gi hub.com/dkuppi z/spa ql-g emlin
2h p://neo4j.o g
3
Some o he ools ela ed o g aph pa e n ma ching a e: G aphLog [5], ha
allows o s uc u e he que ies as g aphs and e alua es he exis ence o pa e ns
be ween a pai o nodes o gene a e a new edge be ween hem; G aphQL 3, a
decla a i e que y language de eloped by Facebook o allow ex e nal applica ions
o access i s in o ma ion; G aql 4, a decla a i e que y language o ien ed o
knowledge g aphs; and GGQL [17], a SQL ex ension wi h addi ional g aph
pa e n ma ching ools (analysis o accessibili y be ween nodes, de ini ion o
pa hs, o cons uc ion o g aphs).
3 P elimina ies
Gi en a se V, we deno e:
V0=∅, V 1=V, V n+1 =Vn×V, V ∗=[
n≥0
Vn
In gene al, we call sequences o lis s he elemen s in V∗. I x∈Vn hen we
say ha xhas leng h n, and we w i e |x|=n.
I x= (a1, . . . , an), y = (b1, . . . , bm)∈V∗, hen he conca ena ion o xand
yis he elemen o V∗gi en by xy = (a1, . . . , an, b1, . . . ,bm).
Fo each x= (a1, . . . , an)∈Vn, we call suppo se o x o s(x) = {ai: 1 ≤
i≤n}. We w i e a∈x o indica e ha a∈s(x).
Fo each a∈V, we deno e |a|x= #{i:xi=a}(whe e #(A) is he
ca dinal o he se A), and we call mul i-suppo o x o he se o pai s ms(x) =
{(a, |a|x) : a∈x}. We de ine he ela ion ∼, which can be easily p o ed o
be equi alence in Vn, as: x∼yi and only i ms(x) = ms(y) And deno e by
Vn
∼=Vn/∼(se quo ien o Vnunde ∼).
Ou in e p e a ion o hese se s will be ha Vndeno es he se o o de ed
uples o V,Vn
∼deno es he se o uno de ed uples o he same se (ie uples
in which elemen s a e impo an , conside ing he possible epe i ions, bu no
he o de in which hey appea ).
Nex , we p esen he Gene alized G aph, ha co e s he di e en a ian s o
g aph ha can be ound in he li e a u e and ha we will need when p esen ing
ou p oposal o p ope y g aph pa e n ma ching ool.
De ini ion 1. AGene alized G aph is a uple G= (V, E, µ)whe e:
•Vand Ea e se s, called, espec i ely, se o nodes and se o edges o G.
•µis a ela ion (usually we will conside i unc ional, bu no necessa ily)
ha associa es each node o edge in he g aph wi h i s se o p ope ies,
ha is, µ: (V∪E)×R→S, whe e R ep esen s he se o possible keys
o hese p ope ies, and S he se o possible alues associa ed.
Usually, o each α∈Rand x∈V∪E, we w i e α(x) = µ(x, α).
In addi ion, we equi e he exis ence o a special key o he edges o he
g aph, which we call incidences and deno e by γ, which associa es o each edge
o he g aph a uple, o de ed o no , o e ices o he g aph.
3h p://g aphql.o g/
4h ps://g akn.ai
4
Al hough he de ini ion ha we ha e p esen ed he e is mo e gene al han
hose ha can be ound in he ela ed li e a u e, we will also call hem P ope y
G aphs, since hey suppose a na u al ex ension o his ype o g aphs.
I should be no ed ha in gene alized g aphs, unlike adi ional de ini ions,
he elemen s in Ea e symbols ep esen ing he edges, and no pai s o elemen s
om V, and γis he unc ion ha associa es o each edge he se o e ices
ha i connec s.
De ini ion 2 (No a ion and de ini ions).In he con ex o he abo e de ini ions,
we use he ollowing no a ion:
•We usually iden i y ewi h γ(e). Thus, we in e p e he edge as he collec-
ion o nodes ha connec s, as classic de ini ions o g aphs.
•Symme ically, o e e y u∈Vwe w i e γ(u) = {e∈E:u∈e}. In
gene al, a gene alized g aph may ha e a combina ion o di ec ed and non-
di ec ed edges. I γ:E→V∗we say G o be Di ec ed (No Di ec ed,
o he wise).
•Fo each e∈E, we de ine he a i y o eas Pa∈e|a|e.
•I γ:E→V2∪V2
∼we say ha he g aph is Bina y (and i ma ches he
mos usual g aph s uc u e). O he wise, he g aph is a Hype g aph.
•An edge, e∈E, is said o be a loop i i connec s a node o i sel , ha is,
i i has a i y o he han 1 bu s(e)is uni a y.
•An edge, e∈E, is said o be inciden on a node, ∈V, i ∈e.
•Two dis inc nodes, u, ∈Va e called adjacen , o neighbo s, in G=
(V, E, µ)i he e exis s e∈Esuch ha {u, } ⊆ e.
•I he e a e di e en edges in Ewi h he same incidence, ha is, edges
connec ing he same nodes, we will say ha he g aph is a Mul i-g aph.
•I eis a di ec ed bina y edge connec ing u o ,e= (u, ), we w i e ue
→ ,
and we also deno e eo=u(ou pu o e) y ei= (inpu o e). In his
case, o each u∈Vwe w i e:
γo(u) = {e∈γ(u) : eo=u}
γi(u) = {e∈γ(u) : ei=u}
which espec i ely deno e he se s o ou going edges and incoming edges
o u.
•Gi en u∈V, we de ine he en i onmen o uin Gas he se o nodes,
including u, ha a e connec ed o i , i.e.: N(u) = Se∈γ(u)γ(e). When
necessa y, we will use he educed en i onmen o u,N∗(u) = N(u) u.
The no ion o subg aph is ob ained om he usual de ini ion by imposing
ha he p ope ies a e also main ained in he common elemen s.
De ini ion 3. A subg aph o a g aph G= (V, E, µ)is a g aph S= (VS, ES, µS)
such ha VS⊆Vand ES⊆Eand µS⊆µ|VS∪ES. We deno e S⊆G.
5
A undamen al concep when wo king wi h g aphs is he concep o pa h,
which allows he s udy o dis ance ela ionships and connec i i y condi ions
be ween di e en elemen s, ex ending he connec i i y allowed by edges o mo e
gene al si ua ions.
As gene alized g aphs a e conside ably mo e gene al han he usual ones we
should gi e some no ions abou he posi ion o a node in an edge:
De ini ion 4. I e∈Eand γ(e)=( 1, . . . , n)∈Vn, hen o each i∈s(e)
we de ine i s o de in eas o de( i) = i. I e∈Vn
∼, hen o each ∈s(e)we
de ine o de( )=0.
We deno e u≤e o indica e ha o de(u)≤o de( ).
F om his ela ion o o de be ween he nodes ha an edge connec s, we can
de ine wha we mean by a pa h in a g aph.
De ini ion 5. Gi en a g aph G= (V, E, µ), he se o pa hs in G, deno ed by
PG, is de ined as he minimal se e i ying:
1. I e∈E,u, ∈ewi h u≤e , hen ρ=ue
→ ∈ PG, and sopV(ρ) =
(u, ),sopE(ρ)=(e). We will say ha ρconnec s he nodes uand o
G, and we will deno e i by uρ
.
2. I ρ1, ρ2∈ PG, wi h uρ1 , ρ2
w, hen ρ1·ρ2∈ PG, wi h uρ1·ρ2
w,
sopV(ρ1·ρ2) = sopV(ρ1)sopV(ρ2),sopE(ρ1·ρ2) = sopE(ρ1)sopE(ρ2).
When u= we say ha ρis a closed pa h, and i he e a e no epea ed edges
in ρwe say ha i is a cycle.
I ρ∈ PG, wi h sopV(ρ) = (u1, . . . , un+1) and sopE(ρ) = (e1. . . , en), hen
we w i e:
ρ=u1
e1
→u2
e2
→. . . en
→un+1
Gene ally we will w i e u∈ρ o exp ess ha u∈sopV(ρ), and e∈ρ o
exp ess ha e∈sopE(ρ).
Rema k.
•Following a simila no a ion o he case o di ec ed bina y edges, i ρ∈
P(G)and uρ
, hen we w i e ρo=uand ρi= .
•When necessa y, we deno e he pa hs h ough u, s a ing in u, and ending
in u, espec i ely, by:
Pu(G) = {ρ∈ P(G) : u∈ρ}
Po
u(G) = {ρ∈ P(G) : ρo=u}
Pi
u(G) = {ρ∈ P(G) : ρi=u}
6
4 Gene alized G aph Que y
Nex , we p esen Gene alized G aph Que y (GGQ, o sho ), ou p oposal o
pe o m g aph pa e n ma ching on gene alized g aphs. Taking in o accoun
he di e en classi ica ions men ioned abo e, we can say ha his p oposal al-
lows o ca y ou s uc u al and seman ic, exac , op imal, and based on a ype
o Regula Pa e n Ma ching que ies, allowing he edges o he pa e n o be
p ojec ed on pa hs (no necessa ily edges). Also, GGQ allows o exp ess mo e
complex cons ain s on each elemen o he pa e n and pe o m cyclic que ies.
One o he cha ac e is ics ha we pu sue o ou ool is o p o ide a mech-
anism o ob ain complemen a y pa e ns o a gi en one. This means ha i a
s uc u e does no e i y a pa e n i mus always e i y one o i s complemen-
a y pa e ns. As we ha e seen in p e ious sec ion, many o he ools de eloped
o pe o m que ies o pa e ns in g aphs equi e o a p ojec ion o be ul illed
be ween he pa e n and he s uc u e o be e alua ed. This p ojec ion p e en s
us om e alua ing he non exis ence o elemen s, some hing ha we will need
o gene a e hese complemen a y pa e ns, o his eason ou p oposed ma ch-
ing sys em will no make use o p ojec ions, bu is based on logical p edica es,
acili a ing he gene a ion o complemen a y pa e ns.
We wan o emphasize ha one o ou main goals is o p o ide a comple e
o maliza ion o he model, bu wi h he seconda y objec i e o p o iding an
implemen a ion ha is usable om a p ac ical poin o iew 5(as a p oo o
concep mo e han as a p o essional ool in his i s s age).
In pu sui o ou objec i es, we will ely on Selec ion G aph model, ex ending
i o add Regula Pa e n Ma ching and some addi ional ea u es ha will allow
us o ob ain a g ea e exp essi eness powe in he pa e ns.
As main di e ences wi h he que y sys ems om he p e ious sec ion we can
indica e ha :
•GGQ may con ain cycles. I will be a la e p oblem o conside imple-
men a ions o GGQs ha handle cycles p ope ly, conside ing addi ional
cons ain s o ensu e ce ain le els o e iciency in hei ac ual execu ion, o
being ca e ul when designing he que y o c ea e a pa e n ha is e icien
in he a ailable implemen a ion.
•GGQ can e alua e subg aphs. In selec ion g aphs i is only possible o
e alua e a single node ep esen ing he a ge able. In he case o GGQ,
ixed elemen s (elemen s ha mus belong o he subg aph unde e al-
ua ion) will be ep esen ed h ough a p edica e ha o ces hem o be
con ained in he subg aph o be e alua ed.
•Indi idual edges o he GGQ can be p ojec ed on o pa hs in he g aph
whe e he pa e n is being checked. Fo his eason, p edica es will be
used in a simila way as in Regula Pa e n Ma ching.
•The p edica es associa ed wi h nodes o edges in he GGQ can e alu-
a e s uc u al and seman ic cha ac e is ics beyond he p ope ies s o ed
h ough he µ unc ion ( o example, using me ics on he g aph o i s
elemen s).
5h ps://gi hub.com/palmag o/ggq
7
We will b ie ly o malize wha we unde s and conc e ely by a p edica e de-
ined on a g aph.
Conside Θ, a collec ion o unc ion, p edica e, and cons an symbols, con-
aining all he unc ions om µ oge he wi h cons an s associa ed wi h each
elemen o he g aph and possibly some addi ional symbols ( o example, me -
ics de ined on he elemen s o he g aph). F om his se o symbols we can
de ine a Fi s O de Language wi h equali y, L, making use o Θ as a se o non
logical symbols, on which we cons uc , in he usual way, he se o e ms o he
language and he se o o mulas, FORM(L), which we will call p edica es.
Al hough, gene ally, he de inable o mulas in Lcan be applied o all objec s
in he uni e se, which in ou con ex will consis in elemen s o g aphs (nodes,
edges, and s uc u es o med om hem), when we wan o make explici he
ypes o objec s we a e wo king wi h, we can w i e FORMV(L) o o mulas on
nodes, FORME(L) o o mulas on edges, FORMP(L) o o mulas on pa hs,
e c.
In o de o simpli y he no a ion, when he e is no possibili y o con usion
we will use FORM o deno e FORM(L).
In addi ion, and aking ad an age o he exp essi eness capaci y o gene al-
ized g aphs, we de ine he que y sys em using he same s uc u e:
De ini ion 6. AGene alized G aph Que y (GGQ) o e Lis a bina y gene -
alized g aph, Q= (VQ, EQ, µQ), whe e exis αand θ, p ope ies in µQ, such
ha :
•α:VQ∪EQ→ {+,−} o al.
•θ:VQ∪EQ→FORM(L)associa es a bina y p edica e, θx, o each
elemen xo VQ∪EQ.
We will w i e Q∈GGQ(L) o deno e ha Qis a Gene alized G aph Que y
o e L(i he language is p e ixed, we simply w i e Q∈GGQ).
In he seman ics associa ed wi h a GGQ we will use he second inpu o
hese bina y p edica es o impose equi emen s o membe ship on subg aphs
o G( he gene al g aph on which we a e e alua ing que ies), whe eas he i s
inpu mus ecei e elemen s o he co esponding ype o which i is associa ed:
i Sis a subg aph and a∈VQ hen θa(., S)∈FORMV, and i e∈EQ hen
θe(., S)∈F ORMP. Fo example:
θa( , S) = ∃z∈S(z )
θe(ρ, S) = ∃y, z(yρ
z∧y /∈S∧z∈S)
θa( , S) will wo k o nodes, and i will be e i ied when he e is a pa h in
G ha connec s a node o S( he subg aph we a e e alua ing) wi h , he inpu
node on which i is e alua ed. θe(ρ, S) will wo k o pa hs, and will be e i ied
when he e alua ed pa h, ρ, connec s Swi h i s complemen a y (in G).
Gi en a GGQ unde he abo e condi ions, x+, espec i ely x−, will indica e
ha α(x) = +, espec i ely α(x) = −, and V+
Q/V −
Q( espec i ely, E+
Q/E−
Q) he
se o posi i e/nega i e nodes ( espec i ely, edges). I o an elemen , θxis no
explici ly de ined, we assume i o be a au ology (gene ally deno ed by T).
As we will see below, posi i e elemen s o he pa e n ep esen elemen s
e i ying he associa ed p edica es ha mus be p esen in he g aph, while
nega i e ones ep esen elemen s ha should no be p esen in he g aph.
8
In o de o be able o exp ess mo e easily he necessa y condi ions ha
de ine he applica ion o a GGQ on a g aph, as well as he esul s ha we will
see la e , we in oduce he ollowing no a ions:
De ini ion 7. Gi en a GGQ, Q= (VQ, EQ, µQ), he se o Q-p edica es asso-
cia ed o Qis:
1. Fo each edge, e∈EQ, we de ine:
Qeo( , S) = ∃ρ∈ Po
(G)θe(ρ, S)∧θeo(ρo, S)∧θei(ρi, S)
Qei( , S) = ∃ρ∈ Pi
(G)θe(ρ, S)∧θeo(ρo, S)∧θei(ρi, S)
In gene al, we will w i e Qe∗( , S), whe e ∗ ∈ {o, i}, and we will deno e:
Q+
e∗=Qe∗, Q−
e∗=¬Qe∗
2. Fo each node, n∈VQ, we de ine:
Qn(S) = ∃ ∈V
^
e∈γo(n)
Qα(e)
eo( , S)∧^
e∈γi(n)
Qα(e)
ei( , S)
=∃ ∈V
^
e∈γ∗(n)
Qα(e)
e∗( , S)
Tha can be w i en gene ally as:
Qn(S) = ∃ ∈V
^
e∈γ(n)
Qα(e)
e( , S)
In addi ion, we deno e:
Q+
n=Qn, Q−
n=¬Qn
F om hese no a ions, we can o mally de ine when a subg aph ma ches a
gi en GGQ:
De ini ion 8. Gi en a subg aph So a p ope y g aph, G= (V, E, µ), and a
Gene alized G aph Que y, Q= (VQ, EQ, µQ), bo h o e language L, we say ha
Sma ches Q, and we will deno e SQ, i he nex o mula is e i ied:
Q(S) = ^
n∈VQ
Qα(n)
n(S)
O he wise, we will w i e: S2Q.
No e ha , in pa icula , using S=Gwe can de ine when a g aph ma ches
a GGQ. A gene ic GGQ example is shown in Figu e 1.
One o he objec i es o GGQ is o p o ide powe enough o exp ess condi-
ions ha make use o elemen s ha a e ou side he subg aph being e alua ed,
some hing ha has been p o en necessa y o ha e a powe ul que y language
9
De ini ion 11. Gi en Q1, Q2∈GGQ, we say ha Q1is a Q−-conse a i e
ex ension o Q2, and we will deno e i by Q2⊆−Q1, i :
1. Q2⊆Q1(as gene alized g aphs, so in he Q2elemen s he alues o αand
θshould coincide o bo h GGQ).
2. Fo each nega i e node in Q2,n∈V−
Q2, and e e y edge inciden o i in
Q1,e∈γQ1(n), exis s an edge inciden o i in Q2,e0∈γQ2(n), imposing
he same es ic ion, ha is: Qe≡Qe0.
Figu e 11: Q−-conse a i e ex ension.
Figu e 11 shows an example o a conse a i e Q−-ex ension. The ex ension
made in he GGQ on he le o ge he GGQ on he igh imposes new e-
s ic ions on he posi i e node bu does no add any u he es ic ions o he
nega i e node.
Since nega i e nodes add non-exis ence cons ain s o subg aph e i ica ion,
conse a i e Q−-ex ensions ensu e ha new cons ain s a e no being added o
hem. Hence, we can gi e he nex esul :
Theo em 2. Gi en Q1, Q2∈GGQ, i Q2⊆−Q1 hen Q1Q2.
P oo . Since Q-p edica es associa ed o edges depend only on he in o ma ion
in he edge i sel (which conside s he alue o θa i s inciden nodes, ega dless
o he alue o αin hem), we can s a e:
∀e∈EQ2(Q1α(e)
e=Q2α(e)
e)
Conside ing his ac , we analyse how he Q-p edica es associa ed wi h he
nodes o bo h GGQ beha e:
•I n∈V−
Q2, since Q2⊆−Q1, is i ial ha Q1−
n=Q2−
n.
•I n∈V+
Q2, hen Q1+
n→Q2+
n, because (we will no e γ1,γ2 he incidence
16
unc ions o Q1and Q2, espec i ely):
Q1+
n=∃ ∈V
^
e∈γ1(n)
Q1α(e)
e
=∃ ∈V
^
e∈γ1(n)∩EQ2
Q1α(e)
e∧^
e∈γ1(n) EQ2
Q1α(e)
e
=∃ ∈V
^
e∈γ2(n)∩EQ2
Q2α(e)
e∧^
e∈γ1(n) EQ2
Q1α(e)
e
→Q2+
n
Hence:
Q1=^
n∈VQ1
Q1α(n)
n=^
n∈VQ2
Q1α(n)
n∧^
n∈VQ1 VQ2
Q1α(n)
n
=^
n∈V+
Q2
Q1α(n)
n∧^
n∈V−
Q2
Q1α(n)
n∧^
n∈VQ1 VQ2
Q1α(n)
n
→^
n∈V+
Q2
Q2α(n)
n∧^
n∈V−
Q2
Q2α(n)
n∧^
n∈VQ1 VQ2
Q1α(n)
n
=^
n∈VQ2
Q2α(n)
n∧^
n∈VQ1 VQ2
Q1α(n)
n
→Q2
P e ious esul sugges s ha a GGQ can be e ined by adding nodes (o
any sign) and edges o he exis ing posi i e nodes, bu because o he (nega ed)
in e p e a ion o Q-p edica es associa ed wi h nega i e nodes, ca e mus be
aken o main ain hei en i onmen o be su e ha adding mo e edges does
no weaken he imposed condi ions (and, he e o e, we would no ge e ined
p edica es).
In o de o ob ain con olled me hods o que y gene a ion, in he ollowing
we will gi e a cons uc i e me hod o e ine GGQ by uni s eps. To do his, we
will s a by looking a how GGQ beha es when cloning nodes.
A clone consis s o making copies o exis ing nodes, and cloning all he edges
inciden on hem (and be ween hem, in case we clone se e al nodes ha a e
connec ed in he o iginal GGQ). O cou se, he cloning ope a ion can be done
on any gene alized g aph, no only on GGQ.
De ini ion 12. Gi en a gene alized g aph G= (V, E, µ), and W⊆V, we de ine
he clone o Gby duplica ion o W, deno ed by ClW
G, as:
ClW
G= (V∪W0, E ∪E0, µ ∪ {(n0, µ(n))}n∈W∪ {(e0, µ(e))}e0∈E0)
whe e:
17
• o each n∈W,n0is a new node, and W0={n0:n∈W},
•E0is a se o new edges ob ained om inciden edges on nodes o Wwhe e
nodes o Wa e eplaced by copies o W0(edges connec ing o iginal nodes
wi h cloned nodes, and edges connec ing cloned nodes, a e cloned).
Figu e 12: Clone o a g aph
Figu e 12 shows an example o a cloned g aph by duplica ing wo o i s
nodes. In he o iginal g aph, on he le , he se o nodes o be cloned a e
highligh ed. The esul o he cloning is p esen ed in he g aph o he igh .
The ollowing esul shows ha cloning posi i e nodes does no al e he
meaning o he que ies.
Theo em 3. I Q∈GGQ and W⊆V+
Q, hen ClW
Q≡Q.
P oo . To acili a e he no a ion, le Q1=ClW
Q. Then, ollowing a simila
easoning o ha o he p e ious p oo :
Q1=^
n∈VQ1
Q1α(n)
n
=^
n∈VQ
Q1α(n)
n∧^
n∈W
Q1α(n0)
n0
=^
n∈VQ γQ(W)
Q1α(n)
n∧^
n∈γQ(W)
Q1α(n)
n∧^
n∈W
Q1α(n0)
n0
=^
n∈VQ γQ(W)
Qα(n)
n∧^
n∈γQ(W)
Qα(n)
n∧^
n∈W
Qα(n)
n
=Q
Con inuing wi h he idea o ob aining ools o build GGQ au oma ically, he
ollowing concep o e inemen comple es he ope a ions ha we need o e ine
a GGQ. A e inemen se o ms a kind o pa i ion o a gi en GGQ.
18
De ini ion 13. Gi en Q∈GGQ,R⊆GGQ is a e inemen se o Qin Gi :
1. ∀Q0∈R(Q0GQ)
2. ∀S⊆G(SQ⇒ ∃!Q0∈R(SQ0))
We a e now eady o p esen some e inemen se s ha will allow o au oma e
he p ocesses o c ea ion and modi ica ion o Gene alized G aph Que y. Le ’s
s a wi h he simples ope a ion, which allows o add new nodes o an exis ing
GGQ:
Theo em 4 (Add new node o Q).Gi en Q∈GGQ and m /∈VQ, he se
Q+{m}, o med by:
Q1= (VQ∪ {m}, EQ, αQ∪(m, +), θQ∪(m, T))
Q2= (VQ∪ {m}, EQ, αQ∪(m, −), θQ∪(m, T))
is a e inemen se o Qin G(Fig. 13).
P oo . We mus e i y ha he wo necessa y condi ions o e inemen se s a e
e i ied:
1. I is i ial ha Q⊆−Q1and Q⊆−Q2, hus Q1Qand Q2Q.
2. Gi en S⊆Gsuch ha SQ. Then:
Q1=Q∧Qm
Q2=Q∧ ¬Qm
whe e Qm=∃ ∈V(T).
I G6=∅, hen SQ1and S2Q2.
I G=∅, hen S2Q1and SQ2.
Usually, G6=∅, hence his ope a ion does no eally e ine, in he sense
ha Q1≡Qand Q2≡ ¬T. Howe e , al hough we ob ain an equi alen GGQ,
his ope a ion is e y use ul o add new nodes o a GGQ in o de o add new
es ic ions o hem la e .
Figu e 13: Re inemen Add node
We p oceed now o gi e a second e inemen se ha allows o c ea e edges
be ween exis ing nodes. In o de o ge a e inemen o he o iginal GGQ we
mus es ic he addi ion o edges o posi i e nodes.
19
Theo em 5 (Add new edge be ween pos i e nodes o Q).Gi en Q∈GGQ
and n, m ∈V+
Q, he se Q+{n+e∗
−→ m+}(∗ ∈ {+,−}), o med by (whe e
Q0=Cl{n,m}
Q):
Q1= (VQ0, EQ0∪ {n+e∗
−→ m+}, θQ0∪(e, T))
Q2= (VQ0, EQ0∪ {n+e∗
−→ m−}, θQ0∪(e, T))
Q3= (VQ0, EQ0∪ {n−e∗
−→ m+}, θQ0∪(e, T))
Q4= (VQ0, EQ0∪ {n−e∗
−→ m−}, θQ0∪(e, T))
is a e inemen o Qin G(Fig. 14).
P oo .
1. Since Q0is a clone o Q, and {n, m} ⊆ V+
Q, hen Q≡Q0. In addi ion,
Q0⊆−Q1, Q2, Q3, Q4, hus Q1, Q2, Q3, Q4Q0≡Q.
2. Le us conside he p edica es:
Pn=∃ ∈V
^
a∈γ(n)
Qα(a)
a∧Qα(e)
eo
Pm=∃ ∈V
^
a∈γ(m)
Qα(a)
a∧Qα(e)
ei
I SQnand SQm, hen we ha e ou mu ually complemen a y
op ions:
•SPn∧SPm⇒SQ1
•SPn∧S2Pm⇒SQ2
•S2Pn∧SPm⇒SQ3
•S2Pn∧S2Pm⇒SQ4
I n=m(eis a loop) hen he p e ious e inemen se is {Q1, Q4}.
Nex ope a ion adds an addi ional p edica e o an exis ing edge. To keep
he necessa y s uc u al condi ions, his ope a ion is es ic ed o posi i e edges
connec ing posi i e nodes.
Theo em 6 (Add p edica e o posi i e edge be ween posi i e nodes o Q).
Gi en Q∈GGQ and n, m ∈V+
Q, wi h n+e+
−→ m+, and ϕ∈FORM, he se
deno ed by Q+{n+e∧ϕ
−→ m+}, o med by (whe e Q0=Cl{n,m}
Q):
Q1=(VQ0, EQ0∪ {n+e0
−→ m+}, θQ0∪(e0, θe∧ϕ))
Q2=(VQ0, EQ0∪ {n+e0
−→ m−}, θQ0∪(e0, θe∧ϕ))
Q3=(VQ0, EQ0∪ {n−e0
−→ m+}, θQ0∪(e0, θe∧ϕ))
Q4=(VQ0, EQ0∪ {n−e0
−→ m−}, θQ0∪(e0, θe∧ϕ))
is a e inemen se o Qin G(Fig. 15).
20
Figu e 14: Re inemen Add edge
P oo . The p oo is simila o hose shown in p e ious esul s.
Figu e 15: Re inemen Add p edica e o edge
Finally, he las ope a ion adds p edica es o exis ing nodes. Again, we
es ic his ope a ion o cases when he a ec ed nodes a e posi i e ( he node
whe e he p edica e is added, and hose connec ed o i ).
Theo em 7 (Add p edica e o posi i e node wi h posi i e en i onmen in Q).
Gi en Q∈GGQ,n∈V+
Q, wi h NQ(n)⊆V+
Q, and ϕ∈FORM. We de ine he
se Q+{n∧ϕ} o med by:
{Qσ= (VQ0, EQ0, αQ0∪σ, θQ0∪(n0, θn∧ϕ)) : σ∈ {+,−}NQ(n)}
whe e Q0=ClNQ(n)
Q, and {+,−}NQ(n)is he se o all possible assigna ions o
signs o elemen s in NQ(n).
Then Q+{n∧ϕ}is a e inemen se o Qin G(Fig. 16).
P oo . The p oo is simila o he p e ious cases. I is only necessa y o ake in o
accoun ha , when modi ying he node n, no only he Q-p edica e associa ed
wi h i is modi ied bu also hose om all i s adjacen nodes, and he se o
unc ions {+,−}NQ(n)co e all possible sign assignmen o he nodes in he
en i onmen .
21
Figu e 16: Re inemen Add p edica e o node
I should be no ed ha hese e inemen s gene a e s uc u es ha can be
simpli ied. Nex we p o ide some ope a ions o simpli y a GGQ and o ob ain
ano he equi alen and simple one.
De ini ion 14. Gi en Q∈GGQ,Q0⊆Qis edundan in Qi Q≡Q−Q0.
Whe e Q−Q0is he subg aph o Qgi en by:
(VQ VQ0, EQ (EQ0∪ {γ(n) : n∈VQ0}), µQ)
Le us see a i s esul ha allows o ob ain simpli ied e sions o a GGQ
by emo ing posi i e edundan nodes:
Theo em 8. Gi en Q∈GGQ, and n∈V+
Qsuch ha exis s m∈VQ e i ying:
•α(n) = α(m),θn≡θm.
•Fo each e∈γ(n), exis s e0∈γ(m), e i ying α(e) = α(e0),θe=θe0and
γ(e) {n}=γ(e0) {m}.
Then, nis edundan in Q.
Essen ially, mis a clone o n, bu possibly wi h mo e edges connec ed. We
can ob ain a simila esul o edges:
Theo em 9. Gi en Q∈GGQ, and wo edges, e, e0∈EQ, such ha n+e
−→ m+
and n+e0
−→ m+. I θe→θe0 hen e0is edundan in Q.
F om hese wo esul s we can gi e simpli ied e sions o he p e ious e ine-
men se s, g ouping posi i e nodes and posi i e edges when, a e ini ial cloning,
he sign o he duplica e elemen has been main ained wi h he o iginal, as well
as in he cases whe e he sign has been main ained and an addi ional p edica e
22
Figu e 17: Re inemen Add edge (simpli ied)
Figu e 18: Re inemen Add p edica e o edge (simpli ied)
has been added. Figu es 17 o 19 shows ep esen a ions o he e inemen se s
Q+{n∧ϕ},Q+{n+e∧ϕ
−→ m+}and Q+{n∧ϕ}applying hese simpli ica ions.
Fo example, he ollowing sequence o e inemen s cons uc s he pa e n
P5(Fig. 20):
Q1=Q∅+{n1}
Q2=Q1+{n1∧( ∈S∧τ( )6=ins i u ion ∧τ( )6=clan}
Q3=Q2+{n2}
Q4=Q3+{n2
e1
−→ n1}
P5=Q4+{n2
e1∧(τ(ρ)=DEVOTED TO)
−→ n1}
F om he s uc u e o a GGQ i is no easy o ob ain a complemen a y
GGQ wi h i . Howe e , he e a e many analysis on p ope y g aphs (o gene -
alized g aphs) whe e we need o wo k wi h sequences o que ies e i ying some
p ope ies o con ainmen and complemen a i y as p edica es. The e inemen s
p esen ed in his sec ion come o co e his gap and o allow, o example, he
cons uc ion o an embedded pa i ion ee wi h he nodes labelled as ollows
(Fig. 21):
•The oo node is labelled wi h Q0(some ini ial GGQ).
23
Figu e 19: Re inemen Add p edica e o node (simpli ied)
Figu e 20: Sequences o e inemen s o P5
•I a ee node is labelled wi h Q, and R= (Q1, . . . , Qn) is a e inemen se
o Q, hen i s child nodes a e labelled wi h he elemen s o R.
No e ha he cons uc ion o his ee comple ely depends on he e inemen
chosen in each b anch, and he ini ial GGQ.
The e inemen s p esen ed he e a e only one op ion, bu no he only one.
Fo example, we could conside e inemen s ha , ins ead o adding cons ain s
o posi i e elemen s, ligh en he condi ions o e nega i e elemen s, and using
disjunc ion o p edica es ins ead o conjunc ion o hem.
7 Conclusions and Fu u e Wo k
In his wo k we ha e p esen ed a amewo k o e alua e subg aphs imme sed
in p ope y g aphs (mo e gene ally, in gene alized g aphs) ha can be used in
disco e y p ocedu es o e ela ional da a. We wan his amewo k o e i y
se e al equi emen s:
•To use he same g amma o he que ies and o he s uc u es o e alua e.
24
Figu e 21: Re inemen s ee
Thanks o he exp essi e powe o gene alized g aphs we ha e p esen ed
a que y ool ha can be exp essed by using gene alized g aphs.
•To p o ide well- ounded basis ha would assu e he que ies beha e con-
sis en ly and obus ly. These esul s ha e been ob ained by s udying he
ela ionships be ween he opological s uc u e o he que y and he logical
meaning o he que y.
•In addi ion, we ha e p o ided a con olled way o cons uc GGQ by
means o a omic ope a o s ha ansla es he opological con ol o he
cons uc ion in o a logical con ol o he meaning. In his sense, we ha e
in oduced a i s amily o e inemen s o achie e his goal.
Because ela ional da a can be iewed as g aphs, and que ies can be iewed
as pa e n sea chs, mos que y languages in da abases can be iewed as (pe haps
p imi i e) g aph pa e n ma ching ools. In his pape we ha e analysed some
o he exis ing que y ools as well as he easibili y o be used in au oma ic
p ocedu es. One o hese ools, Selec ion G aphs, allows o e alua e eco ds
in ela ional da abases h ough acyclic pa e ns ha can be e ined by using
basic ope a ions, and allowing o ob ain complemen a y pa e ns in each case.
They do no equi e an exac p ojec ion o he pa e n ep esen ing he selec ion
g aph on o he subg aph o be e alua ed, bu a he he ul illmen o a se ies
o p edica es exp essed in he pa e n. We mus emembe ha i a p ojec ion
is equi ed when ca ying ou he e i ica ion o a pa e n, he ask o e alua -
ing he non-exis ence o ce ain elemen s becomes ha d. Speci ically, selec ion
g aphs e alua e he exis ence / non-exis ence o pa hs inciden s in o he eco d
unde e alua ion ( hey a e only capable o e alua ing indi idual eco ds) by
e i ying a conjunc ion o p edica es associa ed o hose pa hs, and i can be
seen as he e alua ion o exis ence o a ee oo ed in he node ha ep esen s
he eco d unde e alua ion.
Gene alized G aph Que y ex ends he concep o selec ion g aphs allowing
he e alua ion o gene al subg aphs, beyond a single node, he use o mo e
powe ul p edica es and allowing cyclical pa e ns. As i becomes a equi emen
no o use a p ojec ion o he e i ica ion o a pa e n, hese objec i es ha e
been achie ed by ex ending he o m o e alua ion, which can be seen as he
e alua ion o a ee oo ed in e e y node om he pa e n (allowing he edges o
be iden i ied wi h pa hs in he g aph). Consequen ly, i manages mo e complex
25
lujo de da os que pe mi e a los usua ios exp esa de mane a sencilla consul as
complejas en g a os. De es a o ma, cada consul a es ´a compues a po una se-
cuencia de pasos que ealizan ope aciones a ´omicas en el lujo de da os. G emlin
pe mi e ealiza consul as sem´an icas, exac as, ´op imas, y basadas en isomo -
ismos de subg a os de mane a na u al. Dado que G emlin es un lenguaje, un
juego de ins ucciones y una m´aquina i ual, es posible dise˜na o os lenguajes
de consul a en g a os que compilen al lenguaje G emlin (po ejemplo, SPARQL
puede se compilado pa a ejecu a se en una m´aquina G emlin1).
Los G a os de Selecci´on son un ipo de pa ones mul i- elacionales pa a con-
sul a bases de da os basadas en la ecnolog´ıa SQL. Rep esen an los cimien os
sob e los que es ´a cons uido el algo i mo de inducci´on de ´a boles de decisi´on
mul i- elacionales MRDTL [13] as´ı como o os algo i mos de ap endizaje au-
om´a ico mul i- elacionales [15]. El obje i o inal de los g a os de selecci´on es su
uso en p ocedimien os de b´usqueda de pa ones de ipo op-down [12], y pa a
ello se necesi an ope ado es que pe mi an modi ica , a a ´es de peque˜nos cam-
bios, un g a o de selecci´on dado. Adem´as, pe mi en una ep esen aci´on g ´a ica
muy exp esi a y pueden se cons uidos en pasos sucesi os, o eciendo buenas
condiciones pa a se u ilizados en p ocedimien os de descub imien o. Es po es-
as azones po las que nues a p opues a se puede conside a una gene alizaci´on
de algunas de las ideas que p omo ie on es a ap oximaci´on. Como con apa e,
p esen an el incon enien e de que los pa ones que ep esen an no pueden con-
ene ciclos, limi ando as´ı la po encia exp esi a de las consul as. Los g a os de
selecci´on ep esen an un ipo de G aph Pa e n Ma ching exac o, ´op imo y ba-
sado en el isomo ismo sem´an ico de g a os. Adem´as, al se una ep esen aci´on
g ´a ica de las consul as SQL, he eda los p oblemas de e iciencia que p esen an
los sis emas basados en es a ecnolog´ıa.
Cyphe es un lenguaje de consul a decla a i o desa ollado espec´ı icamen e
pa a abaja sob e la base de da os en g a o Neo4j2. Cyphe es ´a dise˜nado pa a
se un lenguaje de consul a humano, ce cano an o pa a desa ollado es como
pa a usua ios inales, y las consul as de pa ones en g a os que habi ualmen e
son complicadas en o os lenguajes esul an muy sencillas en ´el [2], mos ando
una al a capacidad exp esi a [1]. La base de da os Neo4j sigue con mucha i-
delidad el modelo de g a o con p opiedades, pe o obliga que las a is as engan
un ipo asociado. A di e encia con G emlin, Cyphe no es Tu ing comple o, po
lo que p esen a algunas limi aciones (po ejemplo, no es capaz de lle a a cabo
algunos algo i mos de an´alisis en g a os), y es de m´as al o ni el (po ejemplo,
no es capaz de exp esa la o ma en la que se quie e pa aleliza una consul a).
Las consul as sencillas en Cyphe poseen un buen endimien o, sin emba go no
siemp e es as´ı cuando las consul as siguen pa ones complejos, ya que cuan-
do hay condiciones m´ul iples Cyphe no pe mi e indica en qu´e o den aplica
dichas condiciones. Cyphe pe mi e consul as de pa ones en g a os es uc u a-
les y sem´an icas, ´op imas, exac as, y basadas en el isomo ismo de subg a os.
Adem´as, pe mi e un ipo de Regula Pa e n Ma ching en el que las a is as en el
pa ´on se p oyec en sob e caminos del g a o, y se pueden impone es icciones
a esos caminos a a ´es de exp esiones que hacen uso del ope ado disyunci´on
y del cie e de Kleene. Una limi aci´on desde el pun o de is a acad´emico es
que ca ece de un modelo o mal asociado, y se ha cons uido con un ca ´ac e
1h ps://gi hub.com/dkuppi z/spa ql-g emlin
2h p://neo4j.o g
4
comple amen e aplicado, po lo que algunas de sus ope aciones no han sido a-
lidadas. A pesa de ello, po su excelen e exp esi idad y acep able endimien o,
y po que consume los da os de una base de da os en g a o muy ex endida en su
uso, Cyphe es el lenguaje base que se ha elegido pa a implemen a Gene alized
G aph Que y, nues a p opues a pa a lle a a cabo consul as de pa ones en
g a os con p opiedades.
Algunas o as he amien as elacionadas con la consul a de pa ones en g a-
os son: G aphLog [6], que pe mi e es uc u a las consul as en o ma de g a o
y e al´ua la exis encia de un pa ´on de e minado en e un pa de nodos pa a ge-
ne a una nue a a is a en e ´es os; G aphQL3, lenguaje de consul a decla a i o
desa ollado po la compa˜n´ıa Facebook pa a pe mi i el acceso a su in o ma-
ci´on po pa e de aplicaciones ex e nas; G aql4, lenguaje de consul a decla a i o
o ien ado a g a os de conocimien o; y PGQL [19], que ep esen a una ex ensi´on
SQL con ca ac e ´ıs icas p opias de las consul as en g a os: an´alisis de accesibi-
lidad en e nodos, localizaci´on de caminos, y cons ucci´on de g a os.
3. De iniciones P e ias
Dado Vun conjun o cualquie a, deno a emos po :
V0=∅, V 1=V, V n+1 =Vn×V, V ∗=[
n≥0
Vn
En gene al, a los elemen os de V∗los llama emos secuencias,sucesiones o
lis as. Si x∈Vnen onces di emos que x iene longi ud n, y esc ibi emos |x|=n.
Si x= (a1, . . . , an), y = (b1, . . . , bm)∈V∗, en onces la conca enaci´on de x
eyes el elemen o de V∗dado po xy = (a1, . . . , an, b1, . . . , bm).
Pa a cada x= (a1, . . . , an)∈Vn, llama emos conjun o sopo e de xal
conjun o s(x) = {ai: 1 ≤i≤n},. y, po un abuso del lenguaje, esc ibi emos
a∈xpa a indica que a∈s(x).
Pa a cada a∈V, deno amos |a|x= #{i:xi=a}(donde #(A) deno a el
ca dinal del conjun o A), y llama emos mul iconjun o sopo e de xal conjun o
de pa es ms(x) = {(a, |a|x) : a∈x}.
A pa i de los mul iconjun os sopo e podemos de ini la elaci´on ∼, que se
puede p oba ´acilmen e que es de equi alencia en Vn, como: x∼ysi y solo
si ms(x) = ms(y), y deno a emos po Vn
∼=Vn/∼(conjun o cocien e de Vn
bajo la elaci´on ∼).
Nues a in e p e aci´on de es os conjun os se ´a que, as´ı como Vndeno a el
conjun o de uplas o denadas de elemen os de V,Vn
∼deno a el conjun o de
uplas no o denadas del mismo conjun o (es deci , uplas en las que impo an
los elemen os que apa ecen, conside ando las posibles epe iciones, pe o no el
o den en el que apa ecen).
A con inuaci´on p esen amos la de inici´on de G a o Gene alizado, que aba ca
las di e en es a ian es de g a o que se pueden encon a en la li e a u a y que
necesi a emos a la ho a de p esen a nues a p opues a de consul a de pa ones
en g a os.
De inici´on 1. Un G a o Gene alizado es una upla G= (V, E, µ)donde:
3h p://g aphql.o g/
4h ps://g akn.ai
5
VyEson conjun os, que llama emos, espec i amen e, conjun o de nodos
yconjun o de a is as de G.
µes una elaci´on (habi ualmen e la conside a emos uncional, pe o no
es necesa io) que asocia a cada nodo o a is a en el g a o su conjun o
de p opiedades, es deci , µ: (V∪E)×R→S, donde R ep esen a el
conjun o de posibles cla es pa a dichas p opiedades, y Sel conjun o de
posibles alo es asociados a las mismas.
Habi ualmen e, pa a cada α∈Ryx∈V∪E, esc ibi emos α(x) = µ(x, α).
Adem´as, exigi emos la exis encia de una cla e des acada pa a las a is as del
g a o, que llama emos incidencias y deno a emos po γ, que asocia a cada a is a
del g a o una upla, o denada o no, de ´e ices del g a o.
Aunque la de inici´on que hemos p esen ado aqu´ı es m´as gene al que las que
se pueden encon a en la li e a u a elacionada, ambi´en los denomina emos
G a os con P opiedades, ya que suponen una ex ensi´on na u al de es e ipo de
g a os.
Cabe indica que en los g a os gene alizados que acabamos de mos a , y a
di e encia de las de iniciones adicionales, los elemen os en Eson s´ımbolos que
ep esen an a las a is as y no pa es de elemen os de V, y es γla unci´on que
asocia a cada a is a el conjun o de ´e ices que elaciona.
De inici´on 2 (No aci´on y de iniciones).En el con ex o de las de iniciones an-
e io es, usa emos la siguien e no aci´on:
Habi ualmen e iden i ica emos econ γ(e), de o ma que si ∈Vesc ibi-
emos ∈epa a deno a que ∈γ(e). As´ı, in e p e amos la a is a como
la colecci´on de nodos que conec a, al y como siguen las de iniciones m´as
cl´asicas de g a os.
De o ma sim´e ica, pa a cada u∈Vesc ibi emos γ(u) = {e∈E:u∈
e}.
En gene al, un g a o gene alizado puede ene combinaci´on de a is as di-
igidas y no di igidas. Si γ:E→V∗di emos que el g a o es Di igido. Si
γ:E→V∗
∼di emos que el g a o es No Di igido.
Pa a cada e∈E, se de ine la a idad de ecomo Pa∈e|a|e.
Si γ:E→V2∪V2
∼di emos que el g a o es Bina io (y coincide con la
es uc u a de g a o m´as habi ual). En caso con a io, di emos que el g a o
es un Hipe g a o.
Una a is a, e∈E, se dice que es un lazo si conec a un nodo con ´el mismo,
es deci , si iene a idad dis in a a 1 pe o s(e)es uni a io.
Una a is a, e∈E, se dice inciden e en un nodo, ∈V, si ∈e.
Dos nodos dis in os, u, ∈Vse dicen adyacen es, o ecinos, en Gsi
exis e e∈E al que {u, } ⊆ e.
Si exis en a is as dis in as en Econ la misma incidencia, es deci , a is as
que conec an los mismos nodos, di emos que el g a o es un Mul i-g a o.
6
Si ees una a is a bina ia di igida que conec a ucon ,e= (u, ), esc ibi-
emos ue
→ , y ambi´en no a emos eo=u(ou pu de e) y ei= (inpu
de e). En es e caso, pa a cada u∈Vesc ibi emos:
γo(u) = {e∈γ(u) : eo=u}
γi(u) = {e∈γ(u) : ei=u}
que deno an, espec i amen e, el conjun o de a is as salien es de uy el
conjun o de a is as en an es en u.
Dado u∈V, de inimos el en o no de uen Gcomo el conjun o de nodos,
incluyendo a u, que es ´an conec ados con ´el, es deci : N(u) = Se∈γ(u)γ(e).
Cuando sea necesa io habla emos del en o no educido de ucomo N∗(u) =
N(u) {u}.
La noci´on de subg a o se ob iene de la de inici´on habi ual a˜nadiendo a las
condiciones habi uales de con enci´on de nodos y a is as la condici´on de que las
p opiedades ambi´en se man engan en los elemen os comunes.
De inici´on 3. Un subg a o de un g a o G= (V, E, µ)es un g a o S= (VS, ES, µS)
al que VS⊆VyES⊆EyµS⊆µ|VS∪ES. No a emos S⊆G.
Un concep o undamen al al abaja con g a os es el de camino, que pe mi e
es udia elaciones de dis ancia y condiciones de conec i idad en e di e en es
elemen os, ex endiendo la conec i idad de las a is as a si uaciones m´as gene ales.
Debido a que nues os g a os son conside ablemen e m´as gene ales que los
habi uales (has a el pun o de con ene el concep o de hipe g a o, que gene al-
men e no se cub e en la Teo ´ıa de G a os cl´asica) hemos de da p e iamen e
algunas nociones que pe mi an habla de la posici´on de o den que ocupa un
nodo en una a is a:
De inici´on 4. Si e∈Eyγ(e) = ( 1, . . . , n)∈Vn, en onces pa a cada i∈s(e)
de inimos su o den en ecomo o de( i) = i. Si e∈Vn
∼, en onces pa a cada
∈s(e)de inimos o de( )=0.
Es e o den de ine de o ma na u al un o den en e los nodos inciden es en
una a is a, y esc ibi emos u≤e pa a indica que o de(u)≤o de( ).
A pa i de es a elaci´on de o den en e los nodos que conec a una a is a,
podemos de ini de mane a gene al qu´e en endemos po un camino den o de
un g a o.
De inici´on 5. Dado un g a o G= (V, E, µ), el conjun o de caminos en G, que
deno a emos po PG, se de ine como el meno conjun o e i icando las siguien es
condiciones:
1. Si e∈E,u, ∈econ u≤e , en onces ρ=ue
→ ∈ PG, y sopV(ρ) =
(u, ),sopE(ρ)=(e). Di emos que ρune (o conec a) los ´e ices uy de
G, o que es accesible desde upo medio de ρ, y lo no a emos po uρ
.
2. Si ρ1, ρ2∈ PG, con uρ1 , ρ2
w, en onces ρ1·ρ2∈ PG, con uρ1·ρ2
w,
sopV(ρ1·ρ2) = sopV(ρ1)sopV(ρ2),sopE(ρ1·ρ2) = sopE(ρ1)sopE(ρ2).
En caso de que u= di emos que ρes un camino ce ado, y si adem´as no se
epi en a is as en ρdi emos que es un ciclo.
7
Si ρ∈ PG, con sopV(ρ) = (u1, . . . , un+1) y sopE(ρ) = (e1...,en), en onces
esc ibi emos:
ρ=u1
e1
→u2
e2
→. . . en
→un+1
En gene al, y como no hay con usi´on, esc ibi emos u∈ρpa a exp esa que
u∈sopV(ρ), y e∈ρpa a exp esa que e∈sopE(ρ).
No a.
Siguiendo una no aci´on simila al caso de las a is as bina ias di igidas,
si ρ∈ P(G)yuρ
, en onces esc ibi emos ρo=uyρi= .
Cuando sea necesa io, no a emos los caminos que pasan po u, que co-
mienzan en u, y que acaban en u, espec i amen e, po :
Pu(G) = {ρ∈ P(G) : u∈ρ}
Po
u(G) = {ρ∈ P(G) : ρo=u}
Pi
u(G) = {ρ∈ P(G) : ρi=u}
4. Gene alized G aph Que y
A con inuaci´on p esen amos Gene alized G aph Que y (GGQ, pa a ab e ia ,
a pa i de aho a), nues a p opues a pa a lle a a cabo consul as de pa ones en
g a os. Teniendo en cuen a las di e sas clasi icaciones apun adas an e io men e,
podemos deci que es a p opues a pe mi e lle a a cabo consul as es uc u a-
les y sem´an icas, exac as, ´op imas, y basadas en un ipo de Regula Pa e n
Ma ching que pe mi e, adem´as de p oyec a a is as del pa ´on en caminos (no
necesa iamen e a is as) que cumplan las es icciones impues as, exp esa es-
icciones m´as complejas sob e cada elemen o del pa ´on y ealiza consul as
que posean ciclos.
Una de las ca ac e ´ıs icas que buscamos en nues a he amien a es que pe -
mi a ob ene (de alguna mane a) pa ones complemen a ios a un pa ´on dado.
Es o signi ica que si una es uc u a no e i ica un pa ´on debe e i ica siemp e
uno de sus pa ones complemen a ios. Como hemos is o en la secci´on an e io ,
muchas de las he amien as desa olladas pa a lle a a cabo consul as de pa o-
nes en g a os exigen que se cumpla una p oyecci´on en e el pa ´on y la es uc u a
a e alua . Dicha p oyecci´on impide e alua la no exis encia de elemen os, algo
que amos a necesi a pa a gene a es os pa ones complemen a ios, po lo que
nues a p opues a no se basa en una p oyecci´on a la ho a de e i ica si una
es uc u a cumple con un pa ´on de e minado, sino que se ´a cons uida en base
a p edicados l´ogicos, que acili a ´an la gene aci´on de pa ones complemen a ios.
Hemos de indica que nues o obje i o p incipal es el de p opo ciona una
o malizaci´on comple a del modelo ( en e a implemen aciones incomple as des-
de el pun o de is a o mal, pe o ope a i as), pe o con el obje i o secunda io
de p opo ciona una implemen aci´on que sea u ilizable desde un pun o de is a
p ´ac ico5(aunque m´as como una p ueba de concep o que como una he amien a
p o esional en es a p ime a e apa).
5h ps://gi hub.com/palmag o/ggq
8
En busca de nues os obje i os, nos apoya emos en el concep o de G a o
de Selecci´on is o an e io men e, ampli´andolo pa a a˜nadi le Regula Pa e n
Ma ching y algunas ca ac e ´ıs icas adicionales que nos pe mi i ´an ob ene una
mayo po encia exp esi a en los pa ones que se pueden cons ui .
Como p incipales ca ac e ´ıs icas di e enciado as espec o de los sis emas de
consul a is as en el apa ado an e io , podemos indica que:
Los GGQ pueden con ene ciclos. Se ´a un p oblema pos e io conside a
implemen aciones de los GGQ que manipulen los ciclos adecuadamen e,
conside a es icciones adicionales pa a asegu a cie os ni eles de e icien-
cia en su ejecuci´on eal, o p eocupa se en la e apa de dise˜no de la consul a
de c ea un pa ´on que sea e icien e en la implemen aci´on disponible.
Los GGQ pueden e alua subg a os. Reco demos que en los G a os de
Selecci´on cl´asicos s´olo es posible e alua un ´unico nodo que ep esen a
a la abla a ge . En el caso de los GGQ, los elemen os ijos (elemen os
que deben pe enece al subg a o bajo e aluaci´on) se ´an ep esen ados a
a ´es de un p edicado que obliga a que dichos elemen os es ´en con enidos
en el subg a o a e alua .
Las a is as indi iduales del GGQ pueden se p oyec adas sob e caminos
en el g a o en el que se comp ueba el pa ´on. Pa a ello se ha ´a uso de
p edicados de o ma simila a como se hace en Regula Pa e n Ma ching.
Los p edicados asociados a nodos o a is as en el GGQ pueden e alua
ca ac e ´ıs icas es uc u ales y sem´an icas m´as all´a de las p opiedades al-
macenadas a a ´es de la unci´on µ(po ejemplo, a a ´es de m´e icas
sob e el g a o o sus elemen os).
Aunque ya hemos mencionado que podemos dispone de un conjun o de
p edicados asociados a los elemen os del pa ´on, amos a o maliza b e emen e
qu´e en endemos conc e amen e po un p edicado de inido sob e un g a o.
Tal y como mues a su de inici´on, asociado a un g a o con p opiedades e-
nemos una unci´on µque ep esen a un conjun o de unciones (en pa icula ,
pueden se p edicados) asociadas a nodos y a is as del g a o. Conside emos Θ,
una colecci´on de s´ımbolos de unci´on, p edicados y cons an es, que con iene o-
das las unciones de µjun o con cons an es asociadas a cada elemen o del g a o
y, posiblemen e, algunos s´ımbolos adicionales, an o de unciones como de p e-
dicados y cons an es (po ejemplo, m´e icas de inidas sob e los elemen os del
g a o). A pa i de es e conjun o de s´ımbolos podemos de ini un Lenguaje de
P ime O den con igualdad, L, haciendo uso de Θ como conjun o de s´ımbolos
no l´ogicos, sob e el que cons uimos, de la o ma usual, el conjun o de ´e minos
del lenguaje y el conjun o de ´o mulas, FORM(L), que llama emos p edicados.
Aunque, en gene al, las ´o mulas de inibles en Lse pueden aplica a odos
los obje os del uni e so, que en nues o con ex o es a ´a compues o po elemen-
os de g a os (nodos, a is as, y es uc u as o madas a pa i de ´es os), cuando
que amos explici a sob e qu´e ipos de obje os es amos abajando en cada mo-
men o, pod emos esc ibi FORMV(L) pa a indica que son ´o mulas aplicables
sob e nodos, FORME(L) pa a indica que son ´o mulas aplicables sob e a is as,
FORMP(L) pa a indica que son ´o mulas aplicables sob e caminos, e c.
En lo que sigue supond emos p e ijado un Lenguaje sob e g a os, L, po lo
que, con el obje i o de simpli ica las exp esiones que usemos, no a emos de
9
o ma gene al FORM pa a deno a FORM(L) cuando no haya posibilidad de
con usi´on.
Adem´as, y ap o echando la capacidad exp esi a de los g a os gene alizados,
de inimos las consul as sob e ellos haciendo uso de las mismas es uc u as:
De inici´on 6. Un Gene alized G aph Que y (GGQ) sob e Les un g a o bina io
con p opiedades sob e L,Q= (VQ, EQ, µQ), donde exis en αyθ, p opiedades
des acadas en µQ, ales que:
α:VQ∪EQ→ {+,−} o al.
θ:VQ∪EQ→FORM(L)asocia un p edicado bina io, θx, a cada elemen o
xde VQ∪EQ.
Esc ibi emos Q∈GGQ(L) pa a deno a que Qes un Gene alized G aph
Que y sob e L(si el lenguaje es ´a p e ijado y no hay posibilidad de con usi´on,
esc ibi emos simplemen e Q∈GGQ).
El sen ido de usa p edicados bina ios es que en la sem´an ica asociada a un
GGQ usa emos la segunda en ada de es os p edicados pa a pode habla de
condiciones de pe enencia sob e subg a os de G(el g a o gene al sob e el que
es amos e aluando las consul as), mien as que la p ime a espe a ´a ecibi como
en ada elemen os adecuados al ipo de elemen o al que es ´a asociado. As´ı, si
Ses un subg a o y a∈VQen onces θa(., S)∈FORMV, y si e∈EQen onces
θe(., S)∈F ORMP. Po ejemplo:
θa( , S) = ∃z∈S(z )
θe(ρ, S) = ∃y, z(yρ
z∧y /∈S∧z∈S)
El p ime p edicado end ´a sen ido pa a nodos, y se e i ica ´a cuando exis a un
camino en Gque conec a un nodo de S(el subg a o que es amos e aluando)
con , el nodo de en ada sob e el que se e al´ua. El segundo p edicado end ´a
sen ido pa a caminos, y se e i ica ´a cuando el camino e aluado, ρ, conec a S
con su complemen a io (en G).
Dado un GGQ en las condiciones an e io es, no a emos x+, espec i amen e
x−, pa a indica que α(x) = +, espec i amen e α(x) = −, y V+
Q/V −
Q( espec i-
amen e, E+
Q/E−
Q) el conjun o de nodos ( espec i amen e, a is as) posi i os/ne-
ga i os. Si pa a un elemen o x,θxno es ´a expl´ıci amen e de inida, supond emos
que θxes una au olog´ıa, que podemos deno a en gene al po T.
Tal y como e emos a con inuaci´on, in ui i amen e los elemen os posi i os
del pa ´on ep esen an elemen os que deben es a p esen es en el g a o sob e el
que se ealiza la consul a y que e i ican los p edicados asociados, mien as que
los elemen os nega i os en el pa ´on ep esen an elemen os que no deben es a
p esen es en el g a o.
Pa a pode exp esa con m´as acilidad las condiciones necesa ias que de inen
la aplicaci´on de un GGQ sob e un g a o, as´ı como los esul ados que e emos
m´as adelan e, in oducimos a con inuaci´on una se ie de no aciones que gene an
p edicados aplicables sob e elemen os del g a o:
De inici´on 7. Dado Q= (VQ, EQ, µQ)un GGQ, el conjun o de Q-p edicados
asociados a Qes:
10
1. Pa a cada a is a, e∈EQ, de inimos los Q-p edicados asociados como:
Qeo( , S) = ∃ρ∈ Po
(G)θe(ρ, S)∧θeo(ρo, S)∧θei(ρi, S)
Qei( , S) = ∃ρ∈ Pi
(G)θe(ρ, S)∧θeo(ρo, S)∧θei(ρi, S)
En gene al, esc ibi emos Qe∗( , S), donde ∗ ∈ {o, i}, y no a emos:
Q+
e∗=Qe∗, Q−
e∗=¬Qe∗
2. Pa a cada nodo, n∈VQ, de inimos el Q-p edicado asociado como:
Qn(S) = ∃ ∈V
^
e∈γo(n)
Qα(e)
eo( , S)∧^
e∈γi(n)
Qα(e)
ei( , S)
=∃ ∈V
^
e∈γ∗(n)
Qα(e)
e∗( , S)
Y que podemos esc ibi en gene al como:
Qn(S) = ∃ ∈V
^
e∈γ(n)
Qα(e)
e( , S)
ya que pa a cada nodo no hay posibilidad de con usi´on. Adem´as, no a e-
mos:
Q+
n=Qn, Q−
n=¬Qn
A pa i de es as no aciones, podemos de ini o malmen e cu´ando un sub-
g a o e i ica un GGQ de e minado:
De inici´on 8. Dado un subg a o Sde un g a o con p opiedades, G= (V, E, µ),
y un Gene alized G aph Que y, Q= (VQ, EQ, µQ), ambos sob e el lenguaje L,
di emos que S e i ica Q, y lo deno a emos SQ, si se e i ica la ´o mula:
Q(S) = ^
n∈VQ
Qα(n)
n(S)
En caso con a io, esc ibi emos: S2Q.
En la Figu a 1 se mues a un GGQ gen´e ico a modo de ejemplo.
Uno de los obje i os que pe siguen los GGQ es p opo ciona la capacidad
exp esi a su icien e pa a exp esa condiciones que hacen uso de elemen os que
es ´an ue a del subg a o que se es ´a e aluando, algo que se ha demos ado ne-
cesa io pa a dispone de un lenguaje de consul as po en e y que, sal o en los
g a os de selecci´on, y de o ma muy limi ada, no es ´a p esen e en el es o de
soluciones is as an e io men e.
Obs´e ese que, en pa icula , usando S=Gpodemos de ini cu´ando un
g a o e i ica un GGQ.
Aunque la de inici´on de GGQ que hemos p esen ado hace uso de g a os bina-
ios (no hipe g a os), ya que p oyec a a is as sob e caminos que conec an pa es
11
Figu a 1: Ejemplo de Gene alized G aph Que y.
de nodos, el concep o de g a o gene alizado es su icien emen e lexible como pa-
a pe mi i o as in e p e aciones en las que se pueden conside a GGQs que
hagan uso de es uc u as m´as gene ales. Adem´as, y es impo an e esal a es e
hecho, aunque un GGQ sea bina io, puede aplica se sob e g a os con p opie-
dades que no lo sean (es deci , Gpod ´ıa se un hipe g a o gene alizado), ya
que el concep o de camino que conec a pa es de nodos se de ine independien-
emen e de la a idad de las a is as que in e ienen. En es os casos, se debe ´ıa
usa una no aci´on algo m´as compleja pa a pode de ini los Q-p edicados, pe o
es comple amen e ac ible. Po mo i os de simplicidad, y po la al a de bases
de da os de hipe g a os, hemos es ingido las de iniciones p esen adas a es os
casos pa icula es, pe o quedan abie as pa a se ex endidas a los casos m´as ge-
ne ales en el momen o en el que el uso de hipe g a os se gene alice como medio
de modelado y almacenamien o, ya que en la mayo ´ıa de las (escasas) ocasiones
en que se han necesi ado siemp e se ha esuel o el p oblema po medio de la
c eaci´on de nue os ipos de nodos y a is as bina ias que simulan la p esencia de
hipe a is as.
An es de pasa a analiza algunas p opiedades in e esan es sob e los GGQ y
la o ma de cons ui los, eamos algunos ejemplos que pe mi an en ende c´omo
se in e p e an y qu´e capacidad exp esi a pe mi en.
5. Ejemplos Rep esen a i os
A lo la go de es e pa ´ag a o, y a modo de ejemplo, p esen a emos una colec-
ci´on de peque˜nos GGQ sob e un g a o con p opiedades conc e o con el obje o
de mos a la o ma en que uncionan y su capacidad exp esi a.
En la Figu a 2 se p esen a un g a o con p opiedades que se co esponde con
una secci´on de una base de da os basada en g a os que con iene in o maci´on
ace ca de los pe sonajes p incipales de la se ie S a wa s y que es u ilizada e-
cuen emen e como ejemplo sencillo pa a hace demos aciones elacionadas con
las capacidades de las bases de da os en g a o 6. En lo que sigue ha emos uso
de es e g a o pa a p esen a algunos pa ones que hagan uso del lenguaje so-
b e el que es ´a de inido y pa a comp oba la e i icaci´on de algunos subg a os
6h p://console.neo4j.o g/?id=S a Wa s
12
conc e os del mismo.
Figu a 2: G a o S a wa s pa a ilus a ejemplos de Gene alized G aph Que y.
Con el in de simpli ica la ep esen aci´on de consul as y subg a os, una de las
p opiedades en µ, a la que denomina emos τy que ep esen a una clasi icaci´on
de ipos sob e nodos y a is as, se ´a exp esada di ec amen e sob e la a is as y,
en el caso de los nodos, a a ´es de colo es. Adem´as, la p opiedad name de los
nodos se ´a ep esen ada di ec amen e sob e los mismos, y las a is as no di igidas
se ´an ep esen adas como a is as bidi eccionales.
La ep esen aci´on g ´a ica de los GGQ de ejemplo se mues a en las igu as 3 a
8. Cuando analicemos la in e p e aci´on de es as consul as ambi´en indica emos
algunos subg a os de Gque los e i ican. Cada elemen o en es os GGQ iene
asociada la ep esen aci´on de su p opiedad αdi ec amen e po medio de un
s´ımbolo +/−, y de su p opiedad θdi ec amen e en el elemen o (si el p edicado
asociado a un elemen o del GGQ es una au olog´ıa, dicho p edicado no se ´a
ep esen ado). En exp esiones del ipo τ(ρ) = Xen el p edicado de una a is a,
Xse in e p e a como una exp esi´on egula que debe e i ica se po la secuencia
de p opiedades τde sopE(ρ).
El GGQ P1(Figu a 3) se puede in e p e a en lenguaje na u al a a ´es de
la siguien e sen encia: Pe sonajes y elaci´on alumno-maes o en la que ambos
son de o os de los Jedi y el maes o iene m´as de 500 a˜nos. En es e caso se
imponen es icciones es uc u ales a a ´es de la p esencia de a is as y a a ´es
de p edicados que hacen uso de las p opiedades τ,name, y age. Es e GGQ se
e i ica ´a en subg a os en los que puedan se p oyec ados dos nodos y una a is a
que los une (los es elemen os ma cados como elemen os posi i os en el GGQ)
que cumplan con las es icciones impues as. En el caso de que exis ie a un
pe sonaje que se haya ense˜nado a s´ı mismo (lo que end ´ıa dado po un lazo de
ipo TEACHES) que enga m´as de 500 a˜nos y sea de o o de los Jedi, un subg a o
que con enga es e nodo ambi´en e i ica ´ıa es e pa ´on. El subg a o ma cado
13
Con el in de ob ene m´e odos con olados de gene aci´on de consul as, en lo
que sigue da emos un m´e odo cons uc i o pa a i e inando un GGQ po pasos
uni a ios. Pa a ello, comenza emos iendo c´omo se compo an los GGQ cuando
se clonan nodos.
Un clon consis e en hace copias de nodos exis en es, clonando odas las
a is as inciden es en ellos (y en e ellos, en caso de que clonemos a ios nodos que
es ´an conec ados en el GGQ o iginal). Po supues o, la ope aci´on de clonaci´on
se puede hace sob e g a os con p opiedades cualesquie a, y as´ı la p esen amos.
De inici´on 12. Dado G= (V, E, µ)un g a o con p opiedades, y W⊆V,
de inimos el clon de Gpo duplicaci´on de W, y lo no a emos po ClW
G, como
el g a o con p opiedades siguien e:
ClW
G= (V∪W0, E ∪E0, µ ∪ {(n0, µ(n))}n∈W∪ {(e0, µ(e))}e0∈E0)
donde:
pa a cada n∈W,n0es un nodo nue o, W0={n0:n∈W}, y
E0es un conjun o de a is as nue as que se consiguen a pa i de las a is as
inciden es en nodos de Wdonde se sus i uyen de odas las o mas posibles
los nodos de Wpo copias de W0(de o ma que apa ecen a is as clonadas
que conec an nodos o iginales con nodos copia, y ambi´en a is as clonadas
que conec an nodos copia).
Figu a 12: Clon de un g a o.
La Figu a 12 mues a un ejemplo de un g a o clonado po dupliaci´on de dos
de sus nodos. En el g a o o iginal, a la izquie da, se esal an los dos nodos a se
clonados. El esul ado de la clonaci´on se p esen a en el g a o de la de echa.
El siguien e esul ado nos indica que la clonaci´on de nodos posi i os no al e a
la in e p e aci´on de las consul as.
Teo ema 3. Si Q∈GGQ yW⊆V+
Q, en onces ClW
Q≡Q.
20
Demos aci´on. Pa a acili a la no aci´on, sea Q1=ClW
Q. En onces, siguiendo
un azonamien o simila al de la demos aci´on an e io :
Q1=^
n∈VQ1
Q1α(n)
n
=^
n∈VQ
Q1α(n)
n∧^
n∈W
Q1α(n0)
n0
=^
n∈VQ γQ(W)
Q1α(n)
n∧^
n∈γQ(W)
Q1α(n)
n∧^
n∈W
Q1α(n0)
n0
=^
n∈VQ γQ(W)
Qα(n)
n∧^
n∈γQ(W)
Qα(n)
n∧^
n∈W
Qα(n)
n
=Q
Siguiendo con la idea de ob ene he amien as que nos pe mi an cons ui
GGQ de mane a au om´a ica, el concep o de e inamien o que in oducimos
a con inuaci´on comple a las ope aciones que podemos hace pa a e ina un
GGQ. En cie a o ma, un conjun o de e inamien o o ma una pa ici´on po
e inamien os de un GGQ dado.
De inici´on 13. Dado Q∈GGQ. Di emos que R⊆GGQ es un conjun o de
e inamien o de Qen Gsi e i ica:
1. ∀Q0∈R(Q0GQ)
2. ∀S⊆G(SQ⇒ ∃!Q0∈R(SQ0))
Es amos ya en condiciones de da algunos conjun os de e inamien o que nos
pe mi i ´an au oma iza los p ocesos de c eaci´on y modi icaci´on de Gene alized
G aph Que ies. Comenza emos po la ope aci´on m´as sencilla, que consis e en
e de qu´e o mas se pueden a˜nadi nue os nodos a un GGQ exis en e:
Teo ema 4 (A˜nadi nodo nue o a Q).Dado Q∈GGQ ym /∈VQ, en onces el
conjun o que no a emos como Q+{m}, o mado po :
Q1= (VQ∪ {m}, EQ, αQ∪(m, +), θQ∪(m, T))
Q2= (VQ∪ {m}, EQ, αQ∪(m, −), θQ∪(m, T))
es un conjun o de e inamien o de Qen G(Fig. 13).
Demos aci´on. Hemos de comp oba que se e i ican las dos condiciones nece-
sa ias pa a que sea un conjun o de e inamien o:
1. Es e iden e que Q⊆−Q1yQ⊆−Q2, po lo que Q1QyQ2Q.
2. Sea S⊆G al que SQ. Tenemos que:
Q1=Q∧Qm
Q2=Q∧ ¬Qm
donde Qm=∃ ∈V(T).
Si G6=∅, en onces SQ1yS2Q2.
Si G=∅, en onces S2Q1ySQ2.
21
Como no ma gene al, G6=∅, po lo que es a ope aci´on ealmen e no e ina,
en el sen ido de que Q1≡QyQ2≡ ¬T. Sin emba go, a pesa de que ob enemos
un GGQ equi alen e, es a ope aci´on es muy ´u il pa a a˜nadi nue os nodos a un
GGQ a los que pos e io men e se le pod ´an i a˜nadiendo nue as es icciones.
Figu a 13: Re inamien o a˜nadi nodo.
Teniendo en cuen a los esul ados an e io es que daban elaciones en e las
p opiedades es uc u ales del GGQ y su in e p e aci´on sem´an ica como consul-
a, pasamos a da un segundo conjun o de e inamien o que nos indica c´omo
in e iene la c eaci´on de a is as en e nodos exis en es. Pa a man ene que o-
dos e inen al GGQ o iginal, hemos de es ingi la adici´on de a is as a los nodos
posi i os.
Teo ema 5 (A˜nadi a is a nue a en e nodos posi i os de Q).Dado Q∈GGQ
yn, m ∈V+
Q, en onces el conjun o que deno a emos como Q+{n+e∗
−→ m+}
(∗ ∈ {+,−}), o mado po (donde Q0=Cl{n,m}
Q):
Q1= (VQ0, EQ0∪ {n+e∗
−→ m+}, θQ0∪(e, T))
Q2= (VQ0, EQ0∪ {n+e∗
−→ m−}, θQ0∪(e, T))
Q3= (VQ0, EQ0∪ {n−e∗
−→ m+}, θQ0∪(e, T))
Q4= (VQ0, EQ0∪ {n−e∗
−→ m−}, θQ0∪(e, T))
es un conjun o de e inamien o de Qen G(Fig. 14).
Demos aci´on.
1. Como Q0es un clon de Q, y {n, m} ⊆ V+
Q, enemos que Q≡Q0. Adem´as,
po cons ucci´on, Q0⊆−Q1, Q2, Q3, Q4, po lo que Q1, Q2, Q3, Q4Q0≡
Q.
2. Conside emos los p edicados:
Pn=∃ ∈V
^
a∈γ(n)
Qα(a)
a∧Qα(e)
eo
Pm=∃ ∈V
^
a∈γ(m)
Qα(a)
a∧Qα(e)
ei
22
Si SQnySQm, en onces enemos 4 opciones mu uamen e excluyen-
es, seg´un se e i ique SPny/o SPm, que son:
SPn∧SPm⇒SQ1
SPn∧S2Pm⇒SQ2
S2Pn∧SPm⇒SQ3
S2Pn∧S2Pm⇒SQ4
Si n=m(la a is a a˜nadida es un lazo), en onces el conjun o de e inamien o
an e io queda educido a dos GGQ, los equi alen es a Q1yQ4.
Figu a 14: Re inamien o a˜nadi a is a.
La siguien e modi icaci´on necesa ia es la de a˜nadi un p edicado adicional
a una a is a exis en e. Pa a man ene las condiciones es uc u ales necesa ias,
es ingimos es a ope aci´on a las a is as posi i as que conec an nodos posi i os.
Teo ema 6 (A˜nadi p edicado a a is a posi i a en e nodos posi i os de Q).
Dado Q∈GGQ n, m ∈V+
Q, con n+e+
−→ m+, y ϕ∈FORM, el conjun o que
no a emos como Q+{n+e∧ϕ
−→ m+}, o mado po (donde Q0=Cl{n,m}
Q):
Q1=(VQ0, EQ0∪ {n+e0
−→ m+}, θQ0∪(e0, θe∧ϕ))
Q2=(VQ0, EQ0∪ {n+e0
−→ m−}, θQ0∪(e0, θe∧ϕ))
Q3=(VQ0, EQ0∪ {n−e0
−→ m+}, θQ0∪(e0, θe∧ϕ))
Q4=(VQ0, EQ0∪ {n−e0
−→ m−}, θQ0∪(e0, θe∧ϕ))
es un conjun o de e inamien o de Qen G(Fig. 15).
Demos aci´on. La demos aci´on es simila a la ealizada en los casos an e io es.
Po ´ul imo, la modi icaci´on que nos queda es la de a˜nadi p edicados a nodos
exis en es. De nue o, hemos de es ingi es a ope aci´on a los casos que no
plan ean p oblemas, cuando los nodos a ec ados son posi i os (el nodo al que se
a˜nade el p edicado, y los conec ados a ´el).
23
Figu a 15: Re inamien o a˜nadi p edicado a a is a.
Teo ema 7 (A˜nadi p edicado a nodo posi i o con en o no posi i o en Q).
Dado Q∈GGQ,n∈V+
Q, con NQ(n)⊆V+
Q, y ϕ∈FORM. De inimos el
conjun o que deno a emos como Q+{n∧ϕ} o mado po :
{Qσ= (VQ0, EQ0, αQ0∪σ, θQ0∪(n0, θn∧ϕ)) : σ∈ {+,−}NQ(n)}
donde Q0=ClNQ(n)
Q, y {+,−}NQ(n)es el conjun o odas las posibles asignacio-
nes de signo a los elemen os de NQ(n)(el en o no, en Q, del nodo n).
En onces Q+{n∧ϕ}es un conjun o de e inamien o de Qen G(Fig. 16).
Demos aci´on. La demos aci´on es simila a la ealizada en los casos an e io es.
Solo hay que ene en cuen a que, cuando se modi ica el nodo n, no solo queda
modi icado el Q-p edicado asociado a ´el sino ambi´en el de odos sus nodos
adyacen es.
Po ello, el p ocedimien o que se ha seguido pa a cub i odas las posibles
opciones de asignaci´on de signos pa a los nodos in oluc ados es po medio del
conjun o de unciones {+,−}NQ(n)( eco demos que en NQ(n) ambi´en se iene
en cuen a el cen o, n).
Se debe ene en cuen a que los e inamien os an e io es gene an es uc u as
que pueden se simpli icadas. A con inuaci´on amos a de ini la ope aci´on p in-
cipal que pe mi e simpli ica un GGQ de e minado ob eniendo o o equi alen e
con meno n´ume o de elemen os.
De inici´on 14. Dado Q∈GGQ, di emos que Q0⊆Qes edundan e en Qsi
Q≡Q−Q0. Donde Q−Q0es el subg a o de Qdado po :
(VQ VQ0, EQ (EQ0∪ {γ(n) : n∈VQ0}), µQ)
Veamos un p ime esul ado que, analizando nodos, nos pe mi e ob ene
e siones simpli icadas de un GGQ po medio de la eliminaci´on de nodos edun-
dan es posi i os:
Teo ema 8. Sea Q∈GGQ, y n∈V+
Q al que exis e m∈VQ e i icando:
α(n) = α(m),θn≡θm.
24
Figu a 16: Re inamien o a˜nadi p edicado a nodo.
Pa a cada e∈γ(n), exis e e0∈γ(m), e i icando α(e) = α(e0),θe=θe0y
γ(e) {n}=γ(e0) {m}.
En onces, nes edundan e en Q.
Esencialmen e, la condici´on que impone el esul ado an e io es que msea
un clon de npe o, posiblemen e, con m´as a is as conec adas. Teniendo en men e
es a idea in ui i a, la p ueba es di ec a a pa i de las condiciones impues as.
Podemos ob ene un esul ado simila pa a a is as po medio del siguien e
esul ado:
Teo ema 9. Sea Q∈GGQ, y dos a is as, e, e0∈EQ, ales que n+e
−→ m+y
n+e0
−→ m+. Si θe→θe0en onces e0es edundan e en Q.
A pa i de los esul ados an e io es podemos da e siones simpli icadas
de los conjun os de e inamien o is os, ag upando nodos posi i os y a is as
posi i as en aquellos casos en los que, as la clonaci´on inicial, el signo del
elemen o duplicado se ha man enido con el o iginal, as´ı como en los casos en
los que el signo se ha man enido y se ha a˜nadido un p edicado adicional. En
las Figu as 17 a 19 se mues an diag amas de los conjun os de e inamien o
Q+{n∧ϕ},Q+{n+e∧ϕ
−→ m+}yQ+{n∧ϕ}, espec i amen e, aplicando las
simpli icaciones p esen adas.
Po ejemplo, pa a cons ui el pa ´on P5una posibilidad se ´ıa segui la si-
25
Figu a 17: Re inamien o a˜nadi a is a (simpli icado).
Figu a 18: Re inamien o a˜nadi p edicado a a is a (simpli icado).
guien e secuencia de e inamien os (Fig. 20):
Q1=Q∅+{n1}
Q2=Q1+{n1∧( ∈S∧τ( )6=ins i u ion ∧τ( )6=clan}
Q3=Q2+{n2}
Q4=Q3+{n2
e1
−→ n1}
P5=Q4+{n2
e1∧(τ(ρ)=DEVOTED TO)
−→ n1}
A pa i de la es uc u a de un GGQ no es ´acil ob ene un GGQ comple-
men a io con ´el. Sin emba go, hay muchos p ocesos de an´alisis sob e g a os con
p opiedades en los que necesi amos abaja con sucesiones de consul as que
e i iquen algunas p opiedades de con enci´on y complemen a iedad como p e-
dicados. Los e inamien os is os en es a secci´on ienen a cub i es a ca encia
y pe mi en, po ejemplo, cons ui un ´a bol de pa iciones encajadas con los
nodos e ique ados de la siguien e o ma (Fig. 21):
El nodo a´ız es ´a e ique ado con Q0(un GGQ inicial cualquie a).
Si un nodo del ´a bol es ´a e ique ado con Q, y R= (Q1, . . . , Qn) es un
conjun o de e inamien o de Q, en onces sus nodos hijo se e ique an con
los elemen os de R.
26
Figu a 19: Re inamien o a˜nadi p edicado a nodo (simpli icado).
Figu a 20: Sucesi´on de e inamien os pa a P5.
Obs´e ese que la cons ucci´on del ´a bol an e io depende po comple o de
la elecci´on del conjun o de e inamien o que se elija en cada ami icaci´on.
Los e inamien os que hemos p esen ado en los esul ados an e io es son una
opci´on, pe o no es la ´unica posible. Po ejemplo, se pueden conside a e ina-
mien os que, en ez de a˜nadi es icciones a elemen os posi i os, alige en las
condiciones impues as po los elemen os nega i os, consiguiendo nue os GGQ
que e inan al an e io , y usando la adici´on de p edicados po medio de la dis-
yunci´on en ez de la conjunci´on.
7. Conclusiones y T abajo Fu u o
En es e abajo hemos abo dado el obje i o de ob ene una he amien a pa a
e alua subg a os inme sos en g a os con p opiedades de mane a que pueda se
u ilizada en p ocedimien os de descub imien o de in o maci´on elacional. Pa a
consegui una he amien a de es e ipo e a deseable e i ica a ios equisi os:
Po una pa e, esul aba necesa io dispone de una g am´a ica que exp e-
sase las consul as a e alua de una o ma ce cana a las p opias es uc u as
27
Figu a 21: ´
A bol de e inamien os.
sob e las que iba a abaja . G acias a la capacidad exp esi a de los g a os
gene alizados hemos p esen ado una he amien a de consul a que se puede
exp esa de o ma na u al po medio de un g a o con p opiedades.
Adem´as, e a necesa io do a al sis ema de consul a una base bien un-
damen ada de p opiedades que nos asegu asen que, al se usadas como
p edicados l´ogicos sob e g a os, se compo aban de mane a cohe en e y
obus a. Es e esul ado se ha ob enido p esen ando las elaciones exis-
en es en e la es uc u a opol´ogica de la consul a y las elaciones de
implicaci´on po medio del e inado.
Adem´as, e a necesa io, ya que en ambi´en las usa emos pa a gene a m´e o-
dos au om´a icos de ap endizaje, que las consul as pudiesen se modi icadas
de mane a con olada po medio de ope ado es a ´omicos que adujesen
el con ol opol´ogico en un con ol l´ogico. En es e sen ido, se ha in odu-
cido una p ime a amilia de e inamien os que pe mi en cons ui a pa i
de una consul a inicial una colecci´on o denada de consul as que eco en
las di e sas opciones de e i icaci´on, o mando un e ´ıculo comple o de
consul as.
Debido a que cualquie es uc u a de da os elacional puede se is a como
un g a o, y cualquie consul a puede se is a como la b´usqueda de un pa ´on,
la mayo ´ıa de lenguajes de consul a en bases de da os pueden se is os como
he amien as (quiz´as p imi i as) de consul a de pa ones en g a os con p opie-
dades. En es e abajo ambi´en se han analizado algunas de las he amien as de
consul a exis en es, as´ı como la iabilidad pa a se u ilizadas en p ocedimien os
au om´a icos. Una de las he amien as analizadas, los g a os de selecci´on, pe mi-
e e alua egis os en bases de da os elacionales a a ´es de pa ones ac´ıclicos
que pueden se e inados a pa i de ope aciones b´asicas, pe mi iendo ob ene
pa ones complemen a ios en cada caso. Pa a ello, no equie e una p oyecci´on
exac a del pa ´on que ep esen a el g a o de selecci´on sob e el subg a o a e a-
lua , sino el cumplimien o de una se ie de p edicados exp esados a a ´es de
dicho pa ´on. Debemos eco da que si se exige una p oyecci´on a la ho a de ea-
liza la e i icaci´on de un pa ´on se complica la a ea de e alua la no exis encia
de de e minados elemen os. Conc e amen e, los g a os de selecci´on, e al´uan la
exis encia / no exis encia de caminos inciden es al egis o bajo e aluaci´on (solo
son capaces de e alua egis os indi iduales), pa a ello se e i ica si se cumple
28
una conjunci´on de p edicados sob e caminos que pa en del egis o analizado,
lo cual puede se is o como la e aluaci´on de exis encia de un ´a bol en aizado
en el nodo que ep esen a el egis o bajo e aluaci´on.
Los Gene alized G aph Que ies que hemos p esen ado aqu´ı ex ienden el con-
cep o de g a o de selecci´on pe mi iendo la e aluaci´on de subg a os gene ales, m´as
all´a de un ´unico nodo, y el uso de p edicados abie os a a ´es de la de inici´on de
un lenguaje sob e los elemen os del g a o y pa ones c´ıclicos. Como se con ie e
en un equisi o no usa una p oyecci´on pa a la e i icaci´on de un pa ´on, es os
obje i os los hemos conseguido ex endiendo la o ma de e aluaci´on, que puede
se is a como la e aluaci´on de un ´a bol en aizado po cada nodo p esen e en el
pa ´on. A pesa de que po cada nodo de un GGQ se e al´ua la exis encia de un
nodo que cumpla con las condiciones impues as po su p edicado y las a is as
en las que pa icipa, al pe mi i que las a is as se iden i iquen con caminos en
el g a o (Regula Pa e n Ma ching) se p oduce la e aluaci´on de un ´a bol po
cada nodo, y no de un simple ´a bol. Las in e secciones que se p oducen en e los
di e sos ´a boles y las es icciones impues as en los nodos pe mi en la e alua-
ci´on de pa ones c´ıclicos en los GGQ, algo que no se hab´ıa conseguido en o as
p opues as an e io es.
Como hemos comen ado, al igual que los g a os de selecci´on, los GGQ se pue-
den modi ica y cons ui a pa i de e inamien os, pe o a di e encia del caso
simple de los g a os de selecci´on, no malmen e los e inamien os no son bina ios,
ya que su aplicaci´on puede modi ica m´as de un p edicado en el pa ´on, dando
luga a conjun os de ama˜no 2k(siendo kel n´ume o de p edicados modi ica-
dos). A a ´es de la de inici´on de de e minadas ope aciones de simpli icaci´on y
equi alencia, los e inamien os mos ados pueden se simpli icados dando luga
a he amien as sencillas que pe mi en cons ui consul as complejas en g a os.
En gene al, los e inamien os dan luga a pa iciones encajadas de las es uc-
u as que e al´uan, lo que los con ie e en he amien as ideales pa a p ocedimien-
os de caja blanca. T as habe lle ado a cabo una p ime a implemen aci´on como
p ueba de concep o (pe o o almen e uncional), se ha demos ado expe imen-
almen e que los GGQ son iables bajo condiciones sua es y que cumplen con
los obje i os plan eados de ex ensi´on de las he amien as exis en es.
Un uso expl´ıci o de es as capacidades ya ha sido lle ado a cabo en p ocedi-
mien os de descub imien o de in o maci´on, en conc e o en el algo i mo GGQ-
ID3, que hace uso de los Gene alized G aph Que ies como he amien as de es
pa a la cons ucci´on de un ´a bol de decisi´on siguiendo los undamen os del amo-
so algo i mo ID3. La elaci´on que gua dan los GGQ con GGQ-ID3 es equi alen e
a la elaci´on que gua dan los g a os de selecci´on con el algo i mo MRDTL [13].
En los esul ados de los expe imen os lle ados a cabo, se mues a que GGQ-ID3
es capaz de ex ae pa ones in e esan es que pueden se u ilizados en a eas de
ap endizaje complejas.
Po o o lado, se pueden c ea amilias de e inamien os m´as complejos (po
ejemplo, combina el e inamien o a˜nadi a is a con a˜nadi p opiedad a una
a is a en un solo paso) pa a de es a mane a educi el n´ume o de pasos pa a
ob ene GGQ complejos y amplia la po encia con espec o a los pasos a ´omicos
que son menos in o ma i os. Si se lle a a cabo es a opci´on de mane a adecuada
(uni icando los e inamien os en unci´on de la ecuencia de apa ici´on de es-
uc u as en un g a o, po ejemplo) se puede consegui que los algo i mos de
descub imien o que hacen uso de GGQ se ace quen de mane a m´as ´apida a una
buena soluci´on. En es e caso se consigue una mejo a en la e iciencia sac i icando
29