An Assertion Retrieval Algebra for Object Queries over Knowledge Bases

1 Introduction

Many types of structured data repositories can be viewed as collections of facts about objects (e.g., [Halevy et al., 2006]), often with schematic information encoding rules and constraints for how objects relate to each other. An important class of search queries over these repositories are object queries, which return a set of object identifiers based on given selection criteria. The importance of these queries has given rise to a variety of formalisms for expressing object queries [Fletcher et al., 2009; Jagadish et al., 2007; Ross and Janevski, 2004].

In this paper, we consider a description logic (DL) based representation of the object retrieval problem. Description logics give us a formal representation of facts about objects and provide a rich framework for automated reasoning over the schema information accompanying object databases. In particular, we assume a database is given in the form of a knowledge base K = (T ,A) over some choice of DL dialect L, in which T is a terminology (or TBox) that captures general knowledge, and in which A is a set of assertions (or ABox) that identifies objects of interest to some agent and asserts facts about those objects. In this setting, an object corresponds to an individual name occurring in an ABox and the problem of object querying corresponds to the well-known problem of instance retrieval [Horrocks et al., 2004].

A particular instance retrieval problem for a knowledge base K over L is defined by a concept C in L. The problem is to compute all objects (or instances) a occurring in A for which K |= a : C, that is, for which the assertion a : C, stating that a belongs to concept C, is a logical consequence of K. Thus, object queries correspond to concepts in L and return the subset of ABox objects that satisfy this condition.

We consider a more general problem we call assertion retrieval in which a concept Ca in L is now paired with each object a returned by a query concept. Ca will be "the most informative" concept about a that can be expressed in a subset of L defined by an additional query parameter. In particular, we assume a user query is now given by a pair (C, Pd) in which C is a query concept in L serving the same role as in instance retrieval, and in which Pd is the additional parameter, called a projection description, that defines a subset LPd of the concepts of L. The query returns assertions of the form a : Ca such that K |= a : (C ⊓ Ca), where Ca is the most specific concept in LPd for which this condition holds. A projection description generalizes the effect of the relational projection operation by providing a more general way of controlling both the format and information content of query results.

There are two compelling reasons for considering assertion retrieval over basic object retrieval. The first is a practical reason that relates to usability: since it becomes possible to include relevant facts about objects in addition to their identifiers, the results of querying can be more informative and relevant to a user searching a knowledge base. The second is a more technical reason that relates to performance: by caching the computation of earlier assertion retrieval queries, it becomes possible to explore view-based query rewriting in the context of object queries over knowledge bases. In particular, we show rewritings that eliminate the need for general knowledge base reasoning during query processing by reusing previously computed query results.

A running example used in this work relates to a hypothetical knowledge base system encoding product data. In response to some user action, a web browser submits queries over the knowledge base. The queries originate in the web pages for an enterprise, and are replaced on the fly with the resulting set of concept assertions computed by the query (suitably mapped to HTML).

Example 1 Consider the case of an online dealer of photography equipment. As part of a web presence, the dealer maintains (1) a knowledge base K with a TBox and ABox that respectively capture ontological knowledge of digital cameras and facts about particular cameras available for purchase through the dealer, and (2) a collection of web pages with embedded user queries over this knowledge base. For example, one of the web pages might have a query Q with a query concept C of the form

paired with a projection description Pd of the form

Consequently, when browsing this page, a user sees in place of Q a list of inexpensive digital cameras, with each list element displaying the name of the camera together with a nested sublist of supplier URLs and ratings for that camera.

The example above illustrates how a set of concept assertions computed by our query language can resemble a nested relation. Note that such queries are not expressible as conjunctive queries over either a DL-based knowledge base or a relational database. Our contributions are as follows.

