We address the problem of querying data cubes for Online Analytical Processing (OLAP) analysis, directly on the Semantic Web (SW). We rst introduce CQL, a simple algebra for querying data cubes at a conceptual level. Taking advantage of QB4OLAP metadata, we automatically translate CQL queries into SPARQL ones, and propose query optimization strategies that adapt, to the particular OLAP setting, general-purpose techniques. A web application allows exploring and querying OLAP cubes on the SW, using the machinery presented here.
Month MonthNumber MonthName
Time Year
Year
Age
AgeGroupCode
AgeGroupDesc
main data type is the data cube. We sketch a query simplication strategy for
CQL, and propose algorithms to automatically translate CQL queries into
equivalent SPARQL ones over QB4OLAP data cubes, and a strategy to improve the
performance of those SPARQL queries. Preliminary results (discussed briey)
have shown that our strategies substantially speed up the query evaluation
process, outperforming other proposals. A web application allowing to explore and
query QB4OLAP cubes has been developed. We remark that our goal is to
enable OLAP practitioners, without any knowledge of SPARQL or SW concepts , to
write ecient queries using just operators well-known for any OLAP user, over
a conceptual MD model, regardless the underlying data model and data types.
Running Example. Throughout this paper we use an example based on
statistical data about asylum applications to the European Union, provided by
Eurostat.7 The original data set consists of observations reporting the number of
applications by month, sex, age, application type, country of origin, and destination
country. To show the potential of QB4OLAP, we enriched the existent data set
by building aggregation hierarchies. Figure 1 shows the conceptual schema of the
extended data cube, using the MultiDim notation [
In the remainder, Section 2 sketches the QB4OLAP vocabulary. Section 3 presents the CQLalgebra and the data model, for querying QB4OLAP data cubes. In Section 4 we describe the CQL-to-SPARQL translation process. Section 5 briey discusses related work, and we conclude in Section 6.
We now use our running example to concisely show how data cubes, dimension schemas and dimension instances can be represented using QB4OLAP. 8 Like in QB, the schema of a data set is specied by means of the DSD. QB4OLAP represents the structure of a data set (i.e., a cube) in terms of dimension levels (introducing the class qb4o:LevelProperty ), and measures. The prexes used in this work are presented in Figure 2 in Appendix A.
Example 1. (QB4OLAP cube structure) Below we show the representation of the structure of a data cube for the Eurostat example, using QB4OLAP. schema:migr_asyappctzmQB4O rdf:type qb:DataStructureDenition ; qb:component [ qb4o:level property:age ; qb4o:cardinality qb4o:ManyToOne ] ; qb:component [ qb4o:level sdmxd:refPeriod ; qb4o:cardinality qb4o:ManyToOne ] ; ...
qb:component [ qb4o:level property:citizen ; qb4o:cardinality qb4o:ManyToOne ] ; qb:component [ qb:measure sdmx measure:obsValue ; qb4o:aggregateFunction qb4o:sum ] . Note that dimension levels in this cube are the lowest levels in the dimension hierarchies. Observations (in OLAP terminology, facts ), represent points in an MD space, complying with the schema given above. tu The class qb4o:Hierarchy represents dimension hierarchies , attached to a dimension via the property qb4o:hasHierarchy . Class qb4o:HierarchyStep represents the parent-child relationship between two levels. Each step is associated via qb4o:rollup with a custom property that implements the rollup relationship at the instance level.
Citizenship dimension of Figure 1 (schema:citizenshipDim ), and its Geography hierarchy. Note that levels property:citizen and schema:continent are dened, as well as their attributes, e.g., schema:continentName .
Example 3. (Dimension Instances) Level members are attached to dimension levels via the property qb4o:memberOf . Below we show dimension members corresponding to France, for dimension schema:citizenshipDim . citizen:FR qb4o:memberOf property:citizen ; schema:countryName "France"@en; schema:inContinent citDim:EU ; schema:hasGovernment dbpedia:Unitary_state . citDim:EU
qb4o:memberOf schema:continent ; schema:continentName "Europe" . dbpedia:Unitary_state qb4o:memberOf schema:governmentType ; schema:governmentName "Unitary state"@en . tu tu 3
To allow users to query QB4OLAP cubes without dealing with SPARQL, we
propose an algebra, denoted CQL, based on [
The CQL Language We next dene a formal data model for cubes, and
OLAP operators over this model. A cube expressed in this model can be
represented using the QB4OLAP vocabulary. Due to space limitations, we only
present informally the main ideas, and refer the reader to [
A dimension schema is a tuple hd; L; !; Hi where d is the name of the dimension; L is a set of pairs hl; Ali, where l is a level in L, and Al is a set of attributes associated with l; ‘!’ is a partial order between pairs of levels in L with a unique bottom level and a unique level, denoted All; H is a set of pairs hhn; Lhi, called hierarchies, where h identies the hierarchy, and Lh L is the set of levels in the hierarchy. Given a schema for dimension d, a dimension instance Id for d is dened as follows: for each level l in d there is a set of tuples Tl, and such that for each attribute ai 2 Al there is a value from Dom(ai) in Tl(ai): In addition, there is R, a nite set of rollup relations, one for each pair of levels in ‘!’, denoted as follows: RUPLLij ; Li; Lj 2 L, where Li ! Lj , associating elements in Tli with elements in Tlj .
A cube schema is a tuple hCn; D; M; F i where Cn is the name of the cube; D is a nite set of dimension schemas; M is a nite set of attributes called measures ; and F is a function mapping a measure m 2 M to an aggregate function. Given a cube schema with D dimensions and M measures, and a set of levels VCb = fl1; l2; : : : ; lDg; such that there are not two levels belonging to the same dimension, a cuboid instance Cb is a partial function Cb : Tl1 TlD ! Dom(m1) Dom(mM ), where mk 2 M; 8k; k = 1; : : : ; M , where Tl1 are the instances of level li 2 Idi . The elements in the domain of Cb are called cells, and VCb it the set of levels of the cuboid.
The above allows us to dene a lattice of cuboids, provided that we dene an order between cuboids, as follows. Two cuboids Cb1 and Cb2, that refer to the same cube schema, are adjacent if their corresponding level sets VCb1 and VCb2 dier in exactly one level belonging to the same dimension d. Given two adjacent cuboids Cb1 and Cb2, such that VCb1 VCb2 = flcg and VCb2 VCb1 = flpg, and lc ! lp 2 d, then Cb1 Cb2. Moreover, for each pair of adjacent cuboids Cb1 Cb2, if we assume that RUPllpc is a function, each cell in each cell Cb2 can be obtained from the cells in Cb1, aggregating the measures along the dimension d using such function, and the aggregation functions associated to each measure. Finally, a Cube Instance is the lattice of all cuboids that share the same cube schema. The bottom of this lattice is the original cube, and the top of the lattice is the cuboid with just the All level for all the dimensions in the cube.
Now that we have the intuition of what a cube is, we are ready to give a
precise semantics for the operators composing the CQL algebra (see [
The Roll-up operator summarizes data to a higher level along a dimension hierarchy; that is, it receives a cuboid Cb1 in a cube instance, and returns another cuboid Cb2 in the same instance, such that Cb1 Cb2. The Drill-down operator does the inverse, i.e., it returns a cuboid Cb2 such that Cb2 Cb1. It is clear that a Drill-down over a dimension d can be obtained performing a Roll-up over d from the bottom cuboid. We will use this result in the sequel. Since Roll-up and Drill-down only imply a navigation across a lattice (and do not modify it), we call them Instance Preserving Operators (IPO).
The Dice operator selects the cells in a cuboid that satisfy a boolean
condition , expressed over level member attributes, and/or measure values. The
Slice operator removes one of the dimensions or measures in the cube. We
denote these operators Instance Generating Operators (IGO), since they induce a
new lattice (because they reduce the dimensionality of the cube, or because they
reduce the number of cells in the cuboid), whose bottom cuboid is the result of
the corresponding operation. Again, see [
Example 4. (CQL syntax) Given the query: Total asylum applications submitted by African citizens to France in 2013, by sex, time, age, and citizenship country ; the CQL query below produces the answer. $C1:= ROLLUP (migr_asyappctzm, timeDim, year); $C2:= ROLLUP ($C1,citizenshipDim,continent); $C3:= DICE ($C2,(citizenshipDim|continent|continentName = "Africa")); $C4:= DICE ($C3,(destinationDim|geo|countryName = "France" AND timeDim|year|yearNum = 2013)); $C5:= DRILLDOWN ($C4,citizenshipDim,citizenship); $C6:= SLICE ($C5,asylappDim); $C7:= SLICE ($C6,destinationDim);
The notation of the DICE operation is (dimension|level|attribute). Note that the ROLLUP to the continent level, is performed to allow selecting African citizens. Note that the DRILLDOWN takes the cube down to the Citizenship level (the applicant’s country), and the two nal SLICE operations remove dimensions Application Type and Destination since they are not wanted in the result. tu (b)(Slice jRoll-up+jDrill-down+jDicel+)++; (c)(Slice jRoll-up+jDrill-down+jDicel ) Dice+m:
To restrict the problem to queries that can be evaluated without storing the computation trace, we limit ourselves to consider the subset of CQL queries that satisfy the following patterns, where Dicel and Dicem denote dicing operations on level attribute or measure values, respectively:(a) (Slice jDice jRoll-up )+; CQL simplication Since CQL is aimed at being used by non-experts, input CQL queries may include unnecessary operations. Further, operations can be reordered to reduce the size of the cuboid as early as possible. Thus, we devised the following set of rewriting rules: (1) Remove all the Roll-up or Drill-down operations with the same origin and target level; (2) Given a sequence of Roll-up and/or Drill-down operations over a dimension d, without Dicel operations in-between, and where l 2 d, nd the last level lD in the sequence, and if lD is not the bottom level of d, replace the sequence with a single Roll-up from the bottom to ld; Otherwise, remove all the operations in the group; (3) If there is a Slice over a dimension d (respectively, a measure m), and no Dice operation that considers level members of d (respectively, mentions m), move the Slice to the beginning of the query; otherwise move it to the end; (4) If there is a Slice over a dimension d, a sequence of Roll-up and Drill-down operations over d, and no Dice operation mentions levels in d, remove all the Roll-up and Drill-down operations, and keep only the Slice one.
It can be proved that, applying these rules produces a query such that: (a) If there are no Dice operations in a CQL query, there is at most one Roll-up and no Drill-down operation for each Dimension d; (b) Slice operations are either at the beginning or at the end of the query, but not in the middle. 4
The next step in the process is the translation of CQL queries (expressed at the conceptual level), into SPARQL expressions over QB4OLAP cubes (logical level), avoiding the materialization of intermediate results. We present the ideas by means of an example. Let us consider the query: Total asylum applications per year submitted by Asian citizens to France or United Kingdom, where the number of applications is > 5000, expressed in CQL as: $C1 := ROLLUP (migr_asyappctzm, citizenshipDim,continent); $C2 := ROLLUP ($C1, timeDim, year); $C3 := DICE ($C2, (citizenshipDim|continent|continentName = "Asia")); $C4 := DICE ($C3, ( obsValue > 5000 AND (destinationDim|country|countryName = "France")
OR (destinationDim|country|countryName = "United Kingdom")));
The SPARQL query below, produced by our translation algorithms, implements Query 4. It contains a subquery, where aggregated values are computed, and an outer query where the FILTER conditions that implement the Dice operations are applied. 1 SELECT ?plm1 ?plm2 ?lm3 ?lm4 ?lm5 ?lm6 ?ag1 2 WHERE { 3 { SELECT ?plm1 ?plm2 ?lm3 ?lm4 ?lm5 ?lm6 (SUM(xsd:integer(?m1)) as ?ag1) 4 FROM loc ins:migr_asyapp_clean 5 FROM loc sch:migr_asyappctzmQB4O13 6 WHERE { ?o a qb:Observation . ?o qb:dataSet dt:migr_asyappctzm . 7 ?o sdmxm:obsValue ?m1 . 8 ?o property:citizen ?lm1 . ?lm1 qb4o:memberOf property:citizen . 9 ?lm1 schema:inContinent ?plm1 . ?plm1 qb4o:memberOf schema:continent . 10 ?o sdmxd:refPeriod ?lm2 . ?lm2 qb4o:memberOf sdmxd:refPeriod . 11 ?lm2 schema:inYear ?plm2 . ?plm2 qb4o:memberOf schema:year . 12 ?o property:geo ?lm3 . ?o property:sex ?lm4 . 13 ?o property:age ?lm5 . ?o property:asyl_app ?lm6 . 14 ?plm1 schema:continentName ?plm11 . 15 ?lm3 schema:countryName ?lm31 . 16 FILTER ( ?plm11="Asia" && ((?lm31="France"@en) || (?lm31="United Kingdom"@en))) 17 } GROUP BY ?plm1 ?plm2 ?lm3 ?lm4 ?lm5 ?lm6 18 } FILTER ( ?ag1 > 5000) }
Lines 8 and 9 implement the rst roll-up ( C1). Variable ?lm1 will be instantiated with each member of the Country level in the Citizen dimension hierarchy, related to an observation ?o. Then, we navigate the hierarchy up to the level Continent, using the rollup property schema:inContinent . The variable ?plm1 will contain the continent corresponding to the country that instantiates ?lm1. It is placed in the SELECT clause of the inner query (line 3), in the GROUP BY clause of the inner query (line 18), and in the result of the outer query (line 1). The navigation corresponding to the Rollup in C2 is performed analogously. Lines 12 and 13 instantiate the level members of the remaining dimensions, and variables are added to the GROUP BY and SELECT clauses of the inner and outer queries, respectively. Line 7 retrieves the value of the measure in each observation, and the SUM aggregate function computes ?ag1 in line 3. The aggregated value is added to result of the outer query (line 1) (measure values are converted to integer before applying the SUM, due to format restrictions of Eurostat data). Finally, to implement the Dice operation in statement C3, we need to obtain the name of each continent (line 14) and then use a FILTER clause to keep only the cells that correspond to Asia (line 16). Analogously, the restrictions on country names are implemented in line 16 (country names are retrieved in line 15), while the restriction on the measure values must be performed after the aggregation, and is implemented by the FILTER clause of the outer query (line 19).
SPARQL queries improvement To improve the performance of the queries produced by the nave algorithm, we adapted existing SPARQL optimization techniques to the characteristics of MD data and QB4OLAP.
As a rst strategy, we adapted to our setting the heuristics proposed by
Loizou et al. [
H2 - Specifying alternative URIs. Proposes to transform FILTER clauses with disjunction (||) of equality constraints, using either the UNION of patterns, or a VALUES expression. Since the reported results are not conclusive on which of these strategies leads to better performant queries, we decided to try them both in our experimental evaluation (not discussed in this paper).
As a second strategy, we considered the recommendations in [
We next show the result of applying these strategies to the SPARQL query above. The application of H1 organizes graph patterns in the inner query in two GRAPH clauses: one for the instance graph (lines 7 to 11), and another for the schema graph (lines 12 to 19). Applying H2, the FILTER clause on country names is replaced by a VALUES clause (line 19). Filter clauses are split, and the FILTER clause on continent name is replaced by a graph pattern (line 15). 1 SELECT ?plm1 ?plm2 ?lm3 ?lm4 ?lm5 ?lm6 ?ag1 2 WHERE { 3 { SELECT ?plm1 ?plm2 ?lm3 ?lm4 ?lm5 ?lm6 (SUM(xsd:integer(?m1)) as ?ag1) 4 FROM NAMED loc ins:migr_asyapp_clean 5 FROM NAMED loc sch:migr_asyappctzmQB4O13 6 WHERE { 7 {GRAPH loc ins:migr_asyapp_clean 8 {?o a qb:Observation . ?o qb:dataSet dt:migr_asyappctzm . 9 ?o sdmxm:obsValue ?m1 . ?o property:citizen ?lm1 . 10 ?o sdmxd:refPeriod ?lm2 . ?o property:geo ?lm3 . 11 ?o property:sex ?lm4 . ?o property:age ?lm5 . ?o property:asyl_app ?lm6 . }}. 12 {GRAPH loc sch:migr_asyappctzmQB4O13 13 {?lm1 qb4o:memberOf property:citizen . 14 ?lm1 schema:inContinent ?plm1 . ?plm1 qb4o:memberOf schema:continent . 15 ?plm1 schema:continentName "Asia" . 16 ?lm2 qb4o:memberOf sdmxd:refPeriod . ?lm2 schema:inYear ?plm2 . 17 ?plm2 qb4o:memberOf schema:year . 18 ?lm3 schema:countryName ?lm31 . 19 VALUES ?lm31 {"France"@en "United Kingdom"@en} }} 20 } GROUP BY ?plm1 ?plm2 ?lm3 ?lm4 ?lm5 ?lm6 21 } FILTER (?ag1 > 5000) }
Finally, based on Stocker et. al [
Below, we show the result of applying OC2 to reorder the triple patterns on the second graph of the query. For each dimension, the graph patterns are ordered from higher levels in the hierarchy to lower ones. The Citizenship dimension is considered rst since a member of the dimension is xed to Asia. Then we consider the Destination dimension because there is a restriction on members of this dimension (France or United Kingdom).
GRAPH loc sch:migr_asyappctzmQB4O13 { ?plm1 schema:continentName "Asia" . ?plm1 qb4o:memberOf schema:continent . ?lm1 schema:inContinent ?plm1 . ?lm1 qb4o:memberOf property:citizen . ?lm3 schema:countryName ?lm31 .
VALUES ?lm31 {"France"@en "United Kingdom"@en} ?plm2 qb4o:memberOf schema:year . ?lm2 schema:inYear ?plm2 . ?lm2 qb4o:memberOf sdmxd:refPeriod .}
Experimental results and implementation For the sake of space we
just report that comprehensive experiments have been run adapting the Star
Schema Benchmark (SSB) [
Kmpgen et al. [
Regarding SPARQL query processing, many works study the complexity of
query evaluation [
We have described a simple algebra (CQL) over data cubes, that can be used to express OLAP queries, and automatically translated into ecient SPARQL queries. First, we use QB4OLAP metadata to obtain a nave translation of CQL to SPARQL; then, we adapted general-purpose SPARQL optimization techniques to the OLAP setting. Our experiments over a modied SSB showed that our techniques outperform other proposals, and suggested the best combinations of optimization strategies. An application to explore and query SW cubes completes our contibutions. We think that these results can encourage and promote the publication and sharing of MD data on the SW, and we plan to continue working in this direction, extending CQL with other OLAP operations. A
PREFIX xsd: <http://www.w3.org/2001/XMLSchema#> PREFIX qb: <http://purl.org/linked data/cube#> PREFIX qb4o: <http://purl.org/qb4olap/cubes#> PREFIX sdmxm: <http://purl.org/linked data/sdmx/2009/measure#> PREFIX sdmxd: <http://purl.org/linked data/sdmx/2009/dimension#> PREFIX property: <http://eurostat.linked statistics.org/property#> PREFIX citizen: <http://eurostat.linked statistics.org/dic/citizen#> PREFIX dt: <http://eurostat.linked statistics.org/data/> PREFIX loc ins: <http://www.ng.edu.uy/cubes/instances/> PREFIX loc sch: <http://www.ng.edu.uy/cubes/schemas/> PREFIX schema: <http://www.ng.edu.uy/cubes/schemas/migr_asyapp#> PREFIX citDim: <http://www.ng.edu.uy/cubes/dims/migr_asyapp/citizen#> PREFIX dbpedia: <http://dbpedia.org/resource/>