Annabelle Gillet

Éric Leclercq
email: eric.leclercq@u-bourgogne.fr

Nadine Cullot
email: nadine.cullot@u-bourgogne.fr

Marinette Savonnet
email: marinette.savonnet@u-bourgogne.fr

Empowering Big Data Analytics with Polystore and strongly typed functional queries

Keywords: Information systems → Query languages; Data structures High performance data analytics, Polystore, Query language, Tensor

Polystores are of primary importance to tackle the diversity and the volume of Big Data, as they propose to store data according to specific use cases. Nevertheless, analytics frameworks often lack a uniform interface allowing to fully access and take advantage of the various models offered by the polystore.It also should be ensured that the typing of the algebraic expressions built with data manipulation operators can be checked and that schema can be inferred before starting to execute the operators (type-safe).

Tensors are good candidates for supporting a pivot data model. They are powerful abstract mathematical objects which can embed complex relationships between entities and that are used in major analytics frameworks. However, they are far away from data models, and lack high level operators to manipulate their content, resulting in bad coding habits and less maintainability, and sometimes poor performances.

With TDM (Tensor Data Model), we propose to join the best of both worlds, to take advantage of modeling capabilities of tensors by adding schema and data manipulation operators to them. We developed an implementation in Scala using Spark, providing users with a type-safe and schema inference mechanism that guarantees the technical and functional correctness of composed expressions on tensors at compile time. We show that this extension does not induce overhead and allows to outperform Spark query optimizer using bind join.

INTRODUCTION AND MOTIVATIONS

The variety and the volume of Big Data have changed the storage needs. Rather than having one storage system to keep everything, a multitude of new specialized storage engines have emerged (e.g. NewSQL, NoSQL, Column Stores, Distributed File Systems, Graph databases), each one corresponding to a use case more or less specific. The well-known article of M. Stonebraker [START_REF] Stonebraker | one size fits all": an idea whose time has come and gone[END_REF], "one size does not fit all", explains that the full potential of data will be better exploited with a polystore architecture. A polystore refers to a system that integrates heterogeneous database engines, storage systems and multiple data manipulation or programming languages using different paradigms [START_REF] Gadepally | The BigDAWG Polystore System and Architecture[END_REF]. The use of polystore brings several advantages: it allows to organize data according to particular use cases (e.g. graph DBMS well support linked data and graph traversal or path queries); it enables parallel processing among several data store according to the specificities of each kind of system in the polystore [START_REF] Alotaibi | Towards Scalable Hybrid Stores: Constraint-Based Rewriting to the Rescue[END_REF][START_REF] Kolev | Parallel polyglot query processing on heterogeneous cloud data stores with LeanXcale[END_REF].

Researches on polystores try to overcome the limitation of traditional tools. Extract Transform Load (ETL) processes and warehousing technologies as well as in-database analysis operators are not sufficient to support complex analytics pipelines. ETL processes are expensive and time consuming tasks, and transforming multiple datasets into a single data model in a data warehouse can impact negatively performances and reduce the expressivity of the original data model. In-database analysis cannot take easily into account new algorithms, as they require a specific development for each database model in order to fit the data structure required by the algorithm [START_REF] Liu | Multimodel database management systems-a look forward[END_REF][START_REF] Lu | Multi-model databases: a new journey to handle the variety of data[END_REF]. So researches on polystores are directed towards ETL streaming systems [START_REF] Fernandez | Liquid: Unifying Nearline and Offline Big Data Integration[END_REF][START_REF] Vassiliadis | Near real time ETL[END_REF], multi-database query language [START_REF] Gadepally | The BigDAWG Polystore System and Architecture[END_REF], unification models [START_REF] Gadepally | D4M: Bringing associative arrays to database engines[END_REF], and parallel query processing as well as the integration of polystore with analysis frameworks [START_REF] Kolev | Parallel polyglot query processing on heterogeneous cloud data stores with LeanXcale[END_REF]. This article focus on the last three points.

Analytics tasks require multiple kinds of algorithms based on different theoretical foundations, such as linear algebra, statistics, graph theory. Algorithms are implemented using different computing paradigms such as GPU, map-reduce, concurrent, parallel, or functional programming, and they are used as operators over data in data analytics pipelines. With the adoption of different data models combined with data analysis frameworks and new techniques such as machine learning, we are able to extract more information from data and to have a deeper understanding of the studied phenomena.

Nevertheless, data processing pipelines are becoming complex and heterogeneity is no longer observed only at the data level but also at the analysis level [START_REF] Agrawal | Cloudy with high chance of DBMS: A 10-year prediction for Enterprise-Grade ML[END_REF]. Developing a pivot data model which can generalized polystore underlying data models and which can facilitate data transformations to feed quickly algorithms implemented with frameworks is a major challenge [START_REF] Jananthan | Polystore mathematics of relational algebra[END_REF][START_REF] Kepner | AI Data Wrangling with Associative Arrays[END_REF][START_REF] Liu | Multimodel database management systems-a look forward[END_REF].

