OREGON STATE UNIVERSITY

You are here

How schema independent are schema free query interfaces?

TitleHow schema independent are schema free query interfaces?
Publication TypeConference Paper
Year of Publication2011
AuthorsTermehchy, A., M. Winslett, and Y. Chodpathumwan
Conference Name2011 IEEE International Conference on Data Engineering (ICDE 2011)
Pagination649 - 660
Date Published04/2011
PublisherIEEE
Conference LocationHannover, Germany
ISBN Number978-1-4244-8959-6
Abstract

Real-world databases often have extremely complex schemas. With thousands of entity types and relationships, each with a hundred or so attributes, it is extremely difficult for new users to explore the data and formulate queries. Schema free query interfaces (SFQIs) address this problem by allowing users with no knowledge of the schema to submit queries. We postulate that SFQIs should deliver the same answers when given alternative but equivalent schemas for the same underlying information. In this paper, we introduce and formally define design independence, which captures this property for SFQIs. We establish a theoretical framework to measure the amount of design independence provided by an SFQI. We show that most current SFQIs provide a very limited degree of design independence. We also show that SFQIs based on the statistical properties of data can provide design independence when the changes in the schema do not introduce or remove redundancy in the data. We propose a novel XML SFQI called Duplication Aware Coherency Ranking (DA-CR) based on information-theoretic relationships among the data items in the database, and prove that DA-CR is design independent. Our extensive empirical study using three real-world data sets shows that the average case design independence of current SFQIs is considerably lower than that of DA-CR. We also show that the ranking quality of DA-CR is better than or equal to that of current SFQI methods.

Notes

Best Student Paper Award

DOI10.1109/ICDE.2011.5767880