Description Logics (DLs) are a well-established and popular family of decidable logics for knowledge representation and reasoning [6]. Several systems have been developed to reason over DL knowledge bases (KBs), which usually consist of a TBox and an ABox. A TBox describes the domain in terms of concepts and roles, while an ABox stores information about known instances of concepts and their participation in roles. Naturally, classical reasoning tasks like TBox satisfiability and subsumption under a TBox have received most attention and many reasoners have been devoted to them, e.g. FaCT++ [24], HermiT [22], or ELK [14]. These and other mature systems geared towards TBox reasoning have been rigorously tested and compared (e.g., JustBench [7]) using several real-life ontologies like GALEN and SNOMED-CT. A different category are reasoners for ontology-based query answering (OQA), which plays a major role in ontology-based data access (OBDA) [19]. They are designed to answer queries over DL KBs in the presence of large data instances (see e.g. Ontop [20], Pellet [21], Stardog [4] and OWL-BGP [16]). TBoxes in this setting are usually expressed in low complexity DLs, and are relatively small in size compared to the size of instance data. which makes OQA different from classical TBox reasoners. Several works have considered testing OQA systems [12, 17, 18, 23, 13]. Despite this, it has been acknowledged that judging the performance of OQA reasoners is difficult due to the lack of publicly available benchmarks consisting of large amounts of real-life instance data. In this paper we consider publicly available geographic datasets as a source of test data for OQA systems. In similar spirit, recently some benchmarks have been proposed to test implementations of geospatial extensions of SPARQL [15, 10]. The latter benchmarks are geared towards testing spatial reasoning capabilities, and cannot be easily adapted for testing OQA systems. The main goal of this paper is to describe how benchmarks for OQA systems can be created from OpenStreetMap [2] (OSM) geospatial data by employing a rule-based data transformation framework. The OSM project aims to collaboratively create an open map of the world. It has proven hugely successful and is constantly updated and extended. OSM data describes maps in terms of (possibly tagged) points, ways (geometries), and more complex aggregate objects called relations. We believe the following features make OSM a good source to obtain instance data for OQA reasoners: ? The authors were supported by FWF projects P24090 and P25518, the WWTF project ICT12015, and the EU project Optique FP7-318338.
- Datasets of different sizes exist; e.g., OSM maps for all major cities, countries, and continents are directly available or can be easily generated. - Depending on the location (e.g., urban versus rural), the density, separation, and compactness of object location varies strongly. - Spatial objects have an inherent structure of containment, bordering, and overlapping, which can be exploited to generate topological relations (e.g., contains). - Spatial objects are tagged with semantic information like the type of an object (e.g., hospitals). This information can be naturally represented as DL concepts and roles.
The paper is organized as follows. We first develop a formalization of OSM that allows to view OSM maps as relational structures. We then present a rule-based language to extract information from OSM data. Afterwards, we describe the implementation of our approach together with some generated benchmarks. Finally, we present some experimental results and conclude. 2
In this section, we first formally describe our model for OSM data, and then employ it to describe our rule-based language to extract instance data from OSM data.
Maps in OSM are represented using four basic constructs (a.k.a. elements): (1) nodes, which correspond to points with a geographic location; (2) geometries (a.k.a. ways), which are given as sequences of nodes; (3) tuples (a.k.a. relations), which are given as sequences of nodes, ways and tuples; (4) tags, which are used to describe metadata about nodes, ways and tuples. Geometries are used in OSM to express polylines and polygons, in this way describing streets, rivers, parks, etc. OSM tuples are used to relate several elements, e.g. to indicate the turn priority in an intersection of two streets. Formalization of OSM We assume infinite mutually disjoint sets Mnid; Mgid; Mtid and Mtags of node identifiers, geometry identifiers, tuple identifiers and tags, respectively. We let Mid = Mnid [ Mgid [ Mtid and call it the set of identifiers. An (OSM) map is a triple M = (D; E ; L) such that: 1. D Mid is finite set of identifiers called the domain of M. 2. E is a function from D such that: (a) if e 2 Mnid, then E (e) 2 R R; (b) if e 2 Mgid, then E (e) = (e1; : : : ; em) with fe1; : : : ; emg (c) if e 2 Mtid, then E (e) = (e1; : : : ; em) with fe1; : : : ; emg 3. L is a labeling function L : D ! 2Mtags .
D \ Mnid; D; Intuitively, in a map M = (D; E ; L) the function E assigns to each node identifier a coordinate, to each geometry identifier a sequence of nodes, and to each tuple identifier a sequence of arbitrary identifiers.
Enriching Maps with Computable Relations The above formalizes the raw representation of OSM data. To make it more useful, we support incorporation of information that can be computed from a map. In particular, we allow to enrich maps with arbitrary computable relations over Mid. Let Mrels be an infinite set of map relation symbols, each with an associated nonnegative integer, called the arity.
An enriched map is a tuple M = (D; E ; L; M), where (D; E ; L) is a map and M is
a partial function that assigns to a map relation symbol R 2 Mrels a relation RM Dn,
where n is the arity of R. In this way, a map can be enriched with externally computed
relations like the binary relations “is closer than 100m”, “inside a country”, “reachable
from”, etc. For the examples below, we assume that an enriched map M as above
always defines the unary relation Tag for every tag 2 Mtags. In particular, we let
e 2 TagM iff 2 L(e), where e 2 D. We will also use the binary relation Inside(x; y),
which captures the fact the location of a point x is inside a geometry y.
A Rule Language for Data Extraction We define a rule-based language that can be
used to describe how an ABox is created from an enriched map. Our language is based
on Datalog with stratified negation [
An atom is an expression of the form R(t) or :R(t), where R is a map or a Datalog
relation symbol of arity n, and t is an n-tuple of terms. A rule r is an expression of the
form B1; : : : ; Bn ! R(t); where B1; : : : ; Bn are atoms (called body atoms) and R(t)
is an atom with R a Datalog relation. We assume Datalog safety, i.e. each variable of a
rule occurs in a non-negated body atom. A program P is any finite set of rules. A rule
or program is ground if it has no occurrences of variables. We only consider stratified
programs (see [
The semantics of a program P is given relative to an enriched map M. The
grounding of a program P w.r.t. M is the (ground) program ground(P; M) that can be
obtained from P by substituting in all possible ways the variables in rules of P with
identifiers occurring in M or P . We use a variant of the Gelfond-Lifschitz reduct [
We next illustrate some of the features and advantages of the presented rule language. E.g. the following rule collects in the role hasCinema the cinemas of a city (we use a sans-serif and a typewriter font for map and Datalog relations, respectively):
Point(x); Tagcinema(x); Geom(y); Tagcity(y); Inside(x; y) ! hasCinema(y; x): Negation in rule bodies can be used for default conclusions. E.g. the following rule states that recreational areas include all parks that are not known to be private:
Geom(x); Tagpark(x); :Tagprivate(x) ! RecreationalArea(x):
Mapping Framework. The framework allows the user to define the data transformation for the instance generation in a declarative manner. As simplicity and extensibility are two of our main goals, we address these on two levels.
The first level concerns the extensibility of the mapping language and the related evaluation method by supporting: (a) An ETL mode which resembles the extract, transform, and load (ETL) process of classical data transformation tools; (b) A Datalog mode which offers the features of Datalog with stratified negation. The second level concerns the data sources (e.g., OSM) and external evaluation (e.g. calculating spatial relations). In certain cases we have to use external functionality for more sophisticated computations. E.g., in the ETL mode, we treat the scripts as custom data source or as simple transformations between input and output.
The Datalog and an ETL language are combined in the following custom mapping language. The Data Source Declarations are concerned with the general definitions as PostgreSQL/PostGIS connections. The ETL Mapping Axioms define a single ETL step, where the syntax is an extension of the Ontop mapping language. It is defined either as a pair of source and target or as a triple of source, transform, and target. The following sources and targets are currently available: (a) PostgreSQL/PostGIS with SQL statements as a source or target; (b) Text files with regular expressions as a source or target; (c) RDF files with SPARQL queries as a source; (d) External Python scripts and constants as a source. The Datalog Rules are based on the syntax of the library pyDatalog and embedded into the source and target of a mapping axiom. Implementation. The main Python 2.7 script of the developed generation framework is called as follows: generate.py {mappingFile le.txt {mode etl|datalog
The ETL mode is designed for bulk processing, where scalability and performance is crucial and complex calculations are not used or moved into the external scripts. We implemented the computation in a data streaming-based manner. The Datalog mode is designed for the features of stratified Datalog, where the entire result is always inmemory. In this mode, dependencies between sources and targets are considered by the declarative nature of Datalog. We use the same source and target components as in the ETL mode but follow a computation of three steps: 1. The source components are evaluated to store the n-tuples in the EDB; 2. The stratified Datalog program is evaluated; 3. The IDB predicate outputs are processed by the target components.
The architecture naturally results from the two modes, and the source and target components. Besides the generation script, we already provide a selection of external scripts for processing OSM data. E.g., spatialRelationsReader.py calculates the spatial relations (e.g., contains) between two RDF files. 4
All the mapping files and test data for the introduced benchmark are available online [
The chosen DL-LiteR [
Spatial Relations Benchmark (BM1). For the cities, we transform all the amenities (e.g., restaurants), leisure areas (e.g., playgrounds), and shops to concept assertions. Then, we calculate the roles for the spatial relations inside between leisure areas and amenities. Further we generate several next relations between amenities and shops. The different next relations are generated according to the distances of 50m, 100m, 250m, and 500m between two objects. We define five queries that use the different “spatial” roles. In q1 we evaluate over general concepts with a low selectivity of the role contains. The query q2 determines which shops are next to amenities, which in turn are inside a park. Query q3 resembles a star shaped pattern of relationships and uses the role hasCuisine derived from OSM tags. In query q4, we have a triangular pattern of relationships and query amenities which are located in two leisure areas that overlap. With q5, we illustrate that arbitrary role chains can be used by connecting next. q1(y; z) q2(x; y; z) q3(x; y; z) q4(x) q5(x; y)
Amenity(y); contains(z; y); Leisure(z)
Shop(x); hasOperator(x; w); SupermarketOp(w); next(x; y);
Amenity(y); inside(y; z); Leisure(z)
Amenity(x); hasQualitativeValue(x; u); Cuisine(u); next(x; y);
Shop(y); contains(z; x); Leisure(z)
Amenity(x); next(x; y); Leisure(y); intersect(y; z); Leisure(z); next(x; z)
Amenity(x); next(x; z); next(z; y); Shop(y)
Evaluation and Results. We consider the following query answering systems: (a)
Pellet [
The evaluation results are presented in Table 1, where S stands for Stardog, P for Pellet, and OB for OWL-BGP, and show that BM1 is indeed challenging for instances as Vienna. We can see a gradual increase of difficulties with increasing city size and the distance of next. q1 and q2 can be seen as the baseline results with low/high selectivity and pose no challenge to the reasoners. With the queries q3, q4, and q5, we can see a breaking point where the performance starts to decline for all reasoners. For Stardog this is Vienna with next250 (a next distance of 250), for Pellet this is Vienna next250, and for OWL-BGP it declines with Vienna next250. Remarkably, every reasoner has the following strengths: (a) OWL-BGP has the best performance in the queries q1, q2, and q3; (b) Stardog outperforms the other in the large instances of q4, and q5; (c) Pellet is best at the the medium to large instances of q4, and q5. Note that query q5 is the most challenging one due to the join of the large next relations, which are 939 988 (resp. 2 857 488) instances for next250 (resp. next500) in Vienna. 5
In this paper, we have presented a framework for extracting instance data from OSM. Based on the framework, we have evaluated some state-of-the-art OQA systems with our benchmark and showed that the respective systems have their strengths and weaknesses depending on the particular input query, and the size and the structure of the input ABox.
Future research is directed to variants and extensions of the framework. We aim to extend the implementation to capture more input and output sources, further parameters (e.g. various degrees of graph connectedness), and services. An important functional extension would allow us to remove some assertions that are implied by the input ontology, in this way the information incompleteness could be better controlled. Another extension could be related to automatic generation of TBoxes by means of analysis of geospatial data. Further, our benchmark ontology could be extended to other important DLs as E L and its relatives. Finally, based on our open repository, we aim to collect a wider range of benchmarks with the related transformations and data extracts.