Multiple data analysis frameworks built on different computing paradigms are available, such as Spark [START_REF] Zaharia | Spark: The Definitive Guide[END_REF] (with SparkSQL, GraphX, MLlib), Tensorflow [START_REF] Abadi | Tensorflow: A system for large-scale machine learning[END_REF], PyTorch [START_REF] Paszke | PyTorch: An imperative style, high-performance deep learning library[END_REF], Theano [START_REF] Al-Rfou | A Python framework for fast computation of mathematical expressions[END_REF], Ten-sorLy [START_REF] Kossaifi | Tensorly: Tensor learning in python[END_REF], NumPy [START_REF] Van Der Walt | The NumPy array: a structure for efficient numerical computation[END_REF]. However, frameworks often focus exclusively on applying algorithms, and not on manipulating or transforming data, even if it is a time-consuming and error-prone task. Each of these tools lacks one or several important properties, such as type-safe functions (operators) which guarantee at compile time that a composition of operations is valid (a property that is automatically lost when using dynamic typing, leading to errors during execution), or schema inference when manipulating data. With the absence of these properties, two categories of errors can arise: 1) type errors, when operators are not applied on the right attribute type and 2) functional errors, when operators are applied on the right attribute type but not on the attribute representing the desired information. The second category of errors is the hardest to detect, but also the most dangerous, because the error will be unnoticed, the computations will occur but will give an incorrect result. For example, an inversion between two columns of a dataset1 has already led to a major mistake, that has been discovered only years later, and that has resulted in the retraction of five articles and impacted the work of other researchers that were using the erroneous result in their work. This ascertainment highlights the need of checking the correctness of analysis workflows, as shown by the evolution of the data structure in Spark: from RDDs with unstructured data, to DataFrames with a columnar format, and finally to Datasets with a type-safe layer over DataFrames. Thus, if composition of operators in programs could have a mean to prevent this type of mistakes, without needing user intervention and without adding complexity to the use, data scientists could focus more on the core of the analysis rather than on controlling the result at different steps of the workflow.

In recent analytics frameworks, tensors play an important role. They are abstract and powerful mathematical objects used in multiple data analytics tools [START_REF] Sun | Beyond streams and graphs: dynamic tensor analysis[END_REF], including deep learning to deal with multi-dimensional data or data mining to analyze latent relationships using tensor decompositions [START_REF] Kolda | Tensor decompositions and applications[END_REF][START_REF] Papalexakis | Tensors for data mining and data fusion: Models, applications, and scalable algorithms[END_REF]. However, their pure mathematical definition is relatively abstract, far away from user needs. Their implementation in tools does not really suit coding standards and brings several bad habits, usually banned from good practices of software development, that reduce evolution, reuse, collaborative work, etc. In frameworks such as Tensorflow, Theano or NumPy, tensors are usually defined as multidimensional arrays; users assign an implicit meaning to dimensions' integer indexes and at best put comments in their code to remember the meaning of constructions [START_REF] Rush | Tensor Considered Harmful[END_REF]. It also may concern dimension names or dimension order before or after tensor transformations are applied. This can lead to errors which cannot be easily understood because the computation is technically correct but functionally incorrect. Moreover, tensors are disconnected from data models, data schemas and data sources, failing to take advantage of the expressiveness of data models and semantically well-defined data manipulation operators. It is necessary to use intermediate data structures to perform complex data manipulations before applying tensorial operators such as decompositions. This is even more true when handling multiple data sources, and strengthens the need of a pivot data model.

In [START_REF] Leclercq | Polystore and Tensor Data Model for Logical Data Independence and Impedance Mismatch in Big Data Analytics[END_REF] we have formally defined a semantically rich pivot data model, the Tensor Data Model (TDM), by adding schema to the tensor mathematical object. It provides users with operators that can be combined to express complex data transformations. We have showed that tensors make it possible to generalize common data models, and that virtual or materialized views can be defined among multiple data sources (polystore) using operators on tensors. In this article our contribution are the following: we propose a set of mechanisms to ensure type-safe property and schema inference. As we stated, strong static typing is of primary importance in Big Data analytics because it allows to determine errors before the execution and thus to avoid expensive buggy calculation phases which will end with errors or inconsistencies. We describe our implementation of the operators on the top of Spark that fulfill the type-safe and schema inference properties and includes a mechanism to connect to a polystore.

The article is organized as follow: section 2 is a related work on analytics frameworks and their use of tensors, including the role of pivot data model and query processing in polystores; section 3 gives an overview of the key features of TDM; section 4 describes the mechanism for type-safety and schema inference in functional queries; section 5 describes experiments on the top of Spark and shows how to perform optimisations on tensor construct queries.

RELATED WORK

This section describes three kinds of inter-related researches: i) support of tensor in analytics frameworks and linear algebra in programming languages ; ii) multidimensional arrays data models in databases, query languages and dataframes ; iii) polystores and their integration in analytics frameworks.

NamedTensor [START_REF] Rush | Tensor Considered Harmful[END_REF] is a first step to make tensors safer and usable in complex workflows. Built on Torch tensor [START_REF] Paszke | PyTorch: An imperative style, high-performance deep learning library[END_REF], it proposes to use String names for dimensions instead of Integer indexes. However, Python dynamic typing system does not guarantee safety, and naming dimensions with String does not put away the risk of a typo or the referencing to an old dimension that was removed in a code update. In [START_REF] Chen | Typesafe abstractions for tensor operations[END_REF], Chen with the Nexus2 prototype pushes the tensor safety further than NamedTensor, by providing a statically typed tensor abstraction using Scala. Classical tensor operators are defined, but from a mathematical point of view and not from a data model point of view. So the abstraction level is low. Data transformations are performed using ad-hoc program constructions and not by using well-defined data manipulation operators or a query language.

