Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

ELP: Tractable Rules for OWL 2

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNISA,volume 5318))

Included in the following conference series:

  • 2302Accesses

  • 55Citations

Abstract

We introduce\(\text{\sf{ELP}}\) as a decidable fragment of the Semantic Web Rule Language (SWRL) that admits reasoning in polynomial time.\(\text{\sf{ELP}}\) is based on the tractable description logic\(\mathcal{EL}^{\mathord{+}\mathord{+}}\), and encompasses an extended notion of the recently proposedDL rules for that logic. Thus\(\text{\sf{ELP}}\) extends\(\mathcal{EL}^{\mathord{+}\mathord{+}}\) with a number of features introduced by the forthcoming OWL 2, such as disjoint roles, local reflexivity, certain range restrictions, and the universal role. We present a reasoning algorithm based on a translation of\(\text{\sf{ELP}}\) to Datalog, and this translation also enables the seamless integration of DL-safe rules into\(\text{\sf{ELP}}\). While reasoning with DL-safe rules as such is already highly intractable, we show that DL-safe rules based on the Description Logic Programming (DLP) fragment of OWL 2 can be admitted in\(\text{\sf{ELP}}\) without losing tractability.

Similar content being viewed by others

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible\(\mathcal{SROIQ}\). In: Proc. of the 10th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR 2006), pp. 57–67. AAAI Press, Menlo Park (2006)

    Google Scholar 

  2. Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: Proc. 19th Int. Joint Conf. on Artificial Intelligence (IJCAI 2005), Edinburgh, UK. Morgan-Kaufmann Publishers, San Francisco (2005)

    Google Scholar 

  3. Calvanese, D., Giacomo, G.D., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. of Automated Reasoning 9, 385–429 (2007)

    Article MathSciNet MATH  Google Scholar 

  4. Grosof, B., Horrocks, I., Volz, R., Decker, S.: Description logic programs: Combining logic programs with description logics. In: Proc. of WWW 2003, Budapest, Hungary, pp. 48–57. ACM, New York (2003)

    Google Scholar 

  5. Krötzsch, M., Rudolph, S., Hitzler, P.: Complexity of Horn description logics. In: Proc. 22nd AAAI Conf., AAAI 2007 (2007)

    Google Scholar 

  6. Baader, F., Lutz, C., Brandt, S.: Pushing the EL envelope further. In: Proc. 4th Int. Workshop on OWL: Experiences and Directions (OWLED 2008 DC), Washington, DC (2008)

    Google Scholar 

  7. Motik, B., Sattler, U., Studer, R.: Query answering for OWL DL with rules. J. of Web Semantics 3, 41–60 (2005)

    Article  Google Scholar 

  8. Hustadt, U., Motik, B., Sattler, U.: Data complexity of reasoning in very expressive description logics. In: Proc. 18th Int. Joint Conf. on Artificial Intelligence (IJCAI 2005), Edinburgh, UK, pp. 466–471. Morgan-Kaufmann Publishers, San Francisco (2005)

    Google Scholar 

  9. Krötzsch, M., Rudolph, S., Hitzler, P.: Description logic rules. In: Proc. 18th European Conf. on Artificial Intelligence (ECAI 2008), pp. 80–84. IOS Press, Amsterdam (2008)

    Google Scholar 

  10. Gasse, F., Sattler, U., Haarslev, V.: Rewriting rules into\(\mathcal{SROIQ}\) axioms. In: Poster at 21st Int. Workshop on Description Logics, DL 2008 (2008)

    Google Scholar 

  11. Rudolph, S., Krötzsch, M., Hitzler, P.: All elephants are bigger than all mice. In: Proc. 21st Int. Workshop on Description Logics, DL 2008 (2008)

    Google Scholar 

  12. Krötzsch, M., Rudolph, S., Hitzler, P.: ELP: Tractable rules for OWL 2. Technical report, Universität Karlsruhe, Germany (May 2008),http://korrekt.org/page/ELP

  13. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P. (eds.): The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, Cambridge (2007)

    MATH  Google Scholar 

  14. Horrocks, I., Patel-Schneider, P.F.: A proposal for an OWL rules language. In: Feldman, S.I., Uretsky, M., Najork, M., Wills, C.E. (eds.) Proc. 13th Int. Conf. on World Wide Web (WWW 2004), pp. 723–731. ACM, New York (2004)

    Chapter  Google Scholar 

  15. Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and expressive power of logic programming. ACM Computing Surveys 33, 374–425 (2001)

    Article  Google Scholar 

  16. Krötzsch, M., Rudolph, S., Hitzler, P.: Conjunctive queries for a tractable fragment of OWL 1.1. In: Aberer, K., Choi, K.-S., Noy, N., Allemang, D., Lee, K.-I., Nixon, L., Golbeck, J., Mika, P., Maynard, D., Mizoguchi, R., Schreiber, G., Cudré-Mauroux, P. (eds.) ASWC 2007 and ISWC 2007. LNCS, vol. 4825, pp. 310–323. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  17. Pérez-Urbina, H., Motik, B., Horrocks, I.: Rewriting conjunctive queries under description logic constraints. In: Proc. Int. Workshop on Logic in Databases, LID 2008 (2008)

    Google Scholar 

  18. Pérez-Urbina, H., Motik, B., Horrocks, I.: Rewriting conjunctive queries over description logic knowledge bases. In: Proc. Int. Workshop on Semantics in Data and Knowledge Bases, SDKB 2008 (2008)

    Google Scholar 

  19. Rosati, R.: Conjunctive query answering in EL. In: Proc. 20th Int. Workshop on Description Logics, DL 2007 (2007)

    Google Scholar 

  20. Kazakov, Y.: Saturation-Based Decision Procedures for Extensions of the Guarded Fragment. PhD thesis, Universität des Saarlandes, Germany (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut AIFB, Universität Karlsruhe, Germany

    Markus Krötzsch, Sebastian Rudolph & Pascal Hitzler

Authors
  1. Markus Krötzsch
  2. Sebastian Rudolph
  3. Pascal Hitzler

Editor information

Editors and Affiliations

  1. Department of Computer Science and Engineering, Wright State University, Colonel Glenn Way 3640, 454350001, Dayton, USA

    Amit Sheth

  2. Institut für Informatik, Universität Koblenz-Landau, Universitätsstr. 1, 56016, Koblenz, Germany

    Steffen Staab

  3. BBN Technologies, 48103, Ann Arbor, USA

    Mike Dean

  4. DoCoMo Communications Laboratories Europe GmbH, 80687, Munich, Germany

    Massimo Paolucci

  5. Department of Computer Science, University of Sheffield, Regent Court, 211 Portobello Street, S1 4DP, Sheffield, UK

    Diana Maynard

  6. CSEE Department, UMBC, 1000 Hilltop Circle, MD 21250, Baltimore, USA

    Timothy Finin

  7. Department of Computer Science and Engineering, Wright State University, 3640 Colonel Glenn Highway, OH 45435, Dayton, USA

    Krishnaprasad Thirunarayan

Rights and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Krötzsch, M., Rudolph, S., Hitzler, P. (2008). ELP: Tractable Rules for OWL 2. In: Sheth, A.,et al. The Semantic Web - ISWC 2008. ISWC 2008. Lecture Notes in Computer Science, vol 5318. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88564-1_41

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp