Multidimensional enrichment of spatial RDF data for SOLAP

2.1.Spatial data warehouses and SOLAP

Data cubes and spatially extended cube concepts Data warehouses (DW) are based on a multidimensional model that models data in an n-dimensional space – often referred to as a data cube. A cube schema defines the structure of a cube with MD concepts. The cells of the cube represent (observation) facts with a set of attributes called measures. Facts are linked to dimensions, which are the axes of an MD space and provide perspectives to analyze the data. Dimensions are organized into hierarchies, which allow users to aggregate measures at different granularities along the levels of a hierarchy. Hierarchies are composed of levels, which have a set of attributes describing the characteristics of the level members. Each level member is defined by its attributes and attribute values.

Cube members are MD concepts that are defined at the instance level and composed of level members, attributes of level members, partial order on level members, and fact members. A hierarchy step between levels (a child level and a parent level) defines a set of roll-up relations, where each relation relates a child level member to a parent level member. These roll-up relations define a partial order between level members with a cardinality relation. The cardinality (1:1, 1:N, N:1, N:M) describes the number of members in one level that can be related to a member in the other level for both child and parent levels.

Spatial data warehouses (SDW) extend a DW by storing geometries such as point, line, and polygon in the values of spatial measures and values of level attributes for spatial dimensions. The spatially extended MD schema of an SDW has spatial dimensions, spatial hierarchies, spatial levels [29], spatial hierarchy steps, and topological relations (in addition to cardinality relations) between spatial levels for each spatial hierarchy step [13]. Topological relations are Boolean spatial predicates that specify how two spatial objects are related to each other, e.g., within, intersects, touches, crosses and etc. [6]. Similar to conventional DWs, facts of an SDW can be associated with numeric measures, which are using aggregation functions such as SUM, AVG, etc. A fully extended spatial MD schema of an SDW should also define spatial measures, which have geometries and spatial aggregate functions. Spatial aggregate functions aggregate two or more spatial objects and return a new spatial object. Union, Intersection, ConvexHull, and Minimum-BoundingRectangle (MBR) are example of spatial aggregate functions. For a detailed explanation of SDW concepts we refer the reader to [42].

Fig. 2.

GeoFarmHerdState – parish, farm, and drainage area instances.

Fig. 3.

GeoFarmHerdState – conceptual MD schema of livestock holdings data (spatial concepts).

OLAP and spatial OLAP operations DWs are commonly used to store large volumes of data for decision support with On-Line Analytical Processing (OLAP) operations. Spatial OLAP (SOLAP) integrates the features of OLAP tools and geographical information systems (GIS) [38]. SOLAP enables advanced analytical processing by taking the spatial information in the cube into account.

For example, a spatial data cube of livestock holdings in farms (referred to as GeoFarmHerdState in the rest of this paper) defines the farm location as a spatial measure, which is linked to the observation facts. In order to derive perspectives and relations on the state of the farms’ livestock holdings (herds), spatial levels are defined: parishes and drainage areas. A sample set of the corresponding spatial data cube members are given in Fig. 2. The spatial MD concepts of the data cube are defined in the conceptual schema in Fig. 3, which depicts a simplified version of the GeoFarmHerdState spatial data cube without its non-spatial dimensions (see [12] for further details the GeoFarmHerdState cube). The cube has two spatial dimensions: FarmDim and ParishDim. The latter has a spatial hierarchy (Geography) with two spatial levels: Parish and DrainageArea. FarmDim on the other hand does not have a spatial hierarchy, despite its spatial (base) level: Farm.

The GeoFarmHerdState cube has spatial fact members for farms within a time frame and different kinds of measures, i.e., numeric measures: NumberofAnimals in the farm and NitrogenReduction potential of the farm land/soil, spatial measures: FarmLocation (Fig. 3).11

To evaluate SOLAP operations, spatial levels such as Parish and DrainageArea are used to aggregate measures at different levels of detail. Due to the polygon geometry of the spatial level members, there are two different roll-up relations for the hierarchy step between the Parish and DrainageArea levels, where a parish can be completely contained within a drainage area or a parish and a drainage area can intersect.

For example, parish “Oue” is within drainage area “Mariager Inderfjord”. Thus, all the farms that are within “Oue” are also within “Mariager Inderfjord”. Whereas, parish “Astrup” intersects with drainage areas “Mariager Inderfjord” and “Langerak”. Therefore, some farms that are within “Astrup” are within “Mariager Inderfjord”, while the rest of the farms are within “Langerak”. Figure 2 displays a sample set of Parish and DrainageArea level members.

The possible roll-up relations for the example above are depicted in Fig. 4 with black and red arrows representing the topological relations within and intersects. Blue arrows show the topological relation contains, which are drill-down (inverse operation of roll-up) relations from DrainageArea level to Farm level.

Topological relations between levels and facts can be implicitly specified through the geometry attributes of their instances (level members and fact members). The relations between spatial levels enable processing spatial roll-up and drill-down through range queries with spatial predicates [8]. In terms of cardinality, there is an N:M relationship between level members since a parish may intersect with more than one drainage area and vice versa. This induces the problem of computing measures incorrectly when a roll-up operation goes through an N:M relationship, which actually is the case between the Parish level and the DrainageArea level. For example, we would like to aggregate the measure NumberOfAnimals, from Parish level to the DrainageArea level with a roll-up query. In such a roll-up query, we might falsely aggregate the number of animals in farms that are contained within the parish, but not contained within the drainage area, since the parish intersects with another drainage area. In order to refine such an analysis, SOLAP operations are required, where a (spatial) drill-down should be applied to the lowest granularity – from Parish level members to GeoFarmHerdState fact members, and then a spatial roll-up (with within predicate) can be applied from fact members (Farm instances) to DrainageArea level members. This would prevent falsely aggregating the number of animals from the farms that are (spatially) disjoint to the corresponding drainage area.