The works of Muranushi et al. [START_REF] Muranushi | Experience report: Type-checking polymorphic units for astrophysics research in Haskell[END_REF] and Griffioen [START_REF] Griffioen | Type inference for array programming with dimensioned vector spaces[END_REF] propose a typed linear algebra system, that leads to a more functional and index-free matrix and allows to infer the type of any linear algebra expression. Their implementation in Haskell can detect typing error at compile time. In [START_REF] Muranushi | Experience report: Type-checking polymorphic units for astrophysics research in Haskell[END_REF] they apply it for encoding units of measure in astrophysics data.

In the field of data models and query languages, Bauman [START_REF] Baumann | Management of multidimensional discrete data[END_REF], Libkin et al. [START_REF] Libkin | A query language for multidimensional arrays: design, implementation, and optimization techniques[END_REF] have proposed a query language for multidimensional arrays. More recently Brijder et al. [START_REF] Brijder | MATLANG: Matrix operations and their expressive power[END_REF] study the expressive power of a language for matrix manipulation including linear algebra and graph operations. Barceló et al. [6] study the expressiveness of Lara, a language and a data model built on associative array. The model generalizes standard data models and can also represent tensor but as the building block is an associative array, it forces users to decompose complex relationships into binary ones. Typed arrays are also part of the SQL standard as multi-dimensional arrays [START_REF] Mišev | SQL Support for Multidimensional Arrays[END_REF], but they are mainly designed to be used with an in-database analysis approach or with homogeneous systems, and not with machine learning frameworks and map-reduce paradigm. So, it is much an extension of SQL with new data type rather than a model which is intrinsically based on multi-dimensional structures and can benefit of theoretical results. Spark [START_REF] Zaharia | Spark: The Definitive Guide[END_REF] is a major actor in this field. Its most advanced data structure, the Dataset, provides type-safe guarantee at compile time. Unfortunately, schema transformations such as joining two Datasets do not carry on automatically the type-safe property nor automatic schema inference3 .

To integrate different systems in a polystore and to connect it with analytical tools, two approaches can be distinguished: the model approach and the language approach. The goal of the model approach [START_REF] Barceló | On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra[END_REF][START_REF] Gadepally | D4M: Bringing associative arrays to database engines[END_REF] is to build a pivot model that can support all data models of the polystore. However, this approach has often a low level of abstraction, and thus reduces the expressiveness. The language approach [START_REF] Alotaibi | Towards Scalable Hybrid Stores: Constraint-Based Rewriting to the Rescue[END_REF][START_REF] Kolev | Parallel polyglot query processing on heterogeneous cloud data stores with LeanXcale[END_REF] defines a multidatabase language to manipulate data. It can be mixed with native queries to directly access a specific storage system. However, operators that need to be applied on a set of results from different data sources have to use the common language, that is often close to the SQL standard. Some works have tried to propose an evaluation framework to measure the ability of a query processing technique over heterogeneous data models [START_REF] Tan | Enabling query processing across heterogeneous data models: A survey[END_REF], that use multiple criteria: the heterogeneity (dealing with several databases without losing expressivity), the autonomy (each store can be managed independently of the polystore system), the transparency (having an easy access to data), the flexibility (building multiple kind of workflows) and optimality (benefiting of the optimization of the stores composing the polystore).

To sum up, tensors are a powerful tool for complex analytics pipelines and for generalizing data models in a polystore architecture. Existing implementations of tensors in analytics frameworks stick to their mathematical nature and lack of operators for manipulating data, though at the center of analysis. Furthermore, the need of a type-safe property for analytics tools is essential, as shown by different works on tensors or on specific data structures. However, type-safety cannot be achieved easily in a dynamically typed language such as Python, and complex data manipulation operators that lead to schema transformation can induce a loss of the type-safe property.

TDM: Algebraic Structure and Operators

Tensors are abstract mathematical objects which can be considered according to various points of view such as family of elements, or multi-linear applications. To be closer to usual definition of data model using set theory we will retain the definition of a tensor as an element of the set of the functions from the product of 𝑁 sets

𝐼 𝑗 , 𝑗 = 1, . . . , 𝑁 to R : 𝒳 ∈ R 𝐼 1 ×𝐼 2 ו••×𝐼 𝑁 ,
where 𝑁 is the number of dimensions of the tensor or its order.

