We describe an approach to create a synthetic workload for large scale extensional query answering experiments. The workload comprises multiple interrelated domain ontologies, data sources which commit to these ontologies, synthetic queries and map ontologies that specify a graph over the domain ontologies. Some of the important parameters of the system are the average number of classes and properties of the source ontology which are mapped with the terms of target ontology and the number of data sources per ontology. The ontology graph is described by various parameters like its diameter, number of ontologies and average out-degree of node ontology. These parameters give a significant degree of control over the graph topology. This graph of ontologies is the central component of our synthetic workload that effectively represents a web of data.
One of the primary goals of the Semantic Web is to be able to integrate data from diverse sources irrespective of the ontology to which it commits to. Unfortunately it is difficult to measure progress against this goal. Although there are a large number of ontologies, few have data associated with them, thereby making it difficult to execute large scale integration experiments. The aim of this paper is to provide a benchmark for a synthetic workload that can be easily scaled to the desired configuration for executing large scale extensional query answering experiments.
The benchmark described here was originally developed for evaluating our OBII
system [
The rest of the paper is organized as follows: In section 2 we provide a background about the related work. In Section 3 we define the various steps of data generation process like generation of domain ontologies, data sources, queries and the graph of ontologies to create mapping axioms. We introduce a mapping language for describing maps. In Section 4, we describe the methodology for carrying out an experiment and the performance metrics that can be used for evaluation. In Section 5, we conclude and discuss future work.
The LUBM [
Tempich and Volz [
There has been some prior work on benchmarking DL systems. Horrocks and
Patel-Schneider [
Garcia-Castro and Gomez-Perez [
J. Winick and S. Jamin [
We now describe the process of generating several types of synthetic workloads to represent a wide variety of situations. While generating the data set the user is given the freedom to modify the independent parameters while the rest essentially serve as controls whose values are dependent on the nature of applications, like information integration etc. The characteristics of a domain ontology and a map ontology are clearly demarcated in that the former does not have any import statements and a map inherits the axioms of the two ontologies being mapped. This approach is equivalent to having a set of ontologies some of which inherit the axioms of the others. But our approach is very useful in creating the graph of ontologies.
We implemented a workload generator that allows us to control several characteristics of our dataset. In generating the synthetic domain ontologies we decided to have on the average 20 classes and 20 properties (influenced by the dominance of small ontologies in the current Semantic Web).
Due to restrictions placed on our OBII system our existing implementation only
generates domain ontologies comprising subClassOf and subPropertyOf axioms in
order to support taxonomic reasoning. Also, following the statistical analysis of the
DAML ontology library [
To create a domain ontology, we randomly establish subClassOf and subPropertyOf relationships across classes and properties respectively. The class and property taxonomy have an average branching factor of 4 and an average depth of 3.
We consider a directed graph of interlinked ontologies, where every edge is a map from the source ontology to the target ontology. This map ontology comprises a set of mapping axioms. We describe the following terms for discussing such a graph
Whether the node is a terminal node i.e. has a zero out-degree. Before the map is created, we determine the number of terminal nodes and randomly mark those many domain ontologies as terminal. The algorithm is so designed, that it prevents a non-terminal node from attaining a zero out-degree. Also, there could be some terminal nodes with a zero in-degree, thereby disconnecting them from the graph.
Out-path length: The length of the longest outgoing path of a node
In-path length: The length of the longest incoming path to a node
The inputs to the graph creation algorithm are the number of ontologies, average out-degree of the nodes and diameter of the graph. There is a parameter – longPaths which indicates the number of paths having a diameter length. This parameter has been hard coded to 1 because we need to have at least one path of diameter length. The algorithm usually creates additional paths having a diameter length.
Another important parameter is the total number of maps. We show how this can be calculated from other parameters.
Let maps – total number of maps out – average out-degree onts – total number of ontologies term – total number of terminal ontologies
Parameters like maps, out and term are interrelated in that maps is approximately equal to the product of non terminal ontologies and out. Hence we have onts term out maps (1)
However we do not provide term as an input parameter. We show how a reasonable value can be computed from other parameters. We can express maps as the product of term and diameter. The number of maps is at least equal to this product. This is because the in-path length of a terminal node is equal to the diameter. There could be more maps, in situations where more than one diameter length path leads to a terminal node as explained below –
As shown above, the terminal node (marked ‘T’) has 4 paths of diameter length (diameter is 3) leading to it, effectively yielding more maps. Hence the equation below is desirable but not a requirement. Given that we prefer graphs that will branch out we will use term maps / diameter (2) Substituting (2) in (1) we get onts maps / diameter out maps onts out (maps * out) / diameter maps onts out maps (maps * out ) / diameter onts out diameter maps diameter maps out onts out diameter maps (diameter out)
maps (onts out diameter) /(diameter out)
Steps of the Algorithm term (onts out ) /(diameter out ) (3) (4)
vii. There sometimes arises a situation, where none of the existing nodes can satisfy the above constraints. This can happen in cases of large diameters and large out-degrees or when the diameter is equal to the number of ontologies. When such a situation arises a new ontology is created to serve as a target. Such ontologies which are dynamically created are termed as fresh ontologies. So the total number of ontologies at the end may be greater than the number of ontologies with which the algorithm began.
Once a map ontology is created the attributes of the source and the target have to updated as follows i. The source and the set of ontologies from which it can be reached must be added to the set of ontologies from which the target and its descendants can be reached ii. The out-degree of the source has to be updated. iii. The source must be made the parent of the target iv. The target should be made the child of the source v. The out-path length of the source and all its ancestors has to updated if applicable vi. The in-path length of the target and all its descendants has to be updated if applicable
Once the source and the target ontologies have been identified mapping axioms need to be established. A specific number of terms (classes and properties) from the source ontology are mapped to terms in the target ontology. Since the domain ontologies are randomly chosen while creating a map ontology we expect the latter to reflect a partial overlap between the two. Hence this value has been hard coded to 20% of the total number of classes and properties in the source ontology.
OBII uses the language OWLII [
Definition OWLII i. Let Lac be a DL language where A is an atomic class, and if C and D are classes and R is a property, then C⊓D and R.C are also classes. ii. Let La include all classes in Lac. Also, if C and D are classes then C⊔D is also a La class. iii. Let Lc includes all classes in Lac. Also, if C and D are classes then R.C is also an Lc class. iv. OWLII axioms have the form C⊑D, A B, P⊑Q, P Q, P Q−, where C is an La class, D is an Lc class, A, B are Lac classes and P, Q are properties.
At present we generate mapping axioms that fall strictly within OWLII. The limited expressivity of OWLII prevents generating inconsistent axioms, but when extended to more expressive axioms we can incorporate a consistency check to the ontology generation process.
In what follows we first describe how this is implemented in our current system and how it can be easily extended to OWL-DL. We create each mapping axiom by essentially generating an OWL parse tree with the root node being a subclass operator. Then based on a user supplied frequency table of various OWL constructors the tree is expanded by using named classes or owl constructors. The frequency table allows the users to specify a ratio of various owl constructors which they expect to have in their mapping axioms.
Our algorithm recursively builds the parse tree based on the above and
terminates by choosing named classes for all the remaining operands when the maximum
length of a mapping axiom is reached. If there doesn’t exist a mapping between a pair
of ontologies, it simply means that the latter are not related and represent different
domains. Such a landscape truly reflects the nature of semantic web comprising
groups of interrelated ontologies as well as lone ontologies. Thus answering a query
demands being selective about particular data sources instead of scanning the entire
data set. Our OBII system [
Note: In the above approach we essentially restrict the axiom generation to remain within OWLII by using certain constructors in either the subject or the object position of an axiom. This is done because our current implementation is geared towards data for OBII system. However, if we lift these restrictions and allow for any constructors to be on either side of the tree, we can generate axioms that are OWL-DL.
A specified number of data sources are generated for every domain ontology. Every
data source comprises ABox assertions with named classes/properties. For every
source a particular number of classes and properties are used for creating triples.
These triples are added to the source ontology being created. The number of classes
and properties to be used for creating triples can be controlled by specifying the
relevant parameters. With our current configuration the average data source has 75
triples. Considering the sparse landscape of the number of classes/properties from an
ontology which are actually instantiated [
Our query generation process generates SPARQL queries from a given set of
ontologies. Currently we support single ontology queries i.e. queries that have predicates
from a single namespace. This approach can be extended to multi ontology queries
quite easily. In our current approach we randomly choose an ontology from a set of
ontologies to be the query ontology. These queries are conjunctive in nature as in the
conjunctive query language of Horrocks and Tessaris [
The above policy reflects our desire to have a simplistic query generation approach that can generate queries that are useful in measuring a system's performance. It allows us to generate queries with a decent mix of classes, properties and individuals.
Note: Every conjunct/constant added to the query makes it more selective. With a diverse data set and randomly generated queries we obtain a wide range in the degree of query selectivity.
We present here our methodology of setting up an experiment for OBII and also the performance metrics that could be used for evaluation.
We feel that the most significant parameters that should be investigated are the number of ontologies, data sources, out-degree and diameter. A configuration is denoted as: nO-nD-nS where nO is number of ontologies, nD is diameter and nS is number of sources that commit to an ontology.
Metrics like Load Time, Repository Size, Query Response Time, Query
Completeness and Soundness could serve as good candidates for performance evaluation [
Repository Size: This refers to the resulting size of the repository after loading the benchmark data into the system. Size is only measured for systems with persistent storage and is calculated as the total size of all files that constitute the repository. Instead of specifying the occupied disk space we could express it in terms of the configuration size.
Query Response Time: We recommend this to be based on the process used in database benchmarks where every query is consecutively executed on the repository for 10 times and then the average response time is calculated.
Query Completeness and Soundness: With respect to queries we say a system is
complete if it generates all answers which are entailed by the knowledge base.
However on the Semantic Web partial answers will also be acceptable and hence we
measure the degree of completeness of each query as a percentage of the entailed answers
that are returned by the system. On similar lines we measure the degree of soundness
of each query as the percentage of the answers returned by the system that are actually
entailed. On small data configurations, the reference set for query answers can be
calculated by using state of the art DL reasoners like Racer and FaCT. For large
configurations we can use partitioning techniques such as those of Guo and Heflin [
Initial inspection has shown that our approach creates reasonable ontology graphs in that they are consistent with our input parameters and also have a good path length distribution from 0 to diameter. The graph topologies for some of the configurations are as follows. The nodes in the graph represent the ontologies and the links represent the mappings. A configuration is denoted by the following triple: “No. of ontologies – Outdegree – Diameter”.
Fig. 1a. 10 -2- 2 Fig. 1b. 10 – 2 - 5 There are some nodes in Fig. 1a which are disconnected from the graph. These are terminal nodes with zero in-degree. In the actual semantic web there could be such ontologies which do not map to any ontology and remain isolated.
In this paper we have discussed our approach for developing a benchmark for a complete synthetic workload. In any kind of benchmark there is some tradeoff between realism and in being simple and sufficient. Our approach is simple but could be easily generalized to support more expressive domain ontologies.
We have also introduced a new methodology for creating a graph of multiple interrelated ontologies that could be used by distributed query systems like OBII. The graph can be controlled effectively by parameters like diameter and average outdegree of the nodes. We could incorporate additional variables to represent in-degree and out-degree distributions where a few ontologies serve as “hubs” with very high out-degree and in other cases as “authorities” with a very high in-degree.
A single workload is incapable of evaluating different knowledge base systems. But our workload can be easily scaled to various configurations for the purpose of evaluation. This might encourage the development of more scalable reasoners in the near future.
It would be useful to allow the user to specify the distribution of RDFS, OWL Lite, OWL DL ontologies. Furthermore, we intend to conduct an initial experiment for comparing OWL reasoners such as Sesame, KAON2, Minerva and OWLIM.