=Paper=
{{Paper
|id=Vol-477/paper-42
|storemode=property
|title=A Semantic Algebra for Modularized Description Logics Knowledge Bases
|pdfUrl=https://ceur-ws.org/Vol-477/paper_67.pdf
|volume=Vol-477
|dblpUrl=https://dblp.org/rec/conf/dlog/GoczylaWW09
}}
==A Semantic Algebra for Modularized Description Logics Knowledge Bases==
https://ceur-ws.org/Vol-477/paper_67.pdf
A Semantic Algebra for Modularized Description
Logics Knowledge Bases
Krzysztof Goczyła, Aleksander Waloszek, Wojciech Waloszek
Gdańsk University of Technology, Department of Software Engineering,
ul. Gabriela Narutowicza 11/12, 80-233 Gdańsk, Poland
{kris,alwal,wowal}@eti.pg.gda.pl
1 Introduction
Subsequent years bring increasing attention into the area of modularization of
Description Logics (DL) knowledge bases. The main motivation is the hope to
reach the maturity of the collaborative ontology development and reuse process
comparable to the one achieved by software engineering methods in the case of
software modules. As a consequence many methods and techniques of ontology
decomposition and merging have been devised.
From the mathematical point of view a very useful method to describe a
system of complex operations on ontologies would be an algebra. There were
many attempts to create algebras for ontology modules. Two notable examples
come from [1] and [8]. These algebras treat modules as sets of sentences (as
in the case of [1]) or more complex syntactic structures (like in the case of
[8]). We found this approach unsatisfying, and decided to turn toward algebras
of interpretations. This decision was motivated by two important observations.
The first observation is that the most straightforward definitions of syntactic
algebras do not seem to capture the intended meaning, which is to some extent
a consequence of the fact that the different sets of sentences may have the same
interpretations (we further discuss this issue in Sec. 4).
The second observation is that semantic approach to defining algebra can be
regarded more fundamental than syntactic (or deductive) ones. By using sen-
tences we are in fact eliminating unwanted interpretations. Therefore, by oper-
ating on sets of sentences, we in fact operate on interpretations: every “syntactic”
algebra determines a “semantic” algebra. Study of an algebra operating on inter-
pretations, may be therefore treated as a good theoretical background for design
of any practical “syntactic” algebra operating on linguistic representations.
In this paper we propose an algebra operating on semantic modules. We called
our formalism s-module algebra (“s” stands for “semantic”). Section 3.1 contains
definitions of s-module and algebraic operations. In Section 3.2 we show that our
algebra is fully homomorphic to relational and cylindric algebras, which gives us
a very strong framework for exploring its properties. In Section 4 we discuss the
role of s-module algebra and relevance of choice of operators. Section 5 concludes
the paper.
2 Preliminaries
In the further discussion we assume that we use an arbitrary chosen description
logics L.
We exploit the notion of a signature, denoted S = AC ] AR ] Ind and
assume that for any L it is a disjoint union of concept names (AC), role names
(AR), and individual names (Ind). To refer to specific part of the signature S
we use the notation AC(S), AR(S), Ind(S) respectively. We assume that there
exist sets of acceptable concepts, roles, and individual names, which we denote
NAC , NAR , NInd respectively (AC ⊆ NAC , AR ⊆ NAR , Ind ⊆ NInd ). The full
signature S b contains all the names (S b = NAC ] NRA ] NInd ).
Chosen description logics L determines the set of (possibly complex) con-
cepts, roles and individuals that can be built using the operators of L and names
from a signature S. We denote these sets with LC (S), LR (S), LI (S) respectively.
For instance, if L is ALC, LC (S) ::= A | ¬C | C u D | C t D | ∃R.C | ∀R.C | > | ⊥
where A ∈ AC(S), C, D ∈ LC (S), R ∈ LR (S).
An (base) interpretation I is a pair (∆I , ·I ) where ∆I is a set called the
domain of the interpretation and ·I is an interpretation function assigning each
A ∈ NAC a set AI ⊆ ∆, each R ∈ NAR a binary relation RI ⊆ ∆ × ∆, and
each a ∈ NInd an element aI of the domain ∆I . Note that following [4] we as-
sume that every interpretation interprets all the base symbols. Each description
logic L establishes its own rules of extending the base interpretation to complex
concepts (e.g. in ALC (C u D)I = C I ∩ DI ), however in this paper we primar-
ily focus on base interpretations (this is not really a restriction, since for every
description logic there is one-to-one correspondence between base and extended
interpretation). The class of all (base) interpretations we denote as I.
Each description logic allows for formulating axioms and assertions (sen-
tences), and define the conditions under which a specific interpretation I satis-
fies a particular sentence. We denote the set of axioms and assertions which can
be built from the given signature S as L(S). The fact that the interpretation I
satisfies a given sentence α ∈ L(S) (is its model) is denoted as I |= α.
From the point of view of s-module algebra some selected operations on
interpretations are particularly interesting. These operations are: interpretation
projection (to the given signature) and interpretation restriction (to the given do-
main). Given the set of interpretations
I and the signature S we define the inter-
pretation projection I|S as J ∈ I : ∃I ∈ I : ∆I = ∆J ∧ ∀X ∈ S : X I = X J .
We simplify the notation and instead of {I}|S we write I|S remembering that
we will obtain a set of interpretations as the result. Note that always I ⊆ I|S.
The notion of signature restriction is similar to coincidence of two interpre-
tations on signature S [4]. We say that I and J coincide on a signature S
(notation I|S = J |S ) if ∆I = ∆J and X I = X J for every X ∈ S. Note that
I|S = {J ∈ I : ∃I ∈ I : I|S = J |S }.
The restriction of an interpretation I to the domain ∆0 , denoted by I ∩ ∆0 ,
0 0
is an interpretation I 0 = (∆0 , ·I ) such that X I = X I ∩ ∆0 for every X.
3 S-module algebra
3.1 Basic definitions
The basic element of the universe of the s-module algebra is a semantic module
defined below.
Definition 1 (s-module). A s-module M = (S, W) is a pair of a signature S
(called a signature of the s-module) and a class W of interpretations, such that
W|S = W. The two parts of M are denoted respectively as S(M ) and W(M ).
Each interpretation from W is called a model of M.
According to this definition each module simply consists of all its models.
Models of a specific s-module M cannot express relationships between concepts,
roles, and individuals from outside the signature S, which is guaranteed by the
condition W|S = W. We say that s-module satisfies a particular sentence α ∈ L,
which we denote M |= α, iff ∀I ∈ W(M ) : I |= α.
Models of even very simple s-modules form a proper class because of the fact
that any domain set can be used in each interpretation from W. In practice
we may, without much loss of generality of the formalism, assume that all the
domains of the interpretations in W are subsets of some given set ∆. Under this
assumption W is a set. Note that this assumption differs slightly from fixed-
domain assumption as we do not fix the domain but restrict it to be a subset of
the given (possibly very large) set.
From the point of view of a user of the algebra, each model may be perceived
as a one “possible world” or (to avoid confusion with modal logics) just a “possi-
bility”. The s-module algebra provides the user with operators for manipulating
sets of “possibilities”.
In the process of combining knowledge from different s-modules we distin-
guished three categories of activities:
1. Operations on signatures of the modules, e.g. extending the vocabulary,
2. Operations relating on the whole classes of models of s-modules without
specifying new relationships between concepts, roles, and individuals (terms),
3. Operations introducing new relationships between terms.
For each category we introduced a set of operators. Below we give their formal
definitions. For the sake of simplicity, we assume that description logic L and
domain set ∆ are chosen (in fact none of these assumptions is indispensable).
In all definitions we denote the set of all modules as M, the set of all signatures
as S, and the set of all interpretations as I.
To support the first category of activities we introduce the operations of
signature extension (), projection (π) and rename (ρ), which allow for adding,
removing and changing names in the vocabulary.
S (M ) = (S(M ) ∪ S, W(M )) S∈S
πS (M ) = (S, W(M )|S) S ⊆ S(M )
ργ (M ) = (γ(S(M )), γ(W(M ))) γ is a signature mapping
Extension operation extends a signature of a given module M by names in a
given signature S. The allowed set of interpretations is preserved, and so are the
relationships between original concepts, roles, and individuals (e.g. if M |= α,
α ∈ L(S(M )), then S (M ) |= α).
Projection operation reduces the signature of a given module. The relation-
ships between the original concepts roles and individuals whose names remain
in the signature are preserved (e.g. if M |= α, α ∈ L(S), then πS (M ) |= α).
Rename operation uses the notion of a signature mapping. Signature mapping
γ is a triple of three functions (γC , γR , γI ) each of them being a bijection from
N to N . By γ(S) we mean γC (AC(S)) ] γR (AR(S)) ] γI (Ind(S)), and by γ(I)
0
where I is an interpretation we denote the interpretation I 0 such that ∆I = ∆I
0
and γ(X)I = X I for every X. Rename preserves the relationships between
concepts, roles, and individuals, however with respect to their name changes (e.g.
if M |= α, α ∈ L(S(M )), then ργ (M ) |= γ(α), where by γ(α) we understand the
transformed α sentence in which all the names were systematically changed in
accordance with γ).
For the second category of activities we introduce the operators of union (∪),
intersection (∩) and complement (¬) operating on the set of models.
M1 ∪ M2 = (S(M1 ), W(M1 ) ∪ W(M2 )) S(M1 ) = S(M2 )
M1 ∩ M2 = (S(M1 ), W(M1 ) ∩ W(M2 )) S(M1 ) = S(M2 )
¬M = (S(M ), I − W(M ))
Union, intersection and complement operations perform respective set-theo-
retic operations on sets of models of the s-modules. The condition that S(M1 ) =
S(M2 ) is not very restrictive because we can easily extend the binary operations
to generalized ones. For example, generalized union ∪g can be defined as M1 ∪g
M2 = S(M2 ) (M1 ) ∪ S(M1 ) (M2 ).
Union and complement operators are (along with projection) non-linguistic
(strictly semantic), i.e. their use may lead to generation of a s-module M for
which there does not exist any corresponding set of sentences S in L. This issue
will be elaborated on in the further part of the paper.
The above definitions of s-module and operations do not depend on any
particular logic. However, in the third category of operations we have to choose
a language for relating terms. We have made the assumption that we use one
of the standard Description Logics. Similarly like for RDBs, to relate two terms
from different s-modules, an algebra user have to combine the two modules first
(using union, intersection or difference) and then formulate DL sentences (e.g.
axioms like C ⊆ D) constraining the set of models to those which satisfy the
sentences. To permit the user to do the latter we introduce the selection (σ)
operation.
σα (M ) = (S(M ), {I ∈ W(M ) : I |= α}) α ∈ L(S(M ))
Selection operation leaves in the module only these interpretations that are
models of a chosen sentence α. Obviously σα (M ) |= α.
It is easy to show that the outcome of all of the defined operations is a
s-module itself (principally, it satisfies the condition W(M ) = W(M )|S(M )).
3.2 General properties of the algebra
In this section we present some basic algebraic laws for s-module algebra. One
of the main results in this section is that Codd’s relational algebra laws are also
valid for s-module algebra. In order to transfer the laws we need to create a proper
analogy between the two models. In this analogy a s-module is a counterpart to
a single relation. The signature of a s-module is analogous to relation schema
(i.e. names of the attributes). Consequently the set of models corresponds to
a set of tuples contained in a relation. And since each axiom constrain the set
of possible models, their influence is analogous to θ-restrictions, which (used in
selection) reduce the number of tuples in a relation.
The analogy with RDBs is strong enough to ensure that relational algebra
laws are also valid for s-module algebra. This result comes from the fact that both
algebras are variants of cylindric algebras described in [5]. For relational algebra
it has been shown in [6]. More precisely the authors of [6] show a correspondence
between relational and diagonal-free cylindric algebra.
Let us recall the definition of this cylindric algebra [5]:
Definition 2. A diagonal free cylindric algebra of dimension ω is a structure
(A, +, ·, −, 0, 1, ci ), i ∈ [1..ω), such that 0 and 1 are distinguished elements of A,
− and ci are unary operators on A, + and · are binary operators on A; and the
following conditions are satisfied for any x, y ∈ A and any j, k ∈ [1..ω):
(C0 ) (A, +, ·, −, 0, 1) is a Boolean algebra
(C1 ) cj 0 = 0
(C2 ) x · cj x = x
(C3 ) cj (x · cj y) = cj x · cj y
(C4 ) cj ck x = ck cj x
We will show that s-module algebra is homomorphic to a diagonal free cylin-
dric algebra of dimension ω. An issue we have to deal here with is rather technical
and concerns module signature. We deal with this problem in the following way.
We establish an equivalence relation =l between modules such that M1 =l M2
iff W(M1 ) = W(M2 ). We may identify the equivalence class [M ]=l (we skip the
=l symbol henceforth, writing simply [M ]) with the module M ↑ = (S, b W(M ))
↓ ↓ ↓
or the module M = (S (M ), W(M )) where by S (M ) we mean the smallest
signature S such that W(πS (M )) = W(M ). We then prove that the algebra
over M/ =l with slightly redefined operators satisfies the requirements (C0 ) to
(C4 ).
b = ω the structure (M/ =l , ∪l , ∩l , ¬l , [M̌ ], [M̂ ],
Theorem 1. Provided that |S|
b
rX ) where X ∈ S and
M̌ = (∅, ∅)
M̂ = (∅, I)
[M1 ] ∪l [M2 ] = [M1 ∪g M2 ]
[M1 ] ∩l [M2 ] = [M1 ∩g M2 ]
¬l [M ] = [¬M ]
rX [M ] = πS(M)−{X} (M )
is a diagonal free cylindric algebra of dimension ω.
Proof (sketch). We show that conditions (C1 ) to (C4 ) are satisfied (M1 , M2 are
any modules from M; X, Y are any terms from S): b
(C1 ) rX [M̌ ] = [πS↓ (M)−{X} (M̌ )] = [π∅ (M̌ )] = [M̌ ]
(C2 ) [M1 ] ∩l rX [M1 ] = [M1 ] ∩l [πS(M1 )−{X} (M1 )] =
[M1 ∩g πS↓ (M1 )−{X} (M1 )] = [M1 ∩ S(M1 ) (πS(M1 )−{X} (M1 ))] =
[(S(M1 ), W(M1 ) ∩ W(M1 )|(S↓ (M1 ) − {X}))] = [M1 ]
For proving the next equality we will use the following fact1 (I ∩ J|S)|S =
I|S ∩ J|S.
(C3 ) rX ([M1 ] ∩l rX [M2 ]) = rX ([M1↑ ] ∩l rX [M2↑ ]) =
[πS−{X}
b (M1↑ ∩g πS−{X}
b (M2↑ ))] =
b − {X}, (W(M1) ∩ W(M2 )|(S
[(S b − {X}))|(S
b − {X}))] =
b − {X}, W(M1)|(S
[(S b − {X}) ∩ W(M2 )|(S
b − {X}))] =
[πS−{X}
b (M1↑ ) ∩g πS−{X}
b (M2↑ )] = rX [M1 ] ∩l rX [M2 ]
To prove (C4 ) we will take advantage of the equality: I|S1 |S2 = I|S2 |S1 :
↑ ↑ ↑
(C4 ) rX rY [M1 ] = [πS−{X}
b (πS−{Y
b } (M1 ) ) ] =
b W(M1 )|(S
[(S, b − {Y })|(S
b − {X}))] =
b W(M1 )|(S
[(S, b − {X})|(Sb − {Y }))] =
[πS−{Y
b } (πS−{X}
b (M1↑ )↑ )↑ ] = rY rX [M1 ]
The full proof contains the step showing that operations ∪l , ∩l , ¬l are prop-
erly defined and shows that the condition (C0 ) is also satisfied.
The theorem 1 is very strong and allows us to transfer all laws of cylindric
(and relational) algebra to s-module algebra. The following proposition collects
some of them.
Proposition 1. The following laws hold for s-module algebra:
1. For union, intersection and negation standard set-theoretic laws hold (e.g.
union and intersection are idempotent, associative and commutative).
1
On the basis of the fact that the relation I|S = J |S is associative: I0 ∈ ((I ∩
J|S)|S) ⇔ ∃I ∈ I : ∃J ∈ J : I0 |S = I|S = J |S ⇔ I0 ∈ (I|S ∩ J|S).
2. For projection we have:
a. πS (M ) = πS (πS (M )),
b. πS(M) (M ) = M
c. πS (πS0 (M )) = πS∩S0 (M ) = πS0 (πS (M )),
d. πS (¬M ) = ¬πS (M ),
e. πS (M1 ∪ M2 ) = πS (M1 ) ∪ πS (M2 ),
f. πS (M1 ∩g πS (M2 )) = πS (M1 ) ∩ πS (M2 )
3. For selection we have:
a. σα (M ) = σα (σα (M )),
b. σα (σβ (M )) = σβ (σα (M )),
c. σα (M1 ∪ M2 ) = σα (M1 ) ∪ σα (M2 ),
d. σα (M1 ∩ M2 ) = σα (M1 ) ∩ σα (M2 )
4 Discussion of the Results
By proposing the s-module algebra we do not claim that ontology engineers
should abandon sentences and focus solely on models and interpretations. On
the contrary, we are convinced that linguistic representations (based on sentences
but not necessarily just sets of sentences) are most appropriate for the majority
of engineering tasks. In our intention s-module algebra plays a role of a point of
reference for attempts of creating proper representations of semantics of modules
and, perhaps, proper algebras for manipulating these representations.
Naturally to approve the s-module algebra in the role of such yardstick we
should first agree that the range of offered operations is complete, i.e. suitable
for describing some set of reference problems. The issue is at least to some extent
subjective, but we have an important argument supporting the proposed range.
In the previous part of the paper we showed the strong correspondence be-
tween s-module algebra and Codd’s relational algebra. Although there is no
guarantee that operators used in RDBs are relevant for ontology modules, this
analogy gives us the argument in justifying the proposed range of operators.
“Completeness” (proper choice of operators) for the relational algebra was shown
by Codd with a proof that with algebraic constructions we can express every set
of tuples satisfying a certain expression formulated in a fragment of FOL called
relational calculus [2]. Because it is essentially a feature of cylindric algebra the
s-module algebra has the similar property.
One of the reasons why already created “syntactic” algebras are not, in our
intuition, proper for the role of reference point is the fact that in these approaches
straightforward definitions often fail to capture the intended semantic meaning.
For example, NeOn algebra characterize each module M by the set of sentences
satisfied by it (simplifying a bit and not delving into the details we may denote
the set by {α ∈ L(S)b : M |= α}). The most intuitive way of defining the difference
of two modules (and the one proposed in [1]) M1 − M2 is to say that this is the
module M 0 which satisfies α iff M1 |= α and not M2 |= α. Because M2 satisfies
also all tautologies (e.g. > ≡ >) it follows that M 0 cannot satisfy any tautology,
which is impossible. While there are ways of improving the definition given in the
above example, we believe that problems of this type are hardly avoidable and
to some extent inherent for “syntactic” (or “deductive”) approaches. In contrast,
union, intersection, and negation in s-module algebra, defined in an intuitive
way, naturally form a Boolean algebra.
One problem we have to bear in mind is that simple sets of sentences may
not give enough expressive power to cover the whole range of s-module algebra
operations. Indeed this is the case, and to illustrate it we formalize the issue.
Definition 3 (L-representable s-module). We call an s-module M L-repre-
sentable iff there exists a set of sentences S ⊆ L(S(M )) such that W(M ) =
{I ∈ I : ∀α ∈ S : I |= α}.
In other words L-representable s-modules are the modules whose models are
all the models of a particular set of sentences from L(S(M )). We may denote a
specific L-representable s-module as M (S, S) where S ⊂ L(S), or simply M (S),
if module signature consists of all term used in sentences from S, e.g. M ({A v
B, A(a)}) has the signature {A, B, a}.
While the representation in the form of sentences is convenient, in general we
cannot represent every s-module with a set of DL sentences. Specific algebra op-
erations (namely union, complement and projection) can give the outcome which
is not L-representable even if all operands are. The example below generalizes
even to very expressive logics like SHOIQ.
Example 1 (non-representable s-module). Consider a union M of two ALC-repre-
sentable s-modules M = M ({A v B}) ∪ M ({B v A}). Notice that neither
M |= A v B nor M |= B v A is true. However if we perform the intersection:
M 0 = M ∩g M ({A u ¬B(a), ¬A u B(b)}) we will obtain a s-module with no
models W(M 0 ) = ∅.
The fact that s-module algebra offers greater expressiveness than sets of
sentences stems the problem of transferring the practical results obtained with
use of the algebra to description of practical problems which demand finite and
often linguistic representations. This means that for the transfer of the results we
have to use some “translation” of obtained results to the desired representation.
The kind of “translation” should be appropriate to the problem we want to solve.
One of the possible methods we may consider is rounding. By rounding we
mean reducing or expanding the sets of models to an L-representable one. An
example of rounding function is M ∗ = (S, {I ∈ I : ∀α ∈ L(S(M )) : I |= α ⇔
W |= α}). We have to remember, however, that by using rounding we leave the
world of purely semantic operations. Rounding requires special care with use of
algebra operations (e.g. in general it is not true that M1∗ ∩ M2∗ = (M1 ∩ M2 )∗ )
and it shows its usefulness in situations when we have to describe an issue which
is strictly connected with “syntactic” or “deductive” approach.
To illustrate possible use of rounding, below we show an example of use s-
module algebra for describing problems connected with important and recently
widely discussed subject of safety exploiting the notion of deductive conservative
extension ([7], [4]).
Firstly, let us recall the definition of model conservative extension (by an
ontology O we understand a set of sentences, Sig(O) is a signature containing
all terms used in sentences of O; we assume that we use certain DL L):
Definition 4 (conservative extensions [4]). Given two ontologies O and
O1 ⊆ O, we say that O is a model S-conservative extension of O1 , if for every
model I of O1 , there exists a model J of O such that I|S = J |S . We say that
O is a deductive S-conservative extension of O1 if for every sentence α ∈ L(S)
we have O |= α iff O1 |= α.
Having in mind that I|S = {J ∈ I : ∃I ∈ I : I|S = J |S } (cf. Preliminaries),
it is straightforward to show that, given two ontologies O and O1 ⊆ O, O is a
model S-conservative extension of O1 iff {I : I |= O}|S = {I : I |= O1 }|S. The
following proposition is an immediate corollary:
Proposition 2. Given two ontologies O and O1 ⊆ O: O is a model S-conserva-
tive extension of O1 iff πS (S (M (O))) = πS (S (M (O1 ))); O is a deductive S-
conservative extension of O1 iff πS (S (M (O)))∗ = πS (S (M (O1 )))∗ .
Note that in the above proposition we used rounding to describe a “de-
ductive” notion. Naturally it is also immediate to state that πS (S (M (O)) =
πS (S (M (O1 ))) ⇒ πS (S M (O))∗ = πS (S (M (O1 )))∗ .
The authors of [4] define an important notion of safety for a signature:
Definition 5 (safety for a signature [4]). We say that ontology O is safe for
a signature S if for every ontology O0 with Sig(O) ∪ Sig(O0 ) ⊆ S we have that
O ∩ O0 is a Sig(O0 )-deductive conservative extension of O0 .
This notion is important as it describes an ontology which can safely import
any ontology O0 that shares with it only symbols from S. [4] also provides the
sufficient condition for the safety:
Proposition 3 (safety for a signature vs. model conservative extension
[4]). Let O be an ontology such that O is a model S-conservative extension of
the empty ontology O1 = ∅. Then O is safe for S.
We will prove this proposition with use of s-module algebra. To do this,
according to Definition 5 and Proposition 2 it is sufficient to prove that for
any ontology O0 such that Sig(O) ∪ Sig(O0 ) ⊆ S (\) the following is true:
πSig(O0 ) (M (O0 )) = πSig(O0 ) (M (O) ∩g M (O0 )). From the assumption we have
πS (M (O)) = πS (M (∅)), so, using (\), we can state that πSig(O)∩Sig(O0 ) (M (O)) =
πSig(O)∩Sig(O0 ) (M (∅)) ([). Having this stated, the proof is straightforward:
πSig(O0 ) (M (O) ∩g M (O0 ))
= πSig(O0 ) (M (O) ∩g πSig(O0 ) (M (O0 ))) (by Th. 1 p. 2.b)
= πSig(O0 ) (M (O)) ∩g πSig(O0 ) (M (O0 )) (by Th. 1 p. 2.f)
= πSig(O0 ) (πSig(O) (M (O))) ∩g πSig(O0 ) (M (O0 )) (by Th. 1 p. 2.b)
= πSig(O0 )∩Sig(O) (M (O)) ∩g πSig(O0 ) (M (O0 )) (by Th. 1 p. 2.c)
= πSig(O)∩Sig(O0 ) (M (∅)) ∩g πSig(O0 ) (M (O0 )) (by ([))
0
= πSig(O0 ) (M (O )) (M̂ ∩g M = M )
Although rounding makes each s-module L-representable, we may consider
using different linguistic representations for other purposes. During our study
of decidability problems for s-module algebra we came to the result that repre-
sentation of modules in the form of sets of sentences can be advantageous. The
following definition formalizes the idea.
Definition 6 (L-(2)-representability). We call an s-module M L-(2)-repre-
sentable iff there exists a finite set S = {S1 . . . Sk } of sets of sentences Si ⊆
L(S(M )) such that W(M ) = {I : ∃i ∈ [1..k] : I |= Si }. We call every such
S (2)-representation of M . We call the logic L (2)-representable wrt. a set of
operators A iff every s-module being an outcome of algebraic operations from A
on L-representable s-modules is L-(2)-representable.
(2)-representability is useful because having a (2)-representation of an s-
module we can easily check satisfiability of concept C against the s-module (check
if there exists an interpretation I ∈ W(M ) for which C I 6= ∅). The procedure
consist simply of checking its satisfiability against each set of sentences.2
Proposition 4. SHOIQ is (2)-representable wrt. {, ρ, ∪, ∩, σ}
Proof (sketch). We associate each s-module with sets of sentences (denoted M .
{S1 . . . Sk }) and prove {S1 . . . Sk } is its (2)-representation (claim ([)). The proof
goes by structural induction over the tree of algebraic expressions. Representable
modules of the form M (S) are associated with S (M .{S}), and for these modules
([) obviously holds (which forms the induction basis). Each algebraic operation
produces a new module associated with newly constructed sets:
(M . {S1 . . . Sk }) = M 0 . {S1 . . . Sk }
ργ (M . {S1 . . . Sk }) = M 0 . {γ(Si ) : i ∈ [1..k]}
σα (M . {S1 . . . Sk }) = M 0 . {Si ∪ {α} : i ∈ [1..k]}
M1 . {S11 . . . Sk1 } ∪ M2 . {S12 . . . Sl2 } = M 0 . ({S11 . . . Sk1 } ∪ {S12 . . . Sl2 })
M1 . {S11 . . . Sk1 } ∩ M2 . {S12 . . . Sl2 } = M 0 . {Si1 ∪ Sj2 : i ∈ [1..k], j ∈ [1..l]}
It is straightforward to show that for all the operators (under the induction
hypothesis) claim ([) holds.
Generally, (2)-representations are not strong enough to represent the outcome
of projection (π). The reason for that is the fact that projection πS (M ) may
constrain the signature of the module in the way that some of the sentences may
fall outside L(S).3 Nevertheless, we have to remember these sentences somehow,
as they may imply important relationships between terms in the remaining part
of the signature. To overcome this problem we may separate from S b a special
2
It is worth to note that every L-(2)-representable module is L0 -representable if L0
is the extension of L by disjunctions between sets of sentences (e.g. similarly as
proposed in [9]).
3
Example of which can be found in [10] (Lemma 6).
subset D of “dummy” names and assume that they cannot be a part of s-module
signature but may be used in the sentences in its representation. The following
definition formally shows the idea.
Definition 7 (L-(2)-D-representability). We call an s-module M L-(2)-D-
representable iff there exists a finite set S = {S1 . . . Sk } of sets of sentences Si ⊆
L(S(M ) ∪ D) such that W(M ) = {I : ∃i ∈ [1..k] : I |= Si }|S(M ). We call every
such S (2)-D-representation of M . We call the logic L (2)-D-representable wrt.
a set of operators A iff every s-module being an outcome of algebraic operations
from A on L-representable s-modules is L-(2)-D-representable.
Proposition 5. SHOIQ is (2)-D-representable wrt. {, π, ρ, ∪, ∩, σ}
Proof (sketch). We extend the proof of Proposition 4 by: πS (M . {S1 . . . Sk }) =
S(M) 0
M 0 . {γS (Si ) : i ∈ [1..k]}} Special rename function γSS changes the names
0
from S that fall outside S to unique “dummy” names from D.
Use of dummy names allows us also to handle negation, as shown in the
following proposition.
Proposition 6. SHOIQ is (2)-D-representable wrt. {, ρ, ∪, ∩, ¬, σ}
Proof (sketch). We use the same technique as in the proof of Proposition 4.
For complement (¬) we use the fact that the interpretation not being a model
of M . {S1 . . . Sk } has to contradict at least one sentence from each of the sets
{S1 . . . Sk }. Thus we build a list {Ni } of sets of sentences containing one negated
sentence from each of the sets {S1 . . . Sk }, each Ni = τ¬ ({α1 , α2 , . . . , αk }) , αj ∈
Sj . We negate the sentences using τ¬ translation as follows: C v D we transform
to {x} v C u ¬D; R v S to {x} v ∃R.{y}, {x} v ¬∃S.{y}; Trans(R) to
{x} v ∃R.{y}, {y} v ∃R.{z}, {x} v ¬∃R.{z}; x, y, z are dummy names. The
resulting module is M 0 . {N1 . . . Nl }, where l is the number of sets Ni obtained
with use of the described method.
5 Summary
In this paper we described an algebra, called s-module algebra, operating on
semantically defined modules. We showed that this algebra is homomorphic to
a diagonal free cylindric algebra and, as a consequence, to Codd’s relational
algebra. Basing on this homomorphism we proved some properties of operators
defined for s-module algebra. We also showed some examples of how to use the
algebra to describe selected known problems, e.g. satisfiability in non-linguistic
s-modules or semantic and deductive conservative extension.
For future work we are planning to investigate the wider range of problems
the proposed algebra can be useful to solve. Basing on it we also would like to
derive and investigate algebras, operating on various linguistic representations,
and study their usefulness in covering different tasks.
Acknowledgements. This work was partially supported by Polish Ministry
of Research and Higher Education, project No. N N516 4115 33.
References
1. d’Aquin M. et al.: NeOn Formalisms for Modularization: Syntax, Semantics, Alge-
bra. Neon Project, Deliverable D1.1.3, 2008.
2. Codd E. F.: Relational Completeness of Data Base Sublanguages. In: R. Rustin
(ed.): Database Systems, pp. 65–98, Prentice Hall, also IBM Research Report RJ
987, San Jose, California, 1972.
3. Hall P., Hitchcock P., Todd S.: An algebra of relations for machine computation.
In Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of
programming languages, pp. 225–232, Palo Alto, California, 1975.
4. Grau B. C., Horrocks I., Kazakov Y., Sattler U.: Modular Reuse of Ontologies:
Theory and Practice. In: J. of Artificial Intelligence Research (JAIR), Vol. 31, pp.
273–318, 2008.
5. Henkin, L., Monk J. D., Tarski A. Cylindric Algebras pt. 1, Studies in Logic and
the Foundations of Mathematics, Vol. 64, North-Holland, Amsterdam, 1971.
6. Imielinski T., Lipski W. J.: The Relational Model of Data and Cylindric Algebras.
In: J. Comput. Syst. Sci., Vol. 28, No. 1, pp. 80–102, 1984.
7. Lutz C., Walther D., Wolter F.: Conservative extensions in expressive description
logics. In: Proc. of IJCAI-2007, pp. 453–459, 2007.
8. Mitra P., Wiederhold G.: An Ontology-Composition Algebra. In: Handbook on On-
tologies, pp. 171–216, Germany, 2004.
9. Konev, B., Lutz, C., Walther, D., Wolter, F.: Formal Properties of Modularisation.
In: Modular Ontologies: Concepts, Theories and Techniques for Knowledge Modu-
larization, LNCS 5445, Springer, 2009.
10. Konev, B., Walther, D., Wolter, F.: The Logical Difference Problem for Description
Logic Terminologies. In: Automated Reasoning, Proc. of IJCAR-2008, LNCS 5195,
pp. 259–274, Springer, 2008.