Abstract
Ontology-based data access (OBDA) is widely accepted as an important ingredient of the new generation of information systems. In the OBDA paradigm, potentially incomplete relational data is enriched by means of ontologies, representing intensional knowledge of the application domain. We consider the problem of conjunctive query answering in OBDA. Certain ontology languages have been identified as FO-rewritable (e.g., DL-Lite and sticky-join sets of TGDs), which means that the ontology can be incorporated into the user’s query, thus reducing OBDA to standard relational query evaluation. However, all known query rewriting techniques produce queries that are exponentially large in the size of the user’s query, which can be a serious issue for standard relational database engines. In this paper, we present a polynomial query rewriting for conjunctive queries under unary inclusion dependencies. On the other hand, we show that binary inclusion dependencies do not admit polynomial query rewriting algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Acciarri, A., Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Palmieri, M., Rosati, R.: QuOnto: Querying ontologies. In: Proc. of the 20th Nat. Conf. on Artificial Intelligence (AAAI), pp. 1670–1671 (2005)
Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and relations. J. of Artificial Intelligence Research (JAIR) 36, 1–69 (2009)
Baader, F., Brandt, S., Lutz, C.: Pushing the \(\mathcal{EL}\) envelope further. In: Proc. of the 4th Int. Workshop on OWL: Experiences and Directions, OWLED 2008 DC (2008)
Baget, J.F., Leclère, M., Mugnier, M.L., Salvat, É.: Extending decidable cases for rules with existential variables. In: Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 677–682 (2009)
Calì, A., Gottlob, G., Lukasiewicz, T.: A general Datalog-based framework for tractable query answering over ontologies. In: Proc. of the 28th ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems (PODS), pp. 77–86. ACM, New York (2009)
Calì, A., Gottlob, G., Pieris, A.: Query answering under non-guarded rules in Datalog+ / −. In: Hitzler, P., Lukasiewicz, T. (eds.) RR 2010. LNCS, vol. 6333, pp. 1–17. Springer, Heidelberg (2010)
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: DL-Lite: Tractable description logics for ontologies. In: Proc. of the 20th Nat. Conf. on Artificial Intelligence (AAAI), pp. 602–607 (2005)
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 39(3), 385–429 (2007)
Dolby, J., Fokoue, A., Kalyanpur, A., Ma, L., Schonberg, E., Srinivas, K., Sun, X.: Scalable grounded conjunctive query evaluation over large and expressive knowledge bases. In: Sheth, A.P., Staab, S., Dean, M., Paolucci, M., Maynard, D., Finin, T., Thirunarayan, K. (eds.) ISWC 2008. LNCS, vol. 5318, pp. 403–418. Springer, Heidelberg (2008)
Gottlob, G., Orsi, G., Pieris, A.: Ontological queries: Rewriting and optimization. In: Proc. of the IEEE Int. Conf. on Data Engineering, ICDE (2011)
Gottlob, G., Schwentick, T.: Rewriting ontological queries into small nonrecursive Datalog programs. In: Proc. of the 24th Int. Workshop on Description Logics, DL (2011)
Heymans, S., Ma, L., Anicic, D., Ma, Z., Steinmetz, N., Pan, Y., Mei, J., Fokoue, A., Kalyanpur, A., Kershenbaum, A., Schonberg, E., Srinivas, K., Feier, C., Hench, G., Wetzstein, B., Keller, U.: Ontology reasoning with large data repositories. In: Ontology Management, pp. 89–128. Springer, Heidelberg (2008)
Kontchakov, R., Lutz, C., Toman, D., Wolter, F., Zakharyaschev, M.: The combined approach to query answering in DL-Lite. In: Proc. of the 12th Int. Conf. on Principles of Knowledge Representation and Reasoning, KR (2010)
Kontchakov, R., Lutz, C., Toman, D., Wolter, F., Zakharyaschev, M.: The combined approach to ontology-based data access. In: Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence, IJCAI (2011)
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. 5195, pp. 179–193. Springer, Heidelberg (2008)
Lutz, C., Toman, D., Wolter, F.: Conjunctive query answering in the description logic \(\mathcal{EL}\) using a relational database system. In: Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 2070–2075 (2009)
Pérez-Urbina, H., Motik, B., Horrocks, I.: A comparison of query rewriting techniques for DL-Lite. In: Proc. of the 22nd Int. Workshop on Description Logics (DL). CEUR Workshop Proceedings. CEUR-WS.org, vol. 477 (2009)
Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking data to ontologies. J. on Data Semantics X, 133–173 (2008)
Poggi, A., Rodriguez, M., Ruzzi, M.: Ontology-based database access with DIG-Mastro and the OBDA Plugin for Protégé. In: Proc. of the 4th Int. Workshop on OWL: Experiences and Directions, OWLED 2008 DC (2008)
Rodríguez-Muro, M., Calvanese, D.: Dependencies to optimize ontology-based data access. In: Proc. of the 24th Int. Workshop on Description Logics, DL (2011)
Rosati, R., Almatelli, A.: Improving query answering over DL-Lite ontologies. In: Proc. of the 12th Int. Conf. on Principles of Knowledge Representation and Reasoning, KR (2010)
Vardi, M.: The complexity of relational query languages (extended abstract). In: Proc. of the 14th ACM SIGACT Symp. on Theory of Computing (STOC), pp.137–146 (1982)
Vardi, M.: On the complexity of bounded-variable queries (extended abstract). In: Proc. of the 14th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (PODS), pp. 266–276 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kikot, S., Kontchakov, R., Zakharyaschev, M. (2011). Polynomial Conjunctive Query Rewriting under Unary Inclusion Dependencies. In: Rudolph, S., Gutierrez, C. (eds) Web Reasoning and Rule Systems. RR 2011. Lecture Notes in Computer Science, vol 6902. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23580-1_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-23580-1_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23579-5
Online ISBN: 978-3-642-23580-1
eBook Packages: Computer ScienceComputer Science (R0)