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