Keyword Search over Relational Data

PhD Thesis Proposal Defence


Title: "Keyword Search over Relational Data"

by

Mr. Alexander Markowetz


Abstract:

Ever more complex scenarios employ data streams, monitoring e.g.,
environmental parameters or interactions of online users. These
applications commonly also include relational tables, e.g., to store user
profiles. In this paper, we propose keyword search over relational data
streams (S-KWS) as an effective way to query such heterogeneous
environments, consisting of both, tables and streams. Compared to
structured query methods, S-KWS has several benefits. First, it allows
searching for combinations of terms without knowing in which data sources
they appear. Second, it hides the schema from users and allows it to
change over time, without requiring queries to be re-written.  Third,
keyword queries are easy to express. Finally, many query tasks only become
feasible through S-KWS. Our contributions are summarized as follows. (i)
We provide formal semantics, addressing the temporal validity and order of
results, spanning uniformly over tables and streams. (ii) We introduce two
general methodologies for query processing: graph based (GB) and operator
based (OB). The first generates results by traversing a data graph; the
second by executing operator trees. (iii) We present a range of
optimizations for both approaches. For GB, we speed up graph traversals,
using keyword labels.  For OB, we integrate operator trees into a single
mesh, sharing common expressions. Join operations are further reduced,
using demand driven operator execution. The operator mesh dynamically
adapts to changes in the schema and input characteristics. Two strategies
for purging outdated tuples target either CPU or memory. Extensive
experiments demonstrate the practicability of S-KWS as well as the
tremendous benefits of the proposed optimizations.


Date:     		Thursday, 17 April 2008

Time:                   3:30p.m.-5:30p.m.

Venue:                  Room 3405
			lifts 17-18

Committee Members:      Prof. Dimitris Papadias (Supervisor)
			Prof. Mounir Hamdi (Chairperson)
                        Dr. Lei Chen
			Prof. Nikos Mamoulis (HKU)


**** ALL are Welcome ****