For adding the useful notion of schema to tensors we have formally defined the notion of typed associative array and typed tensor [START_REF] Leclercq | Polystore and Tensor Data Model for Logical Data Independence and Impedance Mismatch in Big Data Analytics[END_REF]. A named and typed associative array is a triple (𝑁 𝑎𝑚𝑒, A,𝑇 ) where 𝑁 𝑎𝑚𝑒 is a unique string that represents the name of a dimension, A is the associative array (i.e. a map 𝐾 → N where 𝐾 is a set of keys), and 𝑇 is the type of the associative array. The schema of a named typed associative array is 𝑁 𝑎𝑚𝑒 : 𝐾. 𝐷𝑜𝑚 𝑁 𝑎𝑚𝑒 is the domain of values taken by the keys of A, i.e., a subset of 𝐾. A typed tensor 𝒳 is a tuple (𝑁 𝑎𝑚𝑒, 𝐷, 𝑉 ,𝑇 ) where 𝑁 𝑎𝑚𝑒 is the name of the tensor, 𝐷 is a list of named typed associative arrays, i.e., one per dimension, 𝑉 is the values of the tensor and 𝑇 is the type of the tensor, i.e., the type of its values. The schema of a typed tensor is 𝑁 𝑎𝑚𝑒 (𝑆) : 𝑇 where 𝑆 is the list of schemas of its dimensions, i. e., associative arrays of 𝐷. More strictly and by analogy with the relational model, the formal schema of a tensor is the list of names of dimensions to which the name of the tensor is added. For example, the typed tensor 𝒰 ℋ𝒯 (𝑈 𝑠𝑒𝑟 : 𝑆𝑡𝑟𝑖𝑛𝑔, 𝐻𝑎𝑠ℎ𝑡𝑎𝑔 : 𝑆𝑡𝑟𝑖𝑛𝑔,𝑇𝑖𝑚𝑒 : 𝐿𝑜𝑛𝑔) : 𝐿𝑜𝑛𝑔 with the dimensions 𝑈 𝑠𝑒𝑟 , 𝐻𝑎𝑠ℎ𝑡𝑎𝑔 and 𝑇𝑖𝑚𝑒 is used to store the number of times a hashtag is used in tweets produced by a user per time slice.

With its straightforward mapping to diverse data models, TDM is a useful pivot model for polystore architectures. These mappings are presented in detail in [START_REF] Leclercq | Polystore and Tensor Data Model for Logical Data Independence and Impedance Mismatch in Big Data Analytics[END_REF]. To summarize the main ideas, we focus on the mapping from the most popular data models to TDM:

• Relational and column: The mapping from a relation 𝑅 to typed tensors produces a set of tensors 𝒳 𝑖 where the dimensions 𝐷 are the 𝑛 attributes that form together the key of 𝑅 and for the 𝑘 -𝑛 remaining attributes we create a tensor for each. The keys of each 𝐷 are formed of different values of each attribute domains. • Key-value: most of key-value stores save data as (𝑘𝑒𝑦, 𝑣𝑎𝑙𝑢𝑒) pairs in a distributed hash table. As typed tensors are described by associative arrays, set of (𝑘𝑒𝑦, 𝑣𝑎𝑙𝑢𝑒) pairs in NoSQL stores are mapped to a 1-order tensor, with the dimension storing the keys. The definition of typed tensor and tensor schema are the starting point to formally define data manipulation operators on tensors. We have specified projection, selection on the values of tensor, restriction on values of dimension, union, intersection, nesting and natural join. These operators respect the closure property thus allow to define compositions of operators as queries over multiple data sources (i.e. a polystore). By adding difference and Cartesian Product the set of operators is relationally complete [START_REF] Codd | Relational completeness of data base sublanguages[END_REF]. We invite the reader to look at [START_REF] Leclercq | Polystore and Tensor Data Model for Logical Data Independence and Impedance Mismatch in Big Data Analytics[END_REF] for a formal definition of the operators, that is based on the formalism of [START_REF] Kanellakis | Elements of relational database theory[END_REF] used to define the relational model. Our definitions are constructed with two levels:

• a description of the operator's behavior on the schema, i.e., restrictions on operand schemas and specification of the result schema; • a specification of the operator's semantics on values. Due to a lack of space we give an outlook of some operators (figure 2 andtable 1) in order to illustrate the two levels on which the operators are working on (i.e., the schema level with constraints on the associative arrays values and the value level). The selection, restriction, union and intersection work only at the value level, while the projection, nesting and natural join work at both the value and the schema level.

Theoretical Complexity

The storage of tensors depends on the nature of data, nevertheless representing and analyzing Big Data with tensor models produces sparsity. For example, in the graph theory, a graph 𝐺 = (𝑉 , 𝐸) is Compressed Sparse Row (CSR) are common data structures used to represent sparse matrices [START_REF] Cichocki | Nonnegative matrix and tensor factorizations: applications to exploratory multi-way data analysis and blind source separation[END_REF]. They can be applied directly to tensors, if we consider tensors as set of matrices [START_REF] Buluc | On the representation and multiplication of hypersparse matrices[END_REF] obtained by unfolding operations.

(𝑇 𝒳 1 ∪ 𝑇 𝒳 2 -𝜋 (𝑑 𝒳 1 𝑖 , 𝒳 3 )𝑇 𝒳 3 ) ∪ 𝜋 (𝑑 𝒳 1 𝑖 , 𝒳 1 𝜃 𝒳 2 )𝑇 𝒳 with 𝑇 𝒳 3 := 𝜎 (𝑑 𝒳 1 𝑖 = 𝑑 𝒳 2 𝑖 )(𝑇 𝒳 1 × 𝑇 𝒳 2 ) 𝑂 (2 + 𝑛𝑧 𝒳 1 + 𝑛𝑧 𝒳 2 )
𝒳 1 ∩ 𝜃 𝒳 2 intersection of two tensors having the same schema and perform the 𝜃 operation on values having the same keys

