Polystore Mathematics of Relational Algebra

Abstract

Financial transactions, internet search, and data analysis are all placing increasing demands on databases. SQL, NoSQL, and NewSQL databases have been developed to meet these demands and each offers unique benefits. SQL, NoSQL, and NewSQL databases also rely on different underlying mathematical models. Polystores seek to provide a mechanism to allow applications to transparently achieve the benefits of diverse databases while insulating applications from the details of these databases. Integrating the underlying mathematics of these diverse databases can be an important enabler for polystores as it enables effective reasoning across different databases. Associative arrays provide a common approach for the mathematics of polystores by encompassing the mathematics found in different databases: sets (SQL), graphs (NoSQL), and matrices (NewSQL). Prior work presented the SQL relational model in terms of associative arrays and identified key mathematical properties that are preserved within SQL. This work provides the rigorous mathematical definitions, lemmas, and theorems underlying these properties. Specifically, SQL Relational Algebra deals primarily with relations - multisets of tuples - and operations on and between these relations. These relations can be modeled as associative arrays by treating tuples as non-zero rows in an array. Operations in relational algebra are built as compositions of standard operations on associative arrays which mirror their matrix counterparts. These constructions provide insight into how relational algebra can be handled via array operations. As an example application, the composition of two projection operations is shown to also be a projection, and the projection of a union is shown to be equal to the union of the projections.

10 pages, 2 figures, accepted to Big Data 2017 2nd International Workshop on Methods to Manage Heterogeneous Big Data and Polystore Databases

References in corpus (8)

• The BigDAWG Polystore System and Architecture
• LaraDB: A Minimalist Kernel for Linear and Relational Algebra Computation
• D4M 2.0 Schema: A General Purpose High Performance Schema for the Accumulo Database
• Version 0.1 of the BigDAWG Polystore System
• Julia Implementation of the Dynamic Distributed Dimensional Data Model
• Constructing Adjacency Arrays from Incidence Arrays
• D4M 3.0: Extended Database and Language Capabilities
• BigDAWG Polystore Release and Demonstration

Cited by in corpus (8)

• Sparse Deep Neural Network Exact Solutions
• Streaming 1.9 Billion Hypersparse Network Updates per Second with D4M
• Mathematics of Digital Hyperspace
• A Billion Updates per Second Using 30,000 Hierarchical In-Memory D4M Databases
• AI Data Wrangling with Associative Arrays
• TabulaROSA: Tabular Operating System Architecture for Massively Parallel Heterogeneous Compute Engines
• A Formal Category Theoretical Framework for Multi-model Data Transformations
• An Algebraic Approach for High-level Text Analytics