OLAP Querying of Document Stores in the Presence of Schema Variety (DISCUSSION PAPER)Matteo Francia0Enrico Gallinucci0Matteo Golfarelli0Stefano Rizzi0Multidimensional Modeling OLAP0DISI, University of Bologna
,
Italy
Document stores are preferred to relational ones for storing heterogeneous data due to their schemaless nature. However, the absence of a unique schema adds complexity to analytical applications. In a previous paper we have proposed an original approach to OLAP on document stores; its basic idea was to stop ghting against schema variety and welcome it as an inherent source of information wealth in schemaless sources. In this paper we focus on the querying phase, showing how queries can be directly rewritten on a heterogeneous collection in an inclusive way, i.e., also including the concepts present in a subset of documents only.
NoSQLIntroduction
Schemaless databases, in particular document stores (DSs) such as MongoDB,
are preferred to relational ones for storing heterogeneous data with variable
schemas and structural forms; typical schema variants within a collection
consist in missing or additional elds, in di erent names or types for a eld, and in
di erent structures for instances. The absence of a unique schema grants
exibility to operational applications but adds complexity to analytical applications,
in which a single analysis often involves large sets of data with di erent schemas.
Dealing with this complexity while adopting a classical data warehouse design
approach would require a notable e ort to understand the rules that drove the
use of alternative schemas, plus an integration activity to identify a common
schema to be adopted for analysis.
In this paper we propose an approach to OLAP querying on DSs. The basic
idea is to welcome data heterogeneity and schema variety as an inherent source
of information wealth. So, instead of trying to hide this variety, we show it
to users (basically, data scientists and data enthusiasts). To the best of our
knowledge, this is the rst approach to propose a form of approximated OLAP
analyses on document stores that embraces and exploits the inherent variety of
documents. OLAP querying is carried out directly on the data source, without
Copyright c 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0). This volume is published
and copyrighted by its editors. SEBD 2020, June 21-24, 2020, Villasimius, Italy.
materializing any cube or data warehouse. Remarkably, we adopt an inclusive
solution to integration, i.e., the user can include a concept in a query even if
it is present in a subset of documents only. We cover both inter-schema and
intra-schema variety, speci cally we cope with missing elds, di erent levels of
detail in instances, di erent eld naming.
2
Related Literature
The rise of NoSQL stores has captured a lot of interest from the research
community, which has proposed a variety of approaches to deal with the schemaless
feature. Accessing schemaless sources often requires the adoption of data
integration techniques to provide a uni ed view of data; as this is not the primary
focus of the paper, we refer the reader to a survey on the subject [
6
].
A distinguishing feature of our approach is the de nition of a
multidimensional representation of the schema to enable OLAP analyses directly on the DS.
From this point of view, a work closely related to ours is [
2
], which proposes a
schema-on-read approach for multidimensional queries over DSs. That approach
di ers from ours because it focuses on the multidimensional representation of
JSON data and overlooks the variety issues, and because the detection of
functional dependencies is activated on-demand only after the user has written a
query. OLAP analyses on DSs are enabled also in [
7
], although a simpler
integration approach is proposed, with no identi cation of functional dependencies
nor multidimensional views.
On the issue of schema variety on DSs, a recent work [
8
] builds on a
simple mapping strategy to hide the variety within a single, comprehensive query.
Whereas the approach proposes a simpler querying mechanism, it only covers a
limited set of schema variants and does not support OLAP.
Finally, several works have focused on bringing NoSQL back to the
relational world. [
11
] discusses an approach to provide schema-on-read capabilities
for exible schema data stored on RDBMSs: it maps the document structure on
di erent tables and provides a data guide as the union of every possible eld at
any level. However, no advanced schema matching mechanism is provided.
3
Approach Overview and Working Example
_id
FirstName
LastName
Date
Gym.Name
Gym.City
Gym.Country
SessionType
DurationSecs
Series
Series_id
ExType
Reps
Weight
SeriesCalories
Document store
array contains an object for every exercise carried out during the session; the
Sets array contains an object for every set that the exercise was split into.
1. Schema extraction. The goal is to identify the set of distinct local schemas
that occur inside a collection of documents. To this end we adopt a tree-like
de nition for schemas which models arrays by considering the union of the
schemas of their elements, as done in [
1
]. This is a completely automatic
stage; its implementation is loosely inspired by the free tool variety.js and
consists of a routine that connects to the desired collection on MongoDB,
extracts the local schemas, and writes the results on a triplestore. With
reference to our example, Figure 1 shows the schema s1 of the sample document.
Each array is represented as a box, with its child primitives listed below
(numeric primitives are in italics). Object elds are pre xed with the object
key (e.g., Facility.Chain). The vertical lines between boxes represent nestings
of arrays, with the root WS on top.
2. Schema integration. The goal here is to integrate the distinct, local schemas
extracted from a collection to obtain a single and comprehensive view of the
latter, i.e., a global schema, and its mappings with each local schema. To
this end we rely on both schema matching and schema mapping techniques:
the former allow to identify the single matches between the attributes, while
the latter de ne the mappings between each local schema and the global
one, thus enabling the rewriting of queries. A mapping between two (sets
of) primitive elds P and P 0 requires a transcoding function to transform
values of P into values of P 0; these functions enable query reformulation in
the presence of selection predicates as well as the integration of the query
results obtained from all documents. The approach we adopt for schema
integration includes two steps. The rst step is automatic and de nes a
preliminary global schema as the name-based union of all local schemas [
10
]. In
the second step, the preliminary global schema is re ned by merging
matching (sets of) elds in the global schema. Existing tools (e.g., Coma 3.0 [
12
])
can be used to automatically nd a list of possible matches between arrays
and primitives; then the user will browse them and possibly de ne
additional mappings. With reference to our example, Figure 1 shows the global
schema g resulting from the integration of s1 with s2, one more schema
from WS; mappings between arrays and primitives are represented with
dotted lines. The transcoding functions of mappings hfDateg; fStartedOngi and
hfFirstName; LastNameg; fUser.FullNamegi are the identity function and a
function that concatenates two strings, respectively.
3. Schema enrichment. The goal is to propose a multidimensional view of
the global schema to enable OLAP analyses. The main informative gap to
be lled to this end is the identi cation of hierarchies, which in turn relies
on the identi cation of functional dependencies (FDs) between elds in the
global schema. By assuming the presence of identi ers at every nesting level,
some exact FDs can be derived from the global schema without looking
at the data. However, additional FDs can exist between primitive nodes,
though they cannot be inferred from the schema and can only be found
by querying the data. More precisely, since DSs may contain incomplete
and faulty data, we look for approximate FDs (AFDs) [
9
], i.e., FDs that
\mostly" hold on data. To detect approximate FDs, we adapted the approach
proposed in [
4
]. As a result, we determine a dependency graph, which provides
a multidimensional view of the global schema in terms of the FDs between its
primitive elds. Figure 3 shows the dependency graph for our example. Each
primitive eld f is represented as a circle whose color is representative of the
support of f , i.e., of the percentage of times that f occurs in the collection
(the lighter the tone, the lower the support). Identi ers (e.g., id) are shown
in bold. Directed arrows are representative of the (A)FDs detected during
schema enrichment; for instance, we have id ! Facility.Name (exact FD, in
black) and Facility.Name Facility.Chain (AFD, in grey). The latter FD is
approximate because it only holds for a subset of documents.
4. Querying. The last stage enables the formulation of multidimensional queries
on the dependency graph and their execution on the collection. First of
Facility.Chain
all, each formulated query is validated against the requirements of
wellformedness proposed in the literature [
13
]. Then, the query is reformulated
into multiple queries, one for each local schema in the collection, which are
translated into the query language of the DS; the results presented to the
user are obtained by merging the results of the single local queries.
4
Querying
In this section we describe the nal querying stage of our approach. Given a
global schema g and the dependency graph M obtained by enriching g with
(A)FDs, a multidimensional query (from now on, md-query) is a triple q =
hG; p; m; 'i where: G is the query group-by set, i.e., a non-empty set of primitive
elds in M; p is an optional selection predicate de ned as a conjunction of
Boolean predicates on primitive elds; m is the query measure, i.e., the numeric
primitive eld to be aggregated; ' is the operator to be used for aggregation
(e.g., avg, sum).
For q to be well-formed, there must exist in M one single eld f such that
all the other elds mentioned in q (either in G, p, or m) can be reached in M
from f . Field f is called the fact of q (denoted f act(q)) and corresponds to the
coarsest granularity of M on which q can be formulated.
Other well-formedness constraints for md-queries are introduced in [
13
]: the
base integrity constraint, stating that the elds in G must be functionally
independent on each other, and the summarization integrity constraint. The base
integrity constraint can be easily checked on the dependency graph (no arcs must
exist between the elds in G). As to the summarization integrity constraint, each
query undergoes a check that can possibly return some warnings to inform the
user of potentially incorrect results. Speci cally, summarization integrity entails
disjointness (to avoid double counting, the measure instances to be aggregated
must be partitioned by the group-by instances) and completeness (the union of
these partitions must constitute the entire set). Disjointness is easily checked
on the dependency graph by verifying if the granularity of measure m is ner
than the one of all the elds in G. Completeness is obtained if all the elds in G
have full support, which is easily contradicted in heterogeneous collections. To
restore completeness, we adopt at query time the balancing strategies used for
incomplete hierarchies in data warehouse design; basically, the $ifNull operator
in MongoDB is used to replace a missing value in a eld with a custom value.
Example 1. The following md-query on the WS collection, q1, measures the
average amount of weight lifted by elderly athletes per city and type of exercise:
q1 = hfFacility.City; Exercises.Typeg; (User.Age
60); Exercises.Sets.Weight; avgi
We have f act(q1) = Exercises.Sets. id. Query q1 passes the validity check with
a warning, because the support of Facility.City is less than one, so balancing
is used to restore completeness. On the other hand, q1 meets the disjointness
constraint because the granularity Exercises.Sets. id of the required measure,
Exercises.Sets.Weight, is ner than both the granularities id and Exercises. id of
the group-by elds.
Once a well-formed md-query q has been formulated by the user on the
dependency graph, it has to be reformulated on each local schema si to e ectively
cope with inter-document variety. To this end we rely on the approach to
mdquery reformulation proposed in [
5
] for federated data warehouse architectures.
This approach has been proved to be complete and to provide all certain answers
to the md-query. As a result, a set of local queries q(i), one for each local schema
si, are determined.
At this point, each local query q(i) is separately executed on the DS; speci
cally, q(i) must target only the documents that belong to local schema si. This
is done in two steps. First, the information about which document has which
schema (obtained in the schema extraction stage) is stored in a di erent
collection (called WS-schemas in our example) in the following form: a document is
created for every schema si, containing an array ids with the id of every
document having schema si. Then, query q(i) is executed by joining it with the list of
identi ers in WS-schemas. Note that, to be executed, q(i) needs be translated to
the MongoDB query language, which allows us to declare a multi-stage pipeline
of transformations to be carried out on the documents of a collection.
Finally, a post-processing activity is required to integrate and, possibly,
further aggregating the results coming from the di erent local queries. This
operation can be performed in-memory, as OLAP queries usually produce a limited
number of records and the transcoding functions provide homogeneous values.
Example 2. Consider an md-query that calculates the total amount of burnt
calories by facility, excluding workout sessions that are shorter than 30 minutes:
q2 = hfFacility.Nameg; (DurationMins
30); Exercises.ExCalories; sumi
Consider the local schemas s1 and s2 in Figure 1. The reformulation of q2 onto
s1 has no e ect (i.e., q2(1) q2); conversely, the reformulation onto s2 generates
the following local query:
q2(2) = hfGym.Nameg; (
DurationSecs
60
30); Series.SeriesCalories; sumi
The MongoDB query obtained from q1 of Example 1 is the following; note that
the missing values of Facility.City are replaced by those of Facility.Name:
db.WS.aggregate(
f f $unwind: "$Exercises" g,
f $unwind: "$Exercises.Sets" g,
f $match: f "User.Age": f $gte: 60 g g g,
f $project:
f "Facility.City": f $ifNull: ["$FacilityCity","$FacilityName"] g g,
"Exercises.Type": 1,
"Exercises.Sets.Weight": 1,
"balanced": f $cond: ["$FacilityCity",false,true]g g g,
f $group:
f " id":
f "FacilityCity","$FacilityCity",
"ExercisesType","$Exercises.Type",
"balanced","$balanced" g,
"Exercises.Sets.Weight":
f $avg: "$Exercises.Sets.Weight" g,
"count": f $sum: 1 g,
"count-m": f $sum: f $cond: ["$Exercises.Sets.Weight",1,0] g g g g g )
5
Conclusions and Evaluation
In this paper we have presented an original approach to OLAP querying on
DSs. Our basic claim is that the heterogeneity and schema variety intrinsic
to DSs should be considered as a source of information wealth. At the core
of our approach are (i) the building of a global schema that maps onto the
di erent local schemas within a collection, (ii) the translation of this schema
into multidimensional form enhanced by the detection of approximate FDs, and
(iii) the reformulation of queries from the global schema onto the local schema
to improve the completeness of the result.
As a proof of concept for our approach we have developed a Java prototype to
support the main phases and tested it on a cluster of seven CentOS 6 machines
with an 8-core i7-4790 CPU @3.60 GHz and 32 GB of RAM. Our reference
realworld collection, WS, is stored on Mongo DB 3.4 and randomly sharded on the
cluster; it contains 5 M workout sessions with 6 di erent local schemas (mostly
due to missing elds), 35 M exercises, and 85 M sets.
Query formulation and translation to MongoDB are done in negligible time.
Reformulation is done with polynomial complexity [
5
]. Thus, performances mainly
depend on query execution. Consider for instance the following three md-queries:
qa = hfUser.Age; Facility.Chaing; T RU E; DurationMins; avgi
qb = hfUser.FullNameg; (SessionType = \Advanced"); Exercises.ExCalories; sumi
qc = hfFacility.Name; Exercises.Typeg; (StartedOn 01=01=2018); User.Age; maxi
Due to the reformulation on the local schemas, 6 local md-queries are created
from each of the three global ones. A simple optimization is done, when possible,
to merge the local queries that involve the same elds on di erent local schemas;
for instance, with reference to Figure 1, a query counting the documents by
SessionType can be translated into a single local query, as every local schema
has the same representation of SessionType. Due to this optimization, qa, qb,
and qc are reformulated into either 2 or 3 local queries. The execution times in
seconds for each query are shown in Figure 4; the times for qb and qc are higher
due to the necessity of unwinding arrays.
1.
Baazizi
,
M.A.
,
Lahmar
,
H.B.
,
Colazzo
,
D.
,
Ghelli
,
G.
,
Sartiani
,
C.
:
Schema inference for massive JSON datasets
.
In: Proc. EDBT
. pp.
222
{
233
(
2017
)
2.
Chouder
,
M.L.
,
Rizzi
,
S.
,
Chalal
, R.:
EXODuS: Exploratory OLAP over document stores
.
Inf. Syst
.
79
,
44
{
57
(
2019
)
3.
Gallinucci
,
E.
,
Golfarelli
,
M.
,
Rizzi
,
S.
:
Approximate OLAP of document-oriented databases: A variety-aware approach
.
Inf. Syst
.
85
,
114
{
130
(
2019
)
4.
Golfarelli
,
M.
,
Graziani
,
S.
,
Rizzi
,
S.
:
Starry vault: Automating multidimensional modeling from data vaults
.
In: Proc. ADBIS
. pp.
137
{
151
(
2016
)
5.
Golfarelli
,
M.
,
Mandreoli
,
F.
,
Penzo
,
W.
,
Rizzi
,
S.
,
Turricchia
, E.:
OLAP query reformulation in peer-to-peer data warehousing
.
Inf. Syst
.
37
(
5
),
393
{
411
(
2012
)
6.
Golshan
,
B.
,
Halevy
,
A.Y.
,
Mihaila
,
G.A.
,
Tan
,
W.
:
Data integration: After the teenage years
.
In: Proc. PODS
. pp.
101
{
106
(
2017
)
7.
Hamadou
,
H.B.
,
Gallinucci
,
E.
,
Golfarelli
,
M.
:
Answering GPSJ queries in a polystore: A dataspace-based approach
.
In: Proc. ER
. pp.
189
{
203
(
2019
)
8.
Hamadou
,
H.B.
,
Ghozzi
,
F.
,
Peninou
,
A.
,
Teste
,
O.
:
Towards schema-independent querying on document data stores
.
In: Proc. DOLAP
(
2018
)
9.
Ilyas
,
I.F.
,
Markl
,
V.
,
Haas
,
P.
,
Brown
,
P.
,
Aboulnaga
,
A.
:
CORDS: Automatic discovery of correlations and soft functional dependencies
.
In: Proc. SIGMOD
. pp.
647
{
658
(
2004
)
10.
Klettke
,
M.
, Storl, U.,
Scherzinger
,
S.
,
Regensburg
,
O.
:
Schema extraction and structural outlier detection for JSON-based NoSQL data stores
.
In: Proc. BTW
. vol.
2105
, pp.
425
{
444
(
2015
)
11.
Liu
,
Z.H.
,
Gawlick
,
D.
:
Management of exible schema data in RDBMSs - opportunities and limitations for NoSQL
.
In: Proc. CIDR
. Asilomar, USA (
2015
)
12. Ma mann, S.,
Raunich
,
S.
, Aumuller,
D.
,
Arnold
,
P.
,
Rahm
, E.:
Evolution of the COMA match system
.
In: Proc. OMISWC
. Bonn,
Germany
(
2011
)
13.
Romero
,
O.
,
Abello
,
A.
:
Multidimensional design by examples
.
In: Proc. DaWaK
. pp.
85
{
94
.
Krakow
,
Poland
(
2006
)