𝜋 (𝑑 𝒳 1 𝑖 , 𝒳 1 𝜃 𝒳 2 )𝑇 𝒳 3 𝑂 (2 + 𝑛𝑧 𝒳 1 + 𝑛𝑧 𝒳 2 )
𝒳 1 𝒳 2 join of two tensors having at least one dimension in common and keep the values of the first tensor

𝜋 ( 𝑗=1,2 𝑖=1,...𝑁 𝒳 𝑗 𝑑 𝒳 𝑗 𝑖 , 𝒳 1 )𝑇 𝒳 3 𝑂 ( 𝑑 ∈𝐷 𝒳 2 |𝐷𝑜𝑚 𝒳 2 𝑑 | + 𝑛𝑧 𝒳 1 )
Table 1: TDM operators with their meaning, expression in relational algebra and their complexity using a sparse representation with hashtables for values of dimensions to sparse tensors with Compressed Sparse Fiber (CSF) format [START_REF] Smith | Splatt: Efficient and parallel sparse tensor-matrix multiplication[END_REF]. CSR, CSC and CSF are effective only for some operators such as multiplication and thus are not suitable for supporting the variety of TDM operators. We will consider two different hypotheses, the first one is the storage of tensors as tuples or elements of a dataframe, the second one, more suitable for in memory storage, is the extension of Knuth structure for sparse matrices [START_REF] Knuth | The art of computer programming[END_REF] (p.302-306) to tensors using hash tables to have direct access to elements sharing the same value on a dimension. The table 1 gives, at the third column, for each operator its cost of execution as a relational algebra expression for the first hypothesis and at the last column its theoretical complexity for the second hypothesis. Notations are the followings: 𝑛𝑧 𝒳 is the number of existing values in tensor 𝒳 , 𝑑 ∈ 𝐷 𝒳 is one of the dimension of a tensor, 𝐷𝑜𝑚 𝒳 𝑑 is the domain, i.e. the set of values for dimension 𝑑 of a tensor 𝒳 , 𝜇 𝒳 𝑑,𝑐 = 𝑛𝑧 𝒳 /|𝐷𝑜𝑚 𝒳 𝑑 | is an estimation of the number of elements in a sub-tensor when a dimension 𝑑 is set to a specific value, 𝑇 𝒳 is a set of tuples in a representation of tensor using relational table or dataframe.

STRONGLY TYPED COMPOSITION OF OPERATORS AS A FUNCTIONAL QUERY LANGUAGE

This section presents the mechanisms that allow to leverage the type-safe and schema inference properties. As we put in evidence in sections 1 and 2, these properties are of primary importance for the manipulation and the transformation of data. Once established, they make it possible to build a functional query language based on the composition of TDM operators, possibly including other analysis operators. TDM is developed in Scala, as this language has facilities to establish the mechanisms needed, partially thanks to its strong statically typing system.

Type-safe and schema inference

In order to have type-safe and schema inference properties in TDM, several mechanisms are needed. In this subsection, we outline phantom types, the shapeless library and implicits, that are the three components of our seeked properties.

Phantom types are types that can never be instantiated. They are used to apply constraints over type, without the need of creating a new object. Their use helps to propagate the type-safe functionality, by allowing the compiler to use these types to check more precise constraints directly over types.

In the TDM library, tensor's dimensions are defined as phantom types, that extends TensorDimension[T] with a given type T :

object User extends TensorDimension[String] object Hashtag extends TensorDimension[String] object Time extends TensorDimension[Long]

By doing so, several properties are given to dimensions: 1) each dimension can have a meaningful name, while being of a simple type (such as String or Long); 2) each dimension is easily identifiable, because it is referenced with a type rather that just a name (e.g. a String or an object instance); 3) tensor's dimensions can be controlled more finely, by accepting only once each phantom type but multiple time the same simple type (e.g. for a tensor representing coordinates, two phantom types are used: Longitude and Latitude, each extending TensorDimension[Double]); 4) multiple tensors can share a same phantom type, and use it as a constraint to apply operators, thus enforcing the type-safe capability at the schema granularity, with the help of implicits (see below). With the shapeless library4 , some structures to manipulate objects at type level are available. It is the case for the HList (Heterogeneous List), that allows to build a list with different types, while keeping the detail of each type and not using a common supertype to work with the list.

In the TDM implementation, a HList of phantom types (e.g. User::Hashtag::Time::HNil) is used to represent the schema of a tensor, and the type of the tensor is made of a parameterized type. This sort of implementation provides us with tools and methods to interact with the schema of a tensor, that can be triggered with implicits. In Scala, implicits [START_REF] Odersky | Programming in scala[END_REF][START_REF] Oliveira | Type classes as objects and implicits[END_REF] are a mean to delegate some code logic to the compiler. When a function defines a parameter as implicit, if the user does not provide explicitly the parameter, the compiler will check in the current scope if it is possible to find a value with the corresponding type to use it for the function call.

