The ever-increasing amount of data in biomedical research, and in cancer research in particular, needs to be managed to support efficient data access, exchange and integration. Existing software infrastructures, such caGrid, support access to distributed information annotated with a domain ontology. However, caGrid's current querying functionality depends on the structure of individual data resources without exploiting the semantic annotations. In this paper, we present the design and development of an ontology-based querying functionality that consists of: the generation of OWL2 ontologies from the underlying data resources metadata and a query rewriting and translation process based on reasoning, which converts a query at the domain ontology level into queries at the software infrastructure level. We present a detailed analysis of our approach as well as an extensive performance evaluation. While the implementation and evaluation was performed for the caGrid infrastructure, the approach could be applicable to other model and metadatadriven environments for data sharing.
In the biomedical sciences, the use, exchange and integration of the ever-increasing amount of data has become paramount to accelerate the discovery of new approaches for the detection, diagnosis, treatment and prevention of diseases. In particular, this applies to cancer, for which the US National Cancer Institute (NCI) and the UK National Cancer Research Institute (NCRI) have implemented Informatics Initiatives focusing on building and deploying software infrastructure to manage and analyse data generated from heterogenous data sources.
In this paper, we provide an analysis of the caGrid[
Our methodology is based on extending the caGrid service-oriented
modeldriven infrastructure with additional services to support ontology-based queries
over the distributed data resources. In this way, the biomedical researchers, as
the end-users of our system, will be able to query cancer data by building queries
using their domain knowledge (expressed as concepts from the NCIt ontology)
rather than having to know the underlying models. This also means that the
queries are reusable across resources, which is not the case in the caGrid
infrastructure. This functionality will be incorporated into the NCRI ONcology
Information eXchange (ONIX4). Our approach involves a customised transformation
from annotated information models to an ontological representation using the
Web Ontology Language version 2 (OWL5). This representation supports
annotations based on a primary concept and a list of qualifiers. Based on these
ontological representations of the data resources, we have designed and
developed a query rewriting and translation approach that converts concept-based
queries into the query language supported by the caGrid infrastructure. This
approach is general and could be used to support other target query languages,
as the only step dependent on caGrid is the last one. This work presents
significant improvements over our previous work[
This paper is structured as follows. Section 2 introduces background material on the caGrid infrastructure. Section 3 presents an analysis of the caGrid query functionality and the type of queries supported by its query language. Then, we present in section 4.1 the OWL representation that is used for query rewriting and translation, which in turn is described in Section 4.2. The implementation details and performance evaluation results are given in Sections 4.3 and 4.4, respectively. The evaluation includes an analysis of the generated ontologies as well as several performance metrics for OWL generation and query rewriting, which justify the viability of our approach. After comparing our approach with related work in Section 5, we conclude the paper in Section 6, including considerations for future work. 4 http://www.ncri-onix.org.uk/ 5 OWL is a recommendation from the World Wide Web Consortium (W3C) and the language overview for its second version can be found at http://www.w3.org/TR/owl2-overview/
Background
caBIG®[
The metadata
hierarchy represents how the
semantics of raw data
(instance data) can be
augmented by overlaying
metadata of increasing
descriptiveness [
A data resource owner can share the data by developing caGrid data
services using common interfaces and metadata, as described above. In this way, a
data service encapsulates the data, which is kept in native formats (including,
for example, relational data or flat files), exposing an access interface based on
the object-oriented (UML) model of the underlying resource. The common
interface also exposes a query processor based on the Common Query Language
(CQL) defined for caGrid. CQL is an object-oriented query language reflecting
the underlying object model of the data resource while abstracting the physical
representation of the data[
caGrid also supports basic distributed aggregations and joins of queries over multiple data services by means of the caGrid Federated Query Infrastructure13, through a distributed extension of CQL called DCQL. Thus, caGrid relies on D/CQL – custom query languages based on the structural characteristics of the resources. In other words, caGrid builds a ’structural layer’, where queries are expressed in terms of objects, attributes and associated objects, without allowing for semantic queries. D/CQL are evolving to provide richer structural queries as new requirements arise from different caBIG® projects. However, these query languages do not allow for data extraction based on semantic information. Thus, a shortcoming of caGrid is that does not currently exploit the referent and domain metadata maintained for its data services. Additionally, as already mentioned, it is not possible to specify rules about the models nor the domain semantics.
As stated in the introduction, this work advocates the extension of the caGrid infrastructure to exploit its rich metadata by building a semantic layer, using semantic web technologies to exploit caGrid’s metadata. Additionally, this extension is capable of: a) accommodating other resources with different ways of dealing with metadata, and b) specifying rules at different levels of abstraction. 3
Analysis of the caGrid Query Language A CQL query is defined by an XML document, which must comply to a specified XML schema14. The schema indicates that a CQL query must specify a Target element, which is the data type of the query result. Optionally, an Attribute element might indicate a predicate over an attribute of the object with Target type and an Association may specify a link with a related object. In Table 1 we show how a CQL query is built recursively presenting it as a context-free grammar, where CQLQuery is the start symbol, is the empty string and xsd:string is the non-terminal variable representing the X SD:string data type.
So, CQL traverses the UML class diagram graph, where the Target is the initial class, the Association conditions allow for path navigation by traversing sequences of consecutive classes and Attribute conditions apply locally to individual classes. The terminal symbols Group and Group1 represent the combination of two or more constraints over a particular node in the UML class graph. 4
Ontology-based queries over the caGrid infrastructure As shown before, the caGrid queries rely on the structure of the underlying data resources, i.e. their UML models. Thus, a biomedical researcher interested in 12 http://cagrid.org/display/dataservices/CQL+2 13 http://cagrid.org/display/fqp/Home 14 The CQL XML schema is available at: http://cagrid.org/display/dataservices/CQL+Schemas LogicalOp →AND OR Predicate →EQUAL TO NOT EQUAL TO
LIKE IS NULL IS NOT NULL LESS THAN LESS THAN EQUAL TO GREATER THAN
GREATER THAN EQUAL TO Name → xsd:string RoleName → xsd:string Value → xsd:string QueryModifier → DistinctAttribute
DistinctAttribute
AttributeNames retrieving data about, for example, a particular gene of interest will need to explore the UML model of each relevant data service and build a query considering the specific attributes and associations of the class maintaining the Gene objects. The queries can be built programmatically or also through the caGrid portal15, which allows to explore the UML models and provides a query builder based on these models.
In this work, we propose a system that allows the user to concentrate on the concepts from the domain, as represented by the NCIt ontology on cancer, and build the ontology-based queries which are high-level 16 and descriptive17. Thus, the ontology-based queries can be applicable to any of the underlying data resources.
Apart from the cancer concepts found on NCIt, the queries combine elements from an ontology we built with metadata on UML models18, namely the UML model ontology. This ontology contains OWL classes to represent UML classes and attributes (UMLClass, UMLAttribute), OWL object properties to represent UML associations and the relationship between a UML class and its attributes (hasAssociation, hasAttribute) and a data property to represent the values of attributes (hasValue).
Some simple example queries19 are: a) Specimen to retrieve all the objects
that are annotated with the Specimen concept; b) Gene and hasAttribute some
15 http://cagrid-portal.nci.nih.gov
16 By a high-level query, we mean a query that can be written without specific details
about the structure of the target resource.
17 By a descriptive query, we refer to queries that provide the criteria for the desired
data rather than the procedure to find the data.
18 We will see later, than the queries could also use elements from the list ontology[
We note that the third query specifies SNPs that are associated with genes. This association may be present in different ways in two separate UML models. For example, the two corresponding classes may have a direct UML association, or the association may arise by traversing an association path from the first class to the second one. In order for our system to deal with those paths of associations, without the user requiring to know the specific underlying UML model, we define the hasAssociation property as transitive and use reasoning to determine the paths.
Next, we introduce our transformation from caGrid models to an OWL2 representation and the query rewriting/translation approach, which transforms ontology-based queries into CQL queries. The OWL2 ontologies provide an unified view of the UML models and their semantic annotations, which allows us to apply reasoning over them. 4.1
agrams. First, we present our customised UML-to-OWL transformation. This transformation differs from previous approaches, as explained in Section 5. Next, we describe the transformation and use the portion of the caBIO 4.2 information model in Figure 2 to give examples. Every UML element is related to its counterpart in the UML model ontology: all Fig. 2: Part of UML class diagram for UML classes and attributes are defined caBIO 4.2 as subclasses of UMLClass and UMLAttribute, respectively (see equations Eq. 1 and Eq. 2 below20); all the UML associations are sub-properties of hasAssociation (Eq. 4), and the datatype property hasValue is used to specify the type of the attributes (Eq. 3) as an existential restriction. Contrary to other UMLto-OWL transformations, we represent UML attributes as OWL classes. This is required so that the ontology-based queries can include the concepts associated with attributes.
c:Chromosome c:Chromosome number c:Chromosome number c:Chromosome locationCollection Location u:UMLClass u:UMLAttribute ∃ u:hasValue.xsd:string u:hasAssociation (1) (2) (3) (4)
UML subclass and superclass relationships are represented with subsumption (Eq. 5). For each UML class, existential restrictions are added for its associaan attribute and two associated UML classes with a restriction over an attribute of one of the classes, respectively. 20 The prefixes used in the equations are: c: for the caBIO 4.2 ontology, u: for the UML model ontology, n: for the NCIt ontology and l: for the list ontology. We note that the name of an OWL class corresponding to an attribute includes the class name to avoid duplications and for associations, it includes its domain and range. 7 tions (Eq. 6) and attributes (Eq. 7). While UML does not explicitly represent inherited associations, our OWL representation makes them explicit, modeling the semantics of UML. For example, as the UML class Location has an association chromosome with the class Chromosome, this association is inherited on the subclass CytogeneticLocation (Eq. 8).
c:CytogeneticLocatoin c:Chromosome c:Chromosome c:CytogeneticLocation c:Location ∃ c:Chromosome locationCollection Location. c:Location ∃ u:hasAttribute.u:Chromosome number ∃ c:Location chromosome Chromosome. c:Chromosome (5) (6) (7) (8)
We note that the generated OWL ontologies belong to OWL2EL[
OWL Representation of the Semantic Annotations. Apart from
representing the UML model, we also model its mapping to NCIt, as maintained
in caDSR. Through the CDEs, UML elements are annotated with a primary
concept, which indicates the meaning of the element. In turn, a list of qualifier
concepts may be used to modify the primary concept, giving specific meaning.
As OWL2 does not natively supports the representation of lists, we used
Drummond et al ’s design pattern for sequences[
c:Chromosome c:Chromosome numer c:SNPCytogeneticLocation n:Chromosome n:Name n:Location (l:OWLList ∃l:hasContents.n:Chromosome Band ∃ l:hasNext.(l:OWLList ∃ l:hasContents.n:Single Nucleotide Polymorphism)) (9) (10) (11)
Module Extraction from NCI Thesaurus Ontology. The NCIt
ontology is very large, as it provides a common vocabulary for the whole cancer
domain[
Query Rewriting and Translation
This section describes how an ontology-based query is rewritten and then
translated, first to an intermediate optimisation language and then to the target CQL
language. While the overall approach is similar to our previous work[
Parsing. First, the user query is syntactically parsed. The query uses
concepts from the NCIt, the UML model (see Section 4.1) and the list ontologies[
UML Extraction. The NCIt concepts in the query are translated into specific UML classes, by reasoning over the generated ontologies. Each concept is the super-class of a UML class or UML attribute, depending on their position on the query. Often, a single NCIt concept will correspond to many UML classes (or attributes) and, in such cases, each UML class is returned to form an individual query. Therefore, the outcome of the UML extraction is a combination of possible queries given the extracted UML classes or attributes. The outcome for our example query is: c:SNP and hasAssociation some (c:Gene and hasAttribute some (c:Gene symbol and hasValue value ”TGFB1”)) .
Data Values Extraction. As the generated ontologies do not contain instances, the semantic validation of the query, expressed as an OWL class expression, must ignore the data expressions. This step extracts the data expressions, which will be reinserted later on. This step results in c:SNP and hasAssociation some (c:Gene and hasAttribute some (c:Gene symbol)).
Semantic Validation. We use a reasoner to check that the resulting query can be satisfied. If the query cannot be satisfied, subsequent rewriting of the query is halted.
Properties Path Finder. This step deals with the ontology corresponding
to the UML model (the semantic annotations do not need to be considered
any longer) and aims at finding the path of UML classes related through the
transitive property hasAssociation21. The path finder rewrites the expression
using non-transitive properties, corresponding to UML associations, by using an
explanation generator[
Data Values Addition. At this point, we can retrieve the data expressions removed earlier and re-insert them into the corresponding OWL classes, resulting in c:SNP and hasAssociation some c:GeneRelativeLocation and hasAssociation some (c:Gene and hasAttribute some (c:Gene symbol and hasValue value ”TGFB1”)).
OWL Expression to MCC Translation. No calculus or algebra has been
defined for the object-oriented query language CQL. To provide a translation
with CQL as target language, we use the monoid comprehension calculus (MCC),
as it is a formal framework to support object queries optimizations[
A MC takes the form ⊕{e q}, where ⊕ is a monoid23 operator called the accumulator, e is the header and q = q1, . . . , qn, n ≥ 0 is a sequence of qualifiers. A qualifier can take the form of a generator, v ← e′ with v a range variable and e′ an expression constructing a collection, or a filter predicate. The symbol denotes the accumulator for bags24. For an OWL class expression from the previous step, an MCC expression is built such that: the header variable is determined by the first concept in the query and the qualifiers are built for each of the remaining expressions. The MCC expression for our example is: { s s ← SNP, r ← s.relativeLocationCollection, r ← GeneRelativeLocation, g ← r.gene, g ← Gene, g.symbol=TGFB1 }
MMC to CQL Translation. Translating the MCC expression into CQL
amounts to: define as Target the type of the variable that appears in the header
and then, including an Association per each pair of generators, one
determining the name (the class to which they belong) and the other identifying the
role name; include an Attribute restriction for each filter. As this last step is
the only one involving CQL, only this last step requires to be modified to
extend our methodology to other model-driven architectures with a different target
language. The resulting CQL in the example is:
<ns1 : CQLQuery xmlns : ns1=”http : / /CQL. caBIG/1/ gov . nih . n c i . c a g r i d . CQLQuery”>
<ns1 : Target name=”gov . nih . n c i . c a b i o . domain . SNP”>
22 For more details, we refer the reader to [
Implementation We have implemented two modules, with the functionalities: a) an OWL generator, which transforms a caGrid annotated UML model into an OWL ontology and includes the generation of a module from the NCIt containing the concepts relevant to the UML model; b) a query translation component, which takes as input a OWL class expression using concepts from the NCI thesaurus and transforms it into a CQL for a single data service.
For the first module, we also produced a caGrid analytical service called OWLGenService25, which provides a simple API for the extraction of modules from NCIt and for the ontology generation, given a specific information model.
The implementation was done in Java and uses caGrid version 1.326, the OWLAPI version 3.1.027 (after upgrading from OWLAPI version 2), and relies on the reasoners Pellet 2.2.228 and HermiT 1.3.029. 4.4
Performance Evaluation This section analyses the generated ontologies and presents two areas of performance evaluation that verify the viability of our approach. Since one important step in the query rewriting/translation process is the property path finder (see Section 4.2), we firstly introduce some metrics to assess the paths in the generated ontologies. These paths are sequences of concepts linked by object properties. Secondly, we present the generation times for the module extraction, the ontology generation and the inference of the ontologies using both the Pellet and HermiT reasoners. These results show that the generation of the ontologies that make possible our approach is done in a timely fashion. Thirdly, we evaluate the performance of the query rewriting process, showing a breakdown of the constituent parts of the rewriting algorithm. For this evaluation, we considered two sets of five queries each run over the caBIO data service30, where each set consists of queries that involve paths of lengths one and two. The tests were run 25 The OWLGenService is accessible through the caGrid tal at http://cagrid-portal.nci.nih.gov and available http://stylus 157.stylusinternet.net:9600/wsrf/services/cagrid/OwlgenService 26 http://wiki.cagrid.org/display/caGrid13/Home 27 http://owlapi.sourceforge.net/ 28 http://clarkparsia.com/pellet/ 29 http://hermit-reasoner.com 30 http://cabiogrid42.nci.nih.gov:80/wsrf/services/cagrid/CaBIO42GridSvc porat 11 on a Red Hat Enterprise Linux Server release 5.3 (Tikanga) with 64 bits and 48285 MB of RAM.
This section analyses the generated ontologies and presents two areas of performance evaluation that verify the viability of our approach. Since one important step in the query rewriting/translation process — from Section 4.2 — is the property path finder, we firstly introduce some metrics to assess the sequences of concepts linked by object properties (paths) in the generated ontologies. Secondly, we present the generation times for the module extraction, the ontology generation and the inference of the ontologies using both the Pellet and HermiT reasoners. These results show that the generation of the ontologies that make possible our approach take a short time. Thirdly, we evaluate the performance of the query rewriting process with a breakdown of the constituent parts of the algorithm. For this evaluation, we considered two sets of five queries each, where each set consists of queries that involve paths of lengths one and two. The results were obtained by running on a Red Hat Enterprise Linux Server release 5.3 (Tikanga) with 64 bits and 48285 MB of RAM.
Throughout this section, we have grouped caGrid projects into three distinct subsets: projects that are available from the caDSR service, all data services that are registered with the caGrid default index service31, and Information Models (or InfoModels) (those models that are supported by a deployed service from the caGrid Index Service)32. We note that the groups caGrid and InfoModels are the more relevant for our system, as only against these projects it is possible to execute CQL queries. While InfoModels include a single project from caDSR for a set of deployed services corresponding to that project, caGrid may include the results for several services that correspond to a single model. Thus, the caGrid results will be skewed according to the relative weight of services as opposed to models.
Analysis of the OWL representation of the information models.
While ontology metrics have been defined in several tools [
As seen in Section 4.2, our rewriting process seeks to remove the upperlevel and transitive object property hasAssociation and express the query using only non-transitive properties, which correspond to the UML associations in the models. In order to achieve this, we consider the paths between pairs of concepts 31 http://cagrid-index.nci.nih.gov:8080/wsrf/services/DefaultIndexService 32 It should be noted that not all caDSR projects are included in the metrics; some contained errors (their semantic metadata is not complete or refers to an older version of the NCI thesaurus) and some models are targeted for data modelling, rather than specifically holding data, making them not representative for our system. Out of the 136 projects in caDSR, 16 were excluded from the analysis for these reasons. However, none of the excluded projects had an associated service. Additionally, the caGrid subset has 63 services and InfoModels has 23 projects. 12 from the query connected through the hasAssociation property. The calculation of these paths is not trivial; there may be many intermediate nodes and there may be more than one path for a given pair of concepts. We define a journey as a traversal from one concept to another. A journey may have one or many paths, which represent the possible routes that the traversal can take. Thus, it is important to evaluate these aspects of the ontologies in order to assess the viability of a rewriting tool.
We propose the following metrics as a measure of complexity in this respect. The Longest Path is the maximum path length that may be computed within a given ontology. The longest path length provides an indication of the worse case for path calculation times. The Average Paths per Journey reflects the degree of path expansion within the rewriting algorithm, as each journey (e.g. from Node A to Node B) may have many different paths. The rewriting algorithm should return all possible paths as each path may refer to a different expression of the query. When we consider that a single query may include multiple independent journeys, the possible query rewritings can become very large. The Average Nodes per Path is the average number of nodes that must be visited in order to return a single path. The path length can affect the calculation time as well as the complexity of the resulting query.
Figure 3 illustrates three box-and-whisker plots with the results of the path metrics for each project subset. We observe that while the longest path can have up to 36 nodes, for 75 % of the projects in each category their length is less than 17 or 18. The average path length varies between 4 and 7 nodes over the three subsets, and for 75 % of the InfoModels it is less than 8. There is an average of around 2 paths returned for each journey, and for 75 % of the projects in each category the average path per journey is less than 2.5, indicating that we will be returning a low number of path combinations as a result. These results, then, verify that the paths within the ontologies are manageable and appropriate for our rewriting tool. We also note that in all the metric diagrams, the caGrid subset is often very densely clustered around the mean. This is due to the fact that there are often many caGrid services for the same project that differ to one another very slightly or not at all, which can result in multiple similar or identical results. 13
Ontology Generation, Module Extraction and Classification. In order to isolate any overhead caused by variations in network performance, we extracted the XML corresponding to each project (or information model) in caDSR. This is a preliminary step to run the performance evaluator locally, and we do not include any data about the performance of this stage. We generate four ontologies for each project: the NCIt module ontology (incorporating the concepts from NCIt relevant to the project), the annotated UML ontology (including the classes describing the UML model) and inferred versions of the two ontologies33. We recorded the time for each generation and Figure 4 shows them for the four ontologies per project grouped by subset. The times are presented in a logarithmic scale. We can see that the vast majority (75%) of NCIt modules take less than 2 seconds to generate and even less time for ontology generation. The classification of the generated ontologies is also timely, with the average inference of the Pellet and HermiT reasoners never taking longer than 100 milliseconds.
Query Rewriting Evaluation. We have developed a suite of queries of
varying complexity in order to evaluate the query rewriting. The results are
presented in figure 5, which shows the average time34 taken at each stage of
the query rewriting process35 for five queries whose rewriting has path length
one, five queries whose rewriting has path length two and the mean times for
these two sets. Path length refers to the number of intermediate nodes in the
query resulting from the rewriting. We can see from figure 5 that, while path
length has a marked effect on the time taken at the path finding stage, the other
stages of implementation remain largely unaffected. We therefore maintain that,
given our analysis of paths within our target ontologies described above, we can
provide query rewriting in a timely and efficient manner.
33 We generate the inferred ontologies classifying the generated ontologies using both
the HermiT and Pellet reasoners.
34 Each query was ran 5 times and the average times calculated.
35 These correspond to the stages of query rewriting; parsing, UML extraction,
validation, path finding, MCC conversion and CQL conversion. For more information,
refer to section 4.2.
The UML-to-OWL transformation has been studied in different contexts and
applications varying from the detection of inconsistencies in UML diagrams to
use as interchangeable modeling artifacts[
The use of semantic web technologies to support semantic queries over
distributed data environments in biomedicine have been implemented in systems
such DartGrid[
Conclusions
This paper presented the design and implementation of an ontology-based
querying functionality implemented over a service-oriented, model-driven
infrastructure aimed at sharing cancer research data. In particular, the implementation
was based on the caGrid infrastructure, but the approach could be used over
similar model-driven software infrastructures. We presented: a) the generation
of customised OWL2 ontologies from annotated UML models, based on the
ISO11179 standard for metadata registries, which differs from traditional
UMLto-OWL conversions and it is an improvement from[
Acknowledgements The authors are grateful to the National Cancer Research Institute Informatics Initiative for support for their research.