I’d rather play golf

On Wednesday I attended a lecture entitled “Towards a Theory of Search Queries” presented by Dirk Van Gucht of Indiana University. The talk summarized the results that were published earlier this year in a paper [1] of the same name at the 12th International Conference on Database Theory (ICDT) (ACM version is here, freely available version here).

One of Van Gucht’s motivations for this work is the increasing popularity of using search tools to query relational database content, rather than the use of more formal query languages such as ANSI/ISO SQL which is not only cumbersome for many people but also requires a structured, well-defined schema.

The paper does not address implementation details or efficiency. Rather, it tries to formally define the types of queries that can be issued using a basic search language – similar to full-text search grammar offered by SQL Anywhere – over semi-structured “dataspaces” that lack a rigid schema. The paper shows that a basic language, augmented with the ability to follow “simlinks” between objects, offers the same expressive power as a relational language based (only) on the semi-join operator. Such a language is unable to express all the classes of queries currently possible in SQL, but in his talk, Van Gucht argued that language extensions beyond (semi)joins – for example, subqueries – are quite cumbersome to use.

This excerpt, from page 210, nicely summarizes the work:

Our goal has been to provide the beginnings of a theoretical foundation for search and associative search queries, motivated by the ubiquity of such queries in everyday information systems. Our approach has been to investigate search queries as restricted kinds of database queries, and to use the tools and concepts already developed in the theory of database queries.

It will be interesting to see if this line of research can yield concrete language designs that better meld relational querying with “Google” style searching.

[1] George H. L. Fletcher, Jan Van den Bussche, Dirk Van Gucht, Stijn Vansummeren (March 2009). Towards a Theory of Search Queries. In Proceedings of the 12th International Conference On Database Theory (ICDT), Saint Petersberg, Russia, pp. 201-211.