{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T19:38:19Z","timestamp":1703187499062},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,8]]},"abstract":"<jats:p>\n            A query\n            <jats:italic>Q<\/jats:italic>\n            is said to be\n            <jats:italic>effectively bounded<\/jats:italic>\n            if for all datasets\n            <jats:italic>D<\/jats:italic>\n            , there exists a subset\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>\n              <jats:italic>Q<\/jats:italic>\n            <\/jats:sub>\n            of\n            <jats:italic>D<\/jats:italic>\n            such that\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            ) =\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>\n              <jats:italic>Q<\/jats:italic>\n            <\/jats:sub>\n            ), and the size of\n            <jats:italic>DQ<\/jats:italic>\n            and time for fetching\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>\n              <jats:italic>Q<\/jats:italic>\n            <\/jats:sub>\n            are\n            <jats:italic>independent of<\/jats:italic>\n            the size of\n            <jats:italic>D<\/jats:italic>\n            . The need for studying such queries is evident, since it allows us to compute\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            ) by accessing a bounded dataset\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>\n              <jats:italic>Q<\/jats:italic>\n            <\/jats:sub>\n            ,\n            <jats:italic>regardless of<\/jats:italic>\n            how big\n            <jats:italic>D<\/jats:italic>\n            is. This paper investigates effectively bounded conjunctive queries (SPC) under an access schema\n            <jats:italic>A<\/jats:italic>\n            , which specifies indices and cardinality constraints commonly used. We provide characterizations (sufficient and necessary conditions) for determining whether an SPC query\n            <jats:italic>Q<\/jats:italic>\n            is effectively bounded under\n            <jats:italic>A<\/jats:italic>\n            . We study several problems for deciding whether\n            <jats:italic>Q<\/jats:italic>\n            is bounded, and if not, for identifying a minimum set of parameters of\n            <jats:italic>Q<\/jats:italic>\n            to instantiate and make\n            <jats:italic>Q<\/jats:italic>\n            bounded. We show that these problems range from quadratic-time to NP-complete, and develop efficient (heuristic) algorithms for them. We also provide an algorithm that, given an effectively bounded SPC query\n            <jats:italic>Q<\/jats:italic>\n            and an access schema\n            <jats:italic>A<\/jats:italic>\n            , generates a query plan for evaluating\n            <jats:italic>Q<\/jats:italic>\n            by accessing a bounded amount of data in any (possibly big) dataset. We experimentally verify that our algorithms substantially reduce the cost of query evaluation.\n          <\/jats:p>","DOI":"10.14778\/2732977.2732996","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"1231-1242","source":"Crossref","is-referenced-by-count":18,"title":["Bounded conjunctive queries"],"prefix":"10.14778","volume":"7","author":[{"given":"Yang","family":"Cao","sequence":"first","affiliation":[{"name":"University of Edinburgh and Beihang University"}]},{"given":"Wenfei","family":"Fan","sequence":"additional","affiliation":[{"name":"University of Edinburgh and Beihang University"}]},{"given":"Tianyu","family":"Wo","sequence":"additional","affiliation":[{"name":"Beihang University"}]},{"given":"Wenyuan","family":"Yu","sequence":"additional","affiliation":[{"name":"Facebook Inc."}]}],"member":"320","published-online":{"date-parts":[[2014,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/data.gov.uk\/dataset\/road-accidents-safety-data.  http:\/\/data.gov.uk\/dataset\/road-accidents-safety-data."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/data.gov.uk\/dataset\/naptan.  http:\/\/data.gov.uk\/dataset\/naptan."},{"key":"e_1_2_1_3_1","unstructured":"http:\/\/data.gov.uk\/dataset\/anonymised_mot_test.  http:\/\/data.gov.uk\/dataset\/anonymised_mot_test."},{"key":"e_1_2_1_4_1","unstructured":"http:\/\/www.tpc.org\/tpch\/.  http:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_2_1_5_1","unstructured":"full. http:\/\/homepages.inf.ed.ac.uk\/s1165433\/bounded.pdf.  full. http:\/\/homepages.inf.ed.ac.uk\/s1165433\/bounded.pdf."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304207"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2078331.2078334"},{"key":"e_1_2_1_10_1","volume-title":"CIDR","author":"Armbrust M.","year":"2009","unstructured":"M. Armbrust , A. Fox , D. A. Patterson , N. Lanham , B. Trushkowsky , J. Trutna , and H. Oh . SCADS: Scale-independent storage for social computing applications . In CIDR , 2009 . M. Armbrust, A. Fox, D. A. Patterson, N. Lanham, B. Trushkowsky, J. Trutna, and H. Oh. SCADS: Scale-independent storage for social computing applications. In CIDR, 2009."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465333"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/554706"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872822"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448522"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.008"},{"key":"e_1_2_1_17_1","volume-title":"KDD","author":"Ester M.","year":"1996","unstructured":"M. Ester , H.-P. Kriegel , J. Sander , and X. Xu . A density-based algorithm for discovering clusters in large spatial databases with noise . In KDD , 1996 . M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD, 1996."},{"key":"e_1_2_1_18_1","unstructured":"Facebook. http:\/\/newsroom.fb.com.  Facebook. http:\/\/newsroom.fb.com."},{"key":"e_1_2_1_19_1","volume-title":"Constraints on the number of photos, friends and tags. https:\/\/www.facebook.com\/help {\/227794810567981, \/community\/question\/?id=364005057055660}","year":"2014","unstructured":"Facebook. Constraints on the number of photos, friends and tags. https:\/\/www.facebook.com\/help {\/227794810567981, \/community\/question\/?id=364005057055660} , 2014 . Facebook. Constraints on the number of photos, friends and tags. https:\/\/www.facebook.com\/help {\/227794810567981, \/community\/question\/?id=364005057055660}, 2014."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594551"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536368"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564746"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559804"},{"key":"e_1_2_1_24_1","volume-title":"VLDB","author":"Ioannidis Y. E.","year":"1999","unstructured":"Y. E. Ioannidis and V. Poosala . Histogram-based approximation of set-valued query-answers . In VLDB , 1999 . Y. E. Ioannidis and V. Poosala. Histogram-based approximation of set-valued query-answers. In VLDB, 1999."},{"key":"e_1_2_1_25_1","volume-title":"VLDB","author":"Jagadish H. V.","year":"2009","unstructured":"H. V. Jagadish , N. Koudas , S. Muthukrishnan , V. Poosala , K. C. Sevcik , and T. Suel . Optimal histograms with quality guarantees . In VLDB , 2009 . H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. C. Sevcik, and T. Suel. Optimal histograms with quality guarantees. In VLDB, 2009."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90013-7"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316801"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0085-6"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516408"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732977.2732996","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:22:47Z","timestamp":1672226567000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732977.2732996"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":29,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.14778\/2732977.2732996"],"URL":"https:\/\/doi.org\/10.14778\/2732977.2732996","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,8]]}}}