{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,26]],"date-time":"2025-12-26T11:32:36Z","timestamp":1766748756290},"publisher-location":"Berlin, Heidelberg","reference-count":100,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642331572"},{"type":"electronic","value":"9783642331589"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33158-9_1","type":"book-chapter","created":{"date-parts":[[2012,8,18]],"date-time":"2012-08-18T09:54:23Z","timestamp":1345283663000},"page":"1-53","source":"Crossref","is-referenced-by-count":20,"title":["Reasoning and Query Answering in Description Logics"],"prefix":"10.1007","author":[{"given":"Magdalena","family":"Ortiz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mantas","family":"\u0160imkus","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","unstructured":"Abiteboul, S., Buneman, P., Suciu, D.: Data on the Web: from Relations to Semistructured Data and XML. Morgan Kaufmann (2000)"},{"key":"1_CR2","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison Wesley Publ. Co. (1995)"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Adali, S., Candan, K.S., Papakonstantinou, Y., Subrahmanian, V.S.: Query caching and optimization in distributed mediator systems. In: Proc. of the ACM SIGMOD Int. Conf. on Management of Data, pp. 137\u2013148 (1996)","DOI":"10.1145\/235968.233327"},{"key":"1_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.2820","volume":"36","author":"A. Artale","year":"2009","unstructured":"Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and relations. J. of Artificial Intelligence Research\u00a036, 1\u201369 (2009)","journal-title":"J. of Artificial Intelligence Research"},{"key":"1_CR5","unstructured":"Baader, F.: Augmenting concept languages by transitive closure of roles: An alternative to terminological cycles. In: Proc. of the 12th Int. Joint Conf. on Artificial Intelligence, IJCAI 1991 (1991)"},{"key":"1_CR6","unstructured":"Baader, F., Brandt, S., Lutz, C.: Pushing the \n                  \n                    \n                  \n                  $\\mathcal{EL}$\n                 envelope. In: Proc. of the 19th Int. Joint Conf. on Artificial Intelligence, IJCAI 2005 (2005)"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications, 2nd edn. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511711787"},{"key":"1_CR8","first-page":"1","volume":"57","author":"F. Baader","year":"2003","unstructured":"Baader, F., Hladik, J., Lutz, C., Wolter, F.: From tableaux to automata for description logics. Fundamenta Informaticae\u00a057, 1\u201333 (2003)","journal-title":"Fundamenta Informaticae"},{"key":"1_CR9","unstructured":"Bienvenu, M., Eiter, T., Lutz, C., Ortiz, M., \u0160imkus, M.: Query answering in the description logic \n                  \n                    \n                  \n                  $\\mathcal{S}$\n                . In: Proc.\u00a0of the 23rd International Workshop on Description Logics, DL 2010. CEUR-WS (2010)"},{"key":"1_CR10","unstructured":"Bienvenu, M., Ortiz, M., \u0160imkus, M.: Answering expressive path queries over lightweight DL knowledge bases. In: Description Logics (2012)"},{"issue":"3:11","key":"1_CR11","first-page":"1","volume":"4","author":"P. Bonatti","year":"2008","unstructured":"Bonatti, P., Lutz, C., Murano, A., Vardi, M.Y.: The complexity of enriched \u03bc-calculi. Logical Methods in Computer Science\u00a04(3:11), 1\u201327 (2008)","journal-title":"Logical Methods in Computer Science"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Buneman, P.: Semistructured data. In: Proc. of the 16th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS 1997, pp. 117\u2013121 (1997)","DOI":"10.1145\/263661.263675"},{"issue":"3","key":"1_CR13","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s10817-007-9078-x","volume":"39","author":"D. Calvanese","year":"2007","unstructured":"Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. of Automated Reasoning\u00a039(3), 385\u2013429 (2007)","journal-title":"J. of Automated Reasoning"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Calvanese, D., De Giacomo, G., Lenzerini, M.: On the decidability of query containment under constraints. In: Proc. of the 17th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS 1998, pp. 149\u2013158 (1998)","DOI":"10.1145\/275487.275504"},{"key":"1_CR15","unstructured":"Calvanese, D., De Giacomo, G., Lenzerini, M.: 2ATAs make DLs easy. In: CEUR Electronic Workshop Proceedings of Proc. of the 2002 Description Logic Workshop,DL\u00a02002, pp. 107\u2013118 (2002)"},{"issue":"3","key":"1_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1352582.1352590","volume":"9","author":"D. Calvanese","year":"2008","unstructured":"Calvanese, D., De Giacomo, G., Lenzerini, M.: Conjunctive query containment and answering under description logics constraints. ACM Trans. on Computational Logic\u00a09(3), 22.1\u201322.31 (2008)","journal-title":"ACM Trans. on Computational Logic"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Logical foundations of peer-to-peer data integration. In: Proc. of the 23rd ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS\u00a02004, pp. 241\u2013251 (2004)","DOI":"10.1145\/1055558.1055593"},{"key":"1_CR18","unstructured":"Calvanese, D., De Giacomo, G., Lenzerini, M., Vardi, M.Y.: Rewriting regular expressions in semi-structured data. In: Proc. of ICDT 1999 Workshop on Query Processing for Semi-Structured Data and Non-Standard Data Formats (1999)"},{"key":"1_CR19","unstructured":"Calvanese, D., De Giacomo, G., Lenzerini, M., Vardi, M.Y.: Containment of conjunctive regular path queries with inverse. In: Proc.\u00a0of the Seventh International Conference on the Principles of Knowledge Representation and Reasoning (KR\u00a02006), pp. 176\u2013185 (2000)"},{"issue":"4","key":"1_CR20","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/959060.959076","volume":"32","author":"D. Calvanese","year":"2003","unstructured":"Calvanese, D., De Giacomo, G., Lenzerini, M., Vardi, M.Y.: Reasoning on regular path queries. SIGMOD Record\u00a032(4), 83\u201392 (2003)","journal-title":"SIGMOD Record"},{"issue":"1","key":"1_CR21","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.tcs.2004.10.031","volume":"336","author":"D. Calvanese","year":"2005","unstructured":"Calvanese, D., De Giacomo, G., Vardi, M.Y.: Decidable containment of recursive queries. Theoretical Computer Science\u00a0336(1), 33\u201356 (2005)","journal-title":"Theoretical Computer Science"},{"key":"1_CR22","unstructured":"Calvanese, D., Eiter, T., Ortiz, M.: Answering regular path queries in expressive description logics: An automata-theoretic approach. In: Proc.\u00a0of the 22nd AAAI Conference on Artificial Intelligence, AAAI\u00a02007, pp. 391\u2013396 (2007)"},{"key":"1_CR23","unstructured":"Calvanese, D., Eiter, T., Ortiz, M.: Regular path queries in expressive description logics with nominals. In: Boutilier, C. (ed.) Proc. of the 21st Int. Joint Conf. on Artificial Intelligence, IJCAI 2009, pp. 714\u2013720 (2009)"},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: Proc. of the 9th ACM Symp. on Theory of Computing, STOC 1977, pp. 77\u201390 (1977)","DOI":"10.1145\/800105.803397"},{"key":"1_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-642-22438-6_16","volume-title":"Automated Deduction \u2013 CADE-23","author":"A. Chortaras","year":"2011","unstructured":"Chortaras, A., Trivela, D., Stamou, G.: Optimized Query Rewriting for OWL 2 QL. In: Bj\u00f8rner, N., Sofronie-Stokkermans, V. (eds.) CADE 2011. LNCS, vol.\u00a06803, pp. 192\u2013206. Springer, Heidelberg (2011), \n                  \n                    http:\/\/dl.acm.org\/citation.cfm?id=2032266.2032282"},{"issue":"4","key":"1_CR26","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/j.websem.2008.05.001","volume":"6","author":"B. Cuenca Grau","year":"2008","unstructured":"Cuenca Grau, B., Horrocks, I., Motik, B., Parsia, B., Patel-Schneider, P., Sattler, U.: OWL\u00a02: The next step for OWL. Journal of Web Semantics\u00a06(4), 309\u2013322 (2008)","journal-title":"Journal of Web Semantics"},{"key":"1_CR27","unstructured":"De Giacomo, G.: Decidability of Class-Based Knowledge Representation Formalisms. Ph.D. thesis, Dipartimento di Informatica e Sistemistica, Universit\u00e0 di Roma \u201cLa Sapienza\u201d (1995)"},{"key":"1_CR28","unstructured":"De Giacomo, G., Lenzerini, M.: Boosting the correspondence between description logics and propositional dynamic logics. In: Proc. of the 12th Nat. Conf. on Artificial Intelligence, AAAI 1994, pp. 205\u2013212 (1994)"},{"key":"1_CR29","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/978-3-540-87803-2_15","volume-title":"Logics in Artificial Intelligence","author":"T. Eiter","year":"2008","unstructured":"Eiter, T., Gottlob, G., Ortiz, M., \u0160imkus, M.: Query answering in the description logic horn-\n                  \n                    \n                  \n                  $\\mathcal{SHIQ}$\n                . In: H\u00f6lldobler, S., Lutz, C., Wansing, H. (eds.) JELIA 2008. LNCS (LNAI), vol.\u00a05293, pp. 166\u2013179. Springer, Heidelberg (2008)"},{"key":"1_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-642-02261-6_3","volume-title":"Logic, Language, Information and Computation","author":"T. Eiter","year":"2009","unstructured":"Eiter, T., Lutz, C., Ortiz, M., \u0160imkus, M.: Query Answering in Description Logics: The Knots Approach. In: Ono, H., Kanazawa, M., de Queiroz, R. (eds.) WoLLIC 2009. LNCS, vol.\u00a05514, pp. 26\u201336. Springer, Heidelberg (2009)"},{"key":"1_CR31","unstructured":"Eiter, T., Lutz, C., Ortiz, M., \u0160imkus, M.: Query answering in description logics with transitive roles. In: Boutilier, C. (ed.) Proc. of the 21st Int. Joint Conf. on Artificial Intelligence, IJCAI\u00a02009, pp. 759\u2013764 (2009)"},{"issue":"1","key":"1_CR32","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jcss.2011.02.012","volume":"78","author":"T. Eiter","year":"2012","unstructured":"Eiter, T., Ortiz, M., Simkus, M.: Conjunctive query answering in the description logic SH using knots. J. Comput. Syst. Sci.\u00a078(1), 47\u201385 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR33","unstructured":"Eiter, T., Ortiz, M., \u0160imkus, M., Tran, T.K., Xiao, G.: Query rewriting for Horn-SHIQ plus rules. In: Proc.\u00a0of the 26th AAAI Conference on Artificial Intelligence, AAAI\u00a02012 (to appear, 2012)"},{"key":"1_CR34","unstructured":"Franconi, E.: Description logics for natural language processing. In: Working Notes of the AAAI Fall Symposium on \u201cKnowledge Representation for Natural Language Processing in Implemented Systems\u201d, pp. 37\u201344 (1994)"},{"key":"1_CR35","first-page":"162","volume-title":"Proc. of the Terminological Logic Users Workshop","author":"M. Gehrke","year":"1991","unstructured":"Gehrke, M., Burkert, G., Forster, P., Franconi, E.: Natural language processing and description logics. In: Peltason, C., von Luck, K., Kindermann, C. (eds.) Proc. of the Terminological Logic Users Workshop, pp. 162\u2013164. Department of Computer Science, Technische Universit\u00e4t Berlin (1991)"},{"key":"1_CR36","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1613\/jair.2372","volume":"31","author":"B. Glimm","year":"2008","unstructured":"Glimm, B., Horrocks, I., Lutz, C., Sattler, U.: Conjunctive query answering for the description logic \n                  \n                    \n                  \n                  $\\mathcal{SHIQ}$\n                . Journal of Artificial Intelligence Research\u00a031, 151\u2013198 (2008)","journal-title":"Journal of Artificial Intelligence Research"},{"key":"1_CR37","unstructured":"Glimm, B., Horrocks, I., Sattler, U.: Unions of conjunctive queries in SHOQ. In: Proc.\u00a0of the 11th International Conference on the Principles of Knowledge Representation and Reasoning (KR 2008), pp. 252\u2013262. AAAI Press\/The MIT Press (2008)"},{"key":"1_CR38","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/978-3-540-89439-1_28","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"B. Glimm","year":"2008","unstructured":"Glimm, B., Kazakov, Y.: Role Conjunctions in Expressive Description Logics. In: Cervesato, I., Veith, H., Voronkov, A. (eds.) LPAR 2008. LNCS (LNAI), vol.\u00a05330, pp. 391\u2013405. Springer, Heidelberg (2008)"},{"key":"1_CR39","unstructured":"Glimm, B., Kazakov, Y., Lutz, C.: Status QIO: An update. In: Proc.\u00a0of the 2009 Description Logic Workshop, DL\u00a02009. CEUR Workshop Proceedings, vol.\u00a0745 (2011)"},{"key":"1_CR40","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Orsi, G., Pieris, A.: Ontological queries: Rewriting and optimization. In: IEEE 27th International Conference on Data Engineering, ICDE, pp. 2\u201313 (April 2011)","DOI":"10.1109\/ICDE.2011.5767965"},{"key":"1_CR41","first-page":"54","volume-title":"Reasoning Web 2012","author":"G. Gottlob","year":"2012","unstructured":"Gottlob, G., Orsi, G., Pieris, A., \u0160imkus, M.: Datalog and its Extensions for the Semantic Web Databases. In: Eiter, T., Krennwallner, T. (eds.) Reasoning Web 2012, vol.\u00a07487, pp. 54\u201377. Springer, Heidelberg (2012)"},{"key":"1_CR42","unstructured":"Gottlob, G., Schwentick, T.: Rewriting ontological queries into small nonrecursive datalog programs. In: Rosati, R., Rudolph, S., Zakharyaschev, M. (eds.) Description Logics. CEUR Workshop Proceedings, vol.\u00a0745, CEUR-WS.org (2011)"},{"key":"1_CR43","first-page":"90","volume":"68","author":"E. Gr\u00e4del","year":"1999","unstructured":"Gr\u00e4del, E.: Why are modal logics so robustly decidable? Bulletin of the European Association for Theoretical Computer Science\u00a068, 90\u2013103 (1999)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"1_CR44","unstructured":"Gupta, A., Ullman, J.D.: Generalizing conjunctive query containment for view maintenance and integrity constraint verification (abstract). In: Workshop on Deductive Databases (In conjunction with JICSLP), Washington D.C. (USA), p. 195 (1992)"},{"key":"1_CR45","unstructured":"Hladik, J.: A tableau system for the description logic SHIO. In: Sattler, U. (ed.) IJCAR Doctoral Programme. CEUR Workshop Proceedings, vol.\u00a0106, CEUR-WS.org (2004)"},{"key":"1_CR46","doi-asserted-by":"crossref","unstructured":"Horrocks, I., Kutz, O., Sattler, U.: The irresistible \n                  \n                    \n                  \n                  $\\mathcal{SRIQ}$\n                . In: Proc. of the 1st Int. Workshop on OWL: Experiences and Directions, OWLED\u00a02005 (2005)","DOI":"10.1007\/11562931_1"},{"key":"1_CR47","unstructured":"Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible \n                  \n                    \n                  \n                  $\\mathcal{SROIQ}$\n                . In: Doherty, P., Mylopoulos, J., Welty, C.A. (eds.) Proc. of the 10th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR\u00a02006), pp. 57\u201367. AAAI Press (2006)"},{"key":"1_CR48","unstructured":"Horrocks, I., Rector, A., Goble, C.: A description logic based schema for the classification of medical data. In: CEUR Electronic Workshop Proceedings, Proc. of the 3rd Int. Workshop on Knowledge Representation Meets Databases, KRDB 1996, pp. 24\u201328 (1996), \n                  \n                    http:\/\/ceur-ws.org\/Vol-4\/"},{"issue":"3","key":"1_CR49","first-page":"239","volume":"8","author":"I. Horrocks","year":"2000","unstructured":"Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for very expressive description logics. J. of the Interest Group in Pure and Applied Logic\u00a08(3), 239\u2013264 (2000)","journal-title":"J. of the Interest Group in Pure and Applied Logic"},{"key":"1_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/10721959_39","volume-title":"Automated Deduction - CADE-17","author":"I. Horrocks","year":"2000","unstructured":"Horrocks, I., Sattler, U., Tobies, S.: Reasoning with Individuals for the Description Logic \n                  \n                    \n                  \n                  $\\mathcal{SHIQ}$\n                . In: McAllester, D. (ed.) CADE 2000. LNCS, vol.\u00a01831, pp. 482\u2013496. Springer, Heidelberg (2000)"},{"key":"1_CR51","unstructured":"Horrocks, I., Tessaris, S.: A conjunctive query language for description logic ABoxes. In: Proc. of the 17th Nat. Conf. on Artificial Intelligence, AAAI 2000, pp. 399\u2013404 (2000)"},{"key":"1_CR52","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-540-32275-7_2","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"U. Hustadt","year":"2005","unstructured":"Hustadt, U., Motik, B., Sattler, U.: A Decomposition Rule for Decision Procedures by Resolution-Based Calculi. In: Baader, F., Voronkov, A. (eds.) LPAR 2004. LNCS (LNAI), vol.\u00a03452, pp. 21\u201335. Springer, Heidelberg (2005)"},{"key":"1_CR53","unstructured":"Hustadt, U., Motik, B., Sattler, U.: Data complexity of reasoning in very expressive description logics. In: Proc. of the 19th Int. Joint Conf. on Artificial Intelligence, IJCAI 2005, pp. 466\u2013471 (2005)"},{"issue":"3","key":"1_CR54","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1137\/0218043","volume":"18","author":"N. Immerman","year":"1989","unstructured":"Immerman, N.: Expressibility and parallel complexity. SIAM J. Comput.\u00a018(3), 625\u2013638 (1989)","journal-title":"SIAM J. Comput."},{"key":"1_CR55","unstructured":"Kazakov, Y.: \n                  \n                    \n                  \n                  $\\mathcal{RIQ}$\n                 and \n                  \n                    \n                  \n                  $\\mathcal{SROIQ}$\n                 are harder than \n                  \n                    \n                  \n                  $\\mathcal{SHOIQ}$\n                . In: Proc.\u00a0of the Eleventh International Conference on the Principles of Knowledge Representation and Reasoning, KR 2008, pp. 274\u2013284 (2008)"},{"key":"1_CR56","unstructured":"Kikot, S., Kontchakov, R., Zakharyaschev, M.: On (in)tractability of OBDA with OWL 2 QL. In: Rosati, R., Rudolph, S., Zakharyaschev, M. (eds.) Description Logics. CEUR Workshop Proceedings, vol.\u00a0745, CEUR-WS.org (2011), \n                  \n                    http:\/\/dblp.uni-trier.de\/db\/conf\/dlog\/dlog2011.html#KikotKZ11"},{"key":"1_CR57","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-540-75560-9_25","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"A. Krisnadhi","year":"2007","unstructured":"Krisnadhi, A., Lutz, C.: Data Complexity in the \n                  \n                    \n                  \n                  $\\mathcal{EL}$\n                 Family of Description Logics. In: Dershowitz, N., Voronkov, A. (eds.) LPAR 2007. LNCS (LNAI), vol.\u00a04790, pp. 333\u2013347. Springer, Heidelberg (2007)"},{"key":"1_CR58","series-title":"LNCS","volume-title":"Reasoning Web 2012","author":"M. Kr\u00f6tzsch","year":"2012","unstructured":"Kr\u00f6tzsch, M.: OWL 2 profiles: An Introduction to Lightweight Ontology Languages. In: Eiter, T., Krennwallner, T. (eds.) Reasoning Web 2012. LNCS, vol.\u00a07487, Springer, Heidelberg (2012)"},{"key":"1_CR59","unstructured":"Kr\u00f6tzsch, M., Rudolph, S.: Conjunctive queries for \n                  \n                    \n                  \n                  $\\mathcal{EL}$\n                 with composition of roles. In: Proc.\u00a0of the 2007 Description Logic Workshop, DL\u00a02007. CEUR Electronic Workshop Proceedings, vol.\u00a0250 (2007), \n                  \n                    http:\/\/ceur-ws.org\/Vol-250\/"},{"key":"1_CR60","unstructured":"Kr\u00f6tzsch, M., Rudolph, S., Hitzler, P.: Complexity boundaries for Horn description logics. In: Proceedings of the 22nd AAAI Conference on Artificial Intelligence, AAAI 2007, pp. 452\u2013457. AAAI Press (2007)"},{"key":"1_CR61","doi-asserted-by":"crossref","unstructured":"Lenzerini, M.: Data integration: A theoretical perspective. In: Proc. of the 21st ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems, PODS\u00a02002, pp. 233\u2013246 (2002)","DOI":"10.1145\/543643.543644"},{"issue":"1-2","key":"1_CR62","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0004-3702(98)00048-4","volume":"104","author":"A.Y. Levy","year":"1998","unstructured":"Levy, A.Y., Rousset, M.C.: Combining Horn rules and description logics in CARIN. Artificial Intelligence\u00a0104(1-2), 165\u2013209 (1998)","journal-title":"Artificial Intelligence"},{"key":"1_CR63","unstructured":"Lutz, C., Toman, D., Wolter, F.: Conjunctive query answering in the description logic \n                  \n                    \n                  \n                  $\\mathcal{EL}$\n                 using a relational database system. In: Proc. of the 21st Int. Joint Conf. on Artificial Intelligence, IJCAI\u00a02009, pp. 2070\u20132075. AAAI Press (2009)"},{"key":"1_CR64","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48242-3_12","volume-title":"Logic Programming and Automated Reasoning","author":"C. Lutz","year":"1999","unstructured":"Lutz, C.: Complexity of Terminological Reasoning Revisited. In: Ganzinger, H., McAllester, D., Voronkov, A. (eds.) LPAR 1999. LNCS, vol.\u00a01705, pp. 181\u2013200. Springer, Heidelberg (1999)"},{"key":"1_CR65","unstructured":"Lutz, C.: Inverse roles make conjunctive queries hard. In: Proc.\u00a0of the 2007 Description Logic Workshop, DL\u00a02007. CEUR Electronic Workshop Proceedings, vol.\u00a0250, pp. 100\u2013111 (2007), \n                  \n                    http:\/\/ceur-ws.org\/Vol-250\/"},{"key":"1_CR66","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-540-71070-7_16","volume-title":"Automated Reasoning","author":"C. Lutz","year":"2008","unstructured":"Lutz, C.: The Complexity of Conjunctive Query Answering in Expressive Description Logics. In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008. LNCS (LNAI), vol.\u00a05195, pp. 179\u2013193. Springer, Heidelberg (2008)"},{"key":"1_CR67","unstructured":"Lutz, C.: Two upper bounds for conjunctive query answering in SHIQ. In: Baader, F., Lutz, C., Motik, B. (eds.) Description Logics. CEUR Workshop Proceedings, vol.\u00a0353, CEUR-WS.org (2008)"},{"key":"1_CR68","unstructured":"McGuinness, D.L.: Ontology-enhanced search for primary care medical literature. In: Proc. of the Int. Medical Informatics Association Working Group 6 \u2013 Conference on Natural Language Processing and Medical Concept Representation, IMIA 1999 (1999)"},{"key":"1_CR69","unstructured":"Motik, B.: Reasoning in Description Logics using Resolution and Deductive Databases. Ph.D. thesis, Univesit\u00e4t Karlsruhe (TH), Karlsruhe, Germany (January 2006)"},{"key":"1_CR70","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0004-3702(90)90087-G","volume":"43","author":"B. Nebel","year":"1990","unstructured":"Nebel, B.: Terminological reasoning is inherently intractable. Artificial Intelligence\u00a043, 235\u2013249 (1990)","journal-title":"Artificial Intelligence"},{"key":"1_CR71","unstructured":"N\u00e9meti, I.: Free algebras and decidability in algebraic logic. DSc. thesis, Mathematical Institute of The Hungarian Academy of Sciences, Budapest (1986)"},{"issue":"4","key":"1_CR72","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1145\/1041410.1041421","volume":"33","author":"N.F. Noy","year":"2004","unstructured":"Noy, N.F.: Semantic integration: A survey of ontology-based approaches. SIGMOD Record\u00a033(4), 65\u201370 (2004)","journal-title":"SIGMOD Record"},{"key":"1_CR73","unstructured":"Ortiz, M.: Query Answering in Expressive Description Logics: Techniques and Complexity Results. Ph.D. thesis, Vienna University of Technology (2010)"},{"key":"1_CR74","unstructured":"Ortiz, M., Calvanese, D., Eiter, T.: Characterizing data complexity for conjunctive query answering in expressive description logics. In: Proc. of the 21st Nat. Conf. on Artificial Intelligence, AAAI\u00a02006. AAAI Press (July 2006)"},{"issue":"1","key":"1_CR75","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s10817-008-9102-9","volume":"41","author":"M. Ortiz","year":"2008","unstructured":"Ortiz, M., Calvanese, D., Eiter, T.: Data complexity of query answering in expressive description logics via tableaux. J. of Automated Reasoning\u00a041(1), 61\u201398 (2008)","journal-title":"J. of Automated Reasoning"},{"key":"1_CR76","unstructured":"Ortiz, M., Rudolph, S., \u0160imkus, M.: Query answering is undecidable in DLs with regular expressions, inverses, nominals, and counting. Tech. Rep. INFSYS RR-1843-10-03, Institut f\u00fcr Informationssysteme, Technische Universit\u00e4t Wien, A-1040 Vienna, Austria (April 2010)"},{"key":"1_CR77","unstructured":"Ortiz, M., Rudolph, S., Simkus, M.: Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2. In: Lin, F., Sattler, U., Truszczynski, M. (eds.) KR 2010, AAAI Press (2010)"},{"key":"1_CR78","unstructured":"Ortiz, M., Rudolph, S., Simkus, M.: Query answering in the Horn fragments of the description logics SHOIQ and SROIQ. In: Walsh, T. (ed.) IJCAI, pp. 1039\u20131044. IJCAI\/AAAI (2011)"},{"key":"1_CR79","unstructured":"Ortiz, M., \u0160imkus, M., Eiter, T.: Worst-case optimal conjunctive query answering for an expressive description logic without inverses. In: Fox, D., Gomes, C.P. (eds.) AAAI 2008, pp. 504\u2013510. AAAI Press (2008)"},{"key":"1_CR80","unstructured":"Patel-Schneider, P., Hayes, P., Horrocks, I.: OWL Web Ontology Language semantics and abstract syntax \u2013 W3C recommendation. Tech. rep., World Wide Web Consortium (February 2004), \n                  \n                    http:\/\/www.w3.org\/TR\/owl-semantics\/"},{"key":"1_CR81","unstructured":"P\u00e9rez-Urbina, H., Motik, B., Horrocks, I.: A comparison of query rewriting techniques for DL-Lite. In: Grau, B.C., Horrocks, I., Motik, B., Sattler, U. (eds.) Description Logics. CEUR Workshop Proceedings, vol.\u00a0477, CEUR-WS.org (2009)"},{"issue":"2","key":"1_CR82","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.jal.2009.09.004","volume":"8","author":"H. P\u00e9rez-Urbina","year":"2010","unstructured":"P\u00e9rez-Urbina, H., Motik, B., Horrocks, I.: Tractable query answering and rewriting under description logic constraints. J. Applied Logic\u00a08(2), 186\u2013209 (2010)","journal-title":"J. Applied Logic"},{"key":"1_CR83","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-540-77688-8_5","volume-title":"Journal on Data Semantics X","author":"A. Poggi","year":"2008","unstructured":"Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking Data to Ontologies. In: Spaccapietra, S. (ed.) Journal on Data Semantics X. LNCS, vol.\u00a04900, pp. 133\u2013173. Springer, Heidelberg (2008)"},{"key":"1_CR84","doi-asserted-by":"crossref","unstructured":"Pratt, V.R.: Models of program logic. In: Proc. of the 20th Annual Symp. on the Foundations of Computer Science (FOCS 1979), pp. 115\u2013122 (1979)","DOI":"10.1109\/SFCS.1979.24"},{"issue":"8","key":"1_CR85","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1016\/j.ic.2009.02.004","volume":"207","author":"I. Pratt-Hartmann","year":"2009","unstructured":"Pratt-Hartmann, I.: Data-complexity of the two-variable fragment with counting quantifiers. Information and Computation\u00a0207(8), 867\u2013888 (2009)","journal-title":"Information and Computation"},{"key":"1_CR86","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0933-3657(96)00369-7","volume":"9","author":"A. Rector","year":"1997","unstructured":"Rector, A., Bechhofer, S., Goble, C.A., Horrocks, I., Nowlan, W.A., Solomon, W.D.: The grail concept modelling language for medical terminology. Artificial Intelligence in Medicine\u00a09, 139\u2013171 (1997)","journal-title":"Artificial Intelligence in Medicine"},{"key":"1_CR87","unstructured":"Rosati, R.: On conjunctive query answering in \n                  \n                    \n                  \n                  $\\mathcal{EL}$\n                . In: Proc.\u00a0of the 2007 Description Logic Workshop, DL 2007. CEUR Electronic Workshop Proceedings, vol.\u00a0250 (2007), \n                  \n                    http:\/\/ceur-ws.org\/Vol-250\/"},{"key":"1_CR88","unstructured":"Rosati, R., Almatelli, A.: Improving query answering over DL-Lite ontologies. In: Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning, KR 2010 (2010)"},{"key":"1_CR89","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1613\/jair.3029","volume":"39","author":"S. Rudolph","year":"2010","unstructured":"Rudolph, S., Glimm, B.: Nominals, inverses, counting, and conjunctive queries or: Why infinity is your friend! J. of Artificial Intelligence Research\u00a039, 429\u2013481 (2010)","journal-title":"J. of Artificial Intelligence Research"},{"key":"1_CR90","doi-asserted-by":"crossref","unstructured":"Sattler, U., Vardi, M.Y.: The hybrid \u03bc-calculus. In: Proc. of the Int. Joint Conf. on Automated Reasoning, IJCAR\u00a02001, pp. 76\u201391 (2001)","DOI":"10.1007\/3-540-45744-5_7"},{"key":"1_CR91","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF00962071","volume":"2","author":"A. Schaerf","year":"1993","unstructured":"Schaerf, A.: On the complexity of the instance checking problem in concept languages with existential quantification. J. of Intelligent Information Systems\u00a02, 265\u2013278 (1993)","journal-title":"J. of Intelligent Information Systems"},{"key":"1_CR92","unstructured":"Schild, K.: A correspondence theory for terminological logics: Preliminary report. In: Proc. of the 12th Int. Joint Conf. on Artificial Intelligence, IJCAI 1991, pp. 466\u2013471 (1991)"},{"key":"1_CR93","unstructured":"Tessaris, S.: Questions and Answers: Reasoning and Querying in Description Logic. Ph.D. thesis, University of Manchester, Department of Computer Science (April 2001)"},{"key":"1_CR94","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1613\/jair.705","volume":"12","author":"S. Tobies","year":"2000","unstructured":"Tobies, S.: The complexity of reasoning with cardinality restrictions and nominals in expressive description logics. J. of Artificial Intelligence Research\u00a012, 199\u2013217 (2000)","journal-title":"J. of Artificial Intelligence Research"},{"key":"1_CR95","unstructured":"Tobies, S.: Complexity Results and Practical Algorithms for Logics in Knowledge Representation. Ph.D. thesis, LuFG Theoretical Computer Science, RWTH-Aachen, Germany (2001)"},{"issue":"2","key":"1_CR96","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0304-3975(99)00219-4","volume":"239","author":"J.D. Ullman","year":"2000","unstructured":"Ullman, J.D.: Information integration using logical views. Theoretical Computer Science\u00a0239(2), 189\u2013210 (2000)","journal-title":"Theoretical Computer Science"},{"key":"1_CR97","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query languages. In: Proc. of the 14th ACM SIGACT Symp. on Theory of Computing, STOC 1982, pp. 137\u2013146 (1982)","DOI":"10.1145\/800070.802186"},{"key":"1_CR98","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1007\/BFb0055090","volume-title":"Automata, Languages and Programming","author":"M.Y. Vardi","year":"1998","unstructured":"Vardi, M.Y.: Reasoning about the Past with Two-Way Automata. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 628\u2013641. Springer, Heidelberg (1998)"},{"key":"1_CR99","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0022-0000(86)90026-7","volume":"32","author":"M.Y. Vardi","year":"1986","unstructured":"Vardi, M.Y., Wolper, P.: Automata-theoretic techniques for modal logics of programs. Journal of Computer and System Sciences\u00a032, 183\u2013221 (1986)","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR100","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to circuit complexity - a uniform approach. In: Texts in Theoretical Computer Science. Springer (1999)","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Lecture Notes in Computer Science","Reasoning Web. Semantic Technologies for Advanced Query Answering"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33158-9_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T03:19:43Z","timestamp":1557199183000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33158-9_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642331572","9783642331589"],"references-count":100,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33158-9_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}