Close and Loose Associa ions in Keywo d Sea ch om
S uc u al Da a
Johanna Vainio
Uni e si y o Tampe e
Kansle in inne 1
FI-33014 Uni e si y o Tampe e,
Finland
s.johanna. ainio@s a .u a. i
Ma ko Junkka i
Uni e si y o Tampe e
Kansle in inne 1
FI-33014 Uni e si y o Tampe e,
Finland
ma ko.junkka i@u a. i
Jaana Kekäläinen
Uni e si y o Tampe e
Kansle in inne 1
FI-33014 Uni e si y o Tampe e,
Finland
jaana.kekalainen@u a. i
ABSTRACT
Keywo d sea ch o e s uc u al da a enables use s o seek
in o ma ion om da abases wi hou knowing he s uc u e o da a
o mas e ing ac ual que y languages like SQL. In a keywo d que y,
da a i ems o ex a ibu es a e ma ched o he keywo ds and he
esul o a que y is ypically a se o g aphs consis ing o connec ed
uples. The esul should be anked which means ha he ex
a ibu es and connec ions mus be sco ed and combined. Typically,
he leng h o a connec ion is he main c i e ion in anking he
connec ions, i.e. sho e connec ions a e sco ed highe han longe
ones. The leng h o a connec ion is usually based on he o eign key
e e ences bu hei di ec ion has ecei ed less a en ion. A he
concep ual le el, ca dinali y cons ains co espond o o eign key
e e ences o hei combina ion. In he p esen pape , we in es iga e
he e ec o he combina ions o ca dinali y cons ains on he esul
o a keywo d sea ch. We ind ha he combina ion o ca dinali y
cons ain s indica es how close he associa ion be ween keywo ds
is. We also show ha he Minimal To al Joining Ne wo k o Tuples
(MTJNT) p inciple loses seman ic connec ions o agmen s he
esul s o a keywo d sea ch om ela ional da abases.
CCS Concep s
•In o ma ion sys ems •In o ma ion sys ems ~ Rela ional
da abase model • In o ma ion sys ems ~ En i y ela ionship
models • In o ma ion sys ems ~ Da abase que y p ocessing
Keywo ds
Keywo d que ies o e s uc u ed da a; associa ions in ela ional
da abases; ca dinali y cons ain s; ER model.
1. INTRODUCTION
Keywo d sea ch enables end-use s o sea ch da a om ela ional
da abases wi hou knowledge o he syn ax o a que y language o
he s uc u e o he da a. Howe e , keywo d sea ch in ol es
ambigui y and aises new challenges. T adi ionally, ambigui y is
associa ed wi h he na u e o keywo d sea ch, i.e. ma ching sea ch
keys o documen con en s is mo e o less uzzy. In he con ex o
s uc u ed da a, he na u e o ela ionships among en i ies and ex
a ibu es may also a ec di e en kinds o seman ic
in e p e a ions. Namely, en i ies may be associa ed wi h each o he
ia di e en kinds o ela ionships. In he p esen pape , we i s
s udy which kinds o se ings he concep ual associa ions o a
seman ic da a model se e o he connec ions o en i ies. Then, we
analyze hei oles in keywo d sea ch in ela ional da abases.
In in o ma ion e ie al, keywo d sea ch inds documen s ha
con ain all o some o he keywo ds and anks he documen s
acco ding o he s a is ical p ope ies o hei wo ds. The e is no
need o sol e how documen s con aining he keywo ds a e
connec ed. In con ex o ela ional da abases, keywo d sea ch can
be used o ind he op anked connec ions o uples ha con ain all
o some o he keywo ds. To p oduce anking, uples ha con ain a
keywo d a e e ie ed, and connec ions be ween hese uples a e
p oduced. A connec ion o uples may, o example, be a minimal
o al joining ne wo k o uples (MTJNT) [4] o S eine ee [1] [2].
The e a e also di e en app oaches how o ank he p oduced
connec ions. Ranking can be based, simply, on he numbe o joins
o a connec ion o a ibu e, uple o edge le el sco es o
combina ions o hem. [6, 7, 8] Di e en connec ions may con ain
di e en amoun o in o ma ion and di e en in e p e a ions, e en
be ween he same keywo d uples. The e o e, he sho es
connec ion is no always he bes ; a longe pa h may be mo e
app op ia e [5, 6]. We d aw his conclusion by analyzing he
closeness and looseness o concep ual associa ion. This dimension
is based on he ca dinali y cons ains ha appea in he connec ions
o en i ies.
2. CONCEPTUAL ASSOCIATIONS
Seman ic da a models a e concep ual me hods o ep esen ing
concep s and he ela ionships among hem. The ER model is he
mos common seman ic da a model and i s p incipal p imi i es a e
he en i y ype, a ibu e, and ela ionship ( ype) be ween he en i y
ypes. A ela ionship in ol es a ca dinali y cons ain ha may be
1:1, 1:N, N:1 o N:M. A cons ain de e mines how many ins ances
a e pa icipa ing in he ela ionship a he ex ensional (ins ance)
le el. Le he ER schema o Figu e 1 illus a e his. The schema is
a agmen om [3] bu no a ibu es a e ep esen ed. The example
con ains ou en i y ypes (DEPARTMENT, EMPLOYEE,
DEPENDENT and PROJECT) and ou ela ionships among hem.
In he example, se e al employees may wo k o a depa men and
an employee wo ks in one depa men . An employee may ha e
se e al dependen s and a dependen has one employee as a
gua dian. Fu he mo e, an employee may wo k on se e al p ojec s
and a p ojec may ha e se e al employees. Finally, a depa men
may con ol se e al p ojec s and a p ojec is con olled by a single
depa men .
2017, Copy igh is wi h he au ho s. Published in he Wo kshop
P oceedings o he EDBT/ICDT 2017 Join Con e ence (Ma ch
21, 2017, Venice, I aly) on CEUR-WS.o g (ISSN 1613-0073).
Dis ibu ion o his pape is pe mi ed unde he e ms o he
C ea i e Commons license CC-by-nc-nd 4.0
Figu e 1: ER- schema
Figu e 1 illus a es ha an employee and a depa men may be in
associa ion in wo ways. Fi s , an employee wo ks o a depa men
and second, (s)he wo ks on a p ojec con olled by he depa men .
The i s al e na i e in ol es one ela ionship and he second wo
ela ionships, i.e. he i s pa h is sho e bu he longe one con ains
mo e in o ma ion because i also de e mines in which p ojec he
employee is wo king. This is an essen ial issue in keywo d sea ch
om s uc u al da a whe e he esul connec ions should be anked.
In o he wo ds, i we wan o emphasize access o mo e in o ma ion
a longe connec ion should be anked be o e sho e connec ions.
Howe e , usually longe connec ions a e lowe in a esul lis o no
in he esul s lis a all. This is jus i ied, because longe connec ions
en ail mo e ambigui y han sho e ones and may lose associa ions
be ween en i ies. Howe e , he le el o he ambigui y a connec ion
in ol es can be examined, and hus, dec eased and con olled. Nex
we in es iga e how he le el o he ambigui y can be de e mined
based on he ca dinali y cons ain s o he ER-model.
An en i y ype in ol es a se o en i ies whe eas ela ionships
de e mine how he en i ies can be connec ed o each o he . In he
p esen pape , we concep ualize ha a close connec ion be ween
en i ies means ha hey a e associa ed wi h each o he
unambiguously h ough hei ela ionships. Table 1 con ains a
sample o immedia e and ansi i e ela ionships be ween en i y
ypes. Rela ionships 1 and 2 ep esen a si ua ion whe e wo en i y
ypes and he co esponding en i ies a e connec ed immedia ely. In
he immedia e ela ionships, he e is no ambigui y in he seman ics
o he connec ions, i.e. he co esponding en i ies a e closely
associa ed o each o he .
A ansi i e ela ionship con ains mo e han one immedia e
ela ionships, i.e. he co esponding en i ies a e connec ed o each
o he ia a middle en i y. T ansi i e ela ionship 3 consis s o wo
immedia e ela ionships bo h ha ing he ca dinali y cons ains 1:N.
In o he wo ds, o one depa men he e a e se e al employees and
o each employee he e may be se e al dependen s, bu no ice
e sa. This means ha he e is a ansi i e 1:N ela ionship be ween
he en i y ypes depa men and dependen . In o he wo ds, he
connec ion is (in e se) unc ional. We in e p e bo h in e se
unc ional connec ions, only 1:N ela ionships, and unc ional
connec ions, only N:1 ela ionships, as unc ional. This is because
a connec ion can be ep esen ed in bo h di ec ions, i.e. he
connec ion 3 in Table 1 can be ep esen ed om dependen o
depa men (dependen N:1 employee N:1 depa men ) as well.
A unc ional ela ionship may also con ain 1:1 ela ionships.
The e o e, we de ine ha i X1,Y1,…,Xn,Yn ep esen s he
ca dinali y cons ain s o a ansi i e ela ionships such ha i 
{1, …, n} holds ha Xi = 1 o i  {1, …, n} holds ha Yi = 1 hen
he ela ionships is unc ional.
In gene al, he immedia e ela ionships and ansi i e unc ional
ela ionships de e mine a close connec ion be ween en i ies a he
ex ensional le el.
Table 1. Rela ionships and hei ca dinali ies in he ER
schema
Rela ionship
Ca dinali y
1
depa men – employee
depa men 1:N employee
2
p ojec – employee
p ojec N:M employee
3
depa men – employee
–dependen
depa men 1:N employee
1:N dependen
4
depa men – p ojec –
employee
depa men 1:N p ojec
N:M employee
5
p ojec – depa men –
employee
p ojec N:1 depa men 1:N
employee
6
depa men – p ojec –
employee – dependen
depa men 1:N p ojec
N:M employee 1:N
dependen
T ansi i e ela ionship 4 consis o 1:N and N:M ela ionships
espec i ely. This means ha one depa men can be associa ed
wi h employees h ough se e al p ojec s. In o he wo ds,
employees ha wo k on a p ojec con olled by a depa men may
o may no wo k in he depa men . Fo he eason ha he e a e
wo kinds o seman ic in e p e a ions, his kind o ansi i e
ela ionship may cause a loose connec ion a he ex ensional le el.
T ansi i e ela ionship 5 con ains wo immedia e ela ionships
ha ing ca dinali y cons ain s N:1 and 1:N espec i ely. This is
called a ansi i e N:M ela ionship because se e al en i ies o he
s a en i y ype may be connec ed o se e al en i ies o he end
en i y ype ia a middle en i y. This kind o ela ionship causes a
mo e ambiguous in e p e a ion on he connec ion o en i ies.
Namely, an employee is associa ed wi h a p ojec al hough s(he)
may no wo k on i , i.e. an employee is associa ed wi h e e y
p ojec a depa men is con olled. The e o e, a ansi i e N:M
ela ionships may also cause a loose connec ion be ween en i ies.
In gene al, le X1,Y1,…,Xn,Yn, whe e X1 ≠ 1 and Yn ≠ 1,
ep esen he ca dinali y cons ain s o a ansi i e ela ionships,
hen he ela ionship is N:M ansi i e. Connec ion 6 con ains h ee
immedia e ela ionships. The i s ela ionship possesses he 1:N
cons ain and he las 1:N cons ain . Howe e , his is no ansi i e
1:N ela ionship because i con ains a ansi i e N:M ela ionship
as a pa o i . The e o e, i allows loose connec ions a he
ex ensional le el.
Nex we demons a e close and loose connec ions a he da abase
le el and hei e ec s on keywo d sea ch in ela ional da abases.
3. ASSOCIATIONS IN RELATIONAL
DATABASES
Roughly speaking, an ER-schema is implemen ed in ela ional
da abases such ha o each en i y ype a ela ion is implemen ed.
Fo each 1:N ela ion a o eign key is inse ed o he N-si e. Fo
each N:M ela ionships a middle ela ion is o med. This ela ion
con ains he o eign keys om bo h he pa icipa ing en i y ypes
( ela ions in RDB). A o eign key cons ain is ypically ep esen ed
as an a ow om a o eign key o he ela ed p ima y key. The
DEPARTMENT
EMPLOYEE
PROJECT
WORKS
ON
WORKS
FOR
CONTROLS
1
N
M
N
N
1
DEPENDENT
DEPENDENTS
1
N
da abase schema and da abase ins ance o Figu e 1 is ep esen ed
in Figu e 2. A ibu es a e now ep esen ed.
DEPARTMENT
ID
D_NAME
D_DESCRIPTION
d1
Cs
The main opics o
eaching a e
p og amming, da abases
and XML.
d2
in
The main opics o
eaching a e in o ma ion
e ie al and XML.
d3
his o y
The main opics o
eaching a e his o y o
Scandina ian.
PROJECT
ID
D_ID
P_NAME
P_DESCRIPTION
p1
d1
DB-
p ojec
Di e en da a models
a e in eg a ed, such as
ela ional, objec and
XML
p2
d2
XML and
IR
XML o e s a
no a ion o
s uc u ed documen s.
p3
d2
IR ask
Task based
in o ma ion e ie al
WORKS_FOR
ESSN
P_ID
HOURS
e1
p1
40
e2
p3
56
e3
p2
70
e4
p3
60
EMPLOYEE
SSN
L_NAME
S_NAME
D_ID
e1
Smi h
John
d1
e2
Smi h
Ba ba a
d2
e3
Mille
Melina
d1
e4
Walke
John
d2
DEPENDENT
ID
ESSN
DEPENDENT_NAME
1
e3
Alice
2
e3
Theodo e
Figu e 2. Da abase schema and ins ance
A keywo d sea ch ypically ocuses on a ibu e alues. A keywo d
may ma ch he whole a ibu e alue o a wo d in a ex a ibu e.
Le us conside a sample keywo d sea ch
Smi h XML
“Smi h” ma ches wo i s employees whe eas “XML” ma ches wo
p ojec s and wo depa men s. Connec ions 1 – 7 in Table 2
ep esen s some o he connec ions o he keywo d que y “Smi h
XML” in he RDB in Figu e 2.
John Smi h is associa ed wi h XML h ough di e en connec ions.
The sho es and he longes connec ions a e be ween an employee
and a depa men as shown in Table 1. John Smi h is also associa ed
wi h XML h ough he p ojec by he connec ions ha ing wo s eps
(connec ions 2 and 3 in Table 2). Howe e , WORKS_FOR is a
middle ela ion and he leng h o he connec ion would be one i he
concep ual schema we e ollowed. In o he wo ds, in concep ual
app oach middle ela ions should no be aken in o accoun when
calcula ing he leng h o a connec ion.
Table 2. Connec ions in he RDB and leng hs o he
connec ions in he RDB and he ER
connec ion
leng h in
RDB
leng h in
ER
1
d1(XML) – e1(Smi h)
1
1
2
p1(XML) – w_ 1 – e1(Smi h)
2
1
3
p1(XML) – d1(XML) – e1(Smi h)
2
2
4
d1(XML) – p1(XML) – w_ 1 –
e1(Smi h)
3
2
5
d2(XML) – e2(Smi h)
1
1
6
p2(XML) – d2(XML) – e2(Smi h)
2
2
7
d2(XML) – p3 – w_ 2 – e2(Smi h)
3
2
8
d1 – e3 – 1(Alice)
2
2
9
d2 – p2 – w_ 3 – e3 – 1(Alice)
4
3
In a schema (in ensional) le el, connec ions 1 and 2 ha e a close
associa ion and connec ions 3 and 4 ha e a loose associa ion
be ween he en i ies. Howe e , in an ins ance le el, also
connec ions 3 and 4 ha e a close associa ion be ween he en i ies.
The connec ions can be ead as ollows:
1) “employee e1(Smi h) wo ks o depa men d1(XML)”
2) “employee e1(Smi h) wo ks on a p ojec p1(XML)”
3) “employee e1(Smi h) wo ks o depa men d1(XML), ha
con ols p ojec p1(XML)”
4) “employee e1(Smi h) wo ks on p ojec p1(XML), ha is
con olled by depa men d1(XML).
In his case employee e1 wo ks on p ojec p1 as associa ed in
connec ion 3 and employee e1 wo ks o depa men d1 as
associa ed in connec ion 4, bu his canno gene ally be assumed
wi hou in es iga ing o he connec ions. This is illus a ed nex .
The closes and longes associa ion be ween Ba ba a Smi h and
XML ela es o he desc ip ion o he depa men because she
wo ks in a depa men ha ma ches XML (connec ions 5 and 7 in
Table 2). I is wo h no ing ha Ba ba a is also associa ed wi h
p ojec p2 in connec ion 6 al hough she does no wo k in i . This is
because he connec ion con ains N:1 and 1:N ela ionships. In o he
wo ds his connec ion gi es b oade in e p e a ion and p ojec p2
and employee e2 (Ba ba a Smi h) a e in a loose associa ion.
I he ank o connec ions 1 - 7 we e based on he leng h o he
connec ion in RDB, he bes connec ions a e 1 and 5 and he wo s
connec ions a e 4 and 7. I he leng h o he ER-model we e
ollowed and he close associa ions we e emphasized, he bes
connec ions a e 1, 2 and 5 and he wo s connec ions a e 3 and 6.
In he la e app oach connec ions 4 and 7 ha e a be e ank
because hey do no lose he close associa ion (in he schema le el),
i.e. he employee wo ks in he depa men and in he p ojec he
connec ion includes. Connec ions 8 and 9 in Tables 2 and 3
co espond o ela ionships 5 and 6 in Table 1. Connec ion 8 has a
close associa ion and connec ions 9 has a loose associa ion be ween
en i ies in bo h he schema and ins ance le els.
A commonly used app oach o o m connec ions is Minimal To al
Joining Ne wo k o Tuples (MTJNT) [4] o S eine ee [1] [2]. In
he MTJNT app oach e e y keywo d exis s in a leas one uple o
he joining ne wo k. I is no possible o emo e any uple om he
joining ne wo k wi hou losing MTJNT. The MTJNT app oach
e u ns minimally connec ed uples ha s ill con ain e e y
keywo d. This app oach can lose some meaning ul uples ha a e
associa ed o keywo d que ies and MTJNTs. In he p e ious
example connec ions 3, 4, 6 and 7 a e los , i he MTJNT app oach
we e ollowed.
Table 3. Connec ions and ela ionships o he connec ions in
he RDB
Connec ion
Connec ion wi h ela ionships
1
d1(XML) – e1(Smi h)
d1(XML) 1:N e1(Smi h)
2
p1(XML) – w_ 1 –
e1(Smi h)
p1(XML) 1:N w_ 1 N:1 e1(Smi h)
3
p1(XML) – d1(XML) –
e1(Smi h)
p1(XML) N:1 d1(XML) 1:N
e1(Smi h)
4
d1(XML) – p1(XML) –
w_ 1 – e1(Smi h)
d1(XML) 1:N p1(XML) 1:N w_ 1
N:1 e1(Smi h)
5
d2(XML) – e2(Smi h)
d2(XML) 1:N e2(Smi h)
6
p2(XML) – d2(XML) –
e2(Smi h)
p2(XML) N:1 d2(XML) 1:N
e2(Smi h)
7
d2(XML) – p3 – w_ 2 –
e2(Smi h)
d2(XML) 1:N p3 1:N w_ 2 N:1
e2(Smi h)
8
d1 – e3 – 1(Alice)
d1 1:N e3 1:N 1(Alice)
9
d2 – p2 – w_ 3 – e3 –
1(Alice)
d2 1:N p2 1:N w_ 3 N:1 e3
1:N 1(Alice)
The associa ion o he keywo d que y in connec ion 4 is al eady
implici ly isible o he use in connec ions 1 and 2. Howe e , in
ha case we ha e o assume ha he use b owses h ough hese
wo answe s and disco e s he associa ion om answe s. Fu he ,
i is no always he case ha he associa ion is implici ly isible in
he o he e u ned associa ions as is he case in connec ion 7.
4. DISCUSSION AND CONCLUSIONS
We ha e in es iga ed he e ec s o he ypes o connec ions on he
esul s o keywo d que ies o e s uc u al da a. We conside ed how
ca dinali y cons ain s a ec he anking o que y esul s. We
no iced ha ca dinali y cons ains can be u ilized o in e he
looseness o an associa ion. A loose associa ion gi es a mo e
ex ensi e esul o a keywo d que y because en i ies ( uples) a e
associa ed o each o he h ough a mo e gene al en i y o se e al
en i ies. The closeness o a connec ion a he ex ensional le el can
pa ly be in e ed om he ca dinali y cons ain s o he ER model.
Immedia e and ansi i e unc ional ela ionships ensu e he close
connec ion be ween he co esponding en i ies. Ins ead, o he
combina ions allow close o loose connec ions be ween
pa icipa i e en i ies. Fo example, in a ansi i e N:M ela ionship
se e al en i ies may be connec ed o each o he h ough a mo e
gene al en i y and he seman ics o he ela ionship is ague.
Howe e , u he s udies a e needed o in es iga ing how ou
indings could be u ilized in anking he esul connec ions. One
c i e ion could be he numbe o ansi i e N:M ela ionships in a
connec ion. A mo e p ecise app oach could be achie ed by
analyzing he ac ual numbe o pa icipa ing en i ies ( uples) in a
da abase ins ance.
We also p oposed ha he leng h o connec ions should be based
on he ela ionships a he concep ual le el because he N:M
ela ionship co esponds o a concep ual ela ionship. Mo eo e ,
1:N o N:1 ela ionship can be implemen ed by a middle ela ion.
By using concep ual ela ionships he leng h o connec ions does
no depend on implemen a ion issues o his kind.
The esul s o a keywo d sea ch may p oduce se e al pa hs be ween
uples and hey should be anked based on hei assumed ele ance.
One widely used indica ion has been he leng h o he pa h, i.e. he
sho es pa hs a e ypically assumed o be mo e ele an han longe
pa hs. Howe e , longe pa hs may con ain mo e in o ma ion han
sho e pa hs and sho e pa hs may chop a seman ic connec ion
be ween en i ies o ex a ibu es/documen s. The e o e, he e
should be an al e na i e whe e he use could selec longe pa hs, i
s/he is in e es ed in la ge con ex o ma ched alues o documen s.
5. REFERENCES
[1] Adi ya, B., Bhalo ia, G., Chak aba i, S., Hulge i, A., Nakhe,
C., Pa ag, P. and Suda shan, S. BANKS: B owsing and
Keywo d Sea ching in Rela ional Da abases. In P oceedings
o he 28 h In e na ional Con e ence on Ve y La ge Da a
Bases. VLDB ’02. VLDB Endowmen , 2002, 1083-1086.
[2] Be gamaschi, S., Gue a, F. and Simonini, G. Keywo d
Sea ch o e Rela ional Da abases: Issues, App oaches and
Open Challenges. In Fe o, N. ed. B idging Be ween
In o ma ion Re ie al and Da abases: PROMISE Win e
School 2013. Re ised Tu o ial Lec u es. Sp inge Be lin
Heidelbe g, Be lin, Heidelbe g, 2014, 54-73. 2002, 1083-
1086.
[3] Elmas i, R. and Na a he, S. B. Fundamen als o Da abase
Sys ems, Fou h Edi ion. Addison-Wesley Longman
Publishing Co., Inc, Bos on, MA, USA, 2003.
[4] H is idis, V. and Papakons an inou, Y. Disco e : Keywo d
Sea ch in Rela ional Da abases. In P oceedings o he 28 h
In e na ional Con e ence on Ve y La ge Da a Bases. VLDB
’02. VLDB Endowmen , 2002, 670-681.
[5] Ka ga , M., An, A., Ce cone, N., God ey, P., Szlich a, J.
and Yu, X. MeanKS: Meaning ul Keywo d Sea ch in
Rela ional Da abases wi h Complex Schema. In P oceedings
o he 2014 ACM SIGMOD In e na ional Con e ence on
Managemen o Da a.. SIGMOD ’14. ACM, New Yo k, NY,
USA, 2014, 905-908.
[6] Ka ga , M., An, A., Ce cone, N., God ey, P., Szlich a, J. and
Yu, X. Meaning ul keywo d sea ch in ela ional da abases
wi h la ge and complex schema. In Anonymous 2015 IEEE
31s In e na ional Con e ence on Da a Enginee ing. 2015,
411-422.
[7] Li, L., Pe schula , S., Tang, G., Pei, J. and Luk, W. E icien
and E ec i e Agg ega e Keywo d Sea ch on Rela ional
Da abases. In .J.Da a Wa ehous.Min., 8, 4 (oc 2012), 41-81.
DOI=10.4018/jdwm.2012100103.
[8] Zeng, Z., Bao, Z., Lee, M. L. and Ling, T. W. Towa ds An
In e ac i e Keywo d Sea ch o e Rela ional Da abases. In
P oceedings o he 24 h In e na ional Con e ence on Wo ld
Wide Web. ACM, New Yo k, NY, USA, 2015, 259-262. .