Fig. 4.

Hierarchy example for SOLAP.

Fig. 5.

Hierarchy steps in QB4OLAP before multidimensional enrichment.

2.2.QB4SOLAP: Spatial RDF data cube vocabulary for SOLAP operations

There is an increasing amount of Linked Open Data (LOD) on the Semantic Web containing spatial information and numerical (statistical) data. This led to new opportunities for OLAP over spatial data using semantic web technologies and standards. Datasets on the SW use a standardized format: RDF (Resource Description Framework).22

In order to enable SOLAP operations on the Semantic Web, a comprehensive vocabulary is needed, i.e., annotation of the spatial hierarchy steps with topological relations. QB4SOLAP [15] is a vocabulary that allows the definition of cube schemas and cube instances in RDF. The QB4SOLAP vocabulary is an extension of QB4OLAP [7] capturing the semantics of spatial MD concepts (i.e., spatial hierarchy steps) that are essential for SOLAP operations. The QB4SOLAP vocabulary V1.3 is available on our project website33 as well as via a persistent URL.44

A comprehensive foundation of spatial data warehouses on the Semantic Web can be found in [15], which includes detailed definitions with semantics of spatial MD concepts both at the schema level and instance level using QB4SOLAP.

In the following, we depict an example of a hierarchy step from gfs:Parish child level to gfs:drainageArea parent level (Fig. 5). In the figure, we prefix the schema elements (attributes, levels, etc.) of the (GeoFarmHerdState) cube with gfs: and instance data from the cube with gfsi:. The left-center part of Fig. 5 shows the hierarchy structure _:hs, between gfs:parish and gfs:drainageArea levels at the schema level with the QB4OLAP vocabulary. QB4OLAP objects, classes, and properties are prefixed with qb4o:. The levels (gfs:parish and gfs:drainageArea) are linked to the instances of level members (e.g., gfsi:parish_8648, gfsi:water_3710 and etc.) by qb4o:memberOf property. The polygon geometry attributes are highlighted in blue boxes, on the top and the bottom of the figure. The coordinates recorded in the geometry attributes can be used to derive the topological relation between the level members by applying spatial boolean predicates (e.g., instersects?, within?) on the polygon geometries of the parish and drainage area level members.

However, QB4OLAP does not support annotating the topological relations that might exist between the level members at a hierarchy step. QB4OLAP uses only skos:broader property from SKOS (Simple Knowledge Organization System) [30] semantic relations for capturing the roll-up relations at hierarchy steps. The roll-up relations with skos:broader property are highlighted in red boxes in Fig. 5. The skos:broader property does not describe the nature of the roll-up relation with topological relations for spatial hierarchies. Therefore, QB4OLAP cannot capture the topological relations in a hierarchy step from Parish level to DrainageArea level or between these levels’ members.

Fig. 6.

Spatial hierarchy steps in QB4SOLAP after multidimensional enrichment.

On the other hand, QB4SOLAP can define topological relations both at the schema level and the instance level. In Fig. 6, we prefix QB4SOLAP objects, classes, and properties with qb4so: and highlight them in green lines. The left-center part of the figure shows the spatial hierarchy structure :_shs, which has a QB4SOLAP property qb4so:pcTopoRel with two QB4SOLAP class instances qb4so:Within and qb4so:Intersects. This means that when we compare the geometry attributes of parish level members and drainage area level members, we discover two different topological relations (within and intersects) for all the (spatial) hierarchy steps between the parish and drainage area levels. And these relations are annotated at the schema level on the left-center part of Fig. 6.

Similarly, gfs:parish and gfs:drainageArea levels are linked to the instances of level members (e.g., gfsi:parish_8648) by qb4o:memberOf property. The explicit topological relations between each level member along a spatial hierarchy step are depicted in the figure with qb4so:intersects or qb4so:within predicates, which are highlighted in green boxes (e.g., gfsi:parish_8648 intersects with gfsi:water_159 and gfsi:water_3170 etc.).

In conclusion, QB4SOLAP enables SOLAP operations by defining the semantics of spatial MD concepts both at the schema level and instance level. These semantics are essential for SOLAP operations, and they are defined as extensions to the QB4OLAP vocabulary.

4.1.Hierarchical enrichment phase

The hierarchical enrichment phase is built around spatial levels and their level members forming the spatial hierarchy of a dimension. Thus, by identifying the spatial relations between spatial levels and their level members, we can find the spatial hierarchy steps and the possible topological relations for these hierarchy steps.

Each spatial hierarchy corresponds to a path of roll-up relationships between the child level and parent level: each of these roll-up relationships corresponds to a spatial hierarchy step (Section 2.1). An example of a (spatial) hierarchy with QB4SOLAP is given in Listing 1. Line 4 extends the QB4OLAP schema definitions by enriching the hierarchy step with the possibility to annotate the spatial hierarchy steps with topological relations (see Section 2 for details and Section 2.2 for examples).

Listing 1.

Spatial hierarchy structure in QB4SOLAP

Listing 2 shows the GeoFarmHerdState spatial level members from Parish and Drainage Area levels. Lines 1–7 (Listing 2) represent the QB4OLAP annotation of a child level member from Parish level before multidimensional enrichment (with skos:broader), which is depicted in Fig. 5. Lines 8–14 represent the QB4SOLAP annotation of the same Parish level member after the multidimensional enrichment with topological relations (depicted in Fig. 6). Lines 15–22 represent the annotation of a parent level member from the Drainage area level, which remains the same before and after multidimensional enrichment since the hierarchy steps are defined with bottom-up relationships from child level to parent level and the roll-up relations and thus also the topological relations are annotated at the child level members of the hierarchy step.

Listing 2.

GeoFarmHerdState level members, attributes, and spatial roll-up relations

We exploit QB4OLAP semantics, such as non-spatial hierarchy steps and levels as a starting point to find the spatial hierarchy steps. We distinguish two cases:

Case 1: Finding explicit spatial hierarchy steps for QB4OLAP levels, with skos:broader roll-up relations between their child-parent level members by detecting spatial hierarchy steps in Section 4.1.2. For this case we assume that level members have direct skos:broader relations as depicted in Fig. 5 and Listing 2, Line 7 with skos:broader property.

Case 2: Finding implicit spatial hierarchy steps from QB4OLAP levels without direct roll-up relations through the skos:broader property. In this case, we assume that the level members are only defined by the qb4o:memberOf property as shown in Listing 2, (Line 2) but do not have the skos:broader roll-up relation as given in Line 7. In this case, it is still possible to discover spatial hierarchy steps by finding spatial (topological) relations between level members through their attributes as explained in Section 4.1.3.

4.1.1.Spatial helper functions

To address the cases explained above, we need two spatial helper functions; for retrieving spatial attribute values (Algorithm 1, getSpatialValues), and for relating spatial attributes (Algorithm 2, relateSpatialValues).

Algorithm 1 (getSpatialValues) The first helper function gets an input graph of attributes of level members GA(lm)I and returns a set of spatial attribute values Vs(a). For example, the function could receive Lines 3–6 from Listing 2 as input. In the algorithm, Lines 3 and 4 check the values vai of each attribute idS(ai) (e.g., gfs:parishName, gfs:ParishArea, etc.) If the value is a type of geo:SpatialLiteral (e.g., the POLYGON geometry value linked to the gfs:parishPolygon attribute), then the value is incrementally added to the output set Vs(a)77 in Line 5.

Algorithm 1

getSpatialValues(GA(lm)I): Vs(a)

Algorithm 2

relateSpatialValues(vac,vap): topoReli

Algorithm 2: (relateSpatialValues) The next helper function is designed based on Table 1, w.r.t. the geometry values of the child-parent level members and based on the structure of a hierarchy step. We prepared Table 1 with topological relations based on DE-9IM.88 We consider only the three simple geometry types, point, line, and polygon as the spatial attribute values of child-parent level members in roll-up relations, excluding complex geometry types, such as multi-polygon, multi-point, etc. The possible topological relations that can occur in a spatial hierarchy step with a roll-up relation from child level to parent level are marked with check sign (✓) in the table. Topological relations, such as contains and covers, are not hierarchically applicable since a spatial child level member cannot contain or cover a spatial parent level member. For these relations, we mark the complete rows with minus sign (−) in the table, since they are not hierarchically applicable. Similarly, we mark the complete columns of line-point, polygon-point, and polygon-line roll-up relations with the minus sign (−) since these are also not hierarchically applicable. This is because we assume that in the instance data, a parent level member should always have a spatial attribute of a geometry type of the same or higher dimensionality of its child level member (a point is 0-dimensional, a line is 1-dimensional and a polygon is 2-dimensional).

Table 1

Topological relations for hierarchy steps (✓: hierarchically and topologically applicable, ×: topologically not applicable, −: hierarchically not applicable)

Topological relations		Roll-up relations
	Child level	Point (pt.)			Line (ln.)			Polygon (po.)
	Parent level	pt.	ln.	po.	pt.	ln.	po.	pt.	ln.	po.
within		×	✓	✓	−	✓	✓	−	−	✓
contains		−	−	−	−	−	−	−	−	−
intersects		✓	✓	✓	−	✓	✓	−	−	✓
touches		×	×	×	−	✓	✓	−	−	✓
overlaps		×	×	×	−	✓	✓	−	−	✓
crosses		×	×	×	−	✓	✓	−	−	×
coveredBy		×	×	×	−	×	✓	−	−	✓
covers		−	−	−	−	−	−	−	−	−
equals		✓	×	×	−	✓	×	−	−	✓

For example, a child level member with a spatial attribute of line geometry can only have parent level member(s) with spatial attributes of line or polygon geometries but not point geometry. We mark the topologically not applicable relations with cross sign (×) according to the DE-9IM model (e.g, a line cannot overlap a polygon).

Fig. 8.

Simplifying topological relations.

In Fig. 8, we depict the hierarchically and topologically applicable topological relations from Table 1. We simplified them by generalizing the possible relations, e.g., if a line touches or crosses another line at one point, they are both classified as intersects in Fig. 8(d). The most general relations are underlined in Fig. 8 for each pair of geometry types (Fig. 8(a), (b), (c), (d), (e), and (f)).

In Algorithm 2 relateSpatialValues, we only consider these general topological relations that have a higher probability to satisfy the corresponding spatial predicates. For example, the topological relation intersects has the highest probability to satisfy from the DE-9IM matrix [6]. We generalize similar spatial predicates to ones that have higher probability to occur in a 2-dimensional space. For example, relations, such as a line overlaps (along the border of) a polygon, can be generalized to the relation – a line crosses a polygon at a minimum two points, which can later be generalized to the relation – a line intersects a polygon at a (minimum) single point as in Fig. 8(e). Similarly, a line touches a polygon at a single point can be generalized to the relation – a line intersects a polygon at a (minimum) single point.

The topological relation coveredBy requires an area of a geometry, therefore it is applicable only in line-polygon and polygon-polygon relations (Fig. 8(e) and 8(f)). For reasons of simplicity, we choose to generalize them as the within topological relation. In the algorithm, we also prioritize to check the topological relations based on the compared geometry types. If the spatial attribute values to relate are point and polygon geometry types, as in Fig. 8(c), it is more likely that a point is within a polygon than a point intersects a polygon in the instance data.

Therefore, we initially check for a more probable relation in the algorithm. For example, for the point-polygon relations case in Algorithm 2, Line 10: initially, the within spatial predicate is checked in the if statement (Line 11), then the intersects spatial predicate is checked in the else if statement (Line 13). After checking all the possible combinations of spatial attribute values in a switch case, a topological relation is returned from the algorithm (Line 30).

Now that we have introduced spatial helper functions, we present the main algorithms for finding the spatial hierarchy steps in the following.

4.1.2.Detecting spatial hierarchy steps

Algorithm 3 (detectSpatialHS) corresponds to case 1 (see the beginning of Section 4.1) and finds the explicit spatial hierarchy steps for QB4OLAP levels with skos:broader roll-up relations between child-parent level members. Intuitively, Algorithm 3 works as follows. Given instance graphs of attributes of level members GA(lm)I and roll-up relations of the hierarchy steps GRU(hs)I between level members (using skos:broader), the key principle is to first retrieve pairs of child-parent level members based on the given input relationships GRU(hs)I. Then, spatial values are extracted (getSpatialValues) and finally the spatial relationship is verified (relateSpatialValues). The output GRU(shs)I is then a graph of detected and verified hierarchy steps.

As an example, let us consider Listing 2: given Lines 1–6 (GAI(lm)), Line 7 (GRIU(hs)), and Lines 15–22 (GAI(lm)) as input, Algorithm 3 produces Line 14 (GRIU(shs)) as output.

Formally, Algorithm 3 works as follows:

Algorithm 3

detectSpatialHS(GRU(hs)I,GA(lm)I): GRU(shs)I

Algorithm 3 (detectspatialHS) The input variables for Algorithm 3 are the instance graphs of attributes of level members GA(lm)I and roll-up relations of the hierarchy steps GRU(hs)I between the level members. The RDF graph formulation of the attributes of the level members A(lm) is: GA(lm)I=⋃i=1p{(idI(lm)idS(ai)vai)∣lm⇝vai}. Here, we denote by lm⇝vai that a level member lm has value vai for attribute ai (e.g., Listing 2, Lines 3–6, Lines 9–13, and Lines 17–22). The RDF graph formulation of the roll-up relations RU(hs) is: GRU(hs)I=⋃i=1k{(idI(lmc)skos:broaderidI(lmp))∣lmci⊑lmpi}. Here, we denote by lmci⊑lmpi the partial order between level members, where a child level member lmci rolls up to a parent level member lmpi99 (e.g., Listing 2, Line 7).

The output of Algorithm 3 is the instance graph of roll-up relations for the detected spatial hierarchy steps GRU(shs)I (e.g., Listing 2, Line 14). In Line 2, initially the output graph is initialized as an empty set. Next, in Line 3 we create two temporary graphs: GA(lmc)I and GA(lmp)I as empty sets,1010 to keep triple patterns separately in two graphs for attributes of child and parent level members. We also create two temporary sets: Vs(ac) and Vs(ap) for keeping the spatial attribute values from the child and parent level members, and initialize them as empty sets in Line 3. A set of spatial attribute values is defined over spatial literals Ls as Vs(a)={va1,…,vai,…,van∣1⩽i⩽n∧vai∈Ls}.

In the foreach loop in Line 4, we go through the elements of the input graphs GA(lm)I and GRU(hs)I that are fulfilling a specific criteria, which is having an explicit skos:broader relation between child and parent level members.

In Line 5, while iterating through the foreach loop, we assign the set of triples of child level members and their attributes to the temporary graph GA(lmc)I. This temporary graph is given in Line 6 as an input to the helper function getSpatialValues (Algorithm 1), which finds the spatial attribute values from the given graph, and returns a set of spatial attribute values (i.e., Vs(ac)) that are found in the input graph. The output of the helper function (Vs(ac)) keeps the spatial attribute values of the child level member idI(lmc).

Next in Line 7, if Vs(ac) is not empty and has some spatial values of idI(lmc), we populate the next temporary graph GA(lmp)I with its parent level idI(lmp) and attributes of the parent level in Line 8.

Similar to Line 6, Line 9 calls the helper function getSpatialValues with the input graph GA(lmp)I and the output of the function is assigned to the temporary set Vs(ap). If this set is also not empty (Line 10), we go through the pairs of values (vac,vap) of the child-parent level members (Line 11), which are selected from the temporary graphs GA(lmc)I and GA(lmp)I.

In this loop, we call the next helper function relateSpatialValues (Algorithm 2), where the input is the spatial value pairs. The output value of this function is the topological relation between the corresponding child and parent level members, and it is assigned to the initially created temporary variable topoReli (Line 12). If this value is not null (checked in Line 13), relateSpatialValues function returns a topological relation (Line 12) that is satisfied as shown with a check-mark (✓) from Table 1.

Finally, the output graph for spatial hierarchy steps GRU(shs)I is incrementally generated by adding the triple pattern with the topological relation (Line 14) and the output graph for the detected spatial hierarchy steps is returned (Line 15).

Algorithm 4:

discoverSpatialHS(GDS,GH(d)S,GL(h)S,GLM(l)I,GA(lm)I): GRU(shs)I.

4.2.Factual enrichment phase

The factual enrichment phase is built around the observation facts and their spatial attributes a.k.a spatial measures and fact-dimension relations (Section 2.1).

Listing 3.

GeoFarmHerdState fact schema definition in QB4SOLAP

In QB4OLAP facts are linked to the dimensions at the lowest granularity level, which is the base level of the dimensions. For example, the GeoFarmHerdState cube has two spatial base levels linked to the cube: Parish level and Farm level. The GeoFarmHerdState cube also has a spatial measure listed in the cube: FarmLocation (Fig. 3). In QB4OLAP, a fact schema defines the structure of a cube with the qb:DataStructureDefinition property (Listing 3, Line 1). Base levels (Lines 2 and 4) and measures (Line 6) are given as qb:components of the fact (Listing 3). The cardinality relationship between the base level and the fact can also be represented with qb4o:cardinality in QB4OLAP as given in Lines 2 and 4 in Listing 3.

