CS700:Graduate Seminar in Computer Science & Informatics

Coupling Query Languages with Structural Indexes

Index data structures are crucial for efficient database query processing. Typically, such indexes are built over the data values which occur in the underlying database instance. Alternatively, indexes can be built over the "structure" of the instance. For example, indexes for XML have been proposed which capture the hierarchical structure of the data. The relationships between query languages and such structural indexes, however, are not clearly understood. In this talk we introduce a new methodology for coupling languages and indexes that is aimed towards a better understanding of the use of structural indexes for efficient query evaluation. We focus on the important case of the XML query language XPath, identifying XPath fragments which are ideally coupled with the newly introduced P(k)-partition, which has its definition grounded in the well known A(k) structural indexes. We will then discuss how these couplings are utilized to investigate fundamental questions about the use of structural indexes to accelerate XPath query processing. This is joint work with colleagues at Indiana University, Hasselt University, and the University of Antwerp, with results published in PODS 2006 and DBPL 2007.
George Fletcher is an assistant professor of computer science at Washington State University, Vancouver. Dr. Fletcher's research interests are in database systems and theory, with a current focus on problems of data integration and sharing in web-scale information systems. Dr. Fletcher received his PhD in 2007 from Indiana University where he held the Paul W. Purdom Fellowship in Informatics.