1. We propose the task of assertion retrieval for object queries over knowledge in which it becomes possible for a user to control the format and content of additional facts about qualifying objects returned in response.
2. By choosing a DL-based presentation of object data in the form of a knowledge base, we provide a way to resolve the problem of incorporating ontological domain knowledge for object queries.
3. We introduce an assertion retrieval algebra over a combination of a knowledge base and a set of cached query results. We show how this can enable a transfer of basic database paradigms involving caching and view based query rewriting.
4. We present an optimization framework for query rewriting and show that applying rewrites to query plans can enable the resulting plans to avoid general knowledge base reasoning during their execution.

We also present experimental results illustrating evidence for both the utility of our optimization framework and the feasibility of our approach for supporting assertion retrieval over knowledge bases.

Subsequent sections are organized as follows. Section 2 provides the necessary foundations. Our main results follow in Section 3 in which we introduce our assertion retrieval algebra together with an optimization framework for this algebra that enables a transfer of basic database paradigms involving caching and view-based query rewriting. The section concludes by considering how rewrites can be introduced that will overcome the overhead of general knowledge based reasoning during query execution. In Section 4, we present the results of preliminary experiments and conclude in Section 5 with a discussion of how our work leads to a variety of possible extensions and future work.

1.1 On Expressiveness and RelatedWork

The notion of an object query language for object data was proposed in [Ross and Janevski, 2004] and further considered in [Fletcher et al., 2009] for object data that includes links between objects. The latter work also exhibits a correspondence between an object query language proposed by the authors and a restricted semi-join algebra over two-column relational data. Thus, in this earlier work, object query languages are viewed as strictly less powerful than first order query languages such as the relational algebra.

2 Definitions

We assume web data is formally understood as a knowledge base over some choice of DL dialect L. For the remainder of the paper, L will correspond to the dialect ALC(S) defined below. However, our results apply to any dialect that has ALC(S) as a fragment, such as the dialect that underlies OWL DL [W3C, 2009]. (This requirement can be relaxed slightly without harm by removing the need to support concept negation.)

Definition 1 (Description Logic ALC(S)) Let {A, A1, . . .}, {R, R1, . . .}, {f, g, f1, . . .} and {a, b, . . .} denote countably infinite and disjoint sets of concept names, role names, concrete features and individual names, respectively. A concept is defined by:

where k is a finite string. A constraint C is an inclusion dependency C ⊑ D, a concept assertion a : C, or role assertion R(a, b). A knowledge base K is a finite set of constraints, further divided into a TBox T of all the inclusion dependencies and an ABox A of concept/role assertions.

An interpretation I is a 2-tuple (△ ⊎ S, ·I ) in which △ is an abstract domain of objects and in which S is a disjoint concrete domain of finite strings. The interpretation function ·I maps each concrete feature f to a total function (f)I : △→ S, each role name R to a relation (R)I ⊆ (△×△), each concept name A to a set (A)I ⊆ △, the "=" symbol to the equality relation on S, the "<" symbol to the binary relation for an alphabetical ordering of S, and a finite string k to itself. The interpretation function is extended to all concepts in the standard way, e.g., (f = k)I = {o ∈ △ | (f)I (o) = k}, (¬C)I = △ - (C)I , etc. An interpretation I satisfies an inclusion dependency C ⊑ D (concept assertion a : C, role assertion R(a, b)) if (C)I ⊆ (D)I ((a)I ∈ (C)I , ((a)I , (b)I ) ∈ (R)I , respectively). We write K |= C if all interpretations that satisfy constraints in K also satisfy C.

We use standard abbreviations such as C ≡ D for (C ⊑ D) ⊓ (D ⊑ C), C ⊔D for ¬(¬C ⊓ ¬D) and f ≤ k for (f = k)⊔((f < g)⊓(g = k)). Also, given a finite set S of ALC(S) concepts, we write ⊓S to be the concept D1 ⊓ · · · ⊓ Dn for Di ∈ S (and ⊤ if S = ∅).

Now recall that a user query (C, Pd) consists of a query concept C paired with a projection description Pd. The syntax for a Pd and the sublanguage of concepts in ALC(S) that are induced by a Pd are defined as follows.

Definition 2 (Projection Description) Let f, R and C be a concrete feature, role and concept, respectively. A projection description Pd is defined by the grammar:

Definition 3 (Induced Concepts) Let Pd be a projection description. We define the sets LPd and LTUP Pd , the L concepts generated by Pd and L tuple concepts generated by Pd, respectively, as follows:

Thus, for a given Pd, any concept occurring in LPd satisfies a syntactic format conforming to Pd independently of any knowledge base K. For example, let Pd = (A? ⊓ (f = 1)?). Then LPd is the set of concepts

where ⊆fin denotes a finite subset. Given a knowledge base K and set of concepts S, we will need to refer to the most informative concepts in S with respect to K.

Definition 4 (Most Informative Concepts w.r.t. LPd)

Let S be a set of concepts specified by LPd and K knowledge base. We write ⌊S⌋K to denote {C ∈ S | ¬∃D ∈ S : (K |= D ⊑ C, K ̸|= C ⊑ D)}.

Lemma 5 Let K be an ALC(S) knowledge base, Pd a projection description and C a concept. The following hold for the set S of concepts defined by {D ∈ LPd | K |= C ⊑ D}:

1. ⌊S⌋K is non-empty;
2. K |= C1 ≡ C2, for any {C1, C2} ⊆ ⌊S⌋K; and
3. ⌊⌊S⌋K⌋∅ is non-empty,

Parts 1 and 2 of Lemma 5 ensure that at least one least subsuming concept of C exists in LPd and, when there is more than one, that any pair are semantically equivalent with respect to a given K. Note that some such L restriction of ALC(S) is essential to ensure Part 1, e.g., that a more general fragment that simply excludes concept negation from ALC(S) may not have this property [Baader et al., 2007]. Also note that, although LPd is infinite in general, for any fixed and finite terminology T and concept C, the language LPd restricted to the symbols used in T and C is necessarily finite. Part 3 of Lemma 5 ensures that, among the least subsuming concepts of C in LPd with respect to K, there is at least one least subsuming concept that is the most informative when no knowledge of K is presumed. For example, let K = {A ⊑ (f = 1)} and Pd = (A? ⊓ f?), and let S = {D ∈ LPd | K |= A ⊑ D}. Then

1. ⌊S⌋K = {A⊓ (f = 1),A⊓⊤},
2. ⌊⌊S⌋K⌋∅ = {A⊓ (f = 1)} and
3. ⌊⌊S⌋⌋K = A⊓ (f = 1).

where ⌊⌊S⌋⌋K is the minimum concept from a set of concepts ⌊⌊S⌋K⌋∅ according to an (arbitrary) total ordering of all concepts in ALC(S).

Definition 6 (Query Semantics) Let K be an ALC(S) knowledge base and Q = (C, Pd) a user query over K. Then Q computes the set of concept assertions

Observe that concept assertion retrieval generalizes instance retrieval. In particular, an instance retrieval query C over K

can be formulated as query (C, ⊤?) (effectively retrieving no further information about qualifying individual names in K).

3 An Assertion Retrieval Algebra

We now introduce an algebra for manipulating sets of concept assertions. The algebra is centered around our ability to store (cache) and later use results of previous queries to aid the evaluation of subsequent queries. To this end the algebra uses operations for (efficient) selection of qualifying objects from cached query results [Pound et al., 2007] and for concept projection [Pound et al., 2009]. Additional operators are included that allow basic combinations of queries. We show how expressions in this algebra can describe a variety of query plans for evaluating a user query that can vary widely in the cost of their evaluation, and we outline how several standard relational-style query optimization techniques can be accommodated in this framework.

3.1 Cached Query Results

Intuitively, cached query results store explicit information about the qualifying individuals obtained by previous user queries.

Definition 7 (Cached Query Results) A cached query result Si is the set of concept assertions obtained by a user query (Ci, Pdi).

