{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:54:14Z","timestamp":1750308854599,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,10,12]],"date-time":"2010-10-12T00:00:00Z","timestamp":1286841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2010,11]]},"abstract":"<jats:p>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 characterize 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. We show that the basic search language extended with associative search can exactly define the queries definable in a restricted fragment of the semijoin algebra working on an explicit relational representation of the dataspace.<\/jats:p>","DOI":"10.1145\/1862919.1862925","type":"journal-article","created":{"date-parts":[[2010,12,20]],"date-time":"2010-12-20T15:55:04Z","timestamp":1292860504000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Towards a theory of search queries"],"prefix":"10.1145","volume":"35","author":[{"given":"George H. L.","family":"Fletcher","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, The Netherlands"}]},{"given":"Jan","family":"Van Den Bussche","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Belgium"}]},{"given":"Dirk","family":"Van Gucht","sequence":"additional","affiliation":[{"name":"Indiana University, Bloomington"}]},{"given":"Stijn","family":"Vansummeren","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2010,10,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley."},{"volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases. 149--158","author":"Agrawal R.","key":"e_1_2_1_2_1","unstructured":"Agrawal , R. , Somani , A. , and Xu , Y . 2001. Storage and querying of e-commerce data . In Proceedings of the 27th International Conference on Very Large Data Bases. 149--158 . Agrawal, R., Somani, A., and Xu, Y. 2001. Storage and querying of e-commerce data. In Proceedings of the 27th International Conference on Very Large Data Bases. 149--158."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/567752.567763"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2009.02.002"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/237661.237689"},{"key":"e_1_2_1_6_1","series-title":"Lecture Notes in Computer Science","volume-title":"Towards a language for the fully generic queries","author":"Beeri C.","unstructured":"Beeri , C. , Milo , T. , and Ta-Shma , P. 1997. Towards a language for the fully generic queries . In Database Programming Languages, S. Cluet and R. Hull, Eds. Lecture Notes in Computer Science . Springer , 239--259. Beeri, C., Milo, T., and Ta-Shma, P. 1997. Towards a language for the fully generic queries. In Database Programming Languages, S. Cluet and R. Hull, Eds. Lecture Notes in Computer Science. Springer, 239--259."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Blackburn P. de Rijke M. and Venema Y. 2001. Modal Logic. Cambridge University Press.   Blackburn P. de Rijke M. and Venema Y. 2001. Modal Logic. Cambridge University Press.","DOI":"10.1017\/CBO9781107050884"},{"key":"e_1_2_1_8_1","volume-title":"Eds","author":"Blackburn P.","year":"2007","unstructured":"Blackburn , P. , van Benthem , J. , and Wolter , F. , Eds . 2007 . Handbook of Modal Logic. Elsevier . Blackburn, P., van Benthem, J., and Wolter, F., Eds. 2007. Handbook of Modal Logic. Elsevier."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90032-X"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1323293.1294281"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases. 367--378","author":"Dittrich J.-P.","year":"2006","unstructured":"Dittrich , J.-P. , and Vaz Salles , M. 2006 . iDM: A unified and versatile data model for personal dataspace management . In Proceedings of the 32nd International Conference on Very Large Data Bases. 367--378 . Dittrich, J.-P., and Vaz Salles, M. 2006. iDM: A unified and versatile data model for personal dataspace management. In Proceedings of the 32nd International Conference on Very Large Data Bases. 367--378."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247487"},{"key":"e_1_2_1_13_1","volume-title":"Informal Proceedings.","author":"Fletcher G. H. L.","year":"2008","unstructured":"Fletcher , G. H. L. 2008 . An algebra for basic graph patterns. Logic in Databases (LID) . Informal Proceedings. Fletcher, G. H. L. 2008. An algebra for basic graph patterns. Logic in Databases (LID). Informal Proceedings."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514919"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376708"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Goranko V. and Otto M. 2007. Model theory of modal logic. in Handbook of Hoda Logic P. Blackburn J. van Benthem and F. Wolter Ed. Chapter 5.  Goranko V. and Otto M. 2007. Model theory of modal logic. in Handbook of Hoda Logic P. Blackburn J. van Benthem and F. Wolter Ed. Chapter 5.","DOI":"10.1016\/S1570-2464(07)80008-5"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055573"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142352"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247483"},{"key":"e_1_2_1_20_1","volume-title":"Advances in Data Management '95","author":"Jain M.","year":"1995","unstructured":"Jain , M. , Mendhekar , A. , and Van Gucht , D. 1995 . A uniform data model for relational data and meta-data query processing . In Advances in Data Management '95 , Tata McGraw-Hill, 146--165. Jain, M., Mendhekar, A., and Van Gucht, D. 1995. A uniform data model for relational data and meta-data query processing. In Advances in Data Management '95, Tata McGraw-Hill, 146--165."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-005-5789-8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.011"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/141356.141389"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Manning C. Raghavan P. and Sh\u00fctze H. 2008. Introduction to Information Retrieval. Cambridge University Press.   Manning C. Raghavan P. and Sh\u00fctze H. 2008. Introduction to Information Retrieval. Cambridge University Press.","DOI":"10.1017\/CBO9780511809071"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376726"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88564-1_5"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559917"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31839-2_15"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007652"},{"volume-title":"Principles of Database and Knowledge-Base Systems","author":"Ullman J.","key":"e_1_2_1_31_1","unstructured":"Ullman , J. 1989. Principles of Database and Knowledge-Base Systems . Vol. II . Computer Science Press . Ullman, J. 1989. Principles of Database and Knowledge-Base Systems. Vol. II. Computer Science Press."},{"key":"e_1_2_1_32_1","unstructured":"W3C. 2004. RDF primer. W3C Recommendation.  W3C. 2004. RDF primer. W3C Recommendation."},{"key":"e_1_2_1_33_1","unstructured":"W3C. 2008. SPARQL query language for RDF. W3C Recommendation.  W3C. 2008. SPARQL query language for RDF. W3C Recommendation."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1862919.1862925","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1862919.1862925","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:14:51Z","timestamp":1750281291000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1862919.1862925"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,12]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.1145\/1862919.1862925"],"URL":"https:\/\/doi.org\/10.1145\/1862919.1862925","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2010,10,12]]},"assertion":[{"value":"2009-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-10-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}