Towards a theory of search queries

ABSTRACT

The need to manage diverse information sources has triggered the rise of very loosely structured data models, known as "dataspace models." Such information management systems must allow querying in simple ways, mostly by a form of searching. Motivated by these developments, we propose a theory of search queries in a general model of dataspaces. In this model, a dataspace is a collection of data objects, where each data object is a collection of data items. Basic search queries are expressed using filters on data items, following the basic model of boolean search in information retrieval. We characterise semantically the class of queries that can be expressed by searching. We apply our theory to classical relational databases, where we connect search queries to the known class of fully generic queries, and to dataspaces where data items are formed by attribute--value pairs. We also extend our theory to a more powerful, associative form of searching where one can ask for objects that are similar to objects satisfying given search conditions. Such associative search queries are shown to correspond to a very limited kind of joins. Specifically, we show that the basic search language extended with associative search can define exactly the queries definable in a restricted fragment of the semijoin algebra working on an explicit relational representation of the dataspace.

REFERENCES

• 1: RDF primer. W3C Recommendation, February 2004.
• 2: SPARQL query language for RDF. W3C Recommendation, January 2008.
• 3: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 4: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 5: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 6: Catriel Beeri , Tova Milo , Paula Ta-Shma, On genericity and parametricity (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.104-116, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237689]
• 7: Catriel Beeri , Tova Milo , Paula Ta-Shma, Towards a Language for the Fully Generic Queries, Proceedings of the 6th International Workshop on Database Programming Languages, p.239-259, August 18-20, 1997
• 8: Patrick Blackburn , Maarten de Rijke , Yde Venema, Modal logic, Cambridge University Press, New York, NY, 2001
• 9: P. Blackburn, J. van Benthem, and F. Wolter, editors. Handbook of Modal Logic. Elsevier, 2007.
• 10: A. Chandra and D. Harel. Computable queries for relational data bases. Journal of Computer and System Sciences, 21(2):156--178, 1980.
• 11: Jens-Peter Dittrich , Marcos Antonio Vaz Salles, iDM: a unified and versatile data model for personal dataspace management, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 12: Xin Dong , Alon Halevy, Indexing dataspaces, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247487]
• 13: G. H. L. Fletcher. An algebra for basic graph patterns. Presented at the workshop on Logic in Databases, Rome, Italy, May 2008.
• 14: Konstantin Golenberg , Benny Kimelfeld , Yehoshua Sagiv, Keyword proximity search in complex data graphs, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376708]
• 15: V. Goranko and M. Otto. Model theory of modal logic. In Blackburn et al. {9}, chapter 5.
• 16: Claudio Gutierrez , Carlos Hurtado , Alberto O. Mendelzon, Foundations of semantic web databases, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055573]
• 17: Alon Halevy , Michael Franklin , David Maier, Principles of dataspace systems, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-9, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142352]
• 18: H. V. Jagadish , Adriane Chapman , Aaron Elkiss , Magesh Jayapandian , Yunyao Li , Arnab Nandi , Cong Yu, Making database systems usable, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247483]
• 19: M. Jain, A. Mendhekar, and D. Van Gucht. A uniform data model for relational data and meta-data query processing. In Advances in Data Management '95, pages 146--165. Tata McGraw-Hill, 1995.
• 20: Dirk Leinders , Maarten Marx , Jerzy Tyszkiewicz , Jan Bussche, The Semijoin Algebra and the Guarded Fragment, Journal of Logic, Language and Information, v.14 n.3, p.331-343, June 2005 [doi>10.1007/s10849-005-5789-8]
• 21: Dirk Leinders , Jan Van den Bussche, On the complexity of division and set joins in the relational algebra, Journal of Computer and System Sciences, v.73 n.4, p.538-549, June, 2007 [doi>10.1016/j.jcss.2006.10.011]
• 22: J. Pérez, M. Arenas, and C. Gutierrez. Semantics and complexity of SPARQL. In The Semantic Web: Proceedings ISWC, volume 4273 of Lecture Notes in Computer Science, pages 30--43. Springer, 2006.
• 23: K. A. Ross and A. Janevski. Querying faceted databases. In Proceedings 2nd International Workshop on Semantic Web and Databases, volume 3372 of Lecture Notes in Computer Science, pages 199--218. Springer, 2005.
• 24: Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies, W. H. Freeman & Co., New York, NY, 1990