The above definition permits the existence of any number of cached query results often organized in data structures designed to support user queries 1 . Note that cached query results are essential in our approach. They enable query evaluation to avoid (or reduce) the amount of general DL reasoning during query evaluation. A particular query answer may be more preferable for caching than that of another, though, in principle, all user query results could be cached. Details on selecting which query answer to store are beyond the scope of this paper.

Example 2 To continue with our running example: we assume cached query results are available:

The first caches the ProductCode of every product (with the idea that the underlying data structure can be efficiently searched given a particular product code), the second caches the Price for products costing under $1000, and the last stores a more elaborate projection of the information associated with every product.

3.2 The Algebra

To facilitate efficient evaluation of such requests we introduce a query algebra to manipulate sets of concept assertions. The algebra allows for the use of cached query results to speed-up search for qualifying individuals and to retrieve appropriate concepts needed to construct answer concept assertions.

1 This is analogous to relational systems, multiple specialized indices are typically defined to support queries. This is in contrast to approaches that aspire to developing a "universal" search structure to represent semantic data.

Definition 8 (Assertion Retrieval Algebra) The algebra consists of the operators listed in the grammar below.

where C is a concept description and Si a cached query result. The semantics of each operator is given immediately to the right of its position in the grammar, and is defined with respect to (a) zero or more cached query results {S1 , . . . , Sn }, and (b) a given knowledge base K.

The operators are either pure or impure: C is impure, P K and Si (Q) are pure, σK C (Q) and πK P d (Q) are pure if Q is pure, and Q1 ∩ Q2 is pure if both Q1 and Q2 are pure.

Each of the operators maps sets of concept assertions to a set of concept assertions, with the Si (Q) operator providing an access to the previously cached results of queries. The operator accepts an argument that can supply search conditions with the intention of using the underlying data structure representing the cached result to facilitate efficient search. For example, the cached result S1 from Example 2 can be used to efficiently search for descriptions of the form (ProductCode = k) for a given string k.

Note that queries of the form C can be, without loss of generality, compactly represented by a single generalized assertion of the form {⋆ : C} where ⋆ stands for an arbitrary ABox individual. This arrangement leads to greatly improved efficiency when executing Si (C) operators to select cached results subsumed by the constant description C.

3.3 Queries as Algebraic Expressions

In this setting, a given user query (C, Pd) can always be translated into the algebraic expression

this follows immediately from the definitions. However, to benefit from the performance gains made possible by cached query results, the algebra allows a richer space of expressions:

Lemma 9 (Caching Introduction) Let (C, Pd) be a user query. Then the expression

is equivalent to (3), provided that (i) Si := (Di, Pdi)), (ii) K |= C ⊑ (D1 ⊓ ... ⊓ Dn), and (iii) Ci = ⌊⌊{D | D ∈ LPdi , K |= C ⊑ D}⌋⌋K, for all 0 < i ≤ n.

Conditions (i) and (ii) ensure that the combination (intersection) of the cached query results Si contains sufficient data to answer the original query. The last condition in the lemma serves two purposes: first it supplies a sufficiently general search concept to each of the cached results. Note that using the original search concept C instead would lead to loss of answers since the concept assertions stored in the cached results are more general than those implied by the knowledge base, in general. Secondly, as the concepts Ci are results of the same projections used to create the cached result Si , all the general subsumption checks reduce to structural tests (cf. section 3.4). This rewriting completely avoids the use of P K.

The rewriting, when coupled with the ability to store and search efficiently among descriptions, yields a path to defining appropriate physical data layout designs in the form of cached query results and in turn to efficient plans for answering assertion retrieval queries. The general form of (4) can be further simplified using the analogues of relational-style query rewrites that allow the use of cached query results:

Lemma 10 (Removing Redundant Selections) The selection operation σK C (·) can be removed from (4) to obtain the expression

Example 3 Recall the running example query (1). With the help of cached query results defined in Example 2, we can obtain the following equivalent query expression:

