{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T10:44:39Z","timestamp":1761561879796},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>\n            A query class is traditionally considered tractable if there exists a polynomial-time (PTIME) algorithm to answer its queries. When it comes to big data, however, PTIME algorithms often become infeasible in practice. A traditional and effective approach to coping with this is to preprocess data off-line, so that queries in the class can be subsequently evaluated on the data efficiently. This paper aims to provide a formal foundation for this approach in terms of computational complexity. (1) We propose a set of \u03a0-tractable queries, denoted by \u03a0T\n            <jats:sub>Q<\/jats:sub>\n            <jats:sup>0<\/jats:sup>\n            , to characterize classes of queries that can be answered in parallel poly-logarithmic time (NC) after PTIME preprocessing. (2) We show that several natural query classes are \u03a0-tractable and are feasible on big data. (3) We also study a set \u03a0T\n            <jats:sub>Q<\/jats:sub>\n            of query classes that can be effectively converted to \u03a0-tractable queries by refactorizing its data and queries for preprocessing. We introduce a form of NC reductions to characterize such conversions. (4) We show that a natural query class is complete for \u03a0T\n            <jats:sub>Q<\/jats:sub>\n            . (5) We also show that \u03a0T\n            <jats:sub>Q<\/jats:sub>\n            <jats:sup>0<\/jats:sup>\n            \u2282 P unless P = NC, i.e., the set \u03a0T\n            <jats:sub>Q<\/jats:sub>\n            <jats:sup>0<\/jats:sup>\n            of all \u03a0-tractable queries is properly contained in the set P of all PTIME queries. Nonetheless, \u03a0T\n            <jats:sub>Q<\/jats:sub>\n            = P, i.e., all PTIME query classes can be made \u03a0-tractable via proper refactorizations. This work is a step towards understanding the tractability of queries in the context of big data.\n          <\/jats:p>","DOI":"10.14778\/2536360.2536368","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"685-696","source":"Crossref","is-referenced-by-count":23,"title":["Making queries tractable on big data with preprocessing"],"prefix":"10.14778","volume":"6","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"Informatics, University of Edinburgh &amp; RCBD and SKLSDE Lab, Beihang University"}]},{"given":"Floris","family":"Geerts","sequence":"additional","affiliation":[{"name":"University of Antwerp"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University &amp; transnational University of Limburg"}]}],"member":"320","published-online":{"date-parts":[[2013,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases","author":"Abiteboul S.","year":"1995","unstructured":"S. Abiteboul , R. Hull , and V. Vianu . Foundations of Databases . Addison-Wesley , 1995 . S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995."},{"key":"e_1_2_1_2_1","volume-title":"EDBT","author":"Afrati F. N.","year":"2011","unstructured":"F. N. Afrati , V. R. Borkar , M. J. Carey , N. Polyzotis , and J. D. Ullman . Map-reduce extensions and recursive queries . In EDBT , 2011 . F. N. Afrati, V. R. Borkar, M. J. Carey, N. Polyzotis, and J. D. Ullman. Map-reduce extensions and recursive queries. In EDBT, 2011."},{"key":"e_1_2_1_3_1","volume-title":"EDBT","author":"Afrati F. N.","year":"2010","unstructured":"F. N. Afrati and J. D. Ullman . Optimizing joins in a map-reduce environment . In EDBT , 2010 . F. N. Afrati and J. D. Ullman. Optimizing joins in a map-reduce environment. In EDBT, 2010."},{"key":"e_1_2_1_4_1","volume-title":"EDBT","author":"Afrati F. N.","year":"2012","unstructured":"F. N. Afrati and J. D. Ullman . Transitive closure and recursive datalog implemented on clusters . In EDBT , 2012 . F. N. Afrati and J. D. Ullman. Transitive closure and recursive datalog implemented on clusters. In EDBT, 2012."},{"issue":"2","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","article-title":"Lowest common ancestors in trees and directed acyclic graphs","volume":"57","author":"Bender M. A.","year":"2005","unstructured":"M. A. Bender , M. Farach-Colton , G. Pemmasani , S. Skiena , and P. Sumazin . Lowest common ancestors in trees and directed acyclic graphs . J. Algorithms , 57 ( 2 ): 75 - 94 , 2005 . M. A. Bender, M. Farach-Colton, G. Pemmasani, S. Skiena, and P. Sumazin. Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms, 57(2):75-94, 2005.","journal-title":"J. Algorithms"},{"key":"e_1_2_1_6_1","volume-title":"WWW","author":"Boldi P.","year":"2011","unstructured":"P. Boldi , M. Rosa , M. Santini , and S. Vigna . Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks . In WWW , 2011 . P. Boldi, M. Rosa, M. Santini, and S. Vigna. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In WWW, 2011."},{"key":"e_1_2_1_7_1","volume-title":"EDBT","author":"Borkar V. R.","year":"2012","unstructured":"V. R. Borkar , M. J. Carey , and C. Li . Inside \"big data management\": ogres, onions, or parfaits ? In EDBT , 2012 . V. R. Borkar, M. J. Carey, and C. Li. Inside \"big data management\": ogres, onions, or parfaits? In EDBT, 2012."},{"issue":"2","key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1006\/inco.2001.3043","article-title":"Pre-processing of intractable problems","volume":"176","author":"Cadoli M.","year":"2002","unstructured":"M. Cadoli , F. M. Donini , P. Liberatore , and M. Schaerf . Pre-processing of intractable problems . Inf. Comput. , 176 ( 2 ): 89 - 120 , 2002 . M. Cadoli, F. M. Donini, P. Liberatore, and M. Schaerf. Pre-processing of intractable problems. Inf. Comput., 176(2):89-120, 2002.","journal-title":"Inf. Comput."},{"key":"e_1_2_1_9_1","volume-title":"KDD","author":"Chierichetti F.","year":"2009","unstructured":"F. Chierichetti , R. Kumar , S. Lattanzi , M. Mitzenmacher , A. Panconesi , and P. Raghavan . On compressing social networks . In KDD , 2009 . F. Chierichetti, R. Kumar, S. Lattanzi, M. Mitzenmacher, A. Panconesi, and P. Raghavan. On compressing social networks. In KDD, 2009."},{"issue":"11","key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/240455.240477","article-title":"A practical model of parallel computation","volume":"39","author":"Culler D. E.","year":"1996","unstructured":"D. E. Culler , R. M. Karp , D. A. Patterson , A. Sahay , E. E. Santos , K. E. Schauser , R. Subramonian , and T. von Eicken . Logp : A practical model of parallel computation . Commun. ACM , 39 ( 11 ): 78 - 85 , 1996 . D. E. Culler, R. M. Karp, D. A. Patterson, A. Sahay, E. E. Santos, K. E. Schauser, R. Subramonian, and T. von Eicken. Logp: A practical model of parallel computation. Commun. ACM, 39(11):78-85, 1996.","journal-title":"Commun. ACM"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-3-642-16367-8_5","volume-title":"Property Testing","author":"Czumaj A.","year":"2010","unstructured":"A. Czumaj and C. Sohler . Sublinear-time algorithms . In Property Testing , pages 41 - 64 , 2010 . A. Czumaj and C. Sohler. Sublinear-time algorithms. In Property Testing, pages 41-64, 2010."},{"key":"e_1_2_1_12_1","volume-title":"MapReduce: Simplified data processing on large clusters. Commun. ACM, 51(1)","author":"Dean J.","year":"2008","unstructured":"J. Dean and S. Ghemawat . MapReduce: Simplified data processing on large clusters. Commun. ACM, 51(1) , 2008 . J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. Commun. ACM, 51(1), 2008."},{"key":"e_1_2_1_13_1","first-page":"185","volume-title":"SPAA","author":"Dorrigiv R.","year":"2008","unstructured":"R. Dorrigiv , A. L\u00f3pez-Ortiz , and A. Salinger . Optimal speedup on a low-degree multi-core parallel architecture (Lo-PRAM) . In SPAA , pages 185 - 187 , 2008 . R. Dorrigiv, A. L\u00f3pez-Ortiz, and A. Salinger. Optimal speedup on a low-degree multi-core parallel architecture (Lo-PRAM). In SPAA, pages 185-187, 2008."},{"issue":"4","key":"e_1_2_1_14_1","first-page":"614","article-title":"Optimal aggregation algorithms for middleware","volume":"66","author":"Fagin R.","year":"2003","unstructured":"R. Fagin , A. Lotem , and M. Naor . Optimal aggregation algorithms for middleware . JCSS , 66 ( 4 ): 614 - 656 , 2003 . R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. JCSS, 66(4):614-656, 2003.","journal-title":"JCSS"},{"key":"e_1_2_1_15_1","volume-title":"SIGMOD","author":"Fan W.","year":"2011","unstructured":"W. Fan , J. Li , Z. Tan , X. Wang , and Y. Wu . Incremental graph pattern matching . In SIGMOD , 2011 . W. Fan, J. Li, Z. Tan, X. Wang, and Y. Wu. Incremental graph pattern matching. In SIGMOD, 2011."},{"key":"e_1_2_1_16_1","first-page":"157","volume-title":"SIGMOD","author":"Fan W.","year":"2012","unstructured":"W. Fan , J. Li , X. Wang , and Y. Wu . Query preserving graph compression . In SIGMOD , pages 157 - 168 , 2012 . W. Fan, J. Li, X. Wang, and Y. Wu. Query preserving graph compression. In SIGMOD, pages 157-168, 2012."},{"issue":"2","key":"e_1_2_1_17_1","first-page":"261","article-title":"Clique partitions, graph compression and speeding-up algorithms","volume":"51","author":"Feder T.","year":"1995","unstructured":"T. Feder and R. Motwani . Clique partitions, graph compression and speeding-up algorithms . JCSS , 51 ( 2 ): 261 - 272 , 1995 . T. Feder and R. Motwani. Clique partitions, graph compression and speeding-up algorithms. JCSS, 51(2):261-272, 1995.","journal-title":"JCSS"},{"issue":"2","key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/090779759","article-title":"Space-efficient preprocessing schemes for range minimum queries on static arrays","volume":"40","author":"Fischer J.","year":"2011","unstructured":"J. Fischer and V. Heun . Space-efficient preprocessing schemes for range minimum queries on static arrays . SICOMP , 40 ( 2 ): 465 - 492 , 2011 . J. Fischer and V. Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays. SICOMP, 40(2):465-492, 2011.","journal-title":"SICOMP"},{"key":"e_1_2_1_19_1","volume-title":"Parameterized Complexity Theory","author":"Flum J.","year":"2006","unstructured":"J. Flum and M. Grohe . Parameterized Complexity Theory . Springer , 2006 . J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006."},{"key":"e_1_2_1_20_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M.","year":"1979","unstructured":"M. Garey and D. Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman and Company , 1979 . M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P-Completeness Theory","author":"Greenlaw R.","year":"1995","unstructured":"R. Greenlaw , H. J. Hoover , and W. L. Ruzzo . Limits to Parallel Computation: P-Completeness Theory . Oxford University Press , 1995 . R. Greenlaw, H. J. Hoover, and W. L. Ruzzo. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, 1995."},{"key":"e_1_2_1_22_1","first-page":"267","volume-title":"LICS","author":"Grohe M.","year":"2008","unstructured":"M. Grohe . The quest for a logic capturing ptime . In LICS , pages 267 - 271 , 2008 . M. Grohe. The quest for a logic capturing ptime. In LICS, pages 267-271, 2008."},{"issue":"4","key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/s007780100054","article-title":"Answering queries using views: A survey","volume":"10","author":"Halevy A. Y.","year":"2001","unstructured":"A. Y. Halevy . Answering queries using views: A survey . VLDB J. , 10 ( 4 ): 270 - 294 , 2001 . A. Y. Halevy. Answering queries using views: A survey. VLDB J., 10(4):270-294, 2001.","journal-title":"VLDB J."},{"issue":"5","key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"1667","DOI":"10.1137\/060668092","article-title":"On the compressibility of NP instances and cryptographic applications","volume":"39","author":"Harnik D.","year":"2010","unstructured":"D. Harnik and M. Naor . On the compressibility of NP instances and cryptographic applications . SICOMP , 39 ( 5 ): 1667 - 1713 , 2010 . D. Harnik and M. Naor. On the compressibility of NP instances and cryptographic applications. SICOMP, 39(5):1667-1713, 2010.","journal-title":"SICOMP"},{"issue":"1","key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/1860702.1860704","article-title":"The declarative imperative: experiences and conjectures in distributed logic","volume":"39","author":"Hellerstein J. M.","year":"2010","unstructured":"J. M. Hellerstein . The declarative imperative: experiences and conjectures in distributed logic . SIGMOD Record , 39 ( 1 ): 5 - 19 , 2010 . J. M. Hellerstein. The declarative imperative: experiences and conjectures in distributed logic. SIGMOD Record, 39(1):5-19, 2010.","journal-title":"SIGMOD Record"},{"key":"e_1_2_1_26_1","volume-title":"Handbook of Theoretical Computer Science","author":"Johnson D. S.","year":"1990","unstructured":"D. S. Johnson . A catalog of complexity classes . In Handbook of Theoretical Computer Science , Volume A: Algorithms and Complexity (A), pages 67- 161 . The MIT Press , 1990 . D. S. Johnson. A catalog of complexity classes. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), pages 67-161. The MIT Press, 1990."},{"issue":"3","key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1145\/243439.243447","article-title":"An introduction to partial evaluation","volume":"28","author":"Jones N. D.","year":"1996","unstructured":"N. D. Jones . An introduction to partial evaluation . ACM Comput. Surv. , 28 ( 3 ): 480 - 503 , 1996 . N. D. Jones. An introduction to partial evaluation. ACM Comput. Surv., 28(3):480-503, 1996.","journal-title":"ACM Comput. Surv."},{"key":"e_1_2_1_28_1","first-page":"938","volume-title":"SODA","author":"Karloff H. J.","year":"2010","unstructured":"H. J. Karloff , S. Suri , and S. Vassilvitskii . A model of computation for MapReduce . In SODA , pages 938 - 948 , 2010 . H. J. Karloff, S. Suri, and S. Vassilvitskii. A model of computation for MapReduce. In SODA, pages 938-948, 2010."},{"key":"e_1_2_1_29_1","first-page":"223","volume-title":"PODS","author":"Koutris P.","year":"2011","unstructured":"P. Koutris and D. Suciu . Parallel evaluation of conjunctive queries . In PODS , pages 223 - 234 , 2011 . P. Koutris and D. Suciu. Parallel evaluation of conjunctive queries. In PODS, pages 223-234, 2011."},{"key":"e_1_2_1_30_1","volume-title":"PODS","author":"Lenzerini M.","year":"2002","unstructured":"M. Lenzerini . Data integration : A theoretical perspective . In PODS , 2002 . M. Lenzerini. Data integration: A theoretical perspective. In PODS, 2002."},{"key":"e_1_2_1_31_1","volume-title":"KDD","author":"Maserrat H.","year":"2010","unstructured":"H. Maserrat and J. Pei . Neighbor query friendly compression of social networks . In KDD , 2010 . H. Maserrat and J. Pei. Neighbor query friendly compression of social networks. In KDD, 2010."},{"key":"e_1_2_1_32_1","volume-title":"SIGMOD","author":"Navlakha S.","year":"2008","unstructured":"S. Navlakha , R. Rastogi , and N. Shrivastava . Graph summarization with bounded error . In SIGMOD , 2008 . S. Navlakha, R. Rastogi, and N. Shrivastava. Graph summarization with bounded error. In SIGMOD, 2008."},{"key":"e_1_2_1_33_1","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994","unstructured":"C. H. Papadimitriou . Computational Complexity . Addison-Wesley , 1994 . C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"e_1_2_1_34_1","volume-title":"Database Management Systems","author":"Ramakrishnan R.","year":"2000","unstructured":"R. Ramakrishnan and J. Gehrke . Database Management Systems . McGraw-Hill Higher Education , 2000 . R. Ramakrishnan and J. Gehrke. Database Management Systems. McGraw-Hill Higher Education, 2000."},{"key":"e_1_2_1_35_1","volume-title":"On the computational complexity of dynamic graph problems. TCS, 158(1-2)","author":"Ramalingam G.","year":"1996","unstructured":"G. Ramalingam and T. Reps . On the computational complexity of dynamic graph problems. TCS, 158(1-2) , 1996 . G. Ramalingam and T. Reps. On the computational complexity of dynamic graph problems. TCS, 158(1-2), 1996."},{"issue":"2","key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1561\/0400000029","article-title":"Algorithmic and analysis techniques in property testing","volume":"5","author":"Ron D.","year":"2010","unstructured":"D. Ron . Algorithmic and analysis techniques in property testing . Foundations and Trends in Theoretical Computer Science , 5 ( 2 ): 73 - 205 , 2010 . D. Ron. Algorithmic and analysis techniques in property testing. Foundations and Trends in Theoretical Computer Science, 5(2):73-205, 2010.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_2_1_37_1","volume-title":"FSTTCS","author":"Saha D.","year":"2007","unstructured":"D. Saha . An incremental bisimulation algorithm . In FSTTCS , 2007 . D. Saha. An incremental bisimulation algorithm. In FSTTCS, 2007."},{"key":"e_1_2_1_38_1","unstructured":"G. Santos. SSD ranking: The fastest solid state drives. http:\/\/www.fastestssd.com\/featured\/ssd-rankings-the-fastest-solid-state-drives\/#pcie Oct 2012.  G. Santos. SSD ranking: The fastest solid state drives. http:\/\/www.fastestssd.com\/featured\/ssd-rankings-the-fastest-solid-state-drives\/#pcie Oct 2012."},{"issue":"2","key":"e_1_2_1_39_1","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1006\/jcss.1997.1525","article-title":"A query language for NC","volume":"55","author":"Suciu D.","year":"1997","unstructured":"D. Suciu and V. Tannen . A query language for NC . J. Comput. Syst. Sci. , 55 ( 2 ): 299 - 321 , 1997 . D. Suciu and V. Tannen. A query language for NC. J. Comput. Syst. Sci., 55(2):299-321, 1997.","journal-title":"J. Comput. Syst. Sci."},{"issue":"8","key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/79173.79181","article-title":"A bridging model for parallel computation","volume":"33","author":"Valiant L. G.","year":"1990","unstructured":"L. G. Valiant . A bridging model for parallel computation . Commun. ACM , 33 ( 8 ): 103 - 111 , 1990 . L. G. Valiant. A bridging model for parallel computation. Commun. ACM, 33(8):103-111, 1990.","journal-title":"Commun. ACM"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536360.2536368","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:51:55Z","timestamp":1672221115000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536360.2536368"}},"subtitle":["through the eyes of complexity theory"],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":40,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["10.14778\/2536360.2536368"],"URL":"https:\/\/doi.org\/10.14778\/2536360.2536368","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,7]]}}}