1 Introduction
1.1 Contribution
1.2 Outline
2 Running example and motivations
2.1 A sample ontology BibOn
-
\(Person\sqsubseteq \lnot Paper\).
-
Class subsumption: \(Author \sqsubseteq Person\), \({ PUTAuthor} \sqsubseteq Author\).
-
Class-driven specialization (definition of extensional predicate): \(Person\,\sqcap \,\exists authorOf.Paper\equiv Author\).
-
Value-driven specialization (definition of extensional predicate): \(Author\sqcap \exists { affiliation}.\{'PUT'\}\equiv { PUTAuthor}\).
-
Property subsumption: \(correspAuthor \sqsubseteq written By\).
-
\(Author\sqcap \exists { authorOf.ACMPaper}\equiv { ACMAuthor}\).
-
\(Conference\sqcap \exists country.\{'USA'\}\equiv { USAConf}\).
-
\(inProceed^-\equiv includesPaper\).
-
chains of properties: \({ inProceed} \circ { ofConf}\equiv {} { presentedAt}\), \(authorOf\circ { presentedAt}\equiv { authorConf}\), \({ authorConf}\circ { confPCMember} \equiv { authConfPCMember}.\)
-
\(dom(name)=Person\), \(rng(name)=Data\),
-
\(dom(correspAuthor)= Paper\),
-
\(rng(correspAuthor)= Author\).
-
\(Person\sqsubseteq \exists name\),
-
\(Author\sqsubseteq \exists writtenBy^-\).
-
name is a functional data property: \((\mathtt{funct\ } name)\),
-
inProceed is a functional object property: \((\mathtt{funct\ } inProceed)\).
2.2 Motivation of the paper
3 Ontological database
3.1 Faceted ontologies and ontological database
3.2 \({\mathcal {SROIQ}}^{Fac}\)—a subset of \({\mathcal {SROIQ}}\)
Syntax | Semantics | |
---|---|---|
Property inversion | \(P^-\) | \(\{(x,y)\ \vert \ (y,x)\in P^{{\mathcal I}}\}\) |
Nominal | \(\{a\}\) | \(\{a^{{\mathcal I}}\}\) |
Conjunction | \(q_1\sqcap q_2\) | \(q_1^{{\mathcal I}}\cap q_2^{{\mathcal I}}\) |
Disjunction | \(q_1\sqcup q_2\) | \(q_1^{{\mathcal I}}\cup q_2^{{\mathcal I}}\) |
Existential | \(\exists R\) | \(\{x\in \Delta ^{{\mathcal I}} \vert \exists y(x,y)\in R^{{\mathcal I}}\}\) |
Restriction | \(\exists R.q\) | \(\{x\in \Delta ^{{\mathcal I}}\ \vert \ \exists y(y\in q^{{\mathcal I}}\) |
\(\wedge (x,y)\in R^{{\mathcal I}})\}\) | ||
\((\ge k)\) restriction | \((\ge k) R\) | \(\{x\in \Delta ^{{\mathcal I}}\ \vert \ \#\{y\in \Delta ^{{\mathcal I}}\) |
\(\wedge (x,y)\in R^{{\mathcal I}}\}\ge k\} \) | ||
\((\ge k) R.q\) | \(\{x\in \Delta ^{{\mathcal I}}\ \vert \ \#\{y\in q^{{\mathcal I}}\) | |
\(\wedge (x,y)\in R^{{\mathcal I}}\}\ge k\}\) | ||
Local reflexivity | \(\exists R.{ Self}\) | \(\{x\ \vert \ (x,x)\in R^{{\mathcal I}}\}\) |
Negation | \(\lnot q\) | \((type(q))^{{\mathcal I}}\setminus q^{{\mathcal I}}\) |
3.3 Query answering in ontological databases
4 Faceted views and faceted interfaces over ontological databases
4.1 Nested facet
4.2 Faceted view
4.3 Faceted interface
-
\(\lambda :N\setminus N_{L}\rightarrow \{\sqcap ,\sqcup \}\times (\{root\}\cup \mathsf{UP}\cup \mathsf{BP})\),
-
\(\lambda :N_{L}\rightarrow \mathsf{UP}\cup \mathsf{BP}\cup \mathsf{Const}\),
-
\(Sel(v)\in \{\varepsilon ,\mathtt{YES}\}\)—indicates whether v is selected (checked) or not.
-
\(AndOr(v)\in \{ \sqcap ,\sqcup \}\)—indicates that the set of children of a non-leaf node v is conjunctive (\(\sqcap \)) or disjunctive (\(\sqcup \)).
-
\(PosNeg(v)\in \{\varepsilon ,\lnot \}\)—indicates whether the subtree rooted in v is negated (excluded) or not.
-
\(NumRestr(v)\in \{\varepsilon ,(\ge ,k)\}\)—indicates if a number restriction is bound to a property node v.
-
\(Self(v)\in \{\varepsilon ,{ Self}\}\)—indicates if a local reflexivity restriction is bound to an object property node v.
5 Faceted queries over ontological databases
5.1 Syntax and semantics of faceted queries—faceted normal form (FacNF) of queries
5.2 Transformation of \({\mathcal {SROIQ}}^{Fac}\) into FacNF
6 Faceted query formulation in DAFO
6.1 Examples of query formulation
-
with default conjunctive and disjunctive facets—query \(q_1\),
-
a disjunctive set is switched to a conjunctive one—query \(q_2\),
-
a subtree is cloned (duplicated) and values of some data properties are added—query \(q_3\).
-
query with one negation (exclusion)—query \(q_4\),
-
query with double negation (equivalent to a universal quantification)—query \(q_5\).
-
a natural language version,
-
a DL version in \({\mathcal {SROIQ}}^{Fac}\),
-
graphical forms of faceted queries \((q_1)\)–\((q_7)\), their first-order forms, for \((q_1)\)–\((q_5)\), and a notation involving variables for \((q_6)\) and \((q_7)\)—all as screenshots on DAFO,
-
operations on the faceted interface used to create the final faceted query.
pcMemberOf.Uncheck(); RemoveAllUnchecked().
authorConf.SetToAND().
authorConf.SetNumRestr.count()>10;
6.2 Expressiveness of DAFO compared to other systems
Query | DAFO | BrowseRDF | Sewelis | SemFacet |
---|---|---|---|---|
A | \(+\) | \(+\) | \(+\) | \(+\) |
\(q_1 \sqcup q_2\) | + | − | + | + |
\(q_1 \sqcap q_2\) | + | + | + | + |
\(q_1 \sqcap \lnot q_2\) | + | + | + | − |
\(\lnot q\) | \(+\) | \(+\) | \(+\) | − |
\(\exists R.q\), | \(+\) | \(+\) | \(+\) | \(+\) |
\(\exists R\) | \(+\) | \(+\) | \(+\) | \(+\) |
\(\exists R.\{a\}\) | \(+\) | \(+\) | \(+\) | \(+\) |
\((\ge k) \exists R.q\) | \(+\) | − | − | \(+\) |
\((\ge k) \exists R\) | \(+\) | − | − | \(+\) |
\(\exists R.{ Self}\) | \(+\) | \(+\) | \(+\) | − |
-
In a negation \(q_1 \sqcap \lnot q_2\), the guard is \(q_1\), and \(q_1\) and \(q_2\) are of the same type.
-
In DAFO, a negation \(\lnot q\) is guarded by the type(q).
-
In BrowseRDF, the negation can only concern the existence of an property. Negation is true for objects that do not have the negated property.
-
In Sewelis, the complement is computed with respect to the set of all objects (the universal class).
7 Materialization of constraint rules
-
\(\forall \mathbf{x} ,\mathbf{y} (\varphi (\mathbf{x} ,\mathbf{y} )\rightarrow \exists \mathbf{z} \psi (\mathbf{x} ,\mathbf{z} ))\),
-
\(\forall \mathbf{x} (\varphi (\mathbf{x} )\rightarrow \lnot \psi (\mathbf{x} ))\),
-
\(\forall \mathbf{x} (\varphi (\mathbf{x} )\rightarrow x_1=x_2)\), where \(x_1,x_2\in \mathbf{x} \).
7.1 Termination of chase
-
\((A_1,1)\rightarrow (R,1)\), \((R,2)\rightarrow (A_2,1)\) – regular edges,
-
\((A_1,1)\xrightarrow {*} (R,2)\) – a special edge (labeled by \(*\)).