On the other hand, with QB4SOLAP we can also represent fact-level topological relations that are similar to the topological relations between the child-parent levels at the hierarchy steps. Fact-level topological relations are given in spatial fact schema with blue in Lines 3 and 5 (Listing 3). QB4SOLAP also extends the (cube) schema with spatial aggregate functions, which are defined over spatial measures as highlighted in blue (Listing 3, Line 7).

Listing 4.

GeoFarmHerdState fact member with base levels and measures

An example of an observation fact (fact member) at the instance level is given in Listing 4. A fact member is a qb:Observation (Line 1), which is related to the base levels (Line 2) with respect to the data structure definition (DSD) of the fact schema, and has a set of measures (Lines 3, 4) where some measures (Line 4) might have spatial values (Listing 4). To define a QB4OLAP fact schema, first, we need to enrich the fact members by annotating with topological relations as highlighted with blue in Line 5. We can derive topological relations between fact members and the (base) level members by comparing the spatial measures of the fact members and spatial attributes of the (base) level members with Boolean spatial predicates. The links between fact members and base level members are already given explicitly in Line 2 (Listing 4). However, these links are simple references between the fact and base level members, which do not describe the nature of the topological relation. By applying Boolean spatial predicates on fact and level members, we can find the exact topological relations, i.e., if a fact member intersects with the level member or if a fact member is within the level member. We explain how to detect these explicit fact-level (topological) relations in Section 4.2.1.

Moreover, there might also be some missing links between the (observartions) fact members and the corresponding base level members. For this case we need to find all the base level members that are spatial and derive the links between the spatial measure values and spatial attribute values (of the base level members) by using Boolean spatial predicates. We explain how to discover fact-level (topological) relations, which are not explicitly linked between observation fact and base level members in Section 4.2.2.

There are also cases where we would like to establish a direct (topological) relation between the fact members and higher granularity (parent) level members, which are not at the base level of the dimension. Using the example depicted in Fig. 4 we explained that wrongly aggregating the measures (i.e., double counting) becomes a problem when we roll-up between the levels that have many-to-many (N:M) cardinality relations (as in Parish and Drainage Area levels). Therefore, it is necessary to drill-down to the lowest granularity (fact members) and find the direct relation between the observation fact members and the corresponding level members of the higher level in many-to-many cardinality relations.

In order to prevent this problem, we address the issue in our algorithm to discover and annotate the fact-level (topological) relations that are between the observation fact members and level members of a higher level in an N:M cardinality relation in Section 4.2.2. For example, such a relation is given in green in Line 6 (Listing 4) that shows a topological relation between an observation fact member (farm state) and a higher level – not a base level – member (drainage area).

Finally, in Section 4.2.3 we explain how to define a data structure definition (DSD) of spatial fact schema using a QB4OLAP fact schema and the spatial fact member instances derived in the previous two algorithms.

4.2.1.Detecting explicit fact-level relations

In this section, we present an algorithm for detecting explicit fact-level topological relations between observation fact members and base level members where there is a direct reference between the fact member and the base level member. To derive these topological relations we need to get the spatial attributes of fact members (spatial measures) and base level members.

Algorithm 5

detectFactLevelRelations(GFM(F)I,GA(lm)I):GFM(Fs)I

Algorithm 5 (detectFactLevelRelations) The input variables for Algorithm 5 are the instance graphs of fact members GFM(F)I, level members GLM(l)I, and attributes of level members GA(lm)I.

Every fact member fi∈FM has an IRI idI(fi) and defined as a qb:Observation. The RDF graph formulation of a fact member fi is:

