{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T17:54:26Z","timestamp":1759341266745,"version":"3.41.0"},"reference-count":89,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2018,8,29]],"date-time":"2018-08-29T00:00:00Z","timestamp":1535500800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR JCJC France","award":["12-JS02-007-01"],"award-info":[{"award-number":["12-JS02-007-01"]}]},{"name":"President of Russian Federation","award":["MK- 5379.2018.1"],"award-info":[{"award-number":["MK- 5379.2018.1"]}]},{"name":"EPSRC UK","award":["EP\/M012670"],"award-info":[{"award-number":["EP\/M012670"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"<jats:p>\n            We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language\n            <jats:italic>OWL\u00a02\u00a0QL<\/jats:italic>\n            : the succinctness problem for first-order rewritings of ontology-mediated queries (OMQs) and the complexity problem for OMQ answering. We classify OMQs according to the shape of their conjunctive queries (treewidth, the number of leaves) and the existential depth of their ontologies. For each of these classes, we determine the combined complexity of OMQ answering and whether all OMQs in the class have polynomial-size first-order, positive existential, and nonrecursive datalog rewritings. We obtain the succinctness results using hypergraph programs, a new computational model for Boolean functions, which makes it possible to connect the size of OMQ rewritings and circuit complexity.\n          <\/jats:p>","DOI":"10.1145\/3191832","type":"journal-article","created":{"date-parts":[[2018,8,30]],"date-time":"2018-08-30T13:45:11Z","timestamp":1535636711000},"page":"1-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Ontology-Mediated Queries"],"prefix":"10.1145","volume":"65","author":[{"given":"Meghyn","family":"Bienvenu","sequence":"first","affiliation":[{"name":"CNRS 8 University of Montpellier, Montpellier CEDEX 5, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stanislav","family":"Kikot","sequence":"additional","affiliation":[{"name":"Birkbeck, University of London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roman","family":"Kontchakov","sequence":"additional","affiliation":[{"name":"Birkbeck, University of London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir V.","family":"Podolskii","sequence":"additional","affiliation":[{"name":"Steklov Mathematical Institute of the Russian Academy of Sciences, Moscow and National Research University Higher School of Economics, Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Zakharyaschev","sequence":"additional","affiliation":[{"name":"Birkbeck, University of London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,8,29]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley.   S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8191-1"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1583"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1734953.1734954"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90002-4"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/772062.772068"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.03.002"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034791"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.38"},{"volume-title":"Proc. of the 23nd Int. Joint Conf. on Artificial Intelligence (IJCAI\u201913)","author":"Bienvenu M.","key":"e_1_2_2_12_1","unstructured":"M. Bienvenu , C. Lutz , and F. Wolter . 2013. First-order rewritability of atomic queries in horn description logics . In Proc. of the 23nd Int. Joint Conf. on Artificial Intelligence (IJCAI\u201913) . IJCAI\/AAAI, 754--760. M. Bienvenu, C. Lutz, and F. Wolter. 2013. First-order rewritability of atomic queries in horn description logics. In Proc. of the 23nd Int. Joint Conf. on Artificial Intelligence (IJCAI\u201913). IJCAI\/AAAI, 754--760."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2831071.2831079"},{"volume-title":"Proc. of the 23nd Int. Joint Conf. on Artificial Intelligence (IJCAI\u201913)","author":"Bienvenu M.","key":"e_1_2_2_14_1","unstructured":"M. Bienvenu , M. Ortiz , M. Simkus , and G. Xiao . 2013. Tractable queries for lightweight description logics . In Proc. of the 23nd Int. Joint Conf. on Artificial Intelligence (IJCAI\u201913) . IJCAI\/AAAI, 768--774. M. Bienvenu, M. Ortiz, M. Simkus, and G. Xiao. 2013. Tractable queries for lightweight description logics. In Proc. of the 23nd Int. Joint Conf. on Artificial Intelligence (IJCAI\u201913). IJCAI\/AAAI, 768--774."},{"key":"e_1_2_2_15_1","volume-title":"Proc. of the 28th Int. Workshop on Description Logics, DL 2015 (CEUR)","volume":"1350","author":"Bienvenu M.","unstructured":"M. Bienvenu and R. Rosati . 2015. Query-based comparison of OBDA specifications . In Proc. of the 28th Int. Workshop on Description Logics, DL 2015 (CEUR) , Vol. 1350 . CEUR-WS, 55--66. M. Bienvenu and R. Rosati. 2015. Query-based comparison of OBDA specifications. In Proc. of the 28th Int. Workshop on Description Logics, DL 2015 (CEUR), Vol. 1350. CEUR-WS, 55--66."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661643"},{"volume-title":"Proc. of the AAAI Conf. on Artificial Intelligence (AAAI\u201916)","author":"Botoeva E.","key":"e_1_2_2_17_1","unstructured":"E. Botoeva , D. Calvanese , V. Santarelli , D. F. Savo , A. Solimando , and G. Xiao . 2016. Beyond OWL 2 QL in OBDA: Rewritings and approximations . In Proc. of the AAAI Conf. on Artificial Intelligence (AAAI\u201916) . E. Botoeva, D. Calvanese, V. Santarelli, D. F. Savo, A. Solimando, and G. Xiao. 2016. Beyond OWL 2 QL in OBDA: Rewritings and approximations. In Proc. of the AAAI Conf. on Artificial Intelligence (AAAI\u201916)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/302970"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2500991"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2012.03.001"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.08.002"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2019470.2019475"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-007-9078-x"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"key":"e_1_2_2_26_1","volume-title":"Proc. of the 23rd Int. Conf. on Automated Deduction (CADE-23)","volume":"6803","author":"Chortaras A.","unstructured":"A. Chortaras , D. Trivela , and G. Stamou . 2011. Optimized query rewriting for OWL 2 QL . In Proc. of the 23rd Int. Conf. on Automated Deduction (CADE-23) (LNCS), Vol. 6803 . Springer, 192--206. A. Chortaras, D. Trivela, and G. Stamou. 2011. Optimized query rewriting for OWL 2 QL. In Proc. of the 23rd Int. Conf. on Automated Deduction (CADE-23) (LNCS), Vol. 6803. Springer, 192--206."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32925-8_8"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11915-1_11"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/321623.321625"},{"volume-title":"Proc. of the 26th AAAI Conf. on Artificial Intelligence (AAAI\u201912)","author":"Eiter T.","key":"e_1_2_2_30_1","unstructured":"T. Eiter , M. Ortiz , M. \u0160imkus , T.-K. Tran , and G. Xiao . 2012. Query rewriting for Horn-SHIQ plus rules . In Proc. of the 26th AAAI Conf. on Artificial Intelligence (AAAI\u201912) . AAAI, 726--733. T. Eiter, M. Ortiz, M. \u0160imkus, T.-K. Tran, and G. Xiao. 2012. Query rewriting for Horn-SHIQ plus rules. In Proc. of the 26th AAAI Conf. on Artificial Intelligence (AAAI\u201912). AAAI, 726--733."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90154-1"},{"key":"e_1_2_2_32_1","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer.   J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2015.82"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.04.004"},{"key":"e_1_2_2_35_1","volume-title":"Proc. of the 26th Int. Coll. on Automata, Languages 8 Programming (ICALP\u201999)","volume":"1644","author":"Gottlob G.","unstructured":"G. Gottlob , N. Leone , and F. Scarcello . 1999. Computing LOGCFL certificates . In Proc. of the 26th Int. Coll. on Automata, Languages 8 Programming (ICALP\u201999) (LNCS), Vol. 1644 . Springer, 361--371. G. Gottlob, N. Leone, and F. Scarcello. 1999. Computing LOGCFL certificates. In Proc. of the 26th Int. Coll. on Automata, Languages 8 Programming (ICALP\u201999) (LNCS), Vol. 1644. Springer, 361--371."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"volume-title":"Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI\u201915)","author":"Gottlob G.","key":"e_1_2_2_37_1","unstructured":"G. Gottlob , M. Manna , and A. Pieris . 2015. Polynomial rewritings for linear existential rules . In Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI\u201915) . AAAI, 2992--2998. G. Gottlob, M. Manna, and A. Pieris. 2015. Polynomial rewritings for linear existential rules. In Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI\u201915). AAAI, 2992--2998."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767965"},{"volume-title":"Proc. of the 13th Int. Conf. on Principles of Knowledge Representation 8 Reasoning (KR\u201912)","author":"Gottlob G.","key":"e_1_2_2_39_1","unstructured":"G. Gottlob and T. Schwentick . 2012. Rewriting ontological queries into small nonrecursive Datalog programs . In Proc. of the 13th Int. Conf. on Principles of Knowledge Representation 8 Reasoning (KR\u201912) . AAAI, 254--263. G. Gottlob and T. Schwentick. 2012. Rewriting ontological queries into small nonrecursive Datalog programs. In Proc. of the 13th Int. Conf. on Principles of Knowledge Representation 8 Reasoning (KR\u201912). AAAI, 254--263."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202025"},{"volume-title":"Proc. of the London Mathematical Society Symp. on Boolean Function Complexity","author":"Grigni M.","key":"e_1_2_2_41_1","unstructured":"M. Grigni and M. Sipser . 1992. Monotone complexity . In Proc. of the London Mathematical Society Symp. on Boolean Function Complexity . Cambridge University Press, 57--75. M. Grigni and M. Sipser. 1992. Monotone complexity. In Proc. of the London Mathematical Society Symp. on Boolean Function Complexity. Cambridge University Press, 57--75."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380867"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2015.06.002"},{"volume-title":"Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI\u201915)","author":"Hansen P.","key":"e_1_2_2_44_1","unstructured":"P. Hansen , C. Lutz , I. Seylan , and F. Wolter . 2015. Efficient query rewriting in the description logic EL and beyond . In Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI\u201915) . AAAI, 3034--3040. P. Hansen, C. Lutz, I. Seylan, and F. Wolter. 2015. Efficient query rewriting in the description logic EL and beyond. In Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI\u201915). AAAI, 3034--3040."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"volume-title":"Handbook of Theoretical Computer Science","author":"Johnson D. S.","key":"e_1_2_2_47_1","unstructured":"D. S. Johnson . 1990. A catalog of complexity classes . In Handbook of Theoretical Computer Science , Volume A: Algorithms and Complexity (A). 67-- 161 . D. S. Johnson. 1990. A catalog of complexity classes. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A). 67--161."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/588111.588138"},{"volume-title":"Boolean Function Complexity \u2014 Advances and Frontiers. Algorithms and Combinatorics","author":"Jukna S.","key":"e_1_2_2_49_1","unstructured":"S. Jukna . 2012. Boolean Function Complexity \u2014 Advances and Frontiers. Algorithms and Combinatorics , Vol. 27 . Springer . S. Jukna. 2012. Boolean Function Complexity \u2014 Advances and Frontiers. Algorithms and Combinatorics, Vol. 27. Springer."},{"volume-title":"Proc. of the 28th AAAI Conference on Artificial Intelligence (AAAI\u201914)","author":"Kaminski M.","key":"e_1_2_2_50_1","unstructured":"M. Kaminski , Y. Nenov , and B. Cuenca Grau . 2014. Datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning . In Proc. of the 28th AAAI Conference on Artificial Intelligence (AAAI\u201914) . AAAI, 1077--1083. M. Kaminski, Y. Nenov, and B. Cuenca Grau. 2014. Datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning. In Proc. of the 28th AAAI Conference on Artificial Intelligence (AAAI\u201914). AAAI, 1077--1083."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62265"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2017.05.005"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2017.02.001"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_26"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603131"},{"key":"e_1_2_2_56_1","volume-title":"Proc. of the 24th Int. Workshop on Description Logics (DL\u201911)","volume":"745","author":"Kikot S.","unstructured":"S. Kikot , R. Kontchakov , and M. Zakharyaschev . 2011. On (in)tractability of OBDA with OWL 2 QL . In Proc. of the 24th Int. Workshop on Description Logics (DL\u201911) , Vol. 745 . CEUR-WS, 224--234. S. Kikot, R. Kontchakov, and M. Zakharyaschev. 2011. On (in)tractability of OBDA with OWL 2 QL. In Proc. of the 24th Int. Workshop on Description Logics (DL\u201911), Vol. 745. CEUR-WS, 224--234."},{"volume-title":"Proc. of the 13th Int. Conf. on Principles of Knowledge Representation 8 Reasoning (KR\u201912)","author":"Kikot S.","key":"e_1_2_2_57_1","unstructured":"S. Kikot , R. Kontchakov , and M. Zakharyaschev . 2012. Conjunctive query answering with OWL 2 QL . In Proc. of the 13th Int. Conf. on Principles of Knowledge Representation 8 Reasoning (KR\u201912) . AAAI, 275--285. S. Kikot, R. Kontchakov, and M. Zakharyaschev. 2012. Conjunctive query answering with OWL 2 QL. In Proc. of the 13th Int. Conf. on Principles of Knowledge Representation 8 Reasoning (KR\u201912). AAAI, 275--285."},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/2832581.2832682"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-140153"},{"volume-title":"Proc. of the 12th Int. Conf.\u00a0 on Principles of Knowledge Representation 8 Reasoning (KR\u201910)","author":"Kontchakov R.","key":"e_1_2_2_60_1","unstructured":"R. Kontchakov , C. Lutz , D. Toman , F. Wolter , and M. Zakharyaschev . 2010. The combined approach to query answering in DL-Lite . In Proc. of the 12th Int. Conf.\u00a0 on Principles of Knowledge Representation 8 Reasoning (KR\u201910) . AAAI, 247--257. R. Kontchakov, C. Lutz, D. Toman, F. Wolter, and M. Zakharyaschev. 2010. The combined approach to query answering in DL-Lite. In Proc. of the 12th Int. Conf.\u00a0 on Principles of Knowledge Representation 8 Reasoning (KR\u201910). AAAI, 247--257."},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11964-9_35"},{"volume-title":"Proc. of the 29th AAAI Conf. on Artificial Intelligence (AAAI\u201915)","author":"Kostylev E. V.","key":"e_1_2_2_62_1","unstructured":"E. V. Kostylev , J. L. Reutter , and D. Vrgo . 2015. XPath for DL ontologies . In Proc. of the 29th AAAI Conf. on Artificial Intelligence (AAAI\u201915) . AAAI, 1525--1531. E. V. Kostylev, J. L. Reutter, and D. Vrgo. 2015. XPath for DL ontologies. In Proc. of the 29th AAAI Conf. on Artificial Intelligence (AAAI\u201915). AAAI, 1525--1531."},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25007-6_13"},{"volume-title":"Elements of Finite Model Theory","author":"Libkin L.","key":"e_1_2_2_64_1","unstructured":"L. Libkin . 2004. Elements of Finite Model Theory . Springer . L. Libkin. 2004. Elements of Finite Model Theory. Springer."},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71070-7_16"},{"volume-title":"Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI\u201911)","author":"Lutz C.","key":"e_1_2_2_66_1","unstructured":"C. Lutz , R. Piro , and F. Wolter . 2011. Description logic TBoxes: Model-theoretic characterizations and rewritability . In Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI\u201911) . IJCAI\/AAAI, 983--988. C. Lutz, R. Piro, and F. Wolter. 2011. Description logic TBoxes: Model-theoretic characterizations and rewritability. In Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI\u201911). IJCAI\/AAAI, 983--988."},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41335-3_20"},{"key":"e_1_2_2_68_1","volume-title":"Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI\u201909). 2070","author":"Lutz C.","year":"2075","unstructured":"C. Lutz , D. Toman , and F. Wolter . 2009. Conjunctive query answering in the description logic EL using a relational database system . In Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI\u201909). 2070 -- 2075 . C. Lutz, D. Toman, and F. Wolter. 2009. Conjunctive query answering in the description logic EL using a relational database system. In Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI\u201909). 2070--2075."},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11964-9_36"},{"key":"e_1_2_2_70_1","volume-title":"Proc. of the 22nd Int. Workshop on Description Logics, DL 2009 (CEUR)","volume":"477","author":"P\u00e9rez-Urbina H.","unstructured":"H. P\u00e9rez-Urbina , B. Motik , and I. Horrocks . 2009. A comparison of query rewriting techniques for DL-lite . In Proc. of the 22nd Int. Workshop on Description Logics, DL 2009 (CEUR) , Vol. 477 . CEUR-WS. H. P\u00e9rez-Urbina, B. Motik, and I. Horrocks. 2009. A comparison of query rewriting techniques for DL-lite. In Proc. of the 22nd Int. Workshop on Description Logics, DL 2009 (CEUR), Vol. 477. CEUR-WS."},{"key":"e_1_2_2_71_1","volume-title":"Proc. of the Joint Workshop on Scalable and High-Performance Semantic Web Systems (SSWS+HPCSW 2012)","volume":"943","author":"P\u00e9rez-Urbina H.","unstructured":"H. P\u00e9rez-Urbina , E. Rodr\u00edguez-D\u00edaz , M. Grove , G. Konstantinidis , and E. Sirin . 2012. Evaluation of query rewriting approaches for OWL 2 . In Proc. of the Joint Workshop on Scalable and High-Performance Semantic Web Systems (SSWS+HPCSW 2012) (CEUR), Vol. 943 . CEUR-WS. H. P\u00e9rez-Urbina, E. Rodr\u00edguez-D\u00edaz, M. Grove, G. Konstantinidis, and E. Sirin. 2012. Evaluation of query rewriting approaches for OWL 2. In Proc. of the Joint Workshop on Scalable and High-Performance Semantic Web Systems (SSWS+HPCSW 2012) (CEUR), Vol. 943. CEUR-WS."},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/1793934.1793939"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146684"},{"key":"e_1_2_2_74_1","first-page":"798","article-title":"Lower bounds for the monotone complexity of some boolean functions","volume":"281","author":"Razborov A.","year":"1985","unstructured":"A. Razborov . 1985 . Lower bounds for the monotone complexity of some boolean functions . Dokl. Akad. Nauk SSSR 281 , 4 (1985), 798 -- 801 . A. Razborov. 1985. Lower bounds for the monotone complexity of some boolean functions. Dokl. Akad. Nauk SSSR 281, 4 (1985), 798--801.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.5555\/647895.740448"},{"volume-title":"Proc. of the 13th Int. Conf. on Principles of Knowledge Representation 8 Reasoning (KR\u201912)","author":"Rodriguez-Muro M.","key":"e_1_2_2_76_1","unstructured":"M. Rodriguez-Muro and D. Calvanese . 2012. High performance query answering over DL-Lite ontologies . In Proc. of the 13th Int. Conf. on Principles of Knowledge Representation 8 Reasoning (KR\u201912) . AAAI, 308--318. M. Rodriguez-Muro and D. Calvanese. 2012. High performance query answering over DL-Lite ontologies. In Proc. of the 13th Int. Conf. on Principles of Knowledge Representation 8 Reasoning (KR\u201912). AAAI, 308--318."},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41335-3_35"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_12"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30284-8_31"},{"volume-title":"Proc. of the 12th Int. Conf. on Principles of Knowledge Representation 8 Reasoning (KR\u201910)","author":"Rosati R.","key":"e_1_2_2_80_1","unstructured":"R. Rosati and A. Almatelli . 2010. Improving query answering over DL-Lite ontologies . In Proc. of the 12th Int. Conf. on Principles of Knowledge Representation 8 Reasoning (KR\u201910) . AAAI, 290--300. R. Rosati and A. Almatelli. 2010. Improving query answering over DL-Lite ontologies. In Proc. of the 12th Int. Conf. on Principles of Knowledge Representation 8 Reasoning (KR\u201910). AAAI, 290--300."},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11964-9_34"},{"key":"e_1_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322083"},{"key":"e_1_2_2_83_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00299636"},{"key":"e_1_2_2_84_1","volume-title":"Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI\u201913)","author":"Thomazo M.","year":"2013","unstructured":"M. Thomazo . 2013 . Compact rewritings for existential rules . In Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI\u201913) . IJCAI\/AAAI, 1125--1131. M. Thomazo. 2013. Compact rewritings for existential rules. In Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI\u201913). IJCAI\/AAAI, 1125--1131."},{"key":"e_1_2_2_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_2_86_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90020-6"},{"volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"Vollmer H.","key":"e_1_2_2_87_1","unstructured":"H. Vollmer . 1999. Introduction to Circuit Complexity: A Uniform Approach . Springer . H. Vollmer. 1999. Introduction to Circuit Complexity: A Uniform Approach. Springer."},{"key":"e_1_2_2_88_1","volume-title":"Proc. of the 7th Int. Conf. on Very Large Data Bases (VLDB\u201981)","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis . 1981 . Algorithms for acyclic database schemes . In Proc. of the 7th Int. Conf. on Very Large Data Bases (VLDB\u201981) . IEEE Computer Society, 82--94. M. Yannakakis. 1981. Algorithms for acyclic database schemes. In Proc. of the 7th Int. Conf. on Very Large Data Bases (VLDB\u201981). IEEE Computer Society, 82--94."},{"key":"e_1_2_2_89_1","doi-asserted-by":"publisher","DOI":"10.5555\/2910557.2910566"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3191832","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3191832","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:43Z","timestamp":1750213603000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3191832"}},"subtitle":["Combined Complexity and Succinctness of Rewritings via Circuit Complexity"],"short-title":[],"issued":{"date-parts":[[2018,8,29]]},"references-count":89,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3191832"],"URL":"https:\/\/doi.org\/10.1145\/3191832","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2018,8,29]]},"assertion":[{"value":"2016-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}