{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T09:06:19Z","timestamp":1712307979375},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>\n            Many data-intensive applications have to query a database that involves sequences of sets of objects. It is not uncommon that the order of the sets in such a sequence does not affect the result of the query. Such queries are called\n            <jats:italic>symmetric.<\/jats:italic>\n            In this paper, the authors wish to initiate research on symmetric queries.\n          <\/jats:p>\n          <jats:p>Thereto, a data model is proposed in which a binary relation between objects and set names encodes set membership. On this data model, two query languages are introduced, QuineCALC and SyCALC. They are correlated in a manner that is made precise with the symmetric Boolean functions of Quine, respectively symmetric relational functions, on sequences of sets of given length. The latter do not only involve the Boolean operations union, intersection, and complement, but also projection and Cartesian product. Quine's characterization of symmetric Boolean functions in terms of incidence information is generalized to QuineCALC queries. In the process, an incidence-based normal form for QuineCALC queries is proposed.<\/jats:p>\n          <jats:p>\n            Inspired by these desirable incidence-related properties of QuineCALC queries,\n            <jats:italic>counting-only<\/jats:italic>\n            queries are introduced as SyCALC queries for which the result only depends on incidence information. Counting-only queries are then characterized as quantified Boolean combinations of QuineCALC queries, and a normal form is proposed for them as well. Finally, it is shown that, while it is undecidable whether a SyCALC query is counting-only, it is decidable whether a counting-only query is a QuineCALC query.\n          <\/jats:p>","DOI":"10.14778\/2732219.2732222","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"25-36","source":"Crossref","is-referenced-by-count":3,"title":["An approach towards the study of symmetric queries"],"prefix":"10.14778","volume":"7","author":[{"given":"Marc","family":"Gyssens","sequence":"first","affiliation":[{"name":"Hasselt University, Transnational Univ. of Limburg, Hasselt, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Paredaens","sequence":"additional","affiliation":[{"name":"University of Antwerp, Antwerp, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk","family":"Van Gucht","sequence":"additional","affiliation":[{"name":"Indiana University, Bloomington, Indiana"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jef","family":"Wijsen","sequence":"additional","affiliation":[{"name":"University of Mons, Mons, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuqing","family":"Wu","sequence":"additional","affiliation":[{"name":"Indiana University, Bloomington, Indiana"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01354881"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170072"},{"key":"e_1_2_1_3_1","volume-title":"SAT","author":"Audemard G.","year":"2004","unstructured":"G. Audemard , B. Mazure , and L. Sais . Dealing with symmetries in quantified Boolean formulas . In SAT , 2004 . G. Audemard, B. Mazure, and L. Sais. Dealing with symmetries in quantified Boolean formulas. In SAT, 2004."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.851743"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247602"},{"key":"e_1_2_1_6_1","first-page":"137","volume-title":"OSDI","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . MapReduce: Simplified data processing on large clusters . In OSDI , pages 137 -- 150 . USENIX Association , 2004 . J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In OSDI, pages 137--150. USENIX Association, 2004."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.009"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2007.07.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-1949-9","volume-title":"Linear Algebra","author":"Lang S.","year":"1987","unstructured":"S. Lang . Linear Algebra : 3 rd Edition. Springer , 1987 . S. Lang. Linear Algebra: 3rd Edition. Springer, 1987.","edition":"3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1992.11995923"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_2_1_13_1","volume-title":"Selected Logic Papers","author":"Quine W. V.","year":"1995","unstructured":"W. V. Quine . Selected Logic Papers . Harvard University Press , 1995 . W. V. Quine. Selected Logic Papers. Harvard University Press, 1995."},{"key":"e_1_2_1_15_1","first-page":"269","volume":"3","author":"Thomas S. J.","year":"1986","unstructured":"S. J. Thomas and P. C. Fischer . Nested relational structures. Advances in Computing Research , 3 : 269 -- 307 , 1986 . S. J. Thomas and P. C. Fischer. Nested relational structures. Advances in Computing Research, 3: 269--307, 1986.","journal-title":"Nested relational structures. Advances in Computing Research"},{"key":"e_1_2_1_16_1","volume-title":"Volume I","author":"van der Waerden B. L.","year":"1970","unstructured":"B. L. van der Waerden . Algebra : Volume I . Frederick Ungar Publishing Co. , 1970 . B. L. van der Waerden. Algebra: Volume I. Frederick Ungar Publishing Co., 1970."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153853"},{"key":"e_1_2_1_18_1","unstructured":"World Wide Web Consortium (W3C). RDF current status. http:\/\/www.w3.org\/standards\/techs\/rdf#w3c_all.  World Wide Web Consortium (W3C). RDF current status. http:\/\/www.w3.org\/standards\/techs\/rdf#w3c_all."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732219.2732222","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:50:52Z","timestamp":1672221052000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732219.2732222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.14778\/2732219.2732222"],"URL":"https:\/\/doi.org\/10.14778\/2732219.2732222","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}