Novel database architectures, data models and technologies have long challenged the one size fits all paradigm. Polyand MultiStores emerged as a solution to combine these new data stores, each with their own strengths and weaknesses. Unfortunately, these systems come with their own set of problems such as a lack of support for adaptivity, data updates, or migration processes. In this work, we propose solutions intended as first steps towards solving these problems. In detail, we look at two main topics, (1) Data Placement and Workload Analysis as well as (2) Data Migration and Integrity Constraint Management, and discuss the challenges associated with them.
focus of these systems, coined Multi- and PolyStores [6], range from aiming to ofer the full data store experience Since the late 2000s novel ways to deal with an ever- (e.g., Polypheny-DB [7], BigDAWG [8]) to cross-platform growing amount of (oftentimes unstructured) data have data processing systems (e.g., Apache Wayang [9]). Most emerged and continue to inspire new database systems of these systems hold a static, manually designated mapand data models. All of these new systems, whether ping to place data to the respective data stores and lack NoSQL or more advanced relational systems, have their any form of flexibility. However, to appropriately react own strengths and weaknesses [1]. Given the large to (possibly changing) requirements based on workloads amount of diferent systems optimized for diferent use and users’ service level agreements (SLAs), these systems cases, developers are often confronted with keeping track should be able to determine an optimal data placement inof where these systems excel or where not [2]. Addi- cluding an appropriate handling of potential constraints. tionally, the traditional way of using a single database Therefore, we want to discuss two main problems and solution for a project and the associated one size fits all outline possible solutions and ideas: (1) How to calcumindset is no longer valid [3, 4]. Furthermore, beside late an optimal data placement based on current data, so-called microservices [5], smaller functional sub-units workload, SLAs, and deployed data stores, and (2) how of larger projects, each with its own database solution, to model and validate integrity constraints in data stores there have also been eforts in recent years to combine as well as implement eficient update/insert processes in several heterogeneous data stores (database systems). In a Multi-/PolyStore setting. an efort to combine the various strengths of these sys- In Section 2, we describe the concept of PolyStores in tems, they are unified within a mediation system and detail and present the state of the art in Section 3. In Secexposed to users as a single data store system [1]. The tions 4 and 5, we focus on our two main topics of Data Placement and Constraint Management, respectively. Fi35th GI-Workshop on Foundations of Databases (Grundlagen von Daten- nally, we provide a brief conclusion in Section 6. banken), May 22-24, 2024, Herdecke, Germany. * Corresponding author. † These authors contributed equally. 2. Multi-/PolyStores $ felix.kiehn@uni-hamburg.de (F. Kiehn); mareike.schmidt-3@uni-hamburg.de (M. Schmidt); Before we dive deeper into the aforementioned problems, fabhiatntp.psa:nse@hpi.de (F. Panse) we want to establish what Poly- and MultiStores are in //vsis-www.informatik.uni-hamburg.de/vsis/members/look/2291 detail first. They can both be classified as "[s]ystems (F. Kiehn); https: federating specialized data stores and enabling query //vsis-www.informatik.uni-hamburg.de/vsis/members/look/2290 processing across heterogeneous data models [...]" [6]. (M. Schmidt); The main diference between these systems is the https://hpi.de/naumann/people/dr-fabian-panse.html (F. Panse) amount of query interfaces they ofer. MultiStores have (M.0S0c0h0-m0i0d0t3);-20304050--80505012-(0F6.7K5i-e4h1n1)6; (0F0.0P0a-0n0s0e2)-7330-6276 one single query interface whereas PolyStores incorpo© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License rate multiple interfaces (Figure 1). However, both are Attribution 4.0 International (CC BY 4.0).
platform-agnostic to platform-specific operators and op
MultiStore timized based on cost estimates. The migration of data Single is done without materialized views or permanent data Query migration but on-demand if data is needed to be shipped Interface DS1 DS2 DS3 from one store to another. The migration and transformation of the data is implemented by using a directed Heterogenous Data Stores conversion graph, which defines the transformation rules from one model to the other.
BigDAWG, a PolyStore developed at MIT and NorthPolyStore western University, is designed as a 3-layer architecture [8]. The first layer contains applications and visualizaMQuulteipryle tions whereas the second layer represents a mediation Interface DS1 DS2 DS3 layer responsible for query planning and optimization. The third layer is formed of so-called islands of information. Each island is built of a data model, a query Heterogenous Data Stores language and a set of underlying data stores.
Without a consideration of write operations or data Figure 1: Diference between Multi- and PolyStores (Based placement, the sole focus of the system is the proon: Tan et al.[6]) cessing of complex, island-overarching read operations. While querying a specified island using so-called SCOPEoperations, data shipping can be manually initiated bebuilt upon heterogeneous data stores. This distinguishes tween diferent islands using CAST-operations. However, them from other system classes such as federated systems transformations from the data model of one island to the or polylingual1 systems, which use a homogeneous selec- model of another island have to be defined manually by tion of data stores as well as single (federated) and mul- the user. Query planning and optimization in BigDAWG tiple (polyglot) query interfaces respectively [6]. Given is achieved by building a performance catalog of query that the issues addressed in our research impact both Mul- plans. In addition, She at al. introduce the concept of tiStores and PolyStores alike, we will employ the term semantic equivalence for query planning according to ’PolyStores’ to encompass both system classes through- which "Semantically equivalent queries [...] are substiout the subsequent discourse for clarity and consistency. tutable" [14].
Regarding their architecture, most PolyStores use a Polypheny was first introduced in [ 7] as a project Mediator-Wrapper Architecture [10] and can be distin- of the University of Basel and later transformed into a guish based on (1) how tightly-coupled the mediation company2. From their original vision, a highly adaptive layer is with the underlying data stores, (2) how they PolyStore, the current release3 already supports a vamodel the relationships between the diferent schemas, riety of data stores with diferent data models such as (3) how they combine data from diferent stores using dif- PostgreSQL for multimodel, MongoDB for document and ferent join algorithms, or (4) how they optimize queries Neo4j for graph data. Schema information is managed across multiple stores to leverage the stores’ strengths using name spaces, each of which has its own data model. [11, 12]. Datasets are assigned manually to one of these name spaces as well as one or several data stores. Queries can 3. State of the Art be formulated using several languages such as SQL, CQL, and Cypher. Additionally, it is possible to formulate name In the following, we want to deep dive into an exemplary space or store overarching queries for some languages selection of PolyStores to highlight how these systems (e.g., SQL). However, the processing of these queries was, work, what they ofer, and in which areas the current at least in our test of the available prototype, unstable research lacks. and the transformation between diferent data models
Apache Wayang, originally developed as Rheem [13], rudimentary. For instance, when querying data residing is a platform-agnostic data analytics framework which in a document store (e.g., MongoDB) with SQL, the data decouples the application from the underlying data store is transformed into the relational model in a way that and places itself in the middle to perform the cross- leads to a table with one column containing complete platform data processing [9]. Data processing jobs are documents. written as Wayang plans which are then mapped from
other publications.
3https://github.com/polypheny/Polypheny-DB/releases/tag/v0.9.1 (v0.9.1)
Polystore
migration Store C
Store B migration Store A migration Dataset 1 Dataset 2
Dataset 3
Use Case
QuerQyueryQuery
Query SLA
Data Placement
Store A
Dataset 1 Store C
Dataset 2 Store B
Dataset 3 ilar approach for the assignment of encryption methods to columns of relational tables.
In our context, we propose the following formulation of a mathematical binary optimization problem to compute an optimal set of dataset assignments : argmin ∑︁ ∑︁ ∑︁ ∈ ∈ ∈ (1)
Here, contains the datasets that should be assigned, is the set of available data stores and is the set of supported operators. Furthermore, are the costs derived from the PolyStore measurements (Subsection 4.2) and the weights model the distribution of operations for each dataset (Subsection 4.3). is the resulting assignment being 1 if dataset is assigned to data store and 0 otherwise.
In order to ensure that every dataset is assigned to exactly one data store, the following constraint is added to the minimization:
To be able to provide an optimized placement of datasets in data stores, a model has to be created that incorporates the characteristics of the related PolyStore and requirements defined by the intended use case. In a first attempt, the placement itself can basically be described as a binary assignment problem. In [17], Tu et al. already used a sim3. There exists a semantically equivalent sequence where diferent parts of the sequence can be performed on diferent data stores with data being shipped between these stores. 4. There exists a semantically equivalent sequence where parts of the sequence can be performed within some of the underlying data stores and the final operations can be performed within the mediation layer. SELECT a . row_num , b . col_num ,
SUM( a . value ∗ b . value ) FROM a , b WHERE a . col_num = b . row_num GROUP BY a . row_num , b . col_num ;
Choosing between these four possibilities is a key challenge in query optimization and is highly intertwined ∈∖ with the placement of datasets in data stores. To be able to Here, contains all datasets to be assigned, whereas choose the best solution, costs such as operation runtime, is the set of SLAs required for a certain dataset . memory consumption, latency, and even transformation is the set of supported data stores, is the set of and migration costs have to be considered during the stores supporting a given SLA and represents the assignment of datasets. We are currently working on assignment. The given formulation implies that the sum assessing these costs for diferent PolyStores. of assignments of to data stores not supporting a given SLA (e.g., strong consistency) is 0. Therefore, datasets cannot be assigned to these data stores.
∀ ∈ : ∀ ∈ : (3)
Information on how a dataset will be processed for a given use case is an important factor for the optimality of 4.5. Usability, Practicability and Future a data placement. The question here is not only how an Directions operation can be performed but also how often it occurs With our proposed optimization model, we present a compared to others. Therefore, it is necessary to extract ifrst solution to tackle the problem of data placement in the distribution of operations for each dataset from a PolyStores. It can be used for both, the initial placement predefined sample workload. of data by solving the optimization in advance and for
To assess a given workload while staying independent adapting the placement to a changing workload by meaof the chosen query language and its individual capaci- suring the workload during a predefined time interval ties, a unifying abstract model for queries is necessary. and adjusting the weights accordingly. Hence, we currently develop a tree model that is enriched Since the number of data stores || supported by one by optional schema information. In order to be able to PolyStore is rather small and the number of datasets || correctly combine the weights () extracted from the is unlikely to exceed a few hundred, the computational tree with the operational costs, we enable the system efort for the optimization is manageable in practice. Esto find semantically equivalent sequences (e.g., us- pecially in the case where a dataset is assigned to exactly ing pattern matching) and to replace them by a single, one store, there are only || × | | possible solutions. more complex operation. Figure 3 shows two formu- Nevertheless, there are some drawbacks, that have to lations of a matrix multiplication. Here, the sequence of be solved in future work: (1) Currently, the costs are only cross product, selection, and aggregation will be replaced defined by data store and operation. Here, (pre-)known within our model by a multiply operation. characteristics of the datasets and its attributes with re
Factoring more complex operations into the distribu- gard to certain operations, such as selectivity, have to be tion derived from the workload, will facilitate the calcula- incorporated. (2) Replication and vertical partitioning of tion of operation costs as it enables the system to replace datasets across diferent data stores might be desirable. the costs for one operation by the costs of a sequence of operations and migrations. Therefore, all ways of computing operations described in Section 4.2 are considered in the overall minimization.
recent years multiple approaches for meta-models for polyglot persistence were proposed, such as U-Schema [18], M-Schema [19], or the Canonical Models used by As motivated in Section 1, developer are confronted with [20] for data transformation and migration. It is our goal a multitude of data stores and a demand for using dif- to implement our constraint approach into a suitable ferent stores in parallel to benefit from their respective meta model to build upon already available work and enstrengths [2, 5]. PolyStores pose a possible solution for hance its capabilities to our needs. For this, a meta-model developers who don’t have the resources or knowledge should fulfill a number of criteria including: (1) Given to be well-versed with all these diferent data stores and the focus on the data stores PostgreSQL, Neo4J and Montheir quirks by managing all data stores transparently goDB, the meta-model must include the relational, the under a mediation layer [12]. However, transparency document, and the graph model. (2) For the focus on introduces a new problem that PolyStores have to deal integrity constraints as well as an eficient validation of with: What if users want guarantees (e.g., foreign key or them, the transformation between meta-model and data check constraints) but know nothing about the underly- store model should generate very "natural" data in the ing data store landscape, the capabilities of the stores, or sense that e.g. data transformed from graph to relational even the location of their data? In this case, PolyStores is similar to data that was intended and designed for the need mechanisms to either delegate these requirements relational model in mind. If graph nodes and edges were to the stores or implement missing constraints in the to be put into two simple tables (one for nodes and one mediation layer. In the following section, we will discuss for adjacency), the validation of constraints – which are challenges that arise in this context and discuss possible typically defined on single entity types – will become solutions for them. very ineficient because the corresponding tuples would have to be identified first.
Migrating data between data stores to place it where it 5.1. Constraint Modeling can be handled most eficiently is a key factor to enable For a PolyStore to delegate constraint handling or sup- PolyStores to adapt themselves to changing requirements. port store capabilities, we need a better grasp of what Ultimately, the need for migration stems from the data constraints are supported by which data stores. We focus placement problem already discussed in Section 4. In on popular data stores, such as MongoDB, Neo4J, and combination with the previously established reasons for PostgreSQL, to cover a broad selection of data models. introducing constraint handling into these systems (e.g., Especially NoSQL systems lack support for constraints transparency), one has to preserve and transform conon their data, as these systems focus more on flexible or straints in the migration process as well. A further challoosely connected data models [2]. Additionally, we have lenge with the migration process lies in how to verify that to consider support for constraints that concern multiple the transformed constraints are still semantically equivadata stores such as foreign key or check constraints that lent to the old ones. When transforming data between reference data in other stores. diferent data models while keeping the constraints intact
For this purpose, we propose a mediation layer compo- one must take the diferent semantics of the models into nent orchestrating constraints by adding support (1) for account (e.g., null values). The authors of the query lanmissing constraints on stores who lack them and (2) for guage SQL++ which is part of the MultiStore FORWARD cross-data-store constraints not achievable on a single [21] include variable semantic definitions per query to store. As these data models oftentimes were not designed bridge the diferent data model semantics. As SQL++ with full integrity control in mind in order to maximize aims to provide an SQL-like, implementation-agnostic case-specific performance benefits, such an approach experience which is detached from the actual data store, will add overhead to the whole system’s performance. To the addendum at the end of each query seems like a minimize this overhead a strong priority lies on imple- suitable solution. However, if implemented as part of a menting missing constraints by methods provided by the PolyStore mediation layer such semantics can be baked stores themselves if possible. directly into the system. This shows that a migration
To better handle the constraint management in the process with constraints needs to consider the diferent mediation layer some kind of catalog of the data residing semantics of the underlying data stores and their data in the stores is required. Meta-modeling the data is a models to ensure equivalence to work properly. From promising approach which can be used to (1) catalogue this, diferent challenges can be identified: the data in a single schema, (2) transform the data (and potentially the constraints as well) eficiently between 1. Developing an abstract language for modeling stores by avoiding direct store-to-store transformations constraints that can be integrated into the meta (3) and finally build the foundation of migrating data as model and translated to the languages of the unwell as the imposed constraints from store to store. In derlying stores (e.g., SQL check constraints). 2. Developing a mechanism to rewrite constraints afected by a data migration process so that the resulting set of constraints is semantically equivalent to the original set of constraints (i.e., the rewriting is accurate and complete).
intermediary result
over multiple data stores themselves are a hard problem as these involve intermediary results and query steps.
As seen in the two round approach illustrated in Figure 4, in order to execute the update command the mediator has to work in steps: (1) The mediator determines all records that need to be updated and calculates a table winittehr minetderiamryedrieasruyltrsesaureltsth(ednepuisceteddtouipndLatineeth2e).o(r2i)gTinhael 123 FS−RE−OLMEGCaTTt1hIeDWr,HrEAeREl∗e1Cv.1a=+n’ WBtIAr’ Se;c Dor d s record based on their IDs (see Lines 6-7). This approach 4 leads to an updated state in our PolyStore but begs the 5 −− U p d a t e e a c h r e c o r d b a s e d on i t s ID question of whether a more eficient one-round variant 6 UPDATE T1 SET A = 9 . 5 WHERE ID = 2 ; may be possible. This is especially important if we con- 7 UPDATE T1 SET A = 8 . 5 WHERE ID = 3 ; sider more advanced and complicated queries which may 8 . . . need more than two rounds to be solvable. Furthermore, there are few to no PolyStores out there, that support up- Figure 4: Example for a two-round approach for updates on date/insert queries over their heterogeneous data stores. a PolyStore (Adapted from [11])
While the previous section mostly focused on the topic of how to model constraints in a polyglot persistence environment, we have to consider the validation process 6. Conclusion of constraints, too. This mainly matters during inserting or updating data in our PolyStore and boils down to two core problems we want to focus on:
PolyStores and the open challenges within these systems 1. Finding an eficient way to update/insert data with respect to data placement and constraint manageacross multiple data stores. ment. Based on our research and the current development direction of state-of-the-art PolyStores, we identi2. Incorporating the constraint validation into a ifed adaptivity as a key factor for future research in this polyglot data update/insert process. ifeld. To ensure adaptivity, we propose research ideas in The last challenge can be further divided into: the topics of (i) data placement and workload analysis as well as (ii) data migration and constraint management. • Eficient validation of constraints involving data For data placement, we plan to incorporate a unifying distributed across diferent data stores. abstract model into the process of workload analysis. The • Consistent execution of referential actions across results of the analytical process and the characteristics of diferent data stores under reuse of existing mech- the PolyStore are then cast into an optimization model, anisms within the individual stores. that computes an assignment of datasets to data stores.
For a migration process in PolyStores we introduced
A naive validation of constraints in the mediator may the idea of an overarching constraint management sysrequire loading large amounts of data from the individual tem as well as the incorporation of a meta-model. Furdata stores. Eficient validation strategies must therefore thermore, we discussed the need for eficient update proattempt to minimize such loading with the help of indices cesses for constraint validation. (e.g., for unique constraints) and clever query generation. Both topics are important step stones on the way to
In summary, developing eficient update/insert as well a fully adaptive PolyStores which can fulfill their initial as constraint validation processes within PolyStores promise to enable users to benefit from modern data store presents considerable challenges. As we move forward, solutions without knowing every nook and cranny of the it is imperative to develop mechanisms that not only en- used technologies. sure eficient data handling but also uphold referential integrity and consistency across multiple data stores.
research questions, 2022. arXiv:2204.05779. [1] P. J. Sadalage, M. Fowler, NoSQL Distilled: A Brief [13] D. Agrawal, L. Ba, L. Berti-Equille, S. Chawla, Guide to the Emerging World of Polyglot Persis- A. Elmagarmid, H. Hammady, Y. Idris, Z. Kaoudi, tence, Pearson Education, Boston, Massachusetts, Z. Khayyat, S. Kruse, M. Ouzzani, P. Papotti, J.-A.
USA, 2012. Quiane-Ruiz, N. Tang, M. J. Zaki, Rheem: Enabling [2] F. Gessert, W. Wingerath, S. Friedrich, N. Ritter, multi-platform task execution, in: Proceedings NoSQL database systems: a survey and decision of the 2016 International Conference on Manageguidance, CSRD 32 (2017) 353–365. doi:10.1007/ ment of Data (SIGMOD), ACM, 2016, p. 2069–2072. s00450-016-0334-3. doi:10.1145/2882903.2899414. [3] M. Stonebraker, U. Çetintemel, "one size fits all": [14] Z. She, S. Ravishankar, J. Duggan, Bigdawg polyAn idea whose time has come and gone (abstract), store query optimization through semantic equivain: K. Aberer, M. J. Franklin, S. Nishio (Eds.), Pro- lences, in: IEEE High Performance Extreme Comceedings of the 21st International Conference on puting Conference (HPEC), 2016, pp. 1–6. doi:10. Data Engineering (ICDE), IEEE, 2005, pp. 2–11. 1109/HPEC.2016.7761584.
doi:10.1109/ICDE.2005.1. [15] D. Glake, M. Schmidt, F. Kiehn, F. Panse, U. Lenfers, [4] M. Stonebraker, C. Bear, U. Çetintemel, M. Cher- T. Clemen, N. Ritter, Operator placement for spationiack, T. Ge, N. Hachem, S. Harizopoulos, J. Lifter, temporal tasks, in: 2022 IEEE International ConJ. Rogers, S. B. Zdonik, One size fits all? part 2: ference on Big Data (Big Data), 2022, pp. 281–290. Benchmarking studies, in: Third Biennial Confer- doi:10.1109/BigData55660.2022.10020279. ence on Innovative Data Systems Research (CIDR), [16] Z. Kaoudi, J.-A. Quiané-Ruiz, B. Contreras-Rojas, 2007, pp. 173–184. URL: http://cidrdb.org/cidr2007/ R. Pardo-Meza, A. Troudi, S. Chawla, Ml-based papers/cidr07p20.pdf. cross-platform query optimization, in: 2020 IEEE [5] W. Hasselbring, G. Steinacker, Microservice ar- 36th International Conference on Data Engineerchitectures for scalability, agility and reliability in ing (ICDE), 2020, pp. 1489–1500. doi:10.1109/ e-commerce, in: IEEE International Conference on ICDE48307.2020.00132.
Software Architecture Workshops (ICSAW), 2017, [17] S. L. Tu, M. F. Kaashoek, S. R. Madden, N. Zeldovich, pp. 243–246. doi:10.1109/ICSAW.2017.11. Processing analytical queries over encrypted data, [6] R. Tan, R. Chirkova, V. Gadepally, T. G. Mattson, En- Proceedings of the 39th International Conference abling query processing across heterogeneous data on Very Large Data Bases (PVLDB) (2013). doi:10. models: A survey, in: IEEE Big Data, 2017, pp. 3211– 14778/2535573.2488336.
3220. doi:10.1109/BigData.2017.8258302. [18] C. J. F. Candel, D. Sevilla Ruiz, J. J. García[7] M. Vogt, A. Stiemer, H. Schuldt, Polypheny-db: To- Molina, A unified metamodel for nosql and rewards a distributed and self-adaptive polystore, in: lational databases, Information Systems 104 (2022) IEEE Big Data, 2018, pp. 3364–3373. doi:10.1109/ 101898. doi:https://doi.org/10.1016/j.is.
BigData.2018.8622353. 2021.101898. [8] J. Duggan, A. J. Elmore, M. Stonebraker, M. Bal- [19] A. Conrad, P. Utzmann, M. Klettke, U. Störl, Metaazinska, B. Howe, J. Kepner, S. Madden, D. Maier, models to support database migration between hetT. Mattson, S. Zdonik, The BigDAWG Polystore erogeneous data stores, in: Proceedings of the System, ACM SIGMOD Record 44 (2015) 11–16. 25th International Conference on Model Driven doi:10.1145/2814710.2814713. Engineering Languages and Systems (MODELS): [9] K. Beedkar, B. Contreras-Rojas, H. Gavriilidis, Companion Proceedings, ACM, 2022, p. 546–551.
Z. Kaoudi, V. Markl, R. Pardo-Meza, J.-A. Quiané- doi:10.1145/3550356.3561574. Ruiz, Apache wayang: A unified data analytics [20] T. Vanhove, M. Sebrechts, G. Van Seghbroeck, framework, ACM SIGMOD Record 52 (2023) 30–35. T. Wauters, B. Volckaert, F. De Turck, Data transfordoi:10.1145/3631504.3631510. mation as a means towards dynamic data storage [10] A. Doan, A. Halevy, Z. Ives, Principles of Data Inte- and polyglot persistence, International Journal of gration, Elsevier, Amsterdam, Netherlands, 2012. Network Management 27 (2017) e1976. doi:https: [11] F. Kiehn, M. Schmidt, D. Glake, F. Panse, //doi.org/10.1002/nem.1976.
W. Wingerath, B. Wollmer, M. Poppinga, N. Rit- [21] K. W. Ong, Y. Papakonstantinou, R. Vernoux, ter, Polyglot data management: state of the art & The SQL++ semi-structured data model and open challenges, Proc. VLDB Endow. 15 (2022) query language: A capabilities survey of sql3750–3753. URL: https://vldb2022.dbis.hamburg/. on-hadoop, nosql and newsql databases, 2014. doi:10.14778/3554821.3554891. arXiv:1405.3631. [12] D. Glake, F. Kiehn, M. Schmidt, F. Panse, N. Ritter,