Database Reference
In-Depth Information
Figure 10. The DBLP database
AND Author.name = '
Papakonstantinou Yannis
'
)
Obviously, this model of search is too complicated for ordinary users. Several methods aim at de-
creasing this complexity by providing keyword search functionality over relational databases. With
such functionality, a user can avoid writing an SQL query; and she/he can just submit a simple keyword
query '
Hristidis Vagelis
and
Papakonstantinou Yannis
' to the DBLP database. Examples include BANKS
(Bhalotia, Hulgeri, Nakhe, Chakrabarti & Sudarshan, 2002), DBXplore (Agrawal, Chaudhuri & Das,
2002) and DISCOVER (Hristidis & Papakonstantinou, 2002). The former system (BANKS) models the
database as a graph and retrieves results by means of traversal, whereas the latter ones (DBXplore and
DISCOVER) exploit the database schema to compute the results.
BANKS
BANKS
xv
(Bhalotia, Hulgeri, Nakhe, Chakrabarti & Sudarshan, 2002) views the database as a directed
weighted graph, where each node represents a tuple, and edges connect tuples that can be joined (e.g.,
according to primary-foreign key relationships). Node weight is inspired by prestige ranking such as
PageRank; node that has large degree
xvi
get a higher prestige. Edge weight reflects the importance of
the relationship between two tuples or nodes
xvii
; lower edge weights correspond to greater proximity or
stronger relationship between the involved tuples. At query time, BANKS employs a
backward
search
strategy to search for results containing all keywords. A result is a tree of tuples (called tuple tree), that is,
sets of tuples which are associated on their primary-foreign key relationships and contain all the keywords
of the query. Figure 11 shows two tuple trees for query
q
= '
Hristidis Vagelis
and
Papakonstantinou
Yannis
' on the example database of Figure 10. More precisely, BANKS constructs paths starting from