The cached results S1 and S2 fully qualify the individuals needed to answer the query and can be efficiently accessed using the concepts (P roductCode = "digicam") and (Price < "250.00"), respectively. The reason for using S3 is to form the concept assertions for the answer since S3 stores the most specific descriptions conforming to Pd.

A final feature of the proposed algebraic framework is its ability to use results of queries to further qualify scans over cached query results:

Lemma 11 (Nested Searches) An expression of the form

is equivalent to

where Pd is such that LPd ⊆ LPdi (the projection description used to define Si ) and Pd′ is an arbitrary projection.

Note that the projection description Pd in the above rewriting rule is not unique; in particular, the projection description ⊤? can be always used in place of Pd. However, the more general this projection description is, the less information about objects retrieved from Sj is used to qualify the search in Si .

Example 4 The above lemma applied twice to our running example (6) will produce the following expression:

Note that the outermost projection is identical to the projection used to define S3 and can be removed.

3.4 On Purely Structural Reasoning

There are a variety of cases in which the operators in our algebra can be evaluated with simple structural subsumption testing in place of general reasoning (indeed, this is already the case when accessing the cached results). In this section, we characterize a general condition in which this holds for various operators in a given concept assertion query Q. We devise a test that allows us to determine whether a particular operator of our algebra can be executed without referring to the knowledge base K. This goal requires us to devise conditions under which OPK(Q1, . . . , Qk) = OP∅ (Q1, . . . , Qk)

for every operator OP in our algebra and every knowledge base K, where OP∅ denotes executing the operator w.r.t. the empty knowledge base. Intuitively this means that the concept assertions in the answers to Qi contain sufficient explicit information about an individual; the goal is to ultimately obtain this information using some cached query result rather than via reasoning in K.

Definition 12 (Representative Language) We define LQ to be a language of representative concepts for an algebraic query Q as follows:

where Pdi is the projection description used to define Si , For representative languages LQ1 and LQ2 we define LQ1 ↪→ LQ2 if for all C1 ∈ LQ1 there is C2 ∈ LQ2 such that |= C1 ≡ C2.

Theorem 13 Let (C, Pd) be a user query, (Ci, Pdi) queries that define cached query results Si , and Q an algebraic query equivalent to (C, Pd). Then, for every pure subquery Q′ of Q, the following holds:

Proof (sketch): (a sketch for case 1; the other case is similar) For (a : D) ∈ σK C (Q′ ) we have (a : D) ∈ Q′ and K ∪ {a : D} |= a : C where D is the most specific in LQ′ such that a : D. However, by the assumption of the theorem, concept C ⊓ D, up to equivalence, is also a member of LQ′ . Thus, ̸|= D ⊑ C implies a : C ⊓ D ∈ Q′ : a contradiction. Hence C ⊑ D and thus (a : C) ∈ σ∅C (Q′ ). The other direction is immediate from definitions.

To make the above theorem into an effective rewriting rule we need to define finite approximations of the languages LQ. Definition 14 Let (C, Pd) be a user query and (Ci, Pdi) queries that define cached query results Si . We define a set of concrete domain values (strings) S to be the set of values k such that (f = k) is a subexpression in any of the above queries for some feature f . We define Lfin Q to be the restriction of the language LQ to those concepts C for which k ∈ {⋆}∪S whenever f = k is a subconcept of C, where ⋆ is an arbitrary concrete value that does not appear in S.

It is easy to see that Lfin Q is finite; moreover:

Hence the precondition for the rewriting defined in Theorem 13 can be tested using finitely many subsumption tests in the underlying description logic.

Example 5 Applying the results in Theorem 13 to the algebraic version of our running example (7) top-down yields:

The complete query can now be executed exclusively using the cached query results and without referring to the knowledge base K.

Note the essential use of S3 that stores sufficient explicit information about retrieved objects, even though in itself does not facilitate the search for such objects.

4 Experimental Evaluation

To evaluate the utility of our optimization framework and the feasibility of our approach to supporting object queries over knowledge bases, we implemented the assertion retrieval algebra defined in the previous section together with a basic DL reasoner to support subsumption testing in ALC(S). Our implementation uses standard tableaux-based techniques with a straightforward extension to support reasoning over our very simple concrete domain of strings. Our implementation of the projection and scanning operations on top of the DL reasoner are based on the algorithms reported in [Pound et al., 2007] and [Pound et al., 2009].

An overview of our system architecture is illustrated in Figure 1. The system assumes clients browse Web pages that contain embedded user queries. These are more generic queries that have parameters that are initialized by user input when browsing such pages. The resulting queries are then sent to the query evaluator for execution. In the current system, general plans for the original queries with parameters will have already been cached. These plans use cached query results that are stored in specialized data structures called description indices [Pound et al., 2007]. Initialized queries are then evaluated using the cached plans to produce the resulting set of concept assertions, which are then returned to the client browser for display.

We compare two systems, both of which evaluate queries using cached query results. The baseline system always evaluates the query using calls to our DL reasoner. The optimized system takes advantage of the structure of cached queries to use structural subsumption testing and avoid general DL reasoning in some cases. The full source code for our implementation, along with our evaluation workload and test data is available online 2 . For our evaluation knowledge base, we encoded all publications from the last ten years of all program committee members for major conferences as an ABox (approximately 900 publications). We then extracted a taxonomy of computer science conferences fromWikipedia using an automated procedure, and hand coded additional axioms for affiliations of authors for our TBox (approximately 350 inclusion dependencies about authors' affiliation, organization locations and so on). Finally, we constructed a suite of queries that exercise various scenarios, such as feature equality queries, feature range queries, and arbitrary concept queries including disjunctions and existential quantification. Queries were created for scenarios in which a cached query result efficiently supports the query (no general DL reasoning is required) and for scenarios in which a full scan and general DL reasoning is necessary. For example, one of our queries finds all publications published in some artificial intelligence proceedings, and returns concept assertions containing the title, proceedings name, and author names:

2 http://code.google.com/p/projection-alcd/

title? ⊓ (∃inP roceedings.name?) ⊓ (∃hasAuthor.name?)).

Figures 2 and 3 summarize our query processing experiments. The results are evidence for both the utility of our optimization framework and the feasibility of our approach to supporting object queries over knowledge bases. Figure 2 shows the overall execution time of each system over all queries with and without optimization, and Figure 3 shows a breakdown of the number of structural (OSS) and reasoner (ORS) subsumption tests for the optimized system, compared to the total number of reasoner subsumption tests for the baseline system (BRS). The results indicate that the optimized system has a clear performance advantage across a majority of our test queries. In particular, queries 3 and 4 involve feature projections on multiple features for a large number of results. In these scenarios, K-free structural subsumption testing leads to a significant advantage over the baseline.

5 Conclusions &FutureWork

The framework for assertion retrieval proposed in this paper provides a basis for introducing efficient relational-style query processing to querying object data. The key features of the approach are the ability to compute projections of general concepts to make properties of individuals syntactically explicit, to cache such assertions for efficient query evaluation, and to account for circumstances in which general knowledge base reasoning can be supplanted with simple structural subsumption testing at query evaluation time.

Future research can use the proposed query algebra to develop additional tools and techniques facilitating efficient query execution, for example: (1) optimization techniques that determine optimal reformulations of user queries in the algebra or its extensions, possibly integrated with cost and selectivity estimates; and (2) extensions of the language of projection descriptions that allow, e.g., alternatives in the explicit information stored with objects (efficient query processing in such an extension crucially depends on the ability to reason with fragments of the original knowledge base, possibly based on the notion of modules [Konev et al., 2008]). Another direction of research is whether more complex user queries, e.g., an equivalent of conjunctive queries, can be accommodated by modest extensions to the framework.