This functionality can be pushed to be used to check advanced constraints, or to infer a result type depending on input parameters. If we want to verify that a type T is in a HList L, we can use implicits in a recursive way (figure 4). We first check if the head of L is of the same type as T, if it is the case, the implicit compiles because it found a correspondence in its scope. If the head of the list is not of the same type as T, the implicit must resolve itself the same implicit, this time called on T and on the tail of L. If no correspondence is found when reaching the end of L, the whole chain of implicits does not compile, thus invalidating the function that used the implicit at the root of the call. By composing these types of constraints, we can build more complex ones, and use them to enforce validity of operators depending on the schema.

Implicits can also be used to infer automatically the schema of the resulting tensor when applying an operator that alters the schema of the current tensor (e.g. projection, join). For this, implicits are combined with path dependent types [START_REF] Amin | Foundations of path-dependent types[END_REF], that allow to compute a type given one or multiple types in input. The implicit application is the same that for the constraint, but we add the expected output type in the implicit call, and when resolving the implicit, the output type is built. An example of this use is to remove all elements of a given type in a HList (figure 3). For an input HList L, and a type T, we can build two output types: one (Out1) as the HList containing all the elements of type T that were a part of L, and one (Out2) as the HList containing all the elements of L except those of type T. This removal can be used to apply a projection operator on a tensor, as it removes the dimension on which we want to focus on. The schema of the tensor resulting of the execution of this operator will depend of the schema of the input tensor and of the dimension on which we want to do the projection.

Towards a functional query language

Scala is a language of choice to develop TDM, because it is statically typed and allows to strongly check type constraints at compile-time (see section 4.1). Our implementation of TDM (available at https: //github.com/AnnabelleGillet/TDM) is based on Spark and uses the shapeless library that enables the development of dependent type based generic programs. Above Spark's DataFrame we add schema, data manipulation operators and tensor decompositions to implement TDM in a type-safe way. TDM implementation is user-friendly: it hides all the shapeless details from the user and detects errors at compile-time.

A TDM tensor is built in three steps: 1) dimensions are defined; 2) these dimensions are added to the tensor (and can be reused in other tensors) and 3) values are obtained by querying a data source or manually added. For example, to build the tensor 𝒰 ℋ𝒯 , its three dimensions are created as: Notice that dimensions defined in this way, on top of providing properties defined in section 4.1, are also used to help users to produce values for a dimension and to express conditions for data manipulation operators. Dimensions are then used with an object TensorBuilder, from which a tensor of type Long is instantiated:

val tensorUHT = TensorBuilder[Long]
.addDimension(User) .addDimension(Hashtag) .addDimension(Time) .build() tensorUHT.addValue(User.value("u1"), Hashtag.value("ht1"), Time.value( 1)

)(1)
Alternatively, a tensor can also be created by retrieving directly its values from a data source. In this case, users must supply:

(1) a Properties object embedding information of connection to the TensorBuilder; (2) the mappings between dimensions and the name of each attribute returned by the query and;

(3) the query to execute and the name of the attribute which contains the tensor's values.

val props = new Properties() ... val query = """SELECT user_screen_name AS user, hashtag, published_hour AS time, COUNT(*) AS value FROM tweet t INNER JOIN hashtag ht ON t.id = ht.tweet_id GROUP BY user_screen_name, hashtag, published_hour HAVING COUNT(*) > 5 """ val tensorUHT = TensorBuilder[Long](props)

.addDimension(User, "user") .addDimension(Hashtag, "hashtag") .addDimension(Time, "time") .build(query, "value")

This mechanism allows all storage systems for which a JDBC driver is available to be used as a data source. By using the Spark's data access layer, data sources without a JDBC driver can also be added easily.

TDM operators add data manipulation capabilities to tensors and infer automatically the schema of the resulting tensor, even when the operator induces a schema transformation, e.g. for the natural join. For example, using a projection on the previously defined tensor 𝒰 ℋ𝒯 for the dimension User and the value 𝑢1 will yield a new tensor ℋ𝒯 populated with the values corresponding to the dimension and the value specified:

val tensorHT = tensorUHT.projection(User)("u1")
With the naming possibilities of Scala, we can also call the projection operator as:

val tensorHT = 𝜋 (tensorUHT)(User)("u1")
Result of this operator can be shown using access to tensor values with the following expressions: tensorHT(Hashtag.value("ht1"), Time.value(1)) // Some(1.0) tensorHT(Hashtag.value("ht2"), Time.value(2)) // None Other operators can associate two tensors in various ways. For example, the union produces a new tensor with all values from both tensors, and intersection produces a new tensor with only common values between the two tensors. Both operators take a function in parameter that determines the function to apply when keys are in common between tensors. val t1 = tensor1.union(tensor2)((v1,v2) => max(v1,v2)) val t2 = tensor1.intersection(tensor2)((v1,v2) => v1 + v2)

