In today's data-driven world, analytical querying, typically based on the data cube concept, is the cornerstone of answering important business questions and making data-driven decisions. Traditionally, the underlying analytical data was mostly internal to the organization and stored in relational data warehouses and data cubes. Today, external data sources are essential for analytics and, as the Semantic Web gains popularity, more and more external sources are available in native RDF. With the recent SPARQL 1.1 standard, performing analytical queries over RDF data sources has finally become feasible. However, unlike their relational counterparts, RDF data cubes stores lack optimizations that enable fast querying. In this paper, we present an approach to optimizing RDF data cubes that is based on three novel cube patterns that optimize RDF data cubes, as well as associated algorithms that transform the RDF data cube. An extensive experimental evaluation shows that the approach allows trading additional storage and/or load times in return for significantly increased query performance. We further provide guidelines for which patterns to apply for specific scenarios and systems.
Data has become the fundamental resource for making informed decisions in almost every organization. Traditionally, the data used for analytics is mostly internal, e.g., sales, finance, or HR data and is processed using heavy Extract-Transform-Load (ETL) flows and stored in relational data warehouses. It is then analyzed, typically using tools based on multidimensional data cube concepts, where important business facts, e.g., a specific lineitem, with associated numerical measures, e.g., price or quantity, are organized in a multidimensional (cube) space spanned by hierarchical dimensions characterizing the fact, e.g., the product being bought, the customer placing the order, and the order date. Data cubes enable easy and efficient analytical queries that aggregate measure values up to the desired level of detail.
External data sources are becoming more and more important to get the full picture
of the situation, often in combination with internal data. Given the growth of the
Semantic Web, such external sources become increasingly available in RDF format, e.g.,
due to efforts in publishing Open Data as Linked Open Data [
Popular RDF stores, such as Jena TDB2 still lack the efficiency of their relational counterparts when answering complex analytical queries. There is thus a significant need for specialized optimization techniques.
This paper introduces cube patterns, or patterns in short, as specialized optimization
techniques of RDF data cubes. The patterns are inspired by effective relational
representations of data cubes and differ from each other in their level of denormalization. In
summary, this paper makes the following novel contributions:
– Proposing three patterns for capturing different levels of denormalization of RDF
data cubes: snowflake pattern, star pattern, and fully denormalized pattern.
– Proposing the Semantic Web OLAP Denormalizer (SWOD) transformation
algorithm that converts an RDF data cube into a cube in either star pattern or fully
denormalized pattern.
– Providing an extensive experimental evaluation, based on the well-known
TPCH dataset [
The remainder of this paper is structured as follows. In Section 2, we introduce basic concepts of RDF graphs and multidimensional cubes. Then, Section 3 discusses related work. The cube patterns are presented in Section 4. Section 5 explains the transformation algorithms. The results of our experimental evaluation are discussed in Section 6. Section 7 concludes the paper with an outlook to future work. 2
In this section, we define important concepts and provide a basic understanding of concepts that the rest of the paper is based upon.
RDF Graphs. An RDF graph can be represented as a set of triples of the form (s, p, o) that are each defined by a subject s, a predicate p, and an object o. A triple encodes the existence of a relationship between subject s and object o, the nature of this relationship is described by predicate p.
Given a set of IRIs U , a set of blank nodes B, and a set of literals L, a triple t is defined as t = (s, p, o) ∈ (U ∪ B) × U × (U ∪ B ∪ L). An RDF graph G consists of a set of triples: G ⊆ (U ∪ B) × U × (U ∪ B ∪ L).
An intuitive way of querying a graph is using triple patterns. A triple pattern may contain variables at any position of a triple. Variables are denoted by a leading “?” in their names, e.g., (?s, p, o). A basic graph pattern (BGP) consists of a set of triple patterns connected via logical conjunctions.
Given a set of IRIs U , a set of blank nodes B, a set of literals L, and a set of variables V , a triple pattern T P is defined as T P = (s, p, o) ∈ (U ∪ B ∪ V ) × (U ∪ V ) × (U ∪ B ∪ L ∪ V ). A Basic Graph Pattern BGP is a set of triple patterns: BGP ⊆ (U ∪ B ∪ V ) × (U ∪ V ) × (U ∪ B ∪ L ∪ V ). When two or more triple patterns share a variable, we say that there is a join between these triple patterns and the shared variable is the join variable.
When evaluating a BGP, {(s1, p1, o1) , (s2, p2, o2) , . . . , (sn, pn, on)} over a graph G we use the notation G (s1 p1 o1 . s2 p2 o2 . . . . . sn pn on). The result is a bag of
bindings for the variables in the BGP. In addition to BGP queries, this paper considers SPARQL 1.1 extensions, such as grouping and aggregation.
Multidimensional Cube. A multidimensional cube is a data structure used for
capturing and analyzing data [
There are in general two approaches for constructing RDF data cubes: 1) Explicit
cube construction uses a vocabulary to define dimensions, measures, etc. The most
commonly used vocabularies to define cubes are: QB [
[
Several approaches addressing OLAP over graph data have been proposed [
RDF data cubes: snowflake pattern, star pattern, and fully denormalized pattern. We will discuss the relationship between the different patterns and how to derive them in Section 5.
Snowflake Pattern. An RDF data cube in snowflake pattern is normalized such that each level is represented by one class in the ontology; an instance of a level is called a level member. Levels are arranged in hierarchies that are organized in dimensions. Facts Fig. 2: Snowflake pattern example link to level members of the bottom level of a dimension. Figure 2 illustrates the fact representing Ben’s purchase, :Lineitem 1 1, linking to a level member at the Order level, :Order 1, which links to its parent at the Customer level member, :Customer 1, and so on. In this example, there is a single attribute describing each level member; in practice, more attributes are often used.
Star Pattern. In a star pattern RDF data cube, all levels have been denormalized into a dimension. An instance of a dimension is called a dimension member, e.g., :Order 1. A dimension member is a resource that has all attributes of all levels in the given dimension. Figure 3 shows the Order dimension and a fact relating to Ben’s purchase modeled as star pattern. In Figure 3, the level members :Region 3, :Nation 7, :Customer 1, and :Order 1 from Figure 2 are merged into a dimension member, called :Order 1.
Fully Denormalized Pattern. In the fully denormalized pattern, in short denormalized pattern, all level attributes are attached directly to the facts. In Figure 4 we see Ben’s purchase modeled as denormalized pattern. The level members :Region 3, :Nation 7, :Customer 1, and :Order 1 from Figure 2 are directly connected to the fact :Lineitem 1 1. 5
In this section, we discuss how to convert an RDF data cube from snowflake pattern into star pattern and denormalized pattern by using the SWOD (Semantic Web OLAP Denormalizer) algorithm. For ease of presentation, we first present the conversion from snowflake pattern into star pattern and afterwards we highlight the differences for the denormalized pattern. We first explain SwodStar (Algorithm 1), which is the main algorithm and then proceed with its auxiliary functions. We assume that a cube is in snowflake pattern because the commonly used multidimensional vocabularies encourage this, and it is arguably the most intuitive way of organizing an RDF data cube. We assume that the give QB4OLAP ontology strictly describe a single cube.
Notation. We use two kinds of variables in the algorithms: BGP variables, which are prefixed with a question mark “?”, and regular algorithm variables. In some places, we use an algorithm variable in a BGP, which represents a constant (URI, literal, or blank node) in the BGP. A graph G0 can be constructed by evaluating a BGP on a graph G e.g., G0 = {(s, p, o) ∈ G (?s rdf:type t . ?s ?p ?o)}. G0 contains all triples with the subject s that are instances of class t in graph G. If a BGP does not contain variables, the result of its evaluation is a boolean value indicating whether the represented set of triples is present in a given graph. We say that we merge a triple a into another triple b in a graph G, when a triple is created with the subject of b and the predicate and object of a. Note that we use [] to represent a blank node. end foreach (fact, prop, obj) ∈ cube(?fact qb:dataSet [ ] . ?fact ?prop ?obj) do if onto(?structure qb:component ?component. ?component qb:attribute prop.) 6= ∅ ∨ onto(?structure qb:component ?component. ?component qb:measure prop.) 6= ∅ then
cube0 = cube0 ∪ {(fact, prop, obj)}; Alg. 1: Conversion of an RDF data cube in snowflake pattern to star pattern Cube Denormalization. SwodStar (Algorithm 1) converts an RDF data cube from snowflake pattern into star pattern. It has two input parameters: the RDF data cube in snowflake pattern (cube), see Figure 2, and the ontology describing the QB4OLAP cube (onto), see Figure 1. SwodStar outputs an RDF data cube (cube0) in star pattern, see Figure 3.
The function GetBottemLevels finds the bottom level for each dimension and returns a set of pairs (level, dim) (line 3). This is possible by traversing the levels (qb4o:level) defined in the QB4OLAP ontology and finding the levels that are not a parent level (qb4o:parentLevel), see Figure 1. The resulting set of pairs is used as input to MergeLevel (Algorithm 2) along with cube and onto. The MergeLevel algorithm (Algorithm 2) is called (line 5) to recursively merge level members with their ancestors into dimension members, the obtained triples are added to the new snowflake pattern cube cube 0. Next, SwodStar connects the dimension members to the facts (line 6), see Figure 3; the algorithm creates triples such as (:Lineitem 1 1, :has order, :Order 1). These triples are inserted into the star pattern cube (cube0). The next step is to loop through the fact triples in the snowflake pattern cube and add them to cube 0 (lines 8–12). In our example, we only have a single fact :Lineitem 1 1, which has a single measure, namely :extendedprice; we add this triple to cube0. Finally, we have converted the RDF data cube from snowflake pattern into star pattern.
Unbalanced Hierarchies. As dimension hierarchies may be unbalanced [
When denormalizing, level members are merged into the bottom level member. In the case where a level member does not have any children but is not the bottom level of the dimension, then the ancestor level members are merged into it. For example the Customer (cust0) does not have any orders and the Nation (nation) and Region (region) level members are merged into the Customer (cust0) along with their attributes (Figure 6). In the denormalized pattern, the same principle is used (Figure 7). end
end Merging Level Members. The MergeLevel function (Algorithm 2) recursively merges level members in a top down manner into dimension members. It has four input parameters: a RDF data cube (cube), a QB4OLAP ontology (onto), the current level (level) and the dimension of the level (dim). If the level member (level) has any parent levels, then we recursively call MergeLevel for each of the parent levels (line 4). When a top level member is reached then no parent levels will exist, thus line 5–12 will be skipped. dimMembers contains all attributes of the ancestor level members, we merge the attributes of the current level member with these (line 15). The function MergeURIs creates new attributes to avoid ambiguity among properties used in multiple levels. We add the level name as a prefix to the property e.g., :name becomes :nation name. We create mapping between the old and the new properties, so that we can always rewrite queries to match a given triple pattern. The final step adds a triple with the name of the current level (line 17).
When we return from the recursion in line 4, we loop through every instance of the parent levels (line 5). We merge the parent level members with the current level member (line 7). To handle unbalanced hierarchies, we add ancestor level members that do not have any children in the current level (lines 9–11).Every subsequent return is handled in the same way. The returned triples of the initial call are dimension members, rather than level members as illustrated in Figure 3.
Fully Denormalized Cube. To construct a denormalized pattern cube, we use similar algorithms as for the star pattern cube. In addition to creating the dimension members, we further merge them with the facts, see Figure 4. To avoid ambiguity among properties used in multiple dimensions, we additionally add the dimension name as a prefix to the property e.g., :order nation name. In case of unbalanced hierarchies, e.g., a customer without any orders, we create dimension members that are not connected to any facts, as oppose to level members.
Query Rewriting. To enable transparency for the user, formulating a query in snowflake pattern, we need to rewrite the query such that it matches the structure of the data in star pattern or denormalized pattern. In principle, a query formulated on the RDF data cube in snowflake pattern can be transformed in a similar way as the cubes. More precise, we loop through the triple patterns in the original query and determine the referenced levels and dimensions using the QB4OLAP ontology. If the subject in the triple pattern does not correspond to a bottom level, then we merge it with the corresponding bottom level in the dimension and change the predicate to match the naming scheme, e.g., ?nation :name ?name becomes ?order :nation name ?name. Recall that level members are connected with the skos:broader predicate, see Figure 2. When we denormalize the cube the level members are merged, thus triple patterns with the skos:broader predicate can be removed. Query 1.1 is in snowflake pattern and finds how much money customers from all nations have spent. Query 1.2 shows the same query rewritten to match the star pattern.
SELECT ? name sum ( ? p r i c e ) WH?ERliEn efi t e m : e x t e n d e d p r i c e ? p r i c e ;
: h a s o r d e r ? o r d e r . ? o r d e r s k o s : b r o a d e r ? c u s t o m e r . ? c u s t o m e r s k o s : b r o a d e r ? n a t i o n .
? n a t i o n : name ? name . g GROUP BY ? name
Query 1.1: Snowflake pattern query SELECT ? name sum ( ? p r i c e ) WH?ERliEn efi t e m : e x t e n d e d p r i c e ? p r i c e ;
: h a s o r d e r ? o r d e r .
? o r d e r : n a t i o n n a m e ? name . g GROUP BY ? name
In some cases query rewriting is not trivial. Assume, we are looking for the number of orders placed by the customer whose name is Ben. The triple :Customer 1 :name "Ben" would be a match in the snowflake pattern (see Figure 2) and we can use the triple pattern ?order skos:broader :Customer 1 to find his orders. For the star pattern, however, we would find several triples, such as :Order 1 :name "Ben" and :Order 2 :customer name "Ben". Here we do not know if Ben and Ben is the same person. When the object is a literal (e.g. Ben) and the predicate :name has not been defined as a functional property, we cannot know if it is the same customer or not. In this case, we have to augment the query with a triple pattern using the functional predicate of the customer and add a group by statement e.g., GROUP BY ?customer ID. If no functional property exist then we use the URI of the customer resource to group the customers uniquely. 6
In this section, we present the results of evaluating the techniques and report on the performance of generating, loading, and querying the three patterns using data sets of different sizes.
Hardware platform. The experiments were run on a HP ProLiant DL385 server with an AMD Opteron(tm) processor 6376 with 32 cores, it has 256 GB DDR3 RAM and is running Ubuntu 14.04.1 LTS (Trusty Tahr). The data was stored on a 1 TB SCSI disks running in a HP Smart Array.
Dataset and queries. We use the well-known TPC-H benchmark [
The TPC-H benchmark data is structured data about sales modeled as a snowflake schema. The analytical queries in the benchmark are originally provided as SQL query templates. We created SPARQL query templates based on the provided SQL benchmark query templates; we transformed the query template such that they match the star pattern and denormalized pattern, hence we have three sets of 22 query templates. The query templates and further details are available at our homepage3.
Pattern generation. We generated the Scale factor TPC-H dataset at different scale factors us- 0.1 0.2 0.3 0.5 ing the supplied DBGEN program4. We Snowflake 15.2 30.4 45.5 75.9 defined cubes by converting the generated Star 17.7 35.4 53.0 88.4 comma separated files using the csv2ttl pro- Denormalized 41.5 82.9 124.5 207.3 gram, which is a part of the BIBM project, Table 1: Dataset sizes (millions of and manually defined a snowflake pattern triples) cube using QB4OLAP. This cube is loaded into Virtuoso-opensource 7.10, where we run the SWOD algorithm, as a result we obtain cubes in star pattern and denormalized pattern. Table 1 shows the sizes of the test data sets in millions of triples The star pattern (denormalized pattern) cubes are about 16% (173%) bigger in terms of the number of triples than the snowflake pattern cubes.
40 ) tse 30 u n i m (e 20 m i t aod 10 L 0
Snowflake Star Denormalized 0.1 0.2 0.3
Scale factor (a) Virtuoso 0.5
100 )se 80 t u inm 60 ( e itm 40 d aoL 20 0 0.1 0.2 0.3
Scale factor (b) Jena 0.5
Load times. We loaded the three cubes into two different stores: we use Apache Jena 2.12 TDB and Virtuoso-opensource 7.10. Figures 8(a) and 8(b) report the times for loading the generated cubes. Virtuoso uses on average 12.5% more time to load the star pattern cube than the snowflake pattern cube and Jena uses 14.2% more time. The denormalized pattern cube takes on average 138.3% longer in Virtuoso, while it takes Jena 183% longer, again compared to the snowflake pattern cube. The increased load time is due to the increased number of triples.
Query evaluation. Each of the three sets of the 22 queries are executed on the two triple stores (Jena TDB and Virtuoso). The queries were run in random order with
Virtuoso Jena Snow Star Denorm Snow Star Denorm 7.3 7.2 7.3 71.8 78.4 76.3 1.7 1.9 1.1 5.7 8.0 54.5 2.9 0.4 1.3 30.0 33.0 25.9 8.8 8.3 3.0 33.57 35.7 31.9 4.3 1.3 0.2 38.6 37.1 23.0 1.8 1.8 1.8 19.6 20.8 21.1 7.8 1.8 0.7 35.5 31.6 20.5 2.5 0.2 0.1 51.8 36.8 25.0 31 6.0 8.4 65.3 47.0 33.4 – 1.2 2.2 15.8 15.2 13.5 1.2 0.3 0.7 0.6 0.6 2.3 1.6 1.6 2.6 26.3 27.2 23.5 1.6 1.7 7.3 8.4 9.7 32.7 2.3 8.4 1.1 21.7 24.0 23.5 3.2 19.4 2.9 31.1 377.7 – 1.8 1.7 4.4 2.1 5.0 34.9 3.6 0.1 0.1 91.8 40 54.2 2.0 1.9 2.0 18.4 19.9 19.9 4.1 2.9 1.5 21.4 27.7 21.8 3.1 1.6 11.2 – – – 9.3 2.2 0.6 43.8 39.4 29.2 0.2 1.7 2.6 3.6 10.5 42.6 50.1 3.3 2.9 74.4 87.5 118.6 3.9 1.8 1.5 22.6 27 35.9 4 11 11 11 2 9
Virtuoso Jena Snow Star Denorm Snow Star Denorm 15.0 14.9 14.8 180.9 193.4 184.6 2.1 2.9 2.4 31.5 34.6 244.5 6.2 0.8 2.7 77.0 78.3 62.2 22.7 20.1 7.4 86.9 125.1 135 7.8 3.3 0.4 97.6 86.2 56.6 2.7 2.8 2.6 47.9 51.2 51.0 19.9 4.4 1.6 90.2 77.6 49.7 7.1 0.4 0.2 131.4 90.7 59.9 82 16.9 23.6 167.9 110.4 78.7 – 1.9 2.8 39.2 37.1 31.7 1.7 0.5 1.2 1.2 1.3 5.5 3.0 3.1 5.8 63.6 66.4 54.2 4.8 5.1 19.7 – – –
5 25.3 2.0 53.8 57.0 55.4 5.9 55 6.3 106.9 – – 4.5 4.1 11.2 5.2 11.8 81.1 6.2 0.2 0.2 – – – 4.4 3.9 4.2 228.8 206.2 169.7 8.1 6.5 2.7 52.3 64.0 52.1 6.2 3.9 28.6 – – – 21.5 5.1 1.2 107.7 93.5 71.0 0.4 3.5 5.7 3.7 28.4 103.0 56.2 8.4 6.7 207.9 246.1 252.1 7.8 3.8 3.2 74.4 91.3 109.3
5 8 10 9 0 10
random parameters as specified by the TPC-H manual [
Table 2 shows the detailed query runtimes for scale factors 0.2 and 0.5. Due to space limitations and because the observations for these results also hold for the other scale factors, we omit detailed runtimes for the remaining ones. Some queries time out and are marked with “–”, symbolizing that the query time exceeds 1000 seconds. We calculated the minimum average and minimum geometric mean (G.M.), we refer to this as minimum because queries that time out are contributing to these numbers with a runtime of 1000 seconds but in reality exceed 1000 seconds. For each query, pattern, and store we mark the fastest execution.
As we can see in Table 2, Virtuoso shows a low average and geometric mean for the denormalized pattern in both scale factors. On average, in Virtuoso, the star pattern (denormalized pattern) is 6 (8) times faster than the snowflake pattern, which is particularly interesting because the snowflake pattern is the pattern in which most RDF data cubes are available. In Virtuoso at scale factor 0.5, 11 out of the 22 queries are fastest on either the star pattern or the denormalized pattern – and only 4 on the snowflake pattern. This shows that Virtuoso is able to handle the increased amount of data and benefits from the denormalization.
For Jena, the results are quite different; the snowflake pattern is the fastest in terms of average/geometric mean. We see that the snowflake pattern cube in scale factor 0.2 has 11 of the fastest query times and in scale factor 0.5 it has nine. The TDB database in Jena is, unlike Virtuoso, experiencing difficulties with high numbers of triples, thus several queries times out, especially when the cubes are denormalized.
For some queries, the two stores perform best on different patterns for the same query. This is caused by the differences in storage, caching, and optimization techniques of the two triple stores. In Virtuoso, query 12 is fastest on the snowflake pattern and star pattern. In Jena, however, the denormalized pattern is fastest. Query 15 contains three subqueries and is not able to execute in denormalized pattern in Jena and in scale factor 0.5 star pattern also exceeds the timeout limit; this illustrates how big a difference the query optimizer makes.
When comparing the results of the two stores for scale factors 0.2 and 0.5, we see only few changes regarding which pattern is fastest on the different queries. For most of the queries where this is changing, e.g., queries 1, 6, and 18, the runtimes for all patterns are very close. Query 6 does not query any levels but only facts, this means that only subject-subject joins are made. The runtimes for the snowflake pattern, the star pattern, and the denormalized pattern are relatively similar in both stores. This indicates that queries of this particular type do not benefit from denormalization.
For some queries, both Jena and Virtuoso performs best on the same pattern. Query 5, for instance, involves seven different levels, this entails many subject-object joins, which resemble long path queries in the snowflake pattern and the star pattern but only a short path in the denormalized pattern. Therefore, query 5 is evaluated fastest on the denormalized pattern.
In general, we observe the tendency that queries that span many distinct levels benefit from denormalization while the opposite is also true: queries that span only a few levels perform better on the snowflake pattern.
Conclusion of the experiments. Based on the three measures load time, storage size, and query time we have gained a deeper understanding of when to use the three patterns. We see that the denormalized pattern has more than twice as many triples as the other patterns and much larger load time but shows the most potential in terms of query time for Virtuoso, for which the denormalized pattern performs up to 35 times faster (in scale factor 0.5). In Virtuoso the star pattern cube represents a sweet spot between query time, load time, and amount of triples. Jena does not in general gain a performance increase in terms of query time when using denormalization.
The fully denormalized pattern is highly recommended for Virtuoso when dealing with static datasets – for frequently changing data, the update costs are too high. This pattern also requires a hardware platform with sufficient storage due to the introduced data redundancy and an underlying system that can efficiently handle a high number of triples. Alternatively, we recommend using the star pattern because of the modest increase in triples and load time – as compared to the snowflake pattern– while on average yielding more than 6 times faster query times in Virtuoso. Based on our experimental results, we do not recommend denormalization in Jena. 7
Motivated by the increasing need to store and query analytical data in RDF format, this paper presented query optimization techniques to increase the performance of queries on RDF data cubes. Inspired by relational data cube representations, the paper proposed three novel cube patterns for RDF data cubes: snowflake pattern, star pattern, and fully denormalized pattern. Furthermore, this paper presented the Semantic Web OLAP Denormalizer (SWOD) algorithm that transforms the pattern of the RDF instance data. Finally, the paper provided an extensive experimental evaluation, based on an RDF version of the TPC-H benchmark, examining storage space, load time, and query time. The evaluation showed that the proposed patterns are effective for improving query performance at the expense of additional storage space and that their performance also depends on the underlying triple store. Interesting directions for future work include implementing additional optimizations for data cube processing, such as materialized views, as well as the integration of the proposed approach directly within a triple store.
This research was partially funded by the Danish Council for Independent Research (DFF) under grant agreement No. DFF-4093-00301.