PhD Qualifying Examination


"Keyword Search on Relational Databases"

Mr. Alexander Markowetz


Abstract:

This survey paper provides an overview of the existing techniques for Key
Word Search (KWS) on relational data. KWS liberates the user from knowing
(i) a query language, (ii) the database schema and (iii) in which
table/column values of interest appear. Its main challenge lies in the
absence of readily available units of information that are expected to
contain the key words. For KWS on unstructured data, as in Web search
engines, these units (the documents) are pre-existent. On relational data,
they have to be created first, by joining tuples from different relations.
A resulting unit of information consists of a tree of joined tuples,
contains all key words and is yet minimal, i.e. it should not be possible
to omit a joining tuple and yet yield all key words. KWS search in
relational databases follows two general frameworks. One family of systems
treats the database as a graph, with nodes representing tuples and edges
connecting join partners. The KWS search is then reduced to finding
Steiner trees that are required to contain all key words. A second family
of systems uses inverted index like structures to detect in which columns
the keywords appear. It then uses this knowledge in combination with the
database schema, to create a set of SQL queries that will evaluate the
KWS. A third type of system, discussed in a single paper only, actually
materializes all basic units of information and writes them out as
documents. KWS is then performed, using a standard inverted index.


Date:     		Monday, 23 January 2006

Time:                   11:00a.m.-1:00p.m.

Venue:                  Room 2504
			lifts 25-26

Committee Members:      Dr. Dimitris Papadias (Supervisor)
			Dr. Lei Chen (Chairperson)
			Prof. Dik Lun Lee
			Prof. Torsten Suel


**** ALL are Welcome ****