GfiI=⋃lj∈L(fi){(idI(fi)idS(lj)idI(lmj)∣fi⇝lmj}∪⋃mk∈M(fi){(idI(fi)idS(mk)vmk∣fi⇝vmk}.

Here, we denote by fi⇝lmj that a fact member fi has an explicit link to a level member lmj (e.g., Listing 4, Line 3). Note that we denote by lm⇝vai that a level member lm has value vai for attribute ai (Section 4.1.2), which is used in Algorithm 5 (Line 12) to get the attribute values of the linked level members. Moreover, we denote here by fi⇝vmk that a fact member lm has value vmk for measure mk (e.g., Listing 4, Lines 5 and 6). The RDF graph formulation of the other input variables are: attributes of level members GA(lm)I and level members GLM(l)I are already given, respectively, in Sections 4.1.2 and 4.1.3.

The output of Algorithm 5 is the enriched instance graph of fact members with topological relations GFM(Fs)I. In Line 2, we initialize the output graph as the input graph of fact members (without topological relations) so that we can gradually enrich it with the detected topological relations (Line 22). Initially, the topological relation variable topoReli is set to null. We also create two temporary graphs: GA(lmj)I and GA(fimk)I as empty sets to keep triple patterns separately in two graphs for attributes of level members and (measures of) fact members. We also create two temporary sets: Vs(mk) and Vs(ai) for keeping the spatial values from the fact and level members, and initialize them also as empty sets in Line 3.

In the first foreach loop (Line 4 and 5) we retrieve the observation fact members from the input graph of fact members, which corresponds to Line 1 in Listing 4. Getting the fact members allows us to access each of their measures in Line 6 and level members in Line 7 (Algorithm 5). In the next foreach loop (Line 9) we match each measure-level member pair, where we can already retrieve the measure values from the input graph of fact members GFM(F)I (Line 10) and through the input graph for attributes of the level members GA(lm)I (Line 11 and 12), we can retrieve the attribute values. In Line 13, we assign the set of triples for measure attributes of fact members to a temporary graph GA(fimk)I created earlier in Line 2. This temporary graph is given as an input to the helper function getSpatialValues (Algorithm 1) in Line 14 (Algorithm 5). The helper function returns the spatial attribute (measure) values of the fact members, which are kept in the temporary set Vs(mk). If this set is not empty (checked in Line 15) and has some spatial measures of fact member idI(fi), we repeat the same procedure for retrieving the spatial attribute values of level member idI(lmj) in Lines 16 and 17. If the output set for spatial attribute values Vs(ai) is also not empty (Line 18), then we go through the pairs of spatial values (vmk,vai) in Line 19. In this loop, we call the next helper function relateSpatialValues (Algorithm 2), where the input is the spatial value pairs. The output value of this function is the topological relation between the corresponding fact and level members, which is assigned to the variable topoReli (Line 20).

Algorithm 6:

discoverFactLevelRelations(GFM(F)I,GLM(l)I,GA(lm)I,GDS,GH(d)S,GHS(h)S):GFM(Fs)I

4.2.3.Defining spatial fact DSD

In this section, we present an algorithm for re-defining the fact schema data structure definition (DSD) by enriching the DSD with fact-level topological relations. An example of a fact schema in QB4OLAP is given in the black-colored lines of Listing 3 (for now please ignore Lines 3, 5 and 7). We re-define the spatial fact schema to QB4SOLAP (Listing 3 Lines 1–7) by using the enriched fact members that are generated via Algorithms 5 and 6.

Algorithm 7:

defineSpatialFactDSD(GFM(Fs)I,GFS):GFsS

Algorithm 7 (defineSpatialFactDSD) The input variables for Algorithm 7 are the instance graph of spatial fact members GFM(Fs)I and schema graph of QB4OLAP fact schema GFS. Spatial fact members in the instance graph GFM(Fs)I must be annotated with QB4SOLAP or can be generated by using Algorithms 5 and 6 from QB4OLAP fact members. A QB4OLAP fact schema GFS has (base) levels and measures of the cube as qb:components and defines the fact-level cardinality relation with qb4o:cardinality predicate, aggregate functions on (numerical) measures with qb4o:aggregateFunction predicate.1111

The output of Algorithm 7 is the enriched fact schema graph GFS annotating the fact-level relations with QB4SOLAP topological relations and measures with spatial aggregate functions.

In Line 2, we initialize the output graph as the input schema graph so that we can gradually enrich it with QB4SOLAP schema annotations (Lines 5 and 15). Initially, an aggregate function variable aggFunci is created and set to null (Line 2).

The first foreach loop iterates through the fact members graph GFM(Fs)I and finds each fact member fi by using the triple pattern (idI(fi)rdf:typeqb:Observation). The second foreach loop gets every distinct topological relation topoReli of the fact member fi (Line 4). Then the output schema is annotated with the identifier of these topological relations (Line 5). Next, we get every measure vmk of the fact member fi (Line 6), and check if it is a spatial measure (Line 7). If it is a spatial measure, we find the geometry type with geoType function (Line 8). We have appointed the corresponding spatial aggregate functions (Lines 10, 12, and 14) with regard to the geometry type of the spatial measure (Lines 9, 11, and 13). Finally, the output schema GFsS is annotated with the identifier of these spatial aggregate functions (Line 15) and returned (Line 16).

4.3.Implementation choices

When implementing the algorithms presented in this section, we had to make some implementation choices both in technical as well as strategical aspects that we would like to briefly comment on. Further details regarding the implementation of the algorithms themselves are available in the Appendix. As mentioned earlier, RDF2SOLAP is implemented in Javascript on the Node.js platform using the N3.js library for parsing the RDF triples in Javascript and the Turfjs library for spatial analysis. Details of our approach, endpoints, and datasets can be found on our project page.1212 The code repository for the whole implementation can be found on GitHub.1313

To answer the question: “Can this approach be reasonably implemented on top of triple stores by directly using Web and Semantic Web technologies?”, we have come across a number of challenges, where specific choices had to be made.

For example, we chose to store RDF data in a well-established triple store (Virtuoso Open Source) that supports many geometry data types (i.e., POLYGON, MULTIPOLYGON). Even though Virtuoso supports several shape types (e.g., POLYGON, MULTIPOLYGON, etc.), it has a limited number of spatial Boolean functions available as built-in functions from the DE9DIM model (see Table 1). Therefore, we have also decided to use a third party Javascript library for spatial analysis, which is called Turfjs⁶. This way, we can ensure that RDF2SOLAP can be used on top of any triple store since the Javascript library provides us with the spatial analysis capabilities and a flexible development environment, independent from the choice of the triple store.

We are working with multi-part POLYGON data (for drainage areas and parishes), which means that, when several polygons are grouped by unique (parish or water) URIs they can compose a MULTIPOLYGON for a single parish or drainage area instance. From the implementation point of view, we had to implement a bounding box function for multi-part POLYGON data, in order to call the spatial Boolean functions (within and intersects) between the correct parish and drainage area instances, then annotate the topological relations between their unique URIs. If triple stores already provided overall support of complex spatial data types, spatial indices, and a complete support of built-in spatial functions, decoupling the triple stores during development of RDF2SOLAP would not have been necessary. We could then directly have used the spatial capabilities of the triple stores that were required for developing RDF2SOLAP. However, to the best of our knowledge, a third party spatial analysis library was needed to fully implement our RDF2SOLAP (spatial) multi-dimensional enrichment algorithms described in Section 4.

5.1.Experimental setup

The rationale for developing RDF2SOLAP is to be able to enrich and annotate existing spatial RDF data with spatial and multi-dimensional metadata while staying within the RDF environment. This upgrades the spatial RDF data to allow SOLAP querying directly in SPARQL. The alternative would be to export the spatial RDF data to relational format, do the enrichment with relational/GIS tools and perform the SOLAP on the resulting relational data, thus loosing all the advantages of having the data in RDF in the first place. Doing the enrichment purely within the RDF environment is expected to come at a cost as support for spatial and multidimensional data in the RDF/SW stack is still less mature; this will however improve over time. Thus, our goal is just to demonstrate that we can do this in a pure RDF environment with adequate performance in terms of runtime and annotation quality (which may vary). In return, RDF2SOLAP provides a solution that is both flexible and general for all data sets. We then compare our general solution to the alternative baseline, which is spending long development times on hand-crafting specialized enrichment solutions using RDBMSes and GIS for each new data set.

We used the common Virtuoso version 07.20.3217 on Linux (x86_64-ubuntu-linux-gnu), Single Server Edition as triplestore. We implemented RDF2SOLAP on the Node.js platform, running on a Macbook Pro 14.3 with one Intel Core i7 2.8GHz 4-core CPU 256KB L2 cache, 6MB L3 cache, and 16GB RAM. All test cases are in the GitHub repository so the experiments can be repeated. Each experiment was run in a single process. For the baseline implementation, we used a leading GIS tool and a leading RDBMS (we cannot write the names due to license restrictions, but they can be supplied on demand). These were running on a Windows 10 Enterprise server with 4 Intel Core i7 2.9GHz CPUs and 32GB memory, i.e., considerably more powerful hardware. We use both the GeoFarmHerdState data set described above and the GeoNorthwind data set from [15].

We now describe how the RDBMS and GIS baselines were implemented. Since the GIS tool and the RDBMS cannot process RDF data in native format, we first have to extract and prepare the data for loading into them. The preparation time is part of the development time discussed below. Doing this preparation requires that the developer has basic knowledge of the domain, extraction of RDF data with SPARQL queries, writing SQL queries, and knows how to use the RDBMS and GIS tools. We extracted the spatial level members (farms states, parishes, and drainage areas) from our RDF endpoint in CSV format. To load the data into the GIS tool and RDBMS we use the relational schema defined by QB4SOLAP. In the GIS tool we saved CSV data layers (for each level; farm states, parishes and drainage areas) and converted these into native GIS format (shape files). Then, we run the Join Attributes By Location function, which is a built-in data management function. We run this function as a batch process, for parishes-drainage areas (Alg. 4), farm states-parishes, and farm states-drainage areas (Alg. 6). We load the WKT data (spatial attributes of level and fact members) in the CSV files into the GIS tool and a relational geo-database, with the same decimal precision for the coordinates. We extract topological relations between the child and parent members by using spatial joins in the GIS tool and built-in spatial functions in the RDBMS. Overall, most of the time was spent on data extraction, preparation, and load, caused by having to convert data from its existing RDF format. None of these tasks are needed if the enrichment is done entirely within an RDF environment, like in RDF2SOLAP.

5.2.Development time comparison

We now compare the time required to develop enrichment solutions for spatial RDF data with RDF2SOLAP to using the RDBMS and GIS baselines. Here, it is important to keep in mind that RDF2SOLAP has general algorithms that use existing metadata and annotations to work for any spatial RDF data set, requiring only a few minutes of configuration, while a new baseline enrichment solution has to be implemented for each new data set, requiring literally (repeated) days of development time. Of course, there was a onetime development cost for RDF2SOLAP. However, this cost is already paid and will not be repeated, unlike the case for the baselines.

The development times for RDF2SOLAP, and the RDBMS and GIS baselines for the one-time step of General Algorithms (only RDF2SOLAP) and the GeoFarmHerdState data set, are given in Table 2. One day corresponds to 8 hours. All development was carried out by the first and fourth author who both have significant experience in all the used tools and platforms, and also recorded the development times for RDF2SOLAP and GeoFarmHerdState. The RDF2SOLAP configuration times for each data set were also recorded by the first author. We find these development times realistic and comparable. As GeoNorthWind is only included to demonstrate that RDF2SOLAP can generalize to other data sets, we have not implemented the baseline enrichment solutions for GeoNorthWind. Thus, we have not reported RDBMS and GIS development times in the table. However, realistic estimates would be in the same range as for GeoFarmHerdState, i.e., one or more days.

From the table, we can see that RDF2SOLAP allows to enrich and annotate new spatial RDF data sets with just minutes of effort, since the enrichment process is done automatically after retrieving the input parameters to the enrichment algorithms from the endpoint. In comparison, each new data set requires one or more days of (repeated) development effort for the baseline RDBMS and GIS enrichments.

5.3.Runtime comparison

Having established that RDF2SOLAP requires up to 2 orders of magnitude less development time for a new data set, we now investigate whether it can do the enrichment with reasonable runtimes, and compare its runtimes to those of the baseline implementations. Both the total runtimes (in minutes) and the subtotals (in seconds, for accuracy) for the different algorithms are reported. The GeoFarmHerdState runtimes are seen in Tables 3 and 4.

Alg. 3 and 5 (to detect explicit topological relations) are only implemented in the RDBMS since the GIS tool does not support the foreign key joins of explicit (skos:broader) relations which are needed for these two algorithms. In order to implement the needed topological relations in RDF2SOLAP, we had to use theturf.js library running on a node.js server, where the RDF data is parsed into JSON format, since these relations were not supported by the triplestore. This meant that we could not take advantage of spatial indexing in the triplestore.

To understand the size of the input and output of the algorithms for GeoFarmHerdState, we report these along with corresponding RDF2SOLAP runtimes in Table 3. The input parameters and numbers for each algorithm are shown in Table 3 under the INPUT column(s). The input datasets to the algorithms are 2,180 parish members, 40,039 farm state members, and 134 drainage area members. The OUTPUT columns show the number of topological relations found and run times of the algorithms. In this section, we only focus on the runtime, the annotation quality is evaluated later.

In Table 3, we can see that most expensive algorithm is Alg. 4 (discoverSpatialHS), which runs in 2,622 seconds. The algorithm takes parishes and drainage areas (POLYGON data type) as input instances, and not explicit relations as in Alg. 3 (detecSpatialHS). Alg. 3, given (2,683) distinct explicit relations, checks the corresponding spatial Boolean functions (within and intersects) 2,683 times each. In comparison, Alg. 4 calls (within and intersects) 134 × 2,180 = 292,120 times each. Similarly, Alg. 6 is slower than Alg. 5 since the former does not use explicit relations. However, it is much faster than Alg. 4 since this calls the spatial Boolean functions between farm states (POINT data type) and parishes and drainage areas (POLYGON data type).

From the GeoFarmHerdState runtimes, we see that Alg. 4 and 6 use the most time, in particular for RDF2SOLAP. However, the total RDF2SOLAP runtime of 85 minutes is very reasonable and well within the requirements for practical use: a user wanting to analyze a new data set (which usually does not happen several times a day) can simply spend a few minutes on configuration and then let RDF2SOLAP run in the background for the next 1.5 hours. Especially for non-developer RDF users, this is a much better value proposition than first spending one or more days on technical development in the baseline tools.

For GeoNorthWind, the baselines were not implemented (see above) so only RDF2SOLAP runtimes are reported, see Table 5. For this smaller data set, RDF2SOLAP completes in just 26 seconds, making it usable even in interactive mode.

In summary, the runtime comparisons show that, even though RDF2SOLAP is slower than the hand-crafted baselines, it still has a runtime performance that is more than adequate for its intended use case.

5.4.Annotation quality comparison

We now compare RDF2SOLAP to the RDBMS and GIS baseline tools in terms of annotation quality. Specifically, we report the number of the topological relations found by each algorithm/step in each tool, and relate these to accuracy and coverage. The numbers are given in Table 6.

As mentioned earlier, Alg. 3 and Alg. 5 were not implemented in the GIS tool due to its lack of support for explicit relations between parent-child members; thus these numbers are reported as N/A. We thus only tested the discovery of implicit topological relations (discoverSpatialHS and discoverFactLevelRelations) by utilizing its spatial join functionality to emulate the results for Alg. 4 and Alg. 6.

For the RDBMS tool, we tested both detect and discover topological relations, where we used joins on unique IDs if they were present (drainage area foreign key in parishes, parish foreign key in farm states), and with spatial joins by using the STWithin, STIntersects, and STOverlaps built-in functions.

We now compare results for each algorithm in the different tools. For Alg. 3, RDF2SOLAP reports only a third of the intersecs relations but almost three times as many within relations, as the RDBMS tool. This is due to generalizing the multi-part POLYGON data as bounding boxes in RDF2SOLAP (due to restrictions in our spatial library), in the spatial RDBMS, multi-part POLYGON data is processed in its original format, yielding better quality. Interestingly, the total number of intersects+within relations for the two tools are exactly the same, namely 2682. This suggest that RDF2SOLAP can get the same annotation quality as the RDBMS tool when better spatial support become available in the RDF environment.

Similar results are seen for Alg. 4. Here, the GIS and RDBMS results are similar, but not identical, showing that perfect annotation quality is not a given, even with traditional tools. Again, RDF2SOLAP finds fever intersects relations and more within relations (again due to the bounding box generalization), and again the total number of relations found by the 3 tools are very similar. This indicates that RDF2SOLAP can achieve the same annotation quality with better spatial RDF support.

For Alg. 5, the RDF2SOLAP and RDBMS results are identical. This perfect annotation quality can be achieved since the within relations are found between points and polygons which can be done exactly by the library.

For Alg. 6, the results found by the 3 tools for (farm states-parishes) are very close, with RDF2SOLAP differing 0.5% from the GIS tool and 0.04% from the RDBMS tool. For (farm states-drainage areas), the RDF2SOLAP and RDBMS results are identical, while the GIS result differs by 0.01%. Thus, the annotation quality for all 3 tools is near-perfect.

Similar results were found for GeoNorthWind. For Hierarchy Step 1, there are 89 correct within relations. Of these, Alg. 3 found 75 of them correctly, while Alg. 4 found 91 relations (the 89 correct and 2 extra incorrect). For Hierarchy Step 2 there are 28 correct within relations: Alg. 3 found 24 of them correctly, while Alg. 4 found all 28 of them correctly. For Hierarchy Step 3, we do not have the correct ground truth since this requires the GIS and RDBMS baselines to have been implemented.

RDF2SOLAP’s problems with POLYGON-POLYGON relations could have been prevented if we had been able to use multi-part POLYGON and MULTIPOLYGON data in its original form instead of generalizing them to bounding boxes. However, We encountered both performance and formatting problems while loading MULTIPOLYGON data to Virtuoso, which led to missing data in the triplestore for drainage areas. Even if the MULTIPOLYGON data was could be successfully loaded, Turf.js is not able to handle POLYGON-MULTIPOLYGON within relations. We thus had to make a trade-off and implement the POLYGON-POLYGON relations with generalized bounding boxes.

In summary, the annotation quality of RDF2SOLAP is near-perfect for the spatial relations that are well supported in the RDF environment. There are some problems with polygon-to-polygon relations, but these are caused by limitations in our spatial library. When better spatial RDF support becomes available, we are confident that RDF2SOLAP will provide near-perfect annotation quality for all cases.

5.5.Experimental summary

In summary, we have seen that RDF2SOLAP provides orders of magnitude less development time for new data sets (minutes versus days), and, while slower than the RDBMS and GIS tools, has adequate runtimes for its intended use case. For some algorithms, its annotation quality is near-perfect, while for others, it will be when better spatial RDF support becomes available.