We introduce a very general variety of path description dependencies (PDDs) for an expressive dialect of the FunDL family of description logics called structural PDDs. In general, PDDs enable capturing equality generating dependencies for an ontology in a progressively more fine-grained manner, starting with equality implied by simple alignment of facts about entities through to new structural PDDs in which equality only follows according to a structured alignment of non-empty sets of facts about an entity. We show that logical consequence for this new FunDL dialect is decidable if a given ontology appeals to an exclusive use of structural PDDs, but that logical consequence becomes undecidable when more course grained varieties of PDDs are also allowed in the ontology. An extension to a referring expression type language for defining concepts in this description logic to serve as referring expressions that depend on structural identification is also presented and is tied to a diagnosis of a singularity condition for such concepts to logical consequence of PDDs for an ontology.
Structured data sources abound, and ontology based data access is all about querying such sources via
an ontological understanding of their content. Here, efective ways to communicate answers to queries
will depend critically on communicating references to underlying entities via referring expressions, also
called definite descriptions [
In this paper, we introduce a more expressive variety of such dependencies when an ontological
understanding is expressed in terms of a description logic, in particular, in terms of an expressive dialect
of the FunDL family of description logics [
For example, consider where a document will have a style consisting of sets of sets of keywords, where each top level set is a group of keywords occurring in one of the document’s paragraphs. It will now be possible to identity document styles with exactly the same keywords that are also grouped in exactly the same way. This is illustrated below in which three graphs define how keywords kw1, kw2 and kw3 relate to three possible document styles ds1, ds2 and ds3 via a path description of the form kw-grp− .kw-dom− .kw-ran:
kw-grp ↗d s↑1 ↖ kw-dom
↑ kw-ran ↓ kw1 ↑ ↓ kw2 ↑ ↓ kw3 ↑ ↓ kw1 ↗d s↑2 ↑ ↖ ↓ kw2
↓ kw3 ↑ ↓ kw1 d↗s3↖ kw-grp ↑ kw-dom ↓ kw-ran kw2 Here, the path description consists of the three features kw-grp, kw-dom and kw-ran, and characterizes how the keywords can be “reached” from a document style by following a path of feature values: first the inverse of kw-grp to one of the document style’s keyword groups, and then the inverse of kw-dom followed by kw-ran to the keywords in a group.
A non-empty set intersection annotation for this path would imply that all three graphs must describe the same document style while this would only hold for the left two graphs with the more fine-grained non-empty set equality annotation. But now, with our new structural equality annotation, the left two must also describe distinct document styles since the same keywords are now grouped by paragraphs in diferent ways.
We define a family of description logics set-ℒℱ ℐ that are members of the FunDL dialects of
description logic [
Definition 1 (Path Descriptions). A path description is defined by the grammar
Pd ::= id | . Pd | − . Pd | C?. Pd, for ∈ F, where − is called the inverse of , a concept, and with the stipulation that substrings of the form . − and − . do not appear in any path description Pd. □
In this paper we study the notion of structural path description agreement in PDDs. Definition 2 (Structural Pd Agreement). Let Pd be a path description, ℐ an interpretation and and be two △ elements. We say that and structurally agree on Pd, Pd≃(, ), when: = if Pd = id , ∀1, 1.(1 = ℐ ()) ∧ (1 = ℐ ()) → Pd1≃(1, 1) if Pd = . Pd1, ∀1.( ℐ (1) = ) → ∃1.( ℐ (1) = ) ∧ Pd1≃(1, 1)
∧ ∀1.( ℐ (1) = ) → ∃1.( ℐ (1) = ) ∧ Pd1≃(1, 1) if Pd = − . Pd1, ∈ Cℐ ∧ ∈ Cℐ ∧ Pd1≃(, ) if Pd = C?. Pd1 .
We introduce other notions of path equality (discussed in the introduction) in place of ≃ in the definition of PDD below in Definition 4.
Definition 3 (Concepts, Subsumptions, and TBoxes). A {≃}-ℒℱ ℐ (a member of the set-ℒℱ ℐ family) concept description is constructed from primitive concepts using Boolean concept constructors ⊓, ⊔, and ¬, value restrictions on features ∀., unqualified existential restrictions on features ∃ and inverse features ∃ − , and the path description dependency (PDD) of the form : Pd1≃, . . . , Pd≃ → Pd≃ . The semantics of all the derived concept descriptions is defined in the standard way; for the PDD concept constructor the semantics is given by ( : Pd1≃, ..., Pd≃ → Pd≃)ℐ =
{ | ∀ ∈ ℐ : Pdℐ ({}) ̸= ∅ ∧ Pdℐ ({}) ̸= ∅ ∧ (⋀︀=1 Pd≃(, )) → Pd≃(, )}, where, for a set ⊆ △ , Pdℐ () is the set of △ elements reachable from in ℐ via Pd. A subsumption is an expression of the form 1 ⊑ 2, where the are concepts, and where PDDs occur only in 2 but not within the scope of negation.1 A terminology (TBox) consists of a finite set of subsumptions, and a posed question is a single subsumption. The notions of satisfaction and entailment are standard. □
The entailment in {≃}-ℒℱ ℐ can be shown decidable via mapping to (unsatisfiability of) an
Ackermann-prefix [
Alternative path-based Pd agreements, introduced in [
The following Theorem shows that mixing path agreement variants in PDDs/TBoxes leads to undecidability: Theorem 2. The entailment problems in {≃, ≈} -ℒℱ ℐ and {≃, ∩}-ℒℱ ℐ are undecidable.
The members of the set-ℒℱ ℐ family are designed to serve as the underlying ontological languages
that allow referring expressions [
Definition 5 (Referring Expression Types). A referring expression type () is defined by the following grammar, where A is a primitive concept.
::= {?} | A → | ∃. | ∃ − . | 1 ⊓ 2 | 1 ; 2 The language of referring concepts inhabiting , ℒ(), is defined as follows:
ℒ({?}) = {{} | is a constant symbol} ℒ(A → ) = {A ⊓ | ∈ ℒ()}
ℒ(∃.) = {∃. | ∈ ℒ()} ℒ(∃ − .) = {(∃ − .[⃗/⃗1]) ⊓ . . . ⊓ (∃ − .[⃗/]) | ∈ ℒ()} ⃗ ℒ(1 ⊓ 2) = {1 ⊓ 2 | 1 ∈ ℒ(1) ∧ 2 ∈ ℒ(2)}
ℒ(1; 2) = ℒ(1) ∪ ℒ(2) where [⃗/⃗] is the concept in which all nominals ⃗ in have been replaced by ⃗; this replacement is over all possible distinct choices of ⃗1, . . . , ⃗ for ⃗ and all ∈ . Given a TBox and referring expression type , the singularity problem for with respect to is to determine if |ℐ | ≤ 1 for every ∈ ℒ() and every model ℐ of . □ Example 1. Each of the three graphs in our introductory example are parse trees for concepts occurring in ℒ() when is “∃kw-grp− .∃kw-dom− .∃kw-ran.{?}”. For example, the middle graph would be the concept (∃kw-grp− .∃kw-dom− .∃kw-ran.{1}) ⊓ (∃kw-grp− .(∃kw-dom− .∃kw-ran.{2} ⊓ ∃kw-dom− .∃kw-ran.{3})).
To formulate our result we need to normalize the referring expression types.
Definition 6 (Normalized Referring Expression Types). We use Norm() to refer to an exhaustive application of the following rewrite rules:
A → (1; 2) ↦→ A → 1; A → 2
⊓ (1; 2) ↦→ ⊓ 1; ⊓ 2
(1; 2) ⊓ ↦→ 1 ⊓ ; 2 ⊓
1Violating this latter condition leads immediately to undecidability [
∃.(1; 2) ↦→ ∃.1; ∃.2 ∃ − .(1; 2) ↦→ ∃ − .1; ∃ − .2 □
The definition of Norm is an adaptation of referring expression type normalization in [
Pds({?}) = {(id )≃} Pds(A → ) = {(A?. Pd)≃ | (Pd)≃ ∈ Pds()}
Pds(∃.) = {(. Pd′)≃ | (Pd′)≃ ∈ Pds()}
Pds(∃ − .) = {( − . Pd′)≃ | (Pd′)≃ ∈ Pds()}
Pds(1 ⊓ 2) = Pds(1) ∪ Pds(2) The function extracts a set of path descriptions adorned with “≃” leading to nominals from the preferencefree referring expression type. The singularity test is now as follows: Theorem 3. Let be a TBox in set-ℒℱ ℐ and a referring expression type. Then all referring concepts in ℒ() are singular with respect to if and only if |= ⊤ ⊑ ⊤ : Pds(′) → id holds for every preference-free component ′ of Norm(). □
The author(s) have not employed any Generative AI tools.