We study query entailment in extensions of the description logic (DL) SQ allowing number restrictions (Q) to be applied to transitive roles (S). Most previous work on query entailment in expressive DLs, such as SHIQ or SHOQ, forbid the interaction of number restrictions and transitive roles [2{4], but it is required in areas like biomedicine, e.g., to restrict the number of certain parts an organ has. For instance, one can express that the human heart has exactly one mitral valve, which has to be shared by its left and right atrium [5]. Allowing for the interaction of S and Q is dangerous in the sense that even modest extensions of SQ, such as with role inclusions or inverse roles, lead to an undecidable satis ability problem [6]. Decidability of satis ability in SQ and in its extension with nominals was shown several years ago [6, 7], but only recently tight computational complexity bounds were established [8]. Even more recently, decidability for entailment of regular path queries over SQ knowledge bases was established. More precisely, based on a novel tree-like model property of SQ it was possible to devise an automata-based decision procedure yielding a tight 2ExpTime upper bound [5].
nite query entailment in SQ is interesting since, due to the presence of
transitivity, SQ lacks nite controllability, and therefore unrestricted and
nite entailment do not coincide. Interestingly, most previous works on
nite query entailment consider logics lacking nite controllability because of
number restrictions and inverse roles [9{12]. The study of nite query
entailment in logics with transitivity (without number restrictions on transitive
roles) started only recently [13{15]. Here, we focus on nite entailment of
9
positive existential queries in SOQ and of instance queries in SIQ .
Contributions. We start by showing a tree-like model property for both SOQ
9
and SIQ . More speci cally, we carefully extend and adapt the canonical tree
decompositions that were introduced for SQ in previous work [
Outlook. This study provides a step towards a complete picture of query entailment in DLs with number restrictions on transitive roles. There are several natural next steps involving nite entailment. For SIQ9 the rst thing to do is to cover the full logic; the second thing is to go beyond instance queries. In general, it would be interesting to study data complexity and consider transitive closure instead of transitivity.