{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T04:17:41Z","timestamp":1726460261495},"reference-count":60,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2014,8,1]],"date-time":"2014-08-01T00:00:00Z","timestamp":1406851200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2018,8,1]],"date-time":"2018-08-01T00:00:00Z","timestamp":1533081600000},"content-version":"vor","delay-in-days":1461,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"publisher","award":["EP\/H051511","EP\/H05099X"],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002261","name":"Russian Foundation for Basic Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002261","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[2014,8]]},"DOI":"10.1016\/j.artint.2014.04.004","type":"journal-article","created":{"date-parts":[[2014,5,5]],"date-time":"2014-05-05T14:12:42Z","timestamp":1399299162000},"page":"42-59","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":41,"special_numbering":"C","title":["The price of query rewriting in ontology-based data access"],"prefix":"10.1016","volume":"213","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[]},{"given":"Stanislav","family":"Kikot","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-9349-9159","authenticated-orcid":false,"given":"Roman","family":"Kontchakov","sequence":"additional","affiliation":[]},{"given":"Vladimir","family":"Podolskii","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Zakharyaschev","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"year":"1995","series-title":"Foundations of Databases","author":"Abiteboul","key":"10.1016\/j.artint.2014.04.004_br0010"},{"issue":"1","key":"10.1016\/j.artint.2014.04.004_br0020","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","article-title":"The monotone circuit complexity of Boolean functions","volume":"7","author":"Alon","year":"1987","journal-title":"Combinatorica"},{"year":"2009","series-title":"Computational Complexity: A Modern Approach","author":"Arora","key":"10.1016\/j.artint.2014.04.004_br0030"},{"key":"10.1016\/j.artint.2014.04.004_br0040","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.2820","article-title":"The DL-Lite family and relations","volume":"36","author":"Artale","year":"2009","journal-title":"J. Artif. Intell. Res."},{"issue":"3","key":"10.1016\/j.artint.2014.04.004_br0050","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1145\/772062.772068","article-title":"Eliminating definitions and Skolem functions in first-order logic","volume":"4","author":"Avigad","year":"2003","journal-title":"ACM Trans. Comput. Log."},{"key":"10.1016\/j.artint.2014.04.004_br0060","series-title":"Proc. of the 21st Int. Joint Conf. on Artificial Intelligence","first-page":"677","article-title":"Extending decidable cases for rules with existential variables","author":"Baget","year":"2009"},{"issue":"9\u201310","key":"10.1016\/j.artint.2014.04.004_br0070","doi-asserted-by":"crossref","first-page":"1620","DOI":"10.1016\/j.artint.2011.03.002","article-title":"On rules with existential variables: walking the decidability line","volume":"175","author":"Baget","year":"2011","journal-title":"Artif. Intell."},{"key":"10.1016\/j.artint.2014.04.004_br0080","series-title":"Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence","first-page":"768","article-title":"Tractable queries for lightweight description logics","author":"Bienvenu","year":"2013"},{"key":"10.1016\/j.artint.2014.04.004_br0090","series-title":"Proc. of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems","first-page":"213","article-title":"Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP","author":"Bienvenu","year":"2013"},{"key":"10.1016\/j.artint.2014.04.004_br0100","series-title":"Proc. of the 23rd Annual Symposium on Foundations of Computer Science","first-page":"65","article-title":"Fast parallel matrix and gcd computations","author":"Borodin","year":"1982"},{"key":"10.1016\/j.artint.2014.04.004_br0110","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.websem.2012.03.001","article-title":"A general datalog-based framework for tractable query answering over ontologies","volume":"14","author":"Cal\u00ec","year":"2012","journal-title":"J. Web Semant."},{"issue":"1","key":"10.1016\/j.artint.2014.04.004_br0120","doi-asserted-by":"crossref","first-page":"554","DOI":"10.14778\/1920841.1920912","article-title":"Advanced processing for ontological queries","volume":"3","author":"Cal\u00ec","year":"2010","journal-title":"Proc. VLDB Endow."},{"key":"10.1016\/j.artint.2014.04.004_br0130","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.artint.2012.08.002","article-title":"Towards more expressive ontology languages: the query answering problem","volume":"193","author":"Cal\u00ec","year":"2012","journal-title":"Artif. Intell."},{"key":"10.1016\/j.artint.2014.04.004_br0140","series-title":"Proc. of the 20th Nat. Conf. on Artificial Intelligence","first-page":"602","article-title":"DL-Lite: tractable description logics for ontologies","author":"Calvanese","year":"2005"},{"key":"10.1016\/j.artint.2014.04.004_br0150","series-title":"Proc. of the 10th Int. Conf. on the Principles of Knowledge Representation and Reasoning","first-page":"260","article-title":"Data complexity of query answering in description logics","author":"Calvanese","year":"2006"},{"issue":"3","key":"10.1016\/j.artint.2014.04.004_br0160","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s10817-007-9078-x","article-title":"Tractable reasoning and efficient query answering in description logics: the DL-Lite family","volume":"39","author":"Calvanese","year":"2007","journal-title":"J. Autom. Reason."},{"issue":"2","key":"10.1016\/j.artint.2014.04.004_br0170","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0304-3975(99)00220-0","article-title":"Conjunctive query containment revisited","volume":"239","author":"Chekuri","year":"2000","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.artint.2014.04.004_br0180","series-title":"Proc. of the 23rd Int. Conf. on Automated Deduction","first-page":"192","article-title":"Optimized query rewriting for OWL 2 QL","volume":"vol. 6803","author":"Chortaras","year":"2011"},{"key":"10.1016\/j.artint.2014.04.004_br0190","series-title":"Proc. of the 7th Int. Semantic Web Conf.","first-page":"403","article-title":"Scalable grounded conjunctive query evaluation over large and expressive knowledge bases","volume":"vol. 5318","author":"Dolby","year":"2008"},{"article-title":"Query rewriting for Horn-SHIQ plus rules","year":"2012","series-title":"Proc. of the 26th AAAI Conf. on Artificial Intelligence","author":"Eiter","key":"10.1016\/j.artint.2014.04.004_br0200"},{"article-title":"Parameterized Complexity Theory","year":"2006","author":"Flum","key":"10.1016\/j.artint.2014.04.004_br0210"},{"year":"1979","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","key":"10.1016\/j.artint.2014.04.004_br0220"},{"article-title":"Polynomial combined rewritings for existential rules","year":"2014","series-title":"Proc. of the 14th Int. Conf. on the Principles of Knowledge Representation and Reasoning","author":"Gottlob","key":"10.1016\/j.artint.2014.04.004_br0230"},{"key":"10.1016\/j.artint.2014.04.004_br0240","unstructured":"G. Gottlob, G. Orsi, A. Pieris Query rewriting and optimization for ontological databases, arXiv:1405.2848 [cs.DB], 12 May 2014."},{"key":"10.1016\/j.artint.2014.04.004_br0250","series-title":"Proc. of the 27th Int. Conf. on Data Engineering","first-page":"2","article-title":"Ontological queries: rewriting and optimization","author":"Gottlob","year":"2011"},{"key":"10.1016\/j.artint.2014.04.004_br0260","series-title":"Proc. of the 13th Int. Conf. on the Principles of Knowledge Representation and Reasoning","first-page":"254","article-title":"Rewriting ontological queries into small nonrecursive datalog programs","author":"Gottlob","year":"2012"},{"key":"10.1016\/j.artint.2014.04.004_br0270","series-title":"Proc. of the 33rd ACM SIGACT Symposium on Theory of Computing","first-page":"657","article-title":"When is the evaluation of conjunctive queries tractable?","author":"Grohe","year":"2001"},{"key":"10.1016\/j.artint.2014.04.004_br0280","series-title":"Ontology Management, Semantic Web, Semantic Web Services, and Business Applications","first-page":"89","article-title":"Ontology reasoning with large data repositories","volume":"vol. 7","author":"Heymans","year":"2008"},{"year":"2012","series-title":"Boolean Function Complexity: Advances and Frontiers","author":"Jukna","key":"10.1016\/j.artint.2014.04.004_br0290"},{"key":"10.1016\/j.artint.2014.04.004_br0300","series-title":"Proc. of the 26th Int. Workshop on Description Logics","first-page":"316","article-title":"Query rewriting over shallow ontologies","volume":"vol. 1014","author":"Kikot","year":"2013"},{"author":"Kikot","key":"10.1016\/j.artint.2014.04.004_br0310"},{"key":"10.1016\/j.artint.2014.04.004_br0320","series-title":"Proc. of the 39th Int. Colloquium on Automata, Languages, and Programming, Part II","first-page":"263","article-title":"Exponential lower bounds and separation for query rewriting","volume":"vol. 7392","author":"Kikot","year":"2012"},{"key":"10.1016\/j.artint.2014.04.004_br0330","series-title":"Proc. of the 13th Int. Conf. on the Principles of Knowledge Representation and Reasoning","first-page":"275","article-title":"Conjunctive query answering with OWL 2 QL","author":"Kikot","year":"2012"},{"key":"10.1016\/j.artint.2014.04.004_br0340","series-title":"Proc. of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems","first-page":"205","article-title":"Conjunctive-query containment and constraint satisfaction","author":"Kolaitis","year":"1998"},{"key":"10.1016\/j.artint.2014.04.004_br0350","series-title":"Proc. of the 6th Int. Conf. on Web Reasoning and Rule Systems","first-page":"122","article-title":"A sound and complete backward chaining algorithm for existential rules","volume":"vol. 7497","author":"K\u00f6nig","year":"2012"},{"key":"10.1016\/j.artint.2014.04.004_br0360","series-title":"Proc. of the 7th Int. Conf. on Web Reasoning and Rule Systems","first-page":"123","article-title":"On the exploration of the query rewriting space with existential rules","volume":"vol. 7994","author":"K\u00f6nig","year":"2013"},{"article-title":"The combined approach to query answering in DL-Lite","year":"2010","series-title":"Proc. of the 10th Int. Conf. on the Principles of Knowledge Representation and Reasoning","author":"Kontchakov","key":"10.1016\/j.artint.2014.04.004_br0370"},{"key":"10.1016\/j.artint.2014.04.004_br0380","series-title":"Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence","first-page":"2656","article-title":"The combined approach to ontology-based data access","author":"Kontchakov","year":"2011"},{"key":"10.1016\/j.artint.2014.04.004_br0390","series-title":"Proc. of the 12th Int. Semantic Web Conf.","first-page":"314","article-title":"The combined approach to OBDA: taming role hierarchies using filters","volume":"vol. 8218","author":"Lutz","year":"2013"},{"key":"10.1016\/j.artint.2014.04.004_br0400","series-title":"Proc. of the 21st Int. Joint Conf. on Artificial Intelligence","first-page":"2070","article-title":"Conjunctive query answering in the description logic EL using a relational database system","author":"Lutz","year":"2009"},{"key":"10.1016\/j.artint.2014.04.004_br0410","series-title":"Proc. of the 9th Int. Conf. on Extending Database Technology","first-page":"441","article-title":"Projection pushing revisited","volume":"vol. 2992","author":"McMahan","year":"2004"},{"key":"10.1016\/j.artint.2014.04.004_br0420","series-title":"Proc. of the 12th Annual Symposium on Switching and Automata Theory","first-page":"188","article-title":"Economy of description by automata, grammars, and formal systems","author":"Meyer","year":"1971"},{"issue":"11","key":"10.1016\/j.artint.2014.04.004_br0430","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.14778\/3402707.3402737","article-title":"Optimizing query answering under ontological constraints","volume":"4","author":"Orsi","year":"2011","journal-title":"Proc. VLDB Endow."},{"key":"10.1016\/j.artint.2014.04.004_br0440","series-title":"Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence","first-page":"1039","article-title":"Query answering in the Horn fragments of the description logics SHOIQ and SROIQ","author":"Ortiz","year":"2011"},{"key":"10.1016\/j.artint.2014.04.004_br0450","series-title":"Proc. of the 22nd Int. Workshop on Description Logics","article-title":"A comparison of query rewriting techniques for DL-Lite","volume":"vol. 477","author":"P\u00e9rez-Urbina","year":"2009"},{"key":"10.1016\/j.artint.2014.04.004_br0460","series-title":"Proc. of SSWS+HPCSW 2012","article-title":"Evaluation of query rewriting approaches for OWL 2","volume":"vol. 943","author":"P\u00e9rez-Urbina","year":"2012"},{"key":"10.1016\/j.artint.2014.04.004_br0470","first-page":"133","article-title":"Linking data to ontologies","volume":"X","author":"Poggi","year":"2008","journal-title":"J. Data Semant."},{"key":"10.1016\/j.artint.2014.04.004_br0480","series-title":"Proc. of the 38th Annual Symposium on Foundations of Computer Science","first-page":"234","article-title":"Separation of the monotone NC hierarchy","author":"Raz","year":"1997"},{"issue":"3","key":"10.1016\/j.artint.2014.04.004_br0490","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1145\/146637.146684","article-title":"Monotone circuits for matching require linear depth","volume":"39","author":"Raz","year":"1992","journal-title":"J. ACM"},{"issue":"4","key":"10.1016\/j.artint.2014.04.004_br0500","first-page":"798","article-title":"Lower bounds for the monotone complexity of some Boolean functions","volume":"281","author":"Razborov","year":"1985","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"10.1016\/j.artint.2014.04.004_br0510","series-title":"Proc. of the 12th Int. Semantic Web Conf.","first-page":"558","article-title":"Ontology-based data access: ontop of databases","volume":"vol. 8218","author":"Rodr\u00edguez-Muro","year":"2013"},{"key":"10.1016\/j.artint.2014.04.004_br0520","series-title":"Proc. of the 10th Int. Workshop on OWL: Experiences and Directions","article-title":"Ontop at work","volume":"vol. 1080","author":"Rodr\u00edguez-Muro","year":"2013"},{"key":"10.1016\/j.artint.2014.04.004_br0530","series-title":"Proc. of the 2007 Int. Workshop on Description Logics","article-title":"On conjunctive query answering in EL","volume":"vol. 250","author":"Rosati","year":"2007"},{"key":"10.1016\/j.artint.2014.04.004_br0540","series-title":"Proc. of the 9th Extended Semantic Web Conf.","first-page":"360","article-title":"Prexto: query rewriting under extensional constraints in DL-Lite","volume":"vol. 7295","author":"Rosati","year":"2012"},{"key":"10.1016\/j.artint.2014.04.004_br0550","series-title":"Proc. of the 10th Int. Conf. on the Principles of Knowledge Representation and Reasoning","first-page":"290","article-title":"Improving query answering over DL-Lite ontologies","author":"Rosati","year":"2010"},{"key":"10.1016\/j.artint.2014.04.004_br0560","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/1379759.1379763","article-title":"Homomorphism preservation theorems","volume":"55","author":"Rossman","year":"2008","journal-title":"J. ACM"},{"key":"10.1016\/j.artint.2014.04.004_br0570","series-title":"Proc. of the 4th Int. Conf. on Conceptual Structures","first-page":"248","article-title":"Sound and complete forward and backward chaining of graph rules","volume":"vol. 1115","author":"Salvat","year":"1996"},{"issue":"4","key":"10.1016\/j.artint.2014.04.004_br0580","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1093\/logcom\/4.4.337","article-title":"Logical description of monotone NP problems","volume":"4","author":"Stewart","year":"1994","journal-title":"J. Log. Comput."},{"key":"10.1016\/j.artint.2014.04.004_br0590","series-title":"Automation of Reasoning 2: Classical Papers on Computational Logic 1967\u20131970","first-page":"466","article-title":"On the complexity of derivation in propositional calculus","author":"Tseitin","year":"1983"},{"key":"10.1016\/j.artint.2014.04.004_br0600","series-title":"Proc. of the 7th Int. Conf. on Very Large Data Bases","first-page":"82","article-title":"Algorithms for acyclic database schemes","author":"Yannakakis","year":"1981"}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370214000459?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370214000459?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,8,18]],"date-time":"2020-08-18T22:48:03Z","timestamp":1597790883000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0004370214000459"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":60,"alternative-id":["S0004370214000459"],"URL":"https:\/\/doi.org\/10.1016\/j.artint.2014.04.004","relation":{},"ISSN":["0004-3702"],"issn-type":[{"type":"print","value":"0004-3702"}],"subject":[],"published":{"date-parts":[[2014,8]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"The price of query rewriting in ontology-based data access","name":"articletitle","label":"Article Title"},{"value":"Artificial Intelligence","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.artint.2014.04.004","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2014 Elsevier B.V. All rights reserved.","name":"copyright","label":"Copyright"}]}}