Polystores provide a loosely coupled integration of heterogeneous data sources based on the direct access, with the local language, to each storage engine for exploiting its distinctive features. In this framework, given the absence of a middleware exposing a global schema, it is hard to know if a query to one system can be satis ed by data stored elsewhere in the polystore. We address this problem by illustrating query augmentation, a data manipulation operator for polystores based on the automatic enrichment of the answer to a local query with related data in the rest of the polystore. Augmentation can be used to implement augmented search and augmented exploration: two e ective methods for information discovery in polystores that avoid middleware layers, abstract query languages, and shared data models.
The concept of polyglot persistence, which consists of using di erent database
technologies to handle di erent data storage needs [
Copyright c 2019 for the individual papers by the papers' authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. SEBD 2019, June 16-19, 2019, Castiglione della Pescaia, Italy.
This approach, however, makes even harder the problem of data integration
given the strong heterogeneity of the systems in play [
Polystore systems (or simply, polystores) have been proposed recently as
an alternative solution for this approach [
In this paper, we present (query ) augmentation, a new construct for data
manipulation in polystores that, based on a simple notion of probabilistic
relationship between objects in di erent data stores, allows the automatic enrichment
of a dataset stored in a local database with data outside the database but
available in the polystore. The implementation of this operator does not require the
addition of an abstraction layer involving query translation and therefore has a
minimal impact on the applications running on top of the data layer. The goal is
to provide a soft mechanism for data integration in polystores that complements
other approaches, such as those based on cross-db joins [
Two e ective methods for data access in polystore can be de ned with the augmentation construct: augmented search and augmented exploration.
Augmented search is a form of query relaxation [
) + (discounts: 40%) (catalogue:f title: Wish,
artist id: a1, artist: The Cure, year: 1992, ... g ) In an augumented search, each retrieved element e is associated with the probability that e is related to the result of the query. Such probability is derived o -line from integrity constraints and data mining techniques. Colors (as in the example above) and rankings can be used in practice to represent, in a more intuitive way, external data and the degree of relevance.
Augmented exploration makes use of the augmentation operator to provide
a more interactive and exible way to access data, which consists of a guided
expansion of the result of a local query. For example, if Lucy submits in
exploratory mode another SQL query to the database transactions for retrieving all
the sales whose total income is greater than 15, she obtains the tuple that
follows, in which the links suggest that further information, related to the returned
tuple, is available elsewhere and allows her to decide with a click (e.g., on the
user name) how to deepen the result. As above, the result is probabilistic.
This process is iterative and provides a method for database exploration [
We have implemented our approach in QUEPA3, a polystore system
equipped with the augmentation operator that provides the access methods
discussed above and is compatible with most modern database engines. QUEPA
operates in a plug-and-play mode and does not a ect the access modalities of
the various storage systems, thus reducing the need for ad-hoc con gurations
and for a middleware involving uni ed query languages or shared data models.
3 A demo of QUEPA has been shown in [
In addition, we have developed an optimization technique that relies on machine learning methods to tune the execution of the augmentation operator.
In the rest of the paper we brie y describe the underlying data model
(Section 2), the augmentation mechanism (Section 3), and its implementation
(Section 4). Details and experimental results are in the full version of the paper [
In PDM (Polystore Data Model) a polystore P is made of a set of databases P = fD1; : : : ; Dng stored in a variety of data management systems S1; : : : ; Sn respectively (relational, key-value, graph, etc.). A database D 2 P consists of a set of data collections each of which is a set of (data) objects. An object o 2 C is just a key-value pair: o = hk; vi where k identi es uniquely o in C and v is an atomic piece of data. A tuple and a JSON document are examples of data objects in a relational database and in a document store of a polystore, respectively.
By de nition, given a database D of a polystore P, a data collection C in D and a data object o = hk; vi in C, we can uniquely identify o in P by means of k, C and D. We call k^ = D:C:k the global-key of o in P.
Example 2. In the polystore in Figure 1 hd1; f id : d1; title : Wish; : : :gi is an object of the albums collection in the catalogue database whereas hs8; (s8; John Doe; 20:0)i is an object of the sales collection in the transactions database. The global-key of the latter is transactions:sales:s8.
This model captures polystores involving any database system satisfying the
minimum requirement that every stored data object can be identi ed and
accessed by means of a key. Note that the granularity of objects inevitably depends
on the designer's choice [
The other main ingredient of PDM is the ability to correlate data objects of possibly di erent databases of the polystore by means of the following basic notion, which we call p-relation (for relation in a polystore).
De nition 1 (p-relation). A p-relation on two objects o1 and o2, denoted by o1Rpo2, represents the existence of a relation R between o1 and o2 with probability p (0 < p 1), where R can be one of the following types: { the identity, denoted by : a re exive, symmetric and transitive relation (i.e., an equivalence relation), representing the fact that o1 and o2 refer to the same real-world entity; { the matching, denoted by : a re exive and symmetric relation (not necessarily transitive), representing the fact that o1 and o2 share some common information.
We assume that in a polystore p-relations are \consistent" in the sense that they satisfy the following condition: for each triple of objects o1, o2 and o3 such that o1 o2 and o2 o3 it is the case that o1 o3. While this is a natural condition (two equivalent objects should match the same objects), it guarantees that the augmentation construct behaves consistently with equivalent objects. Example 3. Consider the polystore in Fig. 1. By denoting the objects with their global keys we have for instance that: catalogue.albums.d1 0:8 discount.drop.k1:cure:wish, and transactions.inventory.a32 1transactions.sales-details.i4.
Basically, while the identity relation serves to represent multiple occurrences
of the same entity in the polystore, the matching relation models general
relationships between data di erent from the identity (e.g., those typically captured by
foreign keys in relational databases or by links in graph databases). On the
practical side, p-relations are derived from the metadata associated with databases
in the polystore (e.g., from integrity constraints) or are discovered using
probabilistic mining techniques. For the latter task, we rely on the state-of-the-art
techniques for probabilistic record linkage [
The augmentation construct. The basic operator of our approach takes as input an object o of a polystore and returns the augmented set n(o), which iteratively returns data objects in the polystore that are related to o with a certain probability. This probability is computed by combining the probabilities of the relationships that connect o with the retrieved objects.
De nition 2. Let o be a set of objects in a polystore P. The augmentation n of level n 0 of o is a set o0 of objects op, where o 2 P and p is the probability of membership of o to o0, de ned as follows (m > 0): { { 0(o) = o [ fop j o p o0 ^ o0 2 og m(o) = m 1(o) [ fop^ j (o p0 o0) ^ (o0p 2 m 1(o)) ^ (p^ = p p0)g Example 4. Let us consider the polystore in Fig. 2 in which nodes represents objects, ovals represent di erent databases, solid lines represent identity prelations, and dashed lines represent matching p-relations. Labels associated with p-relations denote their probability. Then, we have 0(fo4g) = fo4; o01:9g, 1(fo4g) = fo4; o10:9; o70:8; o08:7g, and 3(fo4g) = fo4; o01:9; o07:8; o80:7; o01:07g. Note that, by construction, for every k 0, if o 2 k(o) then o0 2 k(o) for each o0 o. Indeed, if o belongs to k(o) because of an object o00 2 k 1(o) such that o00 o, the consistency condition above implies that if o o0, we have also that o00 o0 and so, by De nition 2, o0 2 k(o).
The augmented construct can be at the basis of two alternative ways to access a polystore, as described in the following.
Augmented Search. An augmented search consists of the expansion of the result of a query over a local database with data that are relevant to the query but are stored elsewhere in the polystore. Consider again a polystore P composed of a set of databases stored in di erent data management systems each equipped with a speci c query language. Now, let QS denote a query expressed in the query language of the storage system S and let QS (D) be the set of objects in the result of QS over a database D stored in S. De nition 3. The augmentation of level n 0 of a query QS over a database D stored in S, denoted by QS (n)(D), consists in the augmentation of level n 0 of the result of QS over D ordered according to the probability of its elements. Example 5. Let Q be a query over the database D1 in Fig. 2 that returns the objects o1 and o2. Then we have Q(0)(D1) = fo1; o2; o04:9g and Q(1)(D1) = (o1; o2; o40:9; o07:7; o80:6; o30:6).
Augmented Exploration Exploratory computing is a new trend in big data
access that aims at helping users to make sense of very big data sets by means of
step-by-step interaction with the system oriented to the progressive re nement
of the data retrieval process [
De nition 4. An augmented exploration of a polystore P starting from a query QS over a database D stored in S consists of a sequence of k steps: [(o0 ! o0); (o1 ! o1); : : : ; (ok ! ok)] where: { o0 2 QS (D) and o0 = { oi 2 oi 1 and oi =
0(fo0g), 1(foig) (i > 0).
Example 6. Consider the query in Example 5 wich returns the set of objects fo1; o2g. Then, a possible augmented exploration involves the steps: (o1 ! fo40:9g); (o2 ! fo30:6g); (o4 ! f 7
o0:8; o80:7g)
We have fully implemented our approach in a system called QUEPA [
The validator rst checks if the query is correct (step Á) and possibly rewrites it (step Â) before its execution over the target database (step Ã). The local answer a is returned to the augmenter which is now ready to compute the augmentation (step Ä). It gets from the A+index the global keys of data objects reachable from those in a with n applications of the augmentation primitive (step Å). These global keys are used to retrieve data objects from the polystore with local queries Qi (step Æ). Finally, the augmented answer is returned to the user (step Ç). The interaction in the augmented exploration is similar but simpli ed since, at each step, only a single data object is augmented.
A comprehensive campaign of experiments done with QUEPA has shown
that our approach is feasible, e ective, and, unlike other approaches, scales nicely
as the polystore grows in the number of stores and size of databases [