=Paper=
{{Paper
|id=Vol-474/paper-6
|storemode=property
|title=Learning Semantic Web Rules: State of the Art and Directions of Research
|pdfUrl=https://ceur-ws.org/Vol-474/paper4.pdf
|volume=Vol-474
}}
==Learning Semantic Web Rules: State of the Art and Directions of Research==
https://ceur-ws.org/Vol-474/paper4.pdf
Learning Semantic Web Rules:
State of the Art and Directions of Research
Francesca A. Lisi and Floriana Esposito
Dipartimento di Informatica, Università degli Studi di Bari
Via E. Orabona 4, 70125 Bari, Italy
{lisi, esposito}@di.uniba.it
Abstract. The acquisition of Semantic Web rules is very demanding
and can be automated though partially by applying Machine Learning
(ML) algorithms. In this paper we provide a state-of-the-art survey of
ML research relevant to this issue. In particular, we take a critical look
at three ML frameworks that extend the methodological apparatus of
Inductive Logic Programming to hybrid Knowledge Representation sys-
tems combining Description Logics and Clausal Logics. From the com-
parison of the three we draw general conclusions that suggest directions
of research on this topic.
1 Motivation and Scope
Rules are currently in the focus within the Semantic Web architecture, and
consequently interest and activity in this area has grown rapidly over recent
years. They would allow the integration, transformation and derivation of data
from numerous sources in a distributed, scalable, and transparent manner. The
rules landscape features design aspects of rule markup; engineering of engines,
translators, and other tools; standardization efforts, such as the recent Rules In-
terchange Format (RIF) activity at W3C; and applications. Rules complement
and extend ontologies on the Semantic Web. They can be used in combination
with ontologies, or as a means to specify ontologies. Rules are also frequently
applied over ontologies, to draw inferences, express constraints, specify poli-
cies, react to events, discover new knowledge, transform data, etc. Rule markup
languages enrich Web ontologies by supporting publishing rules on the Web, ex-
change rules between different systems and tools, share guidelines and policies,
merge and maintain rulebases, and more. Yet, whereas the mark-up language
OWL for Semantic Web ontologies is already undergoing the second round of
the standardization process at W3C, the debate around a RIF is still ongoing.
Because of the great variety in rule languages and rule engine technologies, this
format will consist of a core language to be used along with a set of standard
and non-standard extensions. These extensions need not all be combinable into a
single unified language. As for the expressive power, two directions are followed:
monotonic extensions towards full First Order Logic (FOL) and non-monotonic
extensions based on the Logic Programming tradition, i.e. on Clausal Logics
(CLs). Since the design of OWL has been based on Description Logics (DLs) [1]
(more precisely on the SH family of very expressive DLs [13]), non-monotonic
rule languages for the Semantic Web will most likely be inspired by old hybrid
Knowledge Representation (KR) systems such as AL-log [6] and Carin [17] that
integrate DLs and (fragments of) CLs. Such rule formalisms are of interest to
us. Other uses of rules, e.g. in OWL 2, are beyond the scope of the paper.
The acquisition of Semantic Web rules is very demanding and can be au-
tomated though partially by applying Machine Learning (ML) algorithms. The
ML approach known under the name of Inductive Logic Programming (ILP) [28]
seems particularly promising for the following reasons. ILP is a form of Concept
Learning rooted into Logic Programming. Thus it has been historically con-
cerned with rule induction from examples and background knowledge within the
KR framework of Horn Clausal Logic (HCL) and with the aim of prediction. The
distinguishing feature of ILP, also with respect to other forms of Concept Learn-
ing, is the use of prior knowledge during the induction process. We claim that
learning Semantic Web rules can be reformulated as learning rules by having on-
tologies as prior knowledge. This may motivate an interest of the Semantic Web
community in ILP. In this paper we take a critical look at three ILP attempts
at learning rules within hybrid DL-CL KR frameworks. From the comparative
analysis of them we shall draw general conclusions that can be considered as
guidelines for further ILP research of interest to the Semantic Web.
The paper is organized as follows. Section 2 first provides essential informa-
tion on the ILP methodological apparatus for non informed readers. Section 3
briefly describes three major forms of integration of DLs and CLs. Section 4
provides a state-of-the-art survey of ILP proposals for the hybrid DL-CL for-
malisms considered in Section 3 and outlines directions of future work. Section 5
concludes the paper with final remarks. Appendixes A and B provide the basic
notions of DLs and CLs, respectively.
2 Learning rules with ILP
Inductive Logic Programming (ILP) was born at the intersection between Con-
cept Learning and Logic Programming. From Concept Learning it has inherited
the inferential mechanisms for induction, the most prominent of which is gener-
alization. A distinguishing feature of ILP with respect to other forms of Concept
Learning is the use of background knowledge (BK). From Logic Programming
it has borrowed the KR framework, i.e. HCL.
In Concept Learning, thus in ILP, generalization is traditionally viewed as
search through a partially ordered space of inductive hypotheses [26]. Accord-
ing to this vision, an inductive hypothesis is a clausal theory and the induction
of a single clause requires (i) structuring, (ii) searching and (iii) bounding the
space of clauses [28]. First we focus on (i) by clarifying the notion of ordering for
clauses. An ordering allows for determining which one, between two clauses, is
more general than the other. Since partial orders are considered, uncomparable
pairs of clauses are admitted. One such ordering is θ-subsumption [29]: Given two
clauses C and D, we say that C θ-subsumes D if there exists a substitution θ,
such that Cθ ⊆ D1 . Given the usefulness of BK, orders have been proposed that
reckon with it. Among them, generalized subsumption [2] is of major interest to
this paper: Given two definite clauses C and D standardized apart and a definite
program K, we say that C K D iff there exists a ground substitution θ for C
such that (i) head(C)θ = head(D)σ and (ii) K ∪ body(D)σ |= body(C)θ where σ
is a Skolem substitution for D with respect to {C}∪K. Generalized subsumption
is also called semantic generality in contrast to θ-subsumption which is a purely
syntactic generality. In the general case, generalized subsumption is undecidable
and does not introduce a lattice on a set of clauses. Because of these problems,
θ-subsumption is more frequently used in ILP systems. Yet for Datalog gener-
alized subsumption is decidable and admits a least general generalization. Once
structured, the space of hypotheses can be searched (ii) by means of refinement
operators. A refinement operator is a function which computes a set of special-
izations or generalizations of a clause according to whether a top-down or a
bottom-up search is performed. The two kinds of refinement operator have been
therefore called downward and upward, respectively. The definition of refinement
operators presupposes the investigation of the properties of the various orderings
and is usually coupled with the specification of a declarative bias for bounding
the space of clauses (iii). Bias concerns anything which constrains the search for
theories, e.g. a language bias specifies syntactic constraints on the clauses in the
search space.
Induction with ILP generalizes from individual instances/observations in the
presence of BK, finding valid hypotheses. Validity depends on the underlying set-
ting. At present, there exist several formalizations of induction in ILP that can
be classified according to the following two orthogonal dimensions: the scope of
induction (discrimination vs characterization) and the representation of observa-
tions (ground definite clauses vs ground unit clauses) [5]. Discriminant induction
aims at inducing hypotheses with discriminant power as required in tasks such
as classification. In classification, observations encompass both positive and neg-
ative examples. Characteristic induction is more suitable for finding regularities
in a data set. This corresponds to learning from positive examples only. The
second dimension affects the notion of coverage, i.e. the condition under which a
hypothesis explains an observation. In learning from entailment, hypotheses are
clausal theories, observations are ground definite clauses, and a hypothesis cov-
ers an observation if the hypothesis logically entails the observation. In learning
from interpretations, hypotheses are clausal theories, observations are Herbrand
interpretations (ground unit clauses) and a hypothesis covers an observation if
the observation is a model for the hypothesis.
3 KR behind Semantic Web Rules
The definition of a rule language for the Semantic Web follows the tradition
of KR research on hybrid systems, i.e. those systems which are constituted by
1
See Appendix B for details of set notation for clauses.
two or more subsystems dealing with distinct portions of a single KB by per-
forming specific reasoning procedures [10]. The motivation for investigating and
developing such systems is to improve on two basic features of KR formalisms,
namely representational adequacy and deductive power, by preserving the other
crucial feature, i.e. decidability. Indeed DLs and CLs are FOL fragments in-
comparable as for the expressiveness and the semantics2 but combinable under
certain conditions [30]. In particular, combining DLs with HCL can easily yield
to undecidability if the interaction scheme between the DL and the CL part of
an hybrid KB does not fulfill the condition of safeness, i.e. does not solve the
semantic mismatch between DLs and CLs [27,31].
A comprehensive study of the effects of combining DLs and CLs (more pre-
cisely, Horn rules) can be found in [17]. Special attention is devoted to the DL
ALCN R. The results of the study can be summarized as follows: (i) answering
conjunctive queries over ALCN R TBoxes is decidable, (ii) query answering in
ALCN R extended with non-recursive Datalog rules, where both concepts and
roles can occur in rule bodies, is also decidable, as it can be reduced to an-
swering a union of conjunctive queries (UCQ)3 , (iii) if rules are recursive, query
answering becomes undecidable, (iv) decidability can be regained by disallow-
ing certain combinations of constructors in the logic, and (v) decidability can
be regained by requiring rules to be role-safe, where at least one variable from
each role literal must occur in some non-DL-atom. The integration framework
proposed in [17] and known as Carin is therefore unsafe. Reasoning in Carin
is based on constrained SLD-resolution, i.e. an extension of SLD-resolution with
a tableau calculus for DLs to deal with DL literals in the rules. Constrained
SLD-refutation is a complete and sound method for answering ground queries.
AL-log [6] is a safe hybrid KR system that integrates ALC [34] and Datalog
[4]. In particular, variables occurring in the body of rules may be constrained
with ALC concept assertions to be used as ’typing constraints’. This makes
rules applicable only to explicitly named objects. As in Carin, query answering
is decided using the constrained SLD-resolution which however in AL-log is
decidable and runs in single non-deterministic exponential time.
The hybrid KR framework of DL+log [32] allows for the tight integration of
Datalog¬∨ [7] with DLs. More precisely, it allows a DL KB to be extended with
weakly-safe Datalog¬∨ rules. The condition of weak safeness allows to overcome
the main representational limits of the approaches based on the DL-safeness con-
dition, e.g. the possibility of expressing UCQs, by keeping the integration scheme
still decidable. To a certain extent, DL+log is between AL-log and Carin. For
DL+log two semantics have been defined: a FOL semantics and a nonmonotonic
(NM) semantics. In particular, the latter extends the stable model semantics
2
Remind that the OWA holds for DLs whereas CWA is valid in CLs. Note that the
OWA and CWA have a strong influence on the results of reasoning.
3
A UCQ over a predicate alphabet P is a FOL sentence of the form ∃X.conj1 (X) ∨
. . . ∨ conjn (X), where X is a tuple of variable symbols and each conji (X) is a set
of atoms whose predicates are in P and whose arguments are either constants or
variables from X. A CQ corresponds to a UCQ in the case when n = 1.
Table 1. Three KR frameworks suitable for representing Semantic Web rules.
Carin [17] AL-log [6] DL+log [32]
DL language any DL ALC any DL
CL language Horn clauses Datalog clauses Datalog¬∨ clauses
integration unsafe safe weakly-safe
rule head literals DL/Horn literals Datalog literal DL/Datalog literals
rule body literals DL/Horn literals ALC/Datalog literals (no DL/Datalog¬ literals
roles)
semantics Herbrand models+DL models idem stable models+DL models
reasoning SLD-resolution+tableau calculus idem stable model computation +
Boolean CQ/UCQ contain-
ment
decidability only for some instantiations yes for all instantiations with
DLs for which the Boolean
CQ/UCQ containment is de-
cidable
implementation n.a.(?) n.a.(?) n.a.
of Datalog¬∨ [11]. According to it, DL-predicates are still interpreted under
OWA, while Datalog predicates are interpreted under CWA. Notice that, un-
der both semantics, entailment can be reduced to satisfiability and, analogously,
that CQ answering can be reduced to satisfiability. The problem statement of
satisfiability for finite DL+log KBs relies on the problem known as the Boolean
CQ/UCQ containment problem 4 in DLs. It is shown that the decidability of rea-
soning in DL+log, thus of ground query answering, depends on the decidability
of the Boolean CQ/UCQ containment problem in DL. Currently, SHIQ+log is
one of the most expressive decidable instantiations of DL+log [12].
The distinguishing features of these three hybrid DL-CL KR frameworks are
summarized in Table 1.
4 ILP for Learning Semantic Web Rules
Hybrid KR systems combining DLs and (fragments of) HCL have very recently
attracted some attention in the ILP community.
4.1 State of the Art
Only three ILP frameworks have been proposed that adopt a hybrid DL-CL rep-
resentation for both hypotheses and background knowledge: [33] chooses Carin-
ALN , [18] resorts to AL-log, and [20] builds upon SHIQ+log. A comparative
analysis of the three is reported in Table 2. They can be considered as attempts
at accommodating ontologies in ILP. Indeed, they can deal with ALN , ALC 5 ,
and SHIQ ontologies respectively. Learning Semantic Web rules with ILP can
be reformulated as learning rules by having ontologies as prior knowledge. Both
proposals have been guided by a similar consideration when extending previous
work in ILP to hybrid DL-CL KR frameworks.
4
This problem was called existential entailment in [17].
5
We remind the reader that ALN and ALC are incomparable DLs.
Learning in Carin-ALN The framework proposed in [33] focuses on dis-
criminant induction and adopts the ILP setting of learning from interpretations.
Hypotheses are represented as Carin-ALN non-recursive rules with a Horn lit-
eral in the head that plays the role of target concept. The coverage relation of
hypotheses against examples adapts the usual one in learning from interpreta-
tions to the case of hybrid Carin-ALN BK. The generality relation between
two hypotheses is defined as an extension of generalized subsumption. Proce-
dures for testing both the coverage relation and the generality relation are based
on the existential entailment algorithm of Carin. Following [33], Kietz studies
the learnability of Carin-ALN , thus providing a pre-processing method which
enables ILP systems to learn Carin-ALN rules [16].
Learning in AL-log In [18], hypotheses are represented as constrained Data-
log clauses that are linked, connected (or range-restricted), and compliant with
the bias of Object Identity (OI)6 . As opposite to [33], this framework is general,
meaning that it is valid whatever the scope of induction (description/prediction)
is. Therefore the literal in the head of hypotheses represents a concept to be either
discriminated from others (discriminant induction) or characterized (character-
istic induction). The generality relation for one such hypothesis language is an
adaptation of generalized subsumption, named B-subsumption, to the AL-log
KR framework. It gives raise to a quasi-order and can be checked with a decid-
able procedure based on constrained SLD-resolution [22]. Coverage relations for
both ILP settings of learning from interpretations and learning from entailment
have been defined on the basis of query answering in AL-log [19]. As opposite to
[33], the framework has been implemented in an ILP system [24]. More precisely,
an instantiation of it for the case of characteristic induction from interpretations
has been considered. Indeed, the system supports a variant of a very popu-
lar data mining task - frequent pattern discovery - where rich prior conceptual
knowledge is taken into account during the discovery process in order to find
patterns at multiple levels of description granularity. The search through the
space of patterns represented as unary conjunctive queries in AL-log and orga-
nized according to B-subsumption is performed by applying an ideal downward
refinement operator [23].
Learning in SHIQ+log The ILP framework presented in [20] represents
hypotheses as SHIQ+log rules restricted to positive Datalog and organizes
them according to a generality ordering inspired by generalized subsumption.
The resulting hypothesis space can be searched by means of refinement operators
either top-down or bottom-up. Analogously to [18], this framework encompasses
both scopes of induction but, differently from [18], it assumes the ILP setting of
learning from interpretations only. Both the coverage relation and the generality
6
The OI bias can be considered as an extension of the UNA from the semantic level
to the syntactic one of AL-log. It can be the starting point for the definition of either
an equational theory or a quasi-order for constrained Datalog clauses.
relation boil down to query answering in SHIQ+log, thus can be reformulated
as satisfiability problems. Compared to [33] and [18], this framework shows an
added value which can be summarized as follows. First, it relies on a more
expressive DL, i.e. SHIQ. Second, it allows for inducing definitions for new DL
concepts, i.e. rules with a SHIQ literal in the head. Third, it adopts a tighter
form of integration between the DL and the CL part, i.e. the weakly-safe one.
Table 2. Three ILP frameworks suitable for learning Semantic Web rules.
Learning in Carin-ALN [33] Learning in AL-log [18] Learning in SHIQ+log [20]
prior knowledge Carin-ALN KB AL-log KB SHIQ+log KB
ontology lang. ALN ALC SHIQ
rule lang. Horn clauses Datalog clauses Datalog clauses
hypothesis lang. Carin-ALN non-recursive rules constrained Datalog clauses SHIQ+log non-recursive rules
target predicate Horn literal Datalog literal SHIQ/Datalog literal
setting interpretations interpretations/entailment interpretations
induction predictive predictive/descriptive predictive/descriptive
generality order extension of [2] to Carin-ALN extension of [2] to AL-log extension of [2] to SHIQ+log
coverage test Carin-ALN query answering AL-log query answering SHIQ+log query answering
ref. operators n.a. downward downward/upward
implementation n.a. partial n.a.
application n.a. yes n.a.
4.2 Directions of Research
From the comparative analysis of the ILP frameworks reviewed in Section 4.1, a
common feature emerges: All proposals resort to Buntine’s generalized subsump-
tion and extend it in a non-trivial way. This choice is due to the fact that, among
the semantic generality orders in ILP, generalized subsumption applies only to
definite clauses, therefore suits well the hypothesis language in all three frame-
works. Following these guidelines, new ILP frameworks can be designed to deal
with more or differently expressive hybrid DL-CL languages according to the
DL chosen (e.g., learning Carin-ALCN R rules), or the clausal language chosen
(e.g., learning recursive Carin rules), or the integration scheme (e.g., learning
Carin rules with DL-literals in the head). An important requirement will be
the definition of a semantic generality relation for hypotheses to take into ac-
count the background knowledge. Of course, generalized subsumption may turn
out to be not suitable for these upcoming ILP frameworks, e.g. for the case of
learning disjunctive DL+log rules. Speaking of which, the inclusion of nonmono-
tonic features like negation and disjunction - admissible in DL+log full - into
the language for hypotheses and background knowledge will strengthen the abil-
ity of the ILP frameworks to deal with incomplete knowledge by performing an
inductive form of commonsense reasoning. One such ability can turn out to be
useful in the Semantic Web, and complementary to reasoning with uncertainty
and under inconsistency.
Also it would be interesting to investigate how the nature of rules (i.e., the
intended context of usage) may impact the learning process as for the scope
of induction and other variables in the learning problem statement. E.g., the
problem of learning AL-log rules for classification purposes differ greatly from
the apparently similar learning problem faced in [24].
Besides theoretical issues, most future work will have to be devoted to imple-
mentation and application. When moving to practice, issues like efficiency and
scalability become of paramount importance. These concerns may drive the at-
tention of ILP research towards less expressive hybrid KR frameworks in order
to gain in tractability, e.g. instantiations of DL+log with DL-Lite [3]. Appli-
cations can come out of some of the many use cases for Semantic Web rules
specified by the RIF W3C Working Group. Considering the current trend to
have rules within ontologies rather than on top of ontologies, it is worthwhile to
explore the possibility of learning rules for ontology evolution according to the
proof-of-concept scenario described in [21].
5 Final remarks
Building rules on top of ontologies for the Semantic Web poses several challenges
not only to KR researchers investigating suitable hybrid DL-CL formalisms but
also to the ML community which has been historically interested in application
areas where the Knowledge Acquisition bottleneck is particularly severe.
In this paper, we have revised the ML literature addressing the problem
of learning hybrid DL-CL rules. Only three ILP works have been found that
propose a solution to this problem [33,18,20]. They adopt Carin-ALN , AL-log
and SHIQ+log as KR framework, respectively. Note that matching Table 2
against Table 1 one may figure out what is the state-of-the-art and what are
the directions of research on Semantic Web rules from the ML viewpoint. Also
he/she can get suggestions on what is the most appropriate among these ILP
frameworks to be implemented for a certain intended application.
Closely related to DL-CL KR systems are the hybrid formalims arising from
the study of many-sorted logics, where a FOL language is combined with a sort
language which can be regarded as an elementary DL [8]. In this respect the study
of a sorted downward refinement [9] can be also considered as a contribution
to the problem of interest to this paper. Finally, some work as been done on
discovering frequent association patterns [15] in the form of DL-safe rules [27].
References
1. F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P.F. Patel-Schneider, ed-
itors. The Description Logic Handbook: Theory, Implementation and Applications
(2nd ed.). Cambridge University Press, 2007.
2. W. Buntine. Generalized subsumption and its application to induction and redun-
dancy. Artificial Intelligence, 36(2):149–176, 1988.
3. D. Calvanese, M. Lenzerini, R. Rosati, and G. Vetere. DL-Lite: Practical Reasoning
for Rich DLs. In V. Haarslev and R. Möller, editors, Proceedings of the 2004
International Workshop on Description Logics (DL2004), volume 104 of CEUR
Workshop Proceedings. CEUR-WS.org, 2004.
4. S. Ceri, G. Gottlob, and L. Tanca. Logic Programming and Databases. Springer,
1990.
5. L. De Raedt and L. Dehaspe. Clausal Discovery. Machine Learning, 26(2–3):99–
146, 1997.
6. F.M. Donini, M. Lenzerini, D. Nardi, and A. Schaerf. AL-log: Integrating Datalog
and Description Logics. Journal of Intelligent Information Systems, 10(3):227–252,
1998.
7. T. Eiter, G. Gottlob, and H. Mannila. Disjunctive Datalog. ACM Transactions
on Database Systems, 22(3):364–418, 1997.
8. A.M. Frisch. The substitutional framework for sorted deduction: Fundamental
results on hybrid reasoning. Artificial Intelligence, 49:161–198, 1991.
9. A.M. Frisch. Sorted downward refinement: Building background knowledge into a
refinement operator for inductive logic programming. In S. Džeroski and P. Flach,
editors, Inductive Logic Programming, volume 1634 of Lecture Notes in Artificial
Intelligence, pages 104–115. Springer, 1999.
10. A.M. Frisch and A.G. Cohn. Thoughts and afterthoughts on the 1988 workshop
on principles of hybrid reasoning. AI Magazine, 11(5):84–87, 1991.
11. M. Gelfond and V. Lifschitz. Classical negation in logic programs and disjunctive
databases. New Generation Computing, 9(3/4):365–386, 1991.
12. B. Glimm, I. Horrocks, C. Lutz, and U. Sattler. Conjunctive query answering for
the description logic SHIQ. Journal of Artificial Intelligence Research, 31:151–
198, 2008.
13. I. Horrocks, P.F. Patel-Schneider, and F. van Harmelen. From SHIQ and RDF
to OWL: The making of a web ontology language. Journal of Web Semantics,
1(1):7–26, 2003.
14. I. Horrocks, U. Sattler, and S. Tobies. Practical reasoning for very expressive
description logics. Logic Journal of the IGPL, 8(3):239–263, 2000.
15. J. Józefowska, A. Lawrynowicz, and T. Lukaszewski. Towards discovery of frequent
patterns in description logics with rules. In A. Adi, S. Stoutenburg, and S. Tabet,
editors, Rules and Rule Markup Languages for the Semantic Web, volume 3791 of
Lecture Notes in Computer Science, pages 84–97. Springer, 2005.
16. J.-U. Kietz. Learnability of description logic programs. In S. Matwin and C. Sam-
mut, editors, Inductive Logic Programming, volume 2583 of Lecture Notes in Arti-
ficial Intelligence, pages 117–132. Springer, 2003.
17. A.Y. Levy and M.-C. Rousset. Combining Horn rules and description logics in
CARIN. Artificial Intelligence, 104:165–209, 1998.
18. F.A. Lisi. Building Rules on Top of Ontologies for the Semantic Web with Inductive
Logic Programming. Theory and Practice of Logic Programming, 8(03):271–300,
2008.
19. F.A. Lisi and F. Esposito. Efficient Evaluation of Candidate Hypotheses in AL-log.
In R. Camacho, R. King, and A. Srinivasan, editors, Inductive Logic Programming,
volume 3194 of Lecture Notes in Artificial Intelligence, pages 216–233. Springer,
2004.
20. F.A. Lisi and F. Esposito. Foundations of Onto-Relational Learning. In F. Železný
and N. Lavrač, editors, Inductive Logic Programming, volume 5194 of Lecture Notes
in Artificial Intelligence, pages 158–175. Springer, 2008.
21. F.A. Lisi and F. Esposito. Learning SHIQ+log Rules for Ontology Evolution.
In A. Gangemi, J. Keizer, V. Presutti, and H. Stoermer, editors, Semantic Web
Applications and Perspectives (SWAP2008), volume 426 of CEUR Workshop Pro-
ceedings. CEUR-WS.org, 2008.
22. F.A. Lisi and D. Malerba. Bridging the Gap between Horn Clausal Logic and
Description Logics in Inductive Learning. In A. Cappelli and F. Turini, editors,
AI*IA 2003: Advances in Artificial Intelligence, volume 2829 of Lecture Notes in
Artificial Intelligence, pages 49–60. Springer, 2003.
23. F.A. Lisi and D. Malerba. Ideal Refinement of Descriptions in AL-log. In T. Hor-
vath and A. Yamamoto, editors, Inductive Logic Programming, volume 2835 of
Lecture Notes in Artificial Intelligence, pages 215–232. Springer, 2003.
24. F.A. Lisi and D. Malerba. Inducing Multi-Level Association Rules from Multiple
Relations. Machine Learning, 55:175–210, 2004.
25. J.W. Lloyd. Foundations of Logic Programming. Springer, 2nd edition, 1987.
26. T.M. Mitchell. Generalization as search. Artificial Intelligence, 18:203–226, 1982.
27. B. Motik, U. Sattler, and R. Studer. Query Answering for OWL-DL with Rules.
In S.A. McIlraith, D. Plexousakis, and F. van Harmelen, editors, The Semantic
Web, volume 3298 of Lecture Notes in Computer Science, pages 549–563. Springer,
2004.
28. S.-H. Nienhuys-Cheng and R. de Wolf. Foundations of Inductive Logic Program-
ming, volume 1228 of Lecture Notes in Artificial Intelligence. Springer, 1997.
29. G.D. Plotkin. A note on inductive generalization. Machine Intelligence, 5:153–163,
1970.
30. R. Rosati. On the decidability and complexity of integrating ontologies and rules.
Journal of Web Semantics, 3(1):61–73, 2005.
31. R. Rosati. Semantic and computational advantages of the safe integration of on-
tologies and rules. In F. Fages and S. Soliman, editors, Principles and Practice
of Semantic Web Reasoning, volume 3703 of Lecture Notes in Computer Science,
pages 50–64. Springer, 2005.
32. R. Rosati. DL+log: Tight Integration of Description Logics and Disjunctive Dat-
alog. In P. Doherty, J. Mylopoulos, and C.A. Welty, editors, Proc. of Tenth In-
ternational Conference on Principles of Knowledge Representation and Reasoning,
pages 68–78. AAAI Press, 2006.
33. C. Rouveirol and V. Ventos. Towards Learning in CARIN-ALN . In J. Cussens
and A. Frisch, editors, Inductive Logic Programming, volume 1866 of Lecture Notes
in Artificial Intelligence, pages 191–208. Springer, 2000.
34. M. Schmidt-Schauss and G. Smolka. Attributive concept descriptions with com-
plements. Artificial Intelligence, 48(1):1–26, 1991.
A Description Logics
DLs are a family of decidable FOL fragments that allow for the specification
of knowledge in terms of classes (concepts), binary relations between classes
(roles), and instances (individuals) [1]. Complex concepts can be defined from
atomic concepts and roles by means of constructors (see Table 3). E.g., concept
descriptions in the basic DL AL are formed according to only the constructors of
atomic negation, concept conjunction, value restriction, and limited existential
restriction. The DLs ALC and ALN are members of the AL family [34]. The
former extends AL with (arbitrary) concept negation (also called complement
and equivalent to having both concept union and full existential restriction),
whereas the latter with number restriction. The DL ALCN R adds to the con-
structors inherited from ALC and ALN a further one: role intersection (see
Table 3. Syntax and semantics of DLs.
bottom (resp. top) concept ⊥ (resp. >) ∅ (resp. ∆I )
atomic concept A A I ⊆ ∆I
(abstract) role R RI ⊆ ∆I × ∆I
(abstract) inverse role R− (RI )−
(abstract) individual a a I ∈ ∆I
concept negation ¬C ∆I \ C I
concept intersection C1 u C2 C1I ∩ C2I
concept union C1 t C2 C1I ∪ C2I
value restriction ∀R.C {x ∈ ∆I | ∀y (x, y) ∈ RI → y ∈ C I }
existential restriction ∃R.C {x ∈ ∆I | ∃y (x, y) ∈ RI ∧ y ∈ C I }
at least number restriction ≥ nR {x ∈ ∆I | |{y|(x, y) ∈ RI }| ≥ n}
at most number restriction ≤ nR {x ∈ ∆I | |{y|(x, y) ∈ RI }| ≤ n}
at least qualif. number restriction ≥ nS.C {x ∈ ∆I | |{y ∈ C I |(x, y) ∈ S I }| ≥ n}
at most qualif. number restriction ≤ nS.C {x ∈ ∆I | |{y ∈ C I |(x, y) ∈ S I }| ≤ n}
role intersection R1 u R2 R1I ∩ R2I
concept equivalence axiom C1 ≡ C2 C1I = C2I
concept subsumption axiom C1 v C2 C1I ⊆ C2I
role equivalence axiom R≡S RI = S I
role inclusion axiom RvS RI ⊆ S I
concept assertion a:C aI ∈ C I
role assertion ha, bi : R (aI , bI ) ∈ RI
individual equality assertion a≈b aI = bI
individual inequality assertion a 6≈ b aI 6= bI
Table 3). Conversely, in the DL SHIQ [14] it is allowed to invert roles and to
express qualified number restrictions of the form ≥ nS.C and ≤ nS.C where S
is a simple role (see Table 3). Also transitivity holds for roles.
A DL knowledge base (KB) can state both is-a relations between concepts
(axioms) and instance-of relations between individuals (resp. couples of indi-
viduals) and concepts (resp. roles) (assertions). Concepts and axioms form the
so-called TBox (Terminological Box, or intensional part of a DL KB) whereas
individuals and assertions form the so-called ABox (Assertional Box, or exten-
sional part of a DL KB). A SHIQ KB encompasses also a RBox (Role Box)
which consists of axioms concerning abstract roles. The direct semantics of DLs
is shown in Table 3. An interpretation I = (∆I , ·I ) for a DL KB consists of
a domain ∆I and a mapping function ·I . Individuals are mapped to elements
of ∆I such that aI 6= bI if a 6= b (Unique Names Assumption (UNA). Yet in
SHIQ UNA does not hold by default [12]. Thus individual equality (inequality)
assertions may appear in a SHIQ KB (see Table 3). Also the KB represents
many different interpretations, i.e. all its models. This is coherent with the Open
World Assumption (OWA) that holds in FOL semantics. The main reasoning
task for a DL KB is the consistency check that is performed by applying decision
procedures based on tableau calculus. Decidability of reasoning is crucial in DLs.
B Clausal Logics
The basic element in Clausal Logics (CLs) is the atom of the form p(ti , . . . , tki )
such that each p is a predicate symbol and each tj is a term. A term is either a
constant or a variable or a more complex term obtained by applying a functor
to simpler term. Constant, variable, functor and predicate symbols belong to
mutually disjoint alphabets. A literal is an atom either negated or not. A clause
is a universally quantified disjunction of literals. Usually the universal quantifiers
are omitted to simplify notation, therefore a clause is a disjunctive formula like
h1 ∨ . . . ∨ hn ∨ ¬b1 ∨ . . . ∨ ¬bm
or a set of literals
{h1 , . . . , hn , ¬b1 , . . . , ¬bm }
or, according to the most widely used alternative notation, an implication
h1 ∨ . . . ∨ hn ← b1 ∧ . . . ∧ bm
whose right-hand side and left-hand side are called head and body of the clause,
respectively. A program is a set of clauses. The most studied CL is called Horn
Clausal Logic (HCL). It admits only so-called definite clauses, i.e. clauses with
n = 1, which are called rules and facts for m > 0 and m = 0 respectively. Definite
clauses are at the basis of logic programming [25] and deductive databases [4].
In the logic programming context, the model-theoretic semantics of HCL
is based on the notion of Herbrand interpretation. The corresponding proof-
theoretic semantics is based on the Closed World Assumption (CWA) and is the
starting point for a deductive reasoning mechanism, i.e. SLD-resolution, which
is sound and complete by refutation.
In the deductive database context, a version of HCL free from functors and
recursion leads to Datalog [4]. The main reasoning task in Datalog is query
answering. A query Q to a Datalog program D is a Datalog clause with
n = 0 and m > 0. An answer to a query Q is a substitution θ for the variables
of Q. An answer is correct with respect to the Datalog program D if D |=
Qθ. The answer set to a query Q is the set of answers to Q that are correct
w.r.t. D and such that Qθ is ground. Answers are computed by SLD-refutation.
Disjunctive Datalog (Datalog∨ ) is a variant of Datalog where disjunctions
may appear in the rule heads [7]. Advanced versions (Datalog¬∨ ) also allow for
negated literals in the rule bodies, which can be handled according to a semantics
for negation in CL, e.g. stable model semantics [11]. Under such semantics, a
Datalog¬∨ program may have several alternative models (but possibly none),
each corresponding to a possible view of the reality.