2004 QueryAnsweringforOWL-DLwithRules

(Motik et al., 2004) ⇒ Boris Motik, Ulrike Sattler, and Rudi Studer. (2004). “Query Answering for OWL-DL with Rules.” In: Proceedings of the Third International Semantic Web Conference (ISWC 2004). doi:10.1007/978-3-540-30475-3_38

Subject Headings: Description logics; Rules; Decidability; Hybrid languages.

Notes

Cited By

~254 http://scholar.google.com/scholar?q=%22Query+Answering+for+OWL-DL+with+Rules%22+2005

Quotes

Abstract

Both OWL-DL and function-free Horn rules 3 are decidable logics with interesting, yet orthogonal expressive power: from the rules perspective, OWL-DL is restricted to tree-like rules, but provides both existentially and universally quantiﬁed variables and full, monotonic negation. From the description logic perspective, rules are restricted to universal quantiﬁcation, but allow for the interaction of variables in arbitrary ways. Clearly, a combination of OWL-DL and rules is desirable for building Semantic Web ontologies, and several such combinations have already been discussed. However, such a combination might easily lead to the undecidability of interesting reasoning problems. Here, we present a decidable such combination which is, to the best of our knowledge, more general than similar decidable combinations proposed so far. Decidability is obtained by restricting rules to so-called DL-safe ones, requiring each variable in a rule to occur in a non-DL-atom in the rule body. We show that query answering in such a combined logic is decidable, and we discuss its expressive power by means of a non-trivial example. Finally, we present an algorithm for query answering in SHIQ(D) extended with DL-safe rules based on the reduction to disjunctive datalog.

References

F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P. Patel-Schneider, editors. The Description Logic Handbook. Cambridge University Press, January 2003.
F. Baader and P. Hanschke. A Scheme for Integrating Concrete Domains into Concept Languages. In: Proceedings of the 12th Int’l Joint Conference on Artiﬁcial Intelligence (IJCAI-91), pages 452–457, Sydney, Australia, 1991.
L. Bachmair and H. Ganzinger. Resolution Theorem Proving. In A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, volume I, chapter 2, pages 19–99. Elsevier Science, 2001.Query Answering for OWL-DL with Rules 15
L. Bachmair, H. Ganzinger, C. Lynch, and W. Snyder. Basic Paramodulation. Information and Computation, 121(2):172–192, 1995.
F. M. Donini, M. Lenzerini, D. Nardi, and A. Schaerf. AL-log: Integrating Datalog and Description Logics. J. of Intelligent Information Systems, 10(3):227–252, 1998.
T. Eiter, G. Gottlob, and H. Mannila. Disjunctive Datalog. ACM Transactions on Database Systems, 22(3):364–418, 1997.
E. Gr¨adel, M. Otto, and E. Rosen. Two-Variable Logic with Counting is Decidable. In: Proceedings of 12th IEEE Symposium on Logic in Computer Science LICS ‘97, Warsaw, Poland, 1997.
B. N. Grosof, I. Horrocks, R. Volz, and S. Decker. Description Logic Programs: Combining Logic Programs with Description Logic. In: Proceedings of the Twelfth Int’l World Wide Web Conference (WWW 2003), pages 48–57. ACM, 2003.
V. Haarslev and R. M¨oller. RACER System Description. In 1st Int’l Joint Conference on Automated Reasoning (IJCAR-01), pages 701–706. Springer-Verlag, 2001.
I. Horrocks. Using an Expressive Description Logic: FaCT or Fiction? In: Proceedings. 6th Int’l. Conference on Principles of Knowledge Representation and Reasoning (KR’98), pages 636–647. Morgan Kaufmann Publishers, 1998.
I. Horrocks and P. F. Patel-Schneider. A Proposal for an OWL Rules Language. In: Proceedings of the Thirteenth Int’l World Wide Web Conf.(WWW 2004). ACM, 2004.
I. Horrocks and U. Sattler. Ontology Reasoning in the SHOQ(D) Description Logic. In B. Nebel, editor, Proceedings of the 17th Int’l Joint Conference on Artiﬁcial Intelligence (IJCAI 2001), pages 199–204. Morgan Kaufmann, 2001.
I. Horrocks, U. Sattler, and S. Tobies. Practical Reasoning for Very Expressive Description Logics. Logic Journal of the IGPL, 8(3):239–263, 2000.
U. Hustadt, B. Motik, and U. Sattler. Reasoning for Description Logics around SHIQ in a Resolution Framework. Technical Report 3-8-04/04, FZI, Karlsruhe, Germany, April 2004. http://www.fzi.de/wim/publikationen.php?id=1172.
U. Hustadt, B. Motik, and U. Sattler. Reducing SHIQ − Description Logic to Disjunctive Datalog Programs. In: Proceedings of the 9th Conference on Knowledge Representation and Reasoning (KR2004). AAAI Press, June 2004.
A. Y. Levy and M.-C. Rousset. Combining Horn rules and description logics in CARIN. Artiﬁcial Intelligence, 104(1-2):165–209, 1998.
C. Lutz. Description Logics with Concrete Domains — A Survey. In Advances in Modal Logics, volume 4. King’s College Publications, 2003.
B. Motik, A. Maedche, and R. Volz. Optimizing Query Answering in Description Logics using Disjunctive Deductive Databases. In 10th Int’l Workshop on Knowledge Representation meets Databases (KRDB-2003), Hamburg, Germany, September 15-16 2003.
A. Nonnengart and C. Weidenbach. Computing Small Clause Normal Forms. In A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, volume I, chapter 6, pages 335–367. Elsevier Science, 2001.
P. F. Patel-Schneider, P. Hayes, I. Horrocks, and F. van Harmelen. OWL Web Ontology Language; Semantics and Abstract Syntax, W3C Candidate Recommendation. http://www.w3.org/TR/owl-semantics/, November 2002.
S. Tobies. Complexity Results and Practical Algorithms for Logics in Knowledge Representation. PhD thesis, RWTH Aachen, Germany, 2001.
M. Vardi. Why is modal logic so robustly decidable? In N. Immerman and P. Kolaitis, editors, Descriptive Complexity and Finite Models, volume 31 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 149–184.
R. Volz. Web Ontology Reasoning With Logic Databases. PhD thesis, Universit¨at Fridericiana zu Karlsruhe (TH), Germany, 2004.

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2004 QueryAnsweringforOWL-DLwithRules	Rudi Studer Boris Motik Ulrike Sattler			Conditional Random Fields: Query Answering for OWL-DL with Rules			http://www.cs.ox.ac.uk/boris.motik/pubs/mss04dl-safe.pdf