The natural join allows to merge schema of two tensors when they have at least one dimension in common. The values kept are those of the first tensor for which the keys combination exists in the second tensor. TDM operators are implemented with strong type constraints, which can be grouped in three categories: 1) for operators that work at the tensor value level such as selection, the parameter of the condition used must match the tensor value type, 2) for operators working on dimensions that need a dimension parameter, such as the projection or the restriction. The dimension parameter used has to be a part of the schema of the tensor and 3) for binary operators such as union, intersection, natural join or difference. The schema of both tensors must match according to the operators, e.g., for the union and the intersection, the schema of tensors have to be the same and for the natural join the tensors must have at least one dimension in common.

For the internals, TDM uses Spark's DataFrame, that correspond to our first hypothesis in section 3.2, and the benefit is multiple: 1) working with a well defined and scalable structure, and 2) keeping the optimization capabilities of Spark. The DataFrame is used with n-1 columns for the dimensions' values, and the last column for the value of the tensor associated to these dimensions' values.

The type-safe guarantee is obtained at compile-time by combining shapeless and Scala's implicits, as explained in section 4.1. A compilation-error warns the user if an inconsistency is detected. The use of implicits gives also the capability to define custom compilation-error messages that fit the tensor context, in order to avoid unclear default messages. The following example shows inconsistencies detected at compile time 5 : tensorHT.addValue(Hashtag.value(1), Time.value(2))(2.0) // Wrong type of dimension's value tensorHT.addValue(Hashtag.value("ht2"))(2.0) // Wrong number of dimensions tensorHT.projection(User)("u2") // Dimension not in tensor tensorHT.union(tensorUHT) // Different schemas of tensors By using the different mechanisms (phantom types and implicits), we showed how the implementation of TDM supports type-safe and schema inference properties. The method used to build tensors by using native queries takes advantage of each database of the polystore, and thus allows to perform fine grained optimizations during the construction with specific techniques such as the bind join.

BIND JOIN OPTIMIZATION AND TDM OVERHEAD STUDY: EXPERIMENTS AND RESULTS

In this section, we present two kind of experiments: 1) to show, through a bind join, the benefit of exploiting a polystore and knowing the characteristics of data, and 2) to execute the same combination of operators with TDM and with Spark, in order to see if TDM produces some overhead compared to Spark. The experiments were performed on a Dell PowerEdge R740 server (Intel(R) Xeon(R) Silver 4210 CPU @ 2.20GHz, 20 cores, 256Go RAM).

For the first experiment, we compare a naive join against a bind join that takes advantage of some knowledge about the data. A bind join is an optimisation technique to join a smaller and a bigger sets, where the values of the smaller set are collected and directly sent to the bigger set, in order to minimize data transfers and to limit the bigger set only to values that can actually match with the smaller set. For a set of users 𝒰 , we want to get 𝒯 containing the tweets that a subset of the users have published. These data are stored in a PostgreSQL database, in a table user that have 1M elements, and in a table tweet that have 50M elements. To see the evolution of the execution time, the subsets of user start from 0 to 500 000 elements, with steps of 50 000, and the average execution time of five repetitions is kept.

First, we perform a naive Spark join between 𝒯 and each subset of 𝒰 (the blue line on figure 5). Then, as we know that 𝒰 is smaller than 𝒯 , we perform a bind join: we only retrieve the values of 𝒯 that match those of the subset of 𝒰 , rather than trying to join all the values. This time, we obtain the orange line in figure 5. The execution time is significantly better than the naive join when the subset of 𝒰 is smaller than 350 000 values. Second, we can push further the exploitation of the knowledge of the data: we know that only one user can have published a tweet, so for two distinct subsets of 𝒰 , two distinct subsets of 𝒯 will be matched. We can split the subset of 𝒰 in several slice, run each small bind join against 𝒯 in parallel, and then perform an union on all the results and still get the expected result. The green and red lines of figure 5 represent this parallel bind join, with slices of 10 000 and 25 000 values respectively. As we can see, the execution time of our optimization technique is significantly better than the naive and the bind join. At the end of the curve, the bind join with slices of 10 000 values takes a little more time than the one with 25 000 values: it can be explained by the multiplication of the unions that have to be made between each slice, and by the number of queries that have to be sent to the database, when the processor does not have enough cores to handle all the queries at the same time.

With this experiment, we show that a good knowledge of the data and of the behaviour of the database can significantly improve performances compared to a uniform and naive approach.

For the second experiment, we compare an execution with Spark and with TDM. Spark is a well-known and powerful analytics engine, so, an important objective of developing TDM as a layer over Spark is to keep performance equivalent to Spark while taking advantage of the capabilities of TDM. To estimate the eventual overhead induced by TDM, we run an experiment in Spark and compare the result with the same experiment using TDM. The different phases are: 1) building a tensor 𝒰 with the users and the number of tweets published by each user as tensor's values, 2) building a tensor 𝒰 ℋ𝒯 with the number of hashtags published by users for 1h time slices, 3) performing a selection on tensor 𝒰 to keep only users who have published at least 100 tweets, 4) joining 𝒰 and 𝒰 ℋ𝒯 to keep the values of 𝒰 ℋ𝒯 only for active users. We vary the size of tensor 𝒰 from 0 to 1M elements by steps of 100 000.

This experiment is carried out in two cases: first by forcing the computation at each operation, and second by forcing the execution only at the last operation, in order to witness the optimization of Spark. The executions are repeated five times, and the average time is measured. A real anonymized data set is available on the github of the experiment 6 . As we can see in figure 6 the execution with TDM does not induce overhead compared to Spark, and the optimization capabilities of Spark are preserved (bottom of fig. 6).

