Abstract
While there has been a great deal of work on the development of reasoning algorithms for expressive description logics, in most cases only Tbox reasoning is considered. In this paper we present an algorithm for combined Tbox and Abox reasoning in the \(\mathcal{SHIQ}\) description logic. This algorithm is of particular interest as it can be used to decide the problem of (database) conjunctive query containment w.r.t. a schema. Moreover, the realisation of an efficient implementation should be relatively straightforward as it can be based on an existing highly optimised implementation of the Tbox algorithm in the FaCT system.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Areces, C., Blackburn, P., Marx, M.: A road-map on complexity for hybrid logics. In: Flum, J., RodrÃguez-Artalejo, M. (eds.) CSL 1999. LNCS, vol. 1683, pp. 307–321. Springer, Heidelberg (1999)
Baader, F.: Augmenting concept languages by transitive closure of roles: An alternative to terminological cycles. In: Proc. of IJCAI 1991 (1991)
Baader, F., Bürckert, H.-J., Nebel, B., Nutt, W., Smolka, G.: On the expressivity of feature logics with negation, functional uncertainty, and sort equations. Journal of Logic, Language and Information 2, 1–18 (1993)
Baader, F., Heinsohn, H.-J., Hollunder, B., Muller, J., Nebel, B., Nutt, W., Profitlich, H.-J.: Terminological knowledge representation: A proposal for a terminological logic. Technical Memo TM-90-04, DFKI, Saarbrücken,Germany (1991)
Blackburn, P., Seligman, J.: What are hybrid languages? In: Advances in Modal Logic, vol. 1, pp. 41–62. CSLI Publications, Stanford University (1998)
Buchheit, M., Donini, F.M., Schaerf, A.: Decidable reasoning in terminological knowledge representation systems. J. of Artificial Intelligence Research 1, 109–138 (1993)
Calvanese, D.: Reasoning with inclusion axioms in description logics: Algorithms and complexity. In: Proc. of ECAI 1996, pp. 303–307. JohnWiley & Sons Ltd., England (1996)
Calvanese, D., De Giacomo, G., Lenzerini, M.: On the decidability of query containment under constraints. In: Proc. of PODS 1998, pp. 149–158 (1998)
Calvanese, D., De Giacomo, G., Lenzerini, M., Nardi, D., Rosati, R.: Source integration in data warehousing. In: Proc. of DEXA 1998, IEEE Computer Society Press, Los Alamitos (1998)
Calvanese, D., De Giacomo, G., Lenzerini, M., Nardi, D., Rosati, R.: Description logic framework for information integration. In: Proc. of KR 1998 (1998)
De Giacomo, G., Massacci, F.: Combining deduction and model checking into tableaux and algorithms for converse-PDL. Information and Computation (1998) (to appear)
De Giacomo, G., Lenzerini, M.: What’s in an aggregate: Foundations for description logics with tuples and sets. In: Proc. of IJCAI 1995 (1995)
Haarslev, V. Möller, R.: An empirical evaluation of optimization strategies for abox reasoning in expressive description logics. In Lambrix et al. [19], pp. 15–119
Horrocks, I.: FaCT and iFaCT. In: Lambrix et al. [19], pp. 133–135
Horrocks, I., Rector, A., Goble, C.: A description logic based schema for the classification of medical data. In: Proc. of the 3rd Workshop KRDB 1996, CEUR (June 1996)
Horrocks, I., Sattler, U.: A description logic with transitive and inverse roles and role hierarchies. Journal of Logic and Computation 9(3), 385–410 (1999)
Horrocks, I., Sattler, U., Tessaris, S., Tobies, S.: Query containment using a DLR ABox. LTCS-Report 99-15, LuFG Theoretical Computer Science, RWTH Aachen, Germany (1999)
Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for expressive description logics. In: Ganzinger, H., McAllester, D., Voronkov, A. (eds.) LPAR 1999. LNCS (LNAI), vol. 1705, pp. 161–180. Springer, Heidelberg (1999)
Lambrix, P., Borgida, A., Lenzerini, M., Möller, R., Patel-Schneider, P. (eds.): Proc. of the International Workshop on Description Logics, DL 1999 (1999)
Mays, E., Weida, R., Dionne, R., Laker, M., White, B., Liang, C., Oles, F.J.: Scalable and expressive medical terminologies. In: Proc. of the 1996 AMAI Annual Fall Symposium (1996)
Sattler, U.: A concept language extended with different kinds of transitive roles. In: Görz, G., Hölldobler, S. (eds.) KI 1996. LNCS (LNAI), vol. 1137. Springer, Heidelberg (1996)
Schaerf, A.: Reasoning with individuals in concept languages. Data and Knowledge Engineering 13(2), 141–176 (1994)
Schild, K.: A correspondence theory for terminological logics: Preliminary report. In: Mylopoulos, J., Reiter, R. (eds.) Proc. of IJCAI 1991, Sydney (1991)
Schmidt-Schauß, M., Smolka, G.: Attributive concept descriptions with complements. Artificial Intelligence 48(1), 1–26 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Horrocks, I., Sattler, U., Tobies, S. (2000). Reasoning with Individuals for the Description Logic \(\mathcal{SHIQ}\) . In: McAllester, D. (eds) Automated Deduction - CADE-17. CADE 2000. Lecture Notes in Computer Science(), vol 1831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10721959_39
Download citation
DOI: https://doi.org/10.1007/10721959_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67664-5
Online ISBN: 978-3-540-45101-3
eBook Packages: Springer Book Archive