10/13/2011
Written by
University of Illinois computer science PhD student Arash Termehchy received the Best Student Paper award at the IEEE International Conference on Data Engineering (ICDE) for his work on design independence for schema free query interfaces.
Real world databases are extremely complex, making it difficult, if not impossible, for users to explore the data and formulate effective queries in traditional structured query languages like SQL. Schema free query interfaces make it possible for users to formulate queries, even if they have no knowledge of the underlying database structure.
A well-known example of schema free query interfaces is the keyword query interface that is used in Web search engines such as Google. People can type their queries into Google interface without knowing how Google organizes its data.
Different people naturally organize the same information in different ways. Just take a look at the way different travel sites organize their requests for what is essentially the same information from the potential traveler. Further, the structure of a data set tends to evolve over time.
Termehchy’s work postulates that schema free query interfaces should deliver the same answers to a query when given alternative, but equivalent, organizations of the same underlying information. Otherwise, users would have to alter their queries in order to receive the same answers when the data set is reorganized.
Design independence means that you can organize the data set in a variety of different ways, and still get the same answers to your queries. Termehchy’s work is the first to define and explore this concept of design independence for schema free query interfaces.
The paper, “How Schema Independent Are Schema Free Query Interfaces?”, establishes a theoretical framework to measure the amount of design independence provided by a schema free query interface (SFQI). The paper proves that the rankings of the results of a query in current SFQIs depend on the structure of the data set. Hence, these SFQI may perform well for some arrangements and poorly for other arrangements of the same information.
The paper proposes a novel, design independent SFQI called Duplication Aware Coherency Ranking that achieves superior ranking quality to existing SFQI methods. The user experience will remain the same as always; no matter how data is organized. The paper was authored by Arash Termehchy, Marianne Winslett, and Yodasawalai Chodpathumwan.
An extended version of the paper has been invited to the IEEE Transactions on Knowledge and Data Engineering (TKDE), Special Issue on the Best Papers of ICDE 2011. The extended paper, "Schema Independent Query Interfaces", is authored by Termehchy, Winslett, Chodpathumwan, and Austin Gibbons. Chodpathumwan and Gibbons were UIUC undergrads when they were involved in the paper's research.
The IEEE International Conference on Data Engineering (ICDE) is a premier forum for presentation of research results and advanced data-intensive applications and discussion of issues on data and knowledge engineering. The mission of the conference is to share research solutions to problems of today's information society and to identify new issues and directions for future research and development work.