CONCLUSION

TDM is a tensor based pivot data model that bridges the gap among data sources and analytics frameworks with a unification of the different theoretical foundations of data models (graph, matrix, relation). The type-safe property and the closure of the operators set are major prerequisites for Big Data analytics. Our library demonstrates that tensors can be manipulated in a safer way, and are well-suited for a data centric use with well-defined data manipulation operators.

The type-safe and schema inference properties of TDM library are implemented by constraints carried out by parameterized types and Scala's implicits. They allow to detect schema inconsistencies and incompatibilities of parameters in operator expressions at compile time. TDM operators allow to build complex expressions over tensors, which can be used as a traditional query language. TDM goes beyond Spark DataFrame by providing a layer that keeps the performance of Spark and does not induce overhead, as shown by the comparative experiment between Spark and TDM.

We now focus on developing advanced tensorial operators and algorithms such as hierarchical tensor decomposition, as well as integrating data manipulation operators available for Spark DataFrames that we can use on tensors. We are also studying the capabilities of TDM to take advantage of each database of a polystore depending on the operation optimizations allowed by its model. We plan to develop a mechanism that could optimize the functional queries, by using a context provided by an expert user in order to guide the evaluation depending on the database, as we showed in the particular case of the bind join.

  and schema inference API Analytics algorithms and operators composition for TDM

Figure 1 :

 1 Figure 1: Role of TDM in a polystore system

  𝜋 [𝑈 ,'u1'] 𝒰 ℋ𝒯 𝜌 [𝑈 ='u1'∧𝑇 ≥t1∧𝑇 ≤t2] 𝒰 ℋ𝒯

Figure 2 :

 2 Figure 2: Projection, selection and restriction operators applied to the tensor 𝒰 ℋ𝒯 for the values of u1 (other values are not shown in the example)

Figure 3 :

 3 Figure 3: Example: removing all elements of type T in a HList L with the help of implicits and path dependent type

Figure 4 :

 4 Figure 4: Steps to check if a type T is in a HList L with the help of implicits

object

  User extends TensorDimension[String] object Hashtag extends TensorDimension[String] object Time extends TensorDimension[Long]

  val t3 = tensor1.naturalJoin(tensor3)

Figure 5 :

 5 Figure 5: Execution time for a join, a bind join and a parallel bind join, with slices of 10 000 and 25 000 values

Figure 6 :

 6 Figure 6: Execution time with TDM and Spark

  These representations have been extended 𝒳 projection on some specific value of a dimension, reduce the order by removing the dimension on which the projection is applied𝜋 ({𝑑 1 , ..., 𝑑 𝑁 } -𝑑, 𝒳 )𝜎 (𝑑 = 𝑐)𝑇 𝒳 𝑂 (1 + 𝜇 𝑑,𝑐 )𝒳 1 ∪ 𝜃 𝒳 2 union of two tensors having the same schema and perform the 𝜃 operation on values having the same keys

	Operator Signification	Equivalent Relation Algebra Expression	Complexity
	𝜋 [𝑒𝑥𝑝𝑟 ] 𝜎 [𝑒𝑥𝑝𝑟 ] 𝒳 selection of values, can reduce the set	𝜎 (𝑒𝑥𝑝𝑟 )𝑇 𝒳	𝑂 (1 + 𝑛𝑧 𝒳 )
	of values in dimensions
	𝜌 [𝑒𝑥𝑝𝑟 ] 𝒳 reduce a dimension to only values	𝜎 (𝑒𝑥𝑝𝑟 )𝑇 𝒳	𝑂 (1 + 𝑛𝑧 𝒳 )
	that match the expression, can also
	reduce the values in other dimensions

https://people.ligo-wa.caltech.edu/~michael.landry/calibration/S5/getsignright.pdf

https://github.com/ctongfei/nexus

See for example https://medium.com/@pahomov.egor/spark-datasets-are-not-astype-safe-as-you-think-56a8a9ea0fc3 AN OVERVIEW OF TDM DATA MODELOur aim is to define a pivot model for polystores (figure1) to benefit from all the different underlying data models, without loosing in expressivity. High level of expressivity is achieved by using tensors, as they have facilities to map to various models, and by allowing native queries for accessing the stores. Moreover, native queries can take advantage of the capabilities of each database individually. The execution of analytics algorithms is then facilitated, as their input data structures are obtained and transformed from TDM and not from each data model underneath. Moreover, the tensorial nature of TDM allows also naturally the use of rich tensorial operators, such as decompositions[START_REF] Rabanser | Introduction to tensor decompositions and their applications in machine learning[END_REF].

https://github.com/milessabin/shapeless

See also https://github.com/AnnabelleGillet/TDM/tree/master/src/test/scala/tdm/core for examples of detected inconsistencies

https://github.com/AnnabelleGillet/TDM-experiments/tree/master/SparkCompari son

ACKNOWLEDGMENT. This work is supported by ISITE-BFC (ANR-15-IDEX-0003) coordinated by G. Brachotte, CIMEOS Laboratory (EA 4177), University of Burgundy.