Ontology-based data access has received a lot of attention recently, yet there is no clear methodology to evaluate a "semantically enriched" information system in general or an ontology based data access system in particular. The quality of such an information system clearly depends on how well your data fits your class-level ontology, and how well these two components fit your queries. This paper presents a generic, flexible framework for this kind of analysis: it can be used, e.g., to compare two class-level ontologies w.r.t. their fitness for a given kind of data and query set. We apply the framework to an example case and show how it helps to answer relevant modelling and representation questions.
In this paper we present a framework for evaluating the quality of "semantically enriched" information systems (IS). By that we mean IS that distinguish between schema and data and are geared towards answering queries. The idea behind that is to encapsulate domain experts' background knowledge into the query answering mechanism in order to improve recall and precision. A typical example of such an IS is an ontology-based data access (OBDA) system that uses a classlevel ontology (or Tbox) as a schema and stores the data in a database. Queries retrieve tuples of individuals from the database that answer the query w.r.t. the schema.
The proposed evaluation framework measures the well-suitedness of the various components of an IS. It can be applied to any IS that involves a schema, a collection of data, a collection of information requests and a query language (QL). We call this a modelling approach (MA) for an IS. Thus, the framework is generic and can be applied to a variety of scenarios, e.g. for comparing different OBDA systems or for comparing different IS using database schemas or for comparing heterogeneous systems. ODBA has received a lot of attention recently and can come in many different fashions, e.g. regarding the expressive power of the ontology or the supported query language [2,3,1,10,6,9].
When applying the framework we look at information requests as abstractions of queries (they are independent of schema and QL). For each MA the framework measures if an information request can be answered by a query in a given QL over the given schema and data and how good the query is. More precisely, the metrics produced by the evaluation framework are the fitness of an MA, i.e. the ability of formulating "good" queries, and the flexibility, i.e. the number of different "good" ways of expressing a query.
These measurements can help IS designers in taking important design decisions, e.g. whether to use an off-the-shelf schema or one that is specifically tailored to the application or which OBDA technique or tool to use. The measurements also point out which queries can and cannot be answered w.r.t. a given MA and how complicated it is to formulate these queries. That allows IS designers to identify, compare and discuss weak and strong points of their MA and manage trade-offs between modelling effort, maintainability and scalability.
In the following we will explain the technical details of the evaluation framework and its measurements. Furthermore, we will outline a case study in which we applied the framework to compare different ontology-based MA for medical image annotations. Fig. 1. A modelling approach plus a query and its answers.
We start by formalising the relevant components of a (semantically enriched) information system for which we are then going to evaluate and compare different modelling approaches. We will use the term "modelling approach" to describe the whole system consisting of data, schema, (an abstraction of) queries, and a query language as depicted in Figure 1.
A modelling approach MA = (S, D, R, QL) consists of -a schema S: a finite description of the semantics of the data, e.g. a database schema, a logic program, or the TBox of an ontology, which can be empty. -the data D: e.g. tables and rows in a relational database, ground facts, or ontology ABox assertions.
-a set of information requests R: each r ∈ R represents the answer to a query of D, and is given as a set (of tuples) over D. Ideally, R should be representative for the queries to be answered by the information system to be built.
-a query language QL: e.g. SQL, (union of) conjunctive queries, OWL class expressions.
An information request asks for tuples of the given data that are relevant for the user. The request needs to be distinguished from the actual query, which is a specific manifestation of the information request formulated in QL, see Figure 1. An information request r can correspond to 0, 1 or more queries in a given query language. The former is the case if there are no queries in QL whose answers would be exactly the tuples in r when asked over S and D, i.e., if QL is unable to express the information request over the given schema and data. In the case that there are one or more queries, some of them might be more easily expressible than others. In Figure 1, we sketch a case where the user wants to retrieve three individuals, John, Mary, Steve, from the database that are known to be parentsbut not all of which are explicitly stored as parents. Still, in the presence of the given schema, the query Parents(?x) can be formulated to retrieve exactly those three individuals.
The only assumptions we make is that the query language QL comes with a semantics that identifies, for a given query q of arity n in QL, data D, and schema S, the set of certain answers [4]. More precisely, we assume the existence of an entailment relation |=, and use Ind(D) for the set of individuals or constants in D to define cert(•) as follows:
The basic characteristics we want to evaluate is the fitness of an MA, i.e. how well the schema and the data are suited to enable the formulation of "fit" queries for answering the given information requests, and the flexibility of an MA, i.e. the number of "fit" queries that can be formulated for answering the given information requests. The fitness and flexibility of an MA can be determined by analysing the syntactic, semantic and/or cognitive complexity of the queries that correspond to the information requests and depends on the fitness function.
The Fitness Function Different queries that correspond to an information request can vary in length and be more or less complex, e.g. in terms of using relations and constructors such as conjunctions, disjunctions, etc. They can also be more or less difficult to understand from a cognitive perspective. For example, a human user might find a query that uses terms that are actual words (in the sense that they exist in a domain expert's dictionary) easier to understand than one that uses anonymous identifiers. The purpose of the fitness function is to capture this complexity.
The framework is parametrized with a fitness function f that associates each query q in QL with some value f (q) that is intended to capture its fitness. We only require that f maps QL into a totally ordered set (M, <), e.g. R or N 4 , which we call the query's fitness value. Obvious examples of fitness functions are (i) a query's length, (ii) a query's length combined with the number of constructors involved, either via some (weighted) summation or into a vector, or (iii) a query's length combined with the number of terms not to be found in Wikipedia or a suitable lexicon, or any combinations or extensions of these.
The smaller the fitness value, the "better" the query. We read f (q) < f(q ) as q being "better" or "fitter" than q . The framework evaluates the "best queries" for an information request, e.g., the shortest queries. The fitness function induces a partial order on the queries.
The Query Space Each information request r ∈ R has an associated query space: first, we define correct queries cQ(r, S, D) as those that answer exactly an information request r over S and D:
Next, we define best queries bQ(r, S, D, f ) as those correct queries whose fitness is maximal. Clearly, best queries depend on how we measure fitness, and thus on the fitness function f :
Since the bQ(•) are the "fittest" queries among the correct queries, any two queries in bQ(•) are equally fit, and we can abbreviate their fitness as follows: for f (q i ) = f (q j ), we set f ({q 1 , ..., q k }) to be f (q 1 ). For an empty set, e.g., if an information request cannot be expressed in QL over S and D, we set f (∅) = max < (M ) if such a maximum exists, i.e., maximally unfit, or to some other very unfit value.
If we want to consider the flexibility of an MA, we simply need to consider the number of best queries, i.e., the cardinality of bQ(•). Depending on the application domain, we can adapt the framework to consider only non-redundant queries for measuring the flexibility. For example, if S is a class-level OWL ontology and QL are OWL class expressions for instance retrieval, we can count all elements in bQ(•) that are not structurally equivalent [7].
We will now specify an instantiation of the framework to evaluate OWL ontologybased data access approaches. This specification is still quite flexible: e.g., we cover both the case where the data resides in a database and the case where it is part of an ontology. An MA = (T, A, R, CL) consists of -a TBox T, i.e., a set of OWL class-level axioms, 2 that describes the conceptual model and the terminology of the domain, plus possibly a set of mappings in the sense of [3], -an ABox A, i.e., a set of OWL assertions about named individuals, or, in the presence of the above mentioned mappings, tables from a relational database from which these mappings are defined, -a set R of information requests r, i.e., sets of tuples of OWL individuals, and -CL is the set of OWL class expressions as a query language.
OWL class expressions are an obvious choice for a query language, but there are more expressive ones such as conjunctive queries, unions of conjunctive queries [4], SPARQL, SPARQL-DL, 3 or nRQL [11].
For an ontology-based modelling approach, we suggest a fitness function as follows: f (q) is a fitness vector (a, b, c, d) that contains (i) a as the length |q| of q, (ii) b as the number of distinct OWL constructors in q, (iii) c as the role nesting depth of q, and (iv) d as a flag that is set to 1 if q contains unintelligible codes, and 0 if all terms in q are human readable otherwise. We compare the fitness of queries via the lexicographic ordering from the left of their fitness vectors.
A Simple Example We use a simple example to that captures data about parents and their children. We will use this example to illustrate the components of the modelling approach as well as the query space for an information request.
Consider the modelling approach MA = (T, A, R, CL) consisting of the following TBox and ABox Now consider the information request r(A) = {M ary, John}, i.e., r retrieve "all parents". Using OWL class expressions as a query language, the following queries could be considered:
The correct queries for r are cQ(r, T, A) = {q 1 , q 2 , q 3 , q 4 }, and not all of them are equivalent. The queries q 5 and q 6 are not correct because they return only incomplete answers. W.r.t. the above mentioned fitness function, we have only one best query, q 1 , because it is the shortest correct query.
Please note that, w.r.t. the data given here, q 4 is correct for r, and it would be interesting to see what would happen if we extended A with, say, M an(T om): either r will change as well to include T om, or q 4 ceases to be a correct query.
Fig. 2. General and comparative measurements for modelling approaches.
On the left hand side of Figure 2, we have sketched an evaluation of a modelling approach MA where, for each information request r i ∈ R, we have computed the best queries for r i , and then their fitness and cardinality. Clearly, if we want to compare two modelling approaches MA 1 and MA 2 , we can do the same and compare, for each information request r i ∈ R and each of the two modelling approaches, the fitness and cardinality of the best queries. This can unveil the strengths and weaknesses of the information system to the system designer. For example, if there are information requests for which the set of correct queries is empty, then f (bQ(r, S, D, f )) is prohibitively bad. To overcome this, we can then decide whether to select a different, more powerful query language or to change the schema or the way the data is modelled-or whether perhaps that particular information request is of too little importance for such a change. The measurements can also help to point out where the trade-offs between modelling effort and benefits in terms of easier query answering are. For example, considering an ontology-based modelling approach, whether more modelling effort for a more expressive TBox would be justified for the sake of simpler queries.
In addition, we can aggregate the fitness and flexibility of a modelling approach: this can be interesting if we want to compare two such modelling approaches en gros. In what follows, we use AGG to stand for an aggregation function such as min, max, avg, or count. This function can be fixed in the particular application of the framework.
We can aggregate both the fitness and the flexibility of a modelling approach: the overall fitness of a modelling approach f (MA) is aggregated over the fitness vectors of all best queries for all information requests, i.e.,
The overall flexibility of a modelling approach aggregates over the cardinality of all best queries for all information requests, i.e.,
As illustrated in Figure 2, applying the framework to one modelling approach MA = (S, D, R, QL) reveals -for each r, the fitness value of the best queries: f (bQj). In particular, it will identify information requests for which it is hard to specify a query in QL and those for which this is impossible. -for each r, the number of best queries: |bQj| -the aggregated fitness value m for the entire MA -the aggregated flexibility of the entire modelling approach MA When comparing different modelling approaches (as shown in Figure 4) we can compare the -point-to-point fitness for each information request -overall (aggregated) fitness m of the modelling approaches -point-to-point flexibility for each information request -overall (aggregated) flexibility of the modelling approaches
We will now present the application of the evaluation framework in a case study about ontology-based annotations of medical images and their descriptions. The study is described in more detail in [8].
The modelling process involved a number of design decisions. First, we chose to use a module of the established medical ontology SNOMED CT4 as the TBox of our annotation ontology 5 and translated natural language radiology reports of 50 medical images to ABox assertions of that ontology. The textual descriptions contain medical information such as image type, image modalities, clinical findings, body structures and diagnoses. Next, we had to be decide whether the ABox assertions should be simple class assertions of the relevant medical terms occurring in the text or whether the ABox should contain class and object property assertions, trying to closely reflect the meaning of the text. Furthermore, the SNOMED CT TBox has a very complex structure containing role groups [5] that are used e.g. to model diseases that relate findings to body structures. We had to find a way to translate the textual descriptions in accordance with this complex structure.
In the following, we present three different modelling approaches. MA 1 models the data with a simple ABox that contains almost only class assertions: individuals are only linked by a single object property shows in order to relate an image to the individuals shown in it. MA 2 uses class and object property assertions that capture the relational structure of the image descriptions. MA 3 uses a slightly different TBox than MA 1 and MA 2 in the sense that we created an additional set of roles and a role hierarchy in order to bypass the SNOMED CT specific role groups. An example of a disease in SNOMED CT that is defined using role groups is NeoplasmOfLung. The concept is defined as follows: 6NeoplasmOfLung ≡ DisorderOfLung ∃roleGroup( ∃AssociatedMorphology.Neoplasm ∃FindingSite.LungStructure)
For MA 3 , we introduced three additional object properties: shows, hasFinding and hasLocation and defined the following role hierarchy:
If we want to find all images that show neoplasms in MA 3 , we can formulate a simple OWL class expression query like
∃shows.N eoplasm and would retrieve images labelled with Image ∃roleGroup.∃AssociatedMorphology.NeoplasmOfLung without having to use the complicated role group construct in the query.
We compare the following modelling approaches:
where T 1 is the original SNOMED CT TBox and T 2 the TBox with the additional role hierarchy. A 1 is an ABox with the data formulated in terms of simple class assertions whereas A 2 and A 3 use class assertions as well as object property assertions.
The set of information requests R is derived from the content of the original, natural language image descriptions: clinical findings, findings located in body parts, complex findings (involving role groups), image types and modalities and combinations of the former. We will now list some representative information requests.
-r1: An information request that involves one clinical finding: "All images that show neoplasms." -r2: An information request that involves two concepts, an image type and an image projection: "All X-ray images with PosteroAnterior (PA) projection." -r3: An information request that involves a clinical finding combined with a qualifier value: "All images that show left-sided pleural effusions."
-r4: An information request that involves a clinical finding combined with a body structure: "All images that show soft tissue masses in the pleural membrane."
We expect that MA 1 is good for formulating queries for simple requests (such as those that ask for just one concept, e.g. r 1 and r 2 ) whereas MA 2 is more appropriate for formulating queries for complex requests that involve relations between concepts, such as r 3 and r 4 . However, we also expect that it is difficult to formulate queries for the more complex requests r 3 and r 4 in MA 1 because simple class assertions cannot capture the semantics of findings that are related to qualifier values or body structures. Furthermore, the measurements should highlight that MA 3 allows the formulation of simpler queries as opposed to MA 2 because the TBox contains the additional role hierarchy that allows use to bypass role groups.
Tables 1 -3 illustrate the findings for the three proposed modelling approaches MA i w.r.t. the information requests r 1 to r 4 . For each of the information requests, the best queries as well as the fitness values for length, number of distinct constructors and role nesting depth as well as the flexibility ( ) are listed for the three modelling approaches. 3. Findings for MA 3 .
The results shows that MA 1 allows the formulation of relatively simple queries. However, it is not always possible to formulate a query that returns exactly those tuples that are the certain answers to the information request. As soon as the information request involves nesting of entities, e.g. a finding with a location or a finding with a qualifier, MA 1 does not allow the formulation of a query that is precise enough to return only the correct answers. In this case the fitness values were assigned an exemplary value max = 100, see Table 1 for r 4 . In this information request we want to find images that show soft tissue masses located in the pleural membrane. In our data set there is one image annotation that describes a neoplasm in the pleural membrane and a soft tissue mass in some other body structure. This image would have been returned with a query like Image ∃shows.SoftTissueMass ∃shows.PleuralMembraneStructure, although it is not an answer to the information request. The problem lies in the nature of the data modelling paradigm. The lack of relational structure in the ABox makes it impossible to capture the semantics of the image descriptions appropriately.
MA 2 models the data in the ABox using the relational structures defined in the TBox, in particular the properties shows, roleGroup, associatedMorphology, etc. This allows us to formulate queries for all information requests. However, the queries are rather long and nested due to the fact that the complicated role group construct [5] has to be used. The modelling approach MA 3 can capture the semantics of the image descriptions as well as MA 2 and allows us to formulate queries for all information requests. Furthermore, the queries are significantly simpler than those in MA 2 because MA 3 uses a slightly more expressive TBox than MA 2 with which we can bypass role groups.
The three modelling approaches and their measurements expose evolving design of the retrieval system built in the case study. We started off with a relatively simple ABox that involves little effort compared to the later versions but is not expressive enough to allow the formulation of queries for all information requests. Using a more expressive ABox with object property assertions to relate the class assertions to each other makes it possible to formulate queries for all information requests, however, the queries become significantly more complex. Furthermore, with a little more modelling effort of introducing a small role hierarchy in the TBox we can formulate queries that are as expressive but much simpler than those that came with the original TBox.
The evaluation framework has highlighted the weaknesses of each modelling approach, e.g. the inability or difficulty of formulating queries for information requests. It can also highlight the strengths, e.g. conciseness and flexibility of a modelling approach. The measurements can guide the system engineer and support design decisions. For example, the framework can identify the benefits of changes in the modelling approach and therefore point out whether more modelling effort would be justified.
We have presented a generic information system evaluation framework that can be used to analyse the fitness and flexibility of modelling approaches. It involves evaluating represenative information requests and the complexity of the queries that correspond to these requests as well as the well-suitedness of the components of the modelling approach, i.e. the schema, the data and the queries.
The measurements generated by the framework can be used to highlight strengths and weaknesses of a modelling approach and to compare the fitness of similar modelling approaches. It also supports engineers in making important design decisions, such as using an off-the-shelf schema or creating one that is tailored to the data or, in general, investing more modelling effort if this leads to significant benefits in the fitness of the modelling approach. The measurements can be used as a basis for discussion when building data access applications.
A next step of our work will be to apply the framework in a case study where we compare more heterogeneous modelling approaches with each other, e.g. an ontology-based modelling approach with one based on databases. Furthermore, we want to extend the framework so that it measures the fitness of queries taking into account not only exact matches to the answers of the respective information requests but also partial results. Finally, we will extend this approach so that it not only evaluates the complexity of formulating queries, but also the overal performance and scalability of query answering.