A Caltech Library Service

Polystore mathematics of relational algebra

Jananthan, Hayden and Zhou, Ziqi and Gadepally, Vijay and Hutchison, Dylan and Kim, Suna and Kepner, Jeremy (2017) Polystore mathematics of relational algebra. In: 2017 IEEE International Conference on Big Data (Big Data). IEEE , Piscataway, NJ, pp. 3180-3189. ISBN 978-1-5386-2715-0.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 those 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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2017 IEEE. This material is based in part upon work supported by the NSF under grant number DMS-1312831. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. The authors wish to acknowledge the following individuals for their contributions: Michael Stonebraker, Sam Madden, Bill Howe, David Maier, Alan Edelman, Dave Martinez, Sterling Foster, Paul Burkhardt, Victor Roytburd, Bill Arcand, Bill Bergeron, David Bestor, Chansup Byun, Mike Houle, Matt Hubbell, Mike Jones, Anna Klein, Pete Michaleas, Lauren Milechin, Julie Mullen, Andy Prout, Tony Rosa, Sid Samsi, and Chuck Yee.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20180427-135006043
Persistent URL:
Official Citation:H. Jananthan, Z. Zhou, V. Gadepally, D. Hutchison, S. Kim and J. Kepner, "Polystore mathematics of relational algebra," 2017 IEEE International Conference on Big Data (Big Data), Boston, MA, 2017, pp. 3180-3189. doi: 10.1109/BigData.2017.8258298 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:86084
Deposited By: Tony Diaz
Deposited On:27 Apr 2018 21:08
Last Modified:03 Oct 2019 19:39

Repository Staff Only: item control page