Worl: A nonmonotonic rule language for the semantic Web
We develop a new Web ontology rule language,
called WORL, which combines a variant of OWL 2 RL with
eDatalog. We allow additional features like negation, the
minimal number restriction and unary external checkable
predicates to occur at the left-hand side of concept inclusion
axioms. Some restrictions are adopted to guarantee a translation into eDatalog¬. We also develop the well-founded
semantics and the stable model semantics for WORL as well
as the standard semantics for stratified WORL (SWORL) via
translation into eDatalog¬. Both WORL with respect to the
well-founded semantics and SWORLwithrespect to the standard semantics have PTime data complexity. In contrast to
the existing combined formalisms, in WORL and SWORL
negation in concept inclusion axioms is interpreted using
nonmonotonic semantics.
Trang 1
Trang 2
Trang 3
Trang 4
Trang 5
Trang 6
Trang 7
Trang 8
Trang 9
Trang 10
Tải về để xem bản đầy đủ
Tóm tắt nội dung tài liệu: Worl: A nonmonotonic rule language for the semantic Web
ayer 〈T ,A〉 then HKB is the standard Herbrand model of the stratified eDatalog¬ knowledge base 〈π3(T ),A〉, and by Corollary 1,HKB can be computed in polynomial time and has polynomial size in n. – If KB = 〈〈T ,A〉, {KB1, . . . , KBk}〉 then: – By the inductive assumption,HKB1 ,,HKBk can be com- puted in polynomial time and have polynomial size in n. – HKB is the standard Herbrand model of the stratified eDatalog¬ knowledge base 〈π3(T ),A ∪ HKB1 ∪ · · · ∪ HKBk 〉, and by Corollary 1, HKB can be computed in polynomial time and has polynomial size in the size of A ∪ HKB1 ∪ · · · ∪ HKBk . – Hence, HKB can be computed in polynomial time and has polynomial size in n. As a consequence, the data complexity of SWORL w.r.t. the standard semantics is in PTime. unionsq The standard semantics of SWORL coincides with the well-founded semantics when restricting to SWORL knowl- edge bases that are single layers and to queries of the form (ϕ1 ∧ · · · ∧ ϕh ∧ ξ1 ∧ · · · ∧ ξl ∧ ¬ζ1 ∧ · · · ∧ ¬ζm), where ϕ1, , ϕh are atoms of predicates from DPreds and ξ1, , ξl , ζ1, , ζm are atoms of predicates from ECPreds. 4.1 Example: apartment renting In this subsection we discuss apartment renting, a common activity that is often tedious and time-consuming. The exam- ple is based on the one of [2]. The difference is that we use SWORL instead of defeasible logic. We begin by presenting the potential renter’s require- ments: – Carlos is looking for an apartment of at least 45 m2 with at least two bedrooms. If it is on the third floor or higher, the house must have an elevator. Also, pet animals must be allowed. – Carlos is willing to pay $300 for a centrally located 45 m2 apartment, and $250 for a similar flat in the suburbs. In addition, he is willing to pay an extra $5 perm2 for a larger apartment, and $2 per m2 for a garden. – He is unable to pay more than $400 in total. If given the choice, he would go for the cheapest option. His second priority is the presence of a garden; his lowest priority is additional space. We use the following predicates to describe properties of apartments: – hasSize(X, Y ) : Y is the size of apartment X , – bedrooms(X, Y ) : apartment X has Y bedrooms, – hasPrice(X, Y ) : Y is the rent price of apartment X , – floor(X, Y ) : apartment X is on the Y th floor, – garden(X, Y ) : apartment X has a garden of size Y , – withLift(X) : there is an elevator in the house of X , – allowsPets(X) : pets are allowed in apartment X , – central(X) : apartment X is centrally located. The predicates hasSize, bedrooms, hasPrice, floor and garden are data role names, while the predicates withLift, allowsPets and central are concept names. These predicates are specified by ABox assertions. We define a number of predicates. The first one is withGarden, specified by: garden(X, Y ) → withGarden(X). (5) We use predicate offers(X, N , Y, Z) defined as follows: [hasSize(X, Y ) ∧ central(X) ∧ ¬withGarden(X)] → offers(X, 1, Y, 0) (6) [hasSize(X, Y ) ∧ central(X) ∧ garden(X, Z)] → offers(X, 2, Y, Z) (7) [hasSize(X, Y ) ∧ ¬central(X) ∧ ¬withGarden(X)] → offers(X, 3, Y, 0) (8) [hasSize(X, Y ) ∧ ¬central(X) ∧ garden(X, Z)] → offers(X, 4, Y, Z). (9) The predicate offers(X, N , Y, Z) means Carlos is will- ing to pay f (N , Y, Z) dollars for apartment X , where f (N , Y, Z) is defined as f (N , Y, Z) = ⎧ ⎪⎪⎨ ⎪⎪⎩ 300 + 5(Y − 45) if N = 1 300 + 5(Y − 45) + 2.Z if N = 2 250 + 5(Y − 45) if N = 3 250 + 5(Y − 45) + 2.Z if N = 4. This function is usedonly to specify the external checkable predicate tooExpensive(N , Y, Z , P) ≡ ( f (N , Y, Z) < P), which in turn is used in the following program clause: [offers(X, N , Y, Z) ∧ hasPrice(X, P)∧ tooExpensive(N , Y, Z , P)] → excluded0(X). (10) 123 Vietnam J Comput Sci (2014) 1:57–69 67 Thus, excluded0(X) means apartment X is unacceptable. Apartments acceptable to Carlos are defined by the fol- lowing DL TBox axiom: [∃hasSize.(≥ 45) ∃bedrooms.(≥ 2) (∃floor.(≤ 2) unionsq withLift) allowsPets ¬excluded0 ∃hasPrice.(≤400)] acceptable. (11) In the above axiom, (≥45), (≥2), (≤2) and (≤400) are unary external checkable predicates. Among the acceptable apartments, the cheapest ones are preferable: [acceptable(X) ∧ hasPrice(X, Y ) ∧ acceptable(X ′) ∧ hasPrice(X ′, Y ′) ∧ Y < Y ′] → excluded1(X ′) (12) acceptable(X) ∧ ¬excluded1(X) → preferable1(X). (13) Among the cheapest apartments that are acceptable, the ones with a garden are more preferable: [preferable1(X) ∧ ¬withGarden(X) ∧ preferable1(X ′) ∧ withGarden(X ′)] → excluded2(X) (14) preferable1(X) ∧ ¬excluded2(X) → preferable2(X). (15) Among those apartments, Carlos will rent a largest one: [ preferable2(X) ∧ hasSize(X, Y ) ∧ preferable2(X ′) ∧ hasSize(X ′, Y ′) ∧ Y < Y ′ ] → excluded3(X) (16) preferable2(X) ∧ ¬excluded3(X) → mayRent(X). (17) In the program clauses (12) and (16), ‘<’ is a binary exter- nal checkable predicate. Let T = {(5), , (17)}. It is a stratifiable TBox. Only (11) is a DL TBox axiom, while the other axioms are eDatalog¬ program clauses. The program clauses (5), (13), (15) and (17) can also be expressed as DL TBox axioms, treating withGarden, acceptable, excluded1, preferable1, excluded2, preferable2, excluded3 and mayRent as concept names. Translating the TBox T to a stratified eDatalog¬ program P = π3(T ), the DL TBox axiom (11) is replaced by the following eDatalog¬ program clauses: [hasSize(X, Y1) ∧ Y1 ≥ 45 ∧ bedrooms(X, Y2) ∧ Y2 ≥ 2 ∧ floor(X, Y3) ∧ Y3 ≤ 2 ∧ allowsPets(X) ∧ ¬excluded0(X) ∧ hasPrice(X, Y4) ∧ Y4 ≤ 400 ] → acceptable(X) (18) [hasSize(X, Y1) ∧ Y1 ≥ 45 ∧ bedrooms(X, Y2) ∧ Y2 ≥ 2 ∧ withLift(X) ∧ allowsPets(X) ∧ ¬excluded0(X) ∧ hasPrice(X, Y4) ∧ Y4 ≤ 400] → acceptable(X). (19) A possible stratification of P is: {(5)}, {(6), (7), (8), (9), (10)}, {(18), (19), (12)}, {(13), (14)}, {(15), (16)}, {(17)}. LetA be theABox consisting of the ground atoms of pred- icates bedrooms, hasSize, central, floor, withLift, allowsPets, garden and hasPrice that reflect the information contained in the following table: Flat Bedrooms Size Central Floor Lift Pets Garden Price a1 1 50 Yes 1 No Yes 300 a2 2 45 Yes 0 No Yes 335 a3 2 65 No 2 No Yes 350 a4 2 55 No 1 Yes No 15 330 a5 3 55 Yes 0 No Yes 15 350 a6 2 60 Yes 3 No No 370 a7 3 65 Yes 1 No Yes 12 375 For example, bedrooms(a1, 1), hasSize(a1, 50), central (a1), floor(a1, 1), allowsPets(a1) and hasPrice(a1, 300) are the atoms ofA that involve apartment a1. AsABoxes contain only positive information, only atom withLift(a4) of predi- cate withLift occurs in A. The pair KB = 〈T ,A〉 is a SWORL knowledge layer (and a SWORL knowledge base). The standard Herbrand modelHKB contains atoms acceptable(X) only for X ∈ {a3, a5, a7} and atoms preferable1(X) only for X ∈ {a3, a5}. Only atom preferable2(a5) of predicate preferable2 and atom mayRent(a5) of predicate mayRent occur in HKB. 5 Conclusions We have developed theWeb ontology rule languagesWORL and SWORL together with the well-founded semantics and the stable model semantics for WORL and the standard semantics for SWORL. BothWORLwith respect to thewell- founded semantics and SWORL with respect to the standard semantics have PTime data complexity. As WORL can be translated into eDatalog¬ and SWORL can be translated into stratified eDatalog¬, the languages WORL and SWORL are notmore expressive than eDatalog¬ and stratified eDatalog¬, respectively. However, WORL and SWORL allow using also syntax of description logic (and hence also OWL). This has the same benefits as in the case OWL 2 RL compared to eDatalog, and is very useful for applications of the Semantic Web. As Web ontology rule languages, WORL and SWORL have the advantage of using efficient computational methods of Datalog¬ (extended for eDatalog¬). Using nonmonotonic semantics for negation in concept inclusion axioms is a novelty of our approach. Modularity of SWORL is also worth mentioning. 123 68 Vietnam J Comput Sci (2014) 1:57–69 Acknowledgments This work was supported by the Polish National Science Center (NCN) under Grants No. 2011/01/B/ST6/02769 and 2011/01/B/ST6/02759. The first author would also like to thank the Warsaw Center of Mathematics and Computer Science for support. 6 Appendix: Checking stratifiability of TBoxes We specify a dependency relation between the predicates occurring in a TBox for deciding whether the TBox is strat- ifiable. For ϕ being either a concept of the lC family but not of the form≥ n R.C , or an expression of the form R, R1 ◦ · · · ◦ Rk , , σ or ∃σ , let Preds−(ϕ) be the set of the concept names that occur inϕ under negation, and letPreds+(ϕ) be the set of the predicates from DPreds that occur in ϕ but do not belong to Preds−(ϕ). For a concept C belonging to the rC family, define LPreds+(C), LPreds−(C) and RPreds(C) as follows:5 – case C = A: LPreds+(C) = LPreds−(C) = ∅, RPreds(C) = {A}; – case C = D1 D2: LPreds+(C) = LPreds+(D1) ∪ LPreds+(D2), LPreds−(C) = LPreds−(D1) ∪ LPreds−(D2), RPreds(C) = RPreds(D1) ∪ RPreds(D2); – case C = ∀r.D or C = ∀r−.D: LPreds+(C) = {r} ∪ LPreds+(D), LPreds−(C)=LPreds−(D), RPreds(C) = RPreds(D); – case C = ∃r.{a} or C = ∃r−.{a}: LPreds+(C) = LPreds−(C) = ∅, RPreds(C) = {r}; – case C = ∀σ.DR: LPreds+(C) = {σ }, LPreds−(C) = ∅, RPreds(C) is the set of all data types occurring in DR; – case C = ∃σ.{d}: LPreds+(C) = LPreds−(C) = ∅, RPreds(C) = {σ }; – case C = ≤1 r.D or C = ≤1 r−.D: LPreds+(C) = {r} ∪ Preds+(D), LPreds−(C) = Preds−(D), RPreds(C)={‘=’}; – case C = ≤1 r. or C = ≤1 r−.: LPreds+(C) = {r}, LPreds−(C) = ∅, RPreds(C) = {‘=’}. Let LPreds+(R) = LPreds−(R) = ∅ and RPreds(r) = RPreds(r−) = {r}. Let LPreds+(σ ) = LPreds−(σ ) = ∅ and RPreds(σ ) = {σ }. It can be proved that a TBox T is stratifiable if T does not use the concept constructor ≥ n R.C and there exists a function f from DPreds to positive natural numbers such that: 5 Where L stands for “left of →” and R stands for “right of →”. – for every eDatalog¬ program clause ϕ in T ∪ EqAxioms, if q is the predicate of the head of ϕ and p is a pred- icate from DPreds that occurs in the body of ϕ then f (p) ≤ f (q), and additionally, if p occurs under negation in ϕ then f (p) < f (q); – for every axiom of the form ϕ ψ in T and for every q ∈ RPreds(ψ): – for every p ∈ Preds+(ϕ) ∪ LPreds+(ψ), f (p) ≤ f (q); – for every p ∈ Preds−(ϕ) ∪ LPreds−(ψ), f (p) < f (q); – for every axiom of the form ϕ = ψ in T , all the predicates occurring in ϕ = ψ have the same f value; – for every axiom Key(C, R1, . . . , Rh, σ1, . . . , σk) in T : Preds−(C) = ∅ and, for every predicate p belonging to Preds+(C) or {σ1, . . . , σk} or occurring in R1, . . . , Rh , f (p) = f (‘=’); – for every axiom of the form Func(R) or InvFunc(R) in T , where R = r or R = r−, we have that f (r) = f (‘=’). To check whether a TBox T is stratifiable one can con- struct a graph of dependencies between the predicates occur- ring in T . The condition f (p) ≤ f (q) (resp. f (p) < f (q)) is expressed by an edge with mark + (resp. −) from vertex p to vertex q. The TBox is stratifiable if that graph does not contain any cycle with an edge marked by −. References 1. Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addi- son and Wesley, Reading (1995) 2. Antoniou, G., van Harmelen, F.: A Semantic Web Primer. MIT Press, Cambridge (2004) 3. Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: Pro- ceedings of IJCAI’2005, pp. 364–369. Morgan-Kaufmann, San Franciso (2005). 4. Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope further. In: Proceedings of the OWLED 2008 DC Workshop on OWL: Experiences and Directions (2008) 5. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in descrip- tion logics: the DL-Lite family. J. Autom. Reason. 39(3), 385–429 (2007) 6. Cao, S.T., Nguyen, L.A., Szałas, A.: On the Web ontology rule language OWL 2 RL. In: Proceedings of ICCCI 2011. LNCS, vol. 6922, pp. 254–264. Springer, Berlin (2011) 7. Cao, S.T., Nguyen, L.A., Szalas, A.: WORL: a Web ontology rule language. In Proceedings ofKSE’2011, pp. 32–39. IEEEComputer Society (2011) 8. Donini, F.M., Lenzerini, M., Nardi, D., Schaerf, A.: AL-log: Inte- grating Datalog and description logics. J. Intell. Inf. Syst. 10(3), 227–252 (1998) 9. Drabent, W., Maluszynski, J.: Well-founded semantics for hybrid rules. In: Proceedings of RR’2007. LNCS, vol. 4524, pp. 1–15. Springer, Berlin (2007) 123 Vietnam J Comput Sci (2014) 1:57–69 69 10. Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R.: Well-founded semantics for description logic programs in the Semantic Web. ACM Trans. Comput. Log. 12(2), 11 (2011) 11. VanGelder, A., Ross, K.A., Schlipf, J.S.: Thewell-founded seman- tics for general logic programs. J. ACM 38(3), 620–650 (1991) 12. Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In Proceedings of ICLP/SLP’1988, pp. 1070–1080. MIT Press, Cambridge (1988) 13. Grosof, B.N., Horrocks, I., Volz, R., Decker, S.: Description logic programs: combining logic programs with description logic. In: Proceedings of WWW’2003, pp. 48–57 (2003) 14. Horrocks, I., Patel-Schneider, P.F., Bechhofer, S., Tsarkov, D.: OWL rules:Aproposal and prototype implementation. J.WebSem. 3(1), 23–40 (2005) 15. Hustadt, U., Motik, B., Sattler, U.: Reasoning in description logics by a reduction to disjunctive Datalog. J. Autom. Reason. 39(3), 351–384 (2007) 16. Knorr, M., Alferes, J.J., Hitzler, P.: A coherent well-founded model for hybrid MKNF knowledge bases. In: Proceedings of ECAI’2008. Frontiers in Artificial Intelligence and Applications, vol. 178, pp. 99–103. IOS Press, Amsterdam (2008) 17. Levy, A.Y., Rousset, M.-C.: Combining Horn rules and description logics in CARIN. Artif. Intell. 104(1–2), 165–209 (1998) 18. Motik, B., Rosati, R.: Reconciling description logics and rules. J. ACM. 57(5) (2010) 19. Motik, B., Sattler, U., Studer, R.: Query answering for OWL-DL with rules. J. Web Sem. 3(1), 41–60 (2005) 20. Nguyen, L.A., Nguyen, T.-B.-L., Szałas, A.: Horn-DL: an expres- sive Horn description logic with PTime data complexity. In Pro- ceedings of RR’2013. LNCS, vol. 7994, pp. 259–264. Springer, Berlin (2013) 21. Ortiz, M., Rudolph, S., Simkus, M.: Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2. In: Proceedings of KR’2010. AAAI Press, Cambridge (2010) 22. (2009) 23. Ricca, F., Gallucci, L., Schindlauer, R., Dell’Armi, T., Grasso, G., Leone, N.: OntoDLV: an ASP-based system for enterprise ontolo- gies. J. Log. Comput. 19(4), 643–670 (2009) 24. Rosati, R.: DL+log: Tight integration of description logics and disjunctiveDatalog. In: Proceedings ofKR’2006, pp. 68–78.AAAI Press, Cambridge (2006) 123
File đính kèm:
- worl_a_nonmonotonic_rule_language_for_the_semantic_web.pdf