Providing machine learning (ML) over relational data is a mainstream requirement for data analytics systems. While almost all the ML tools require the input data to be presented as a single table, many datasets are multi-table, which forces data scientists to join those tables first, leading to data redundancy and runtime waste. Recent works on "factorized" ML mitigate this issue for a few specific ML algorithms by pushing ML through joins. But their approaches require a manual rewrite of ML implementations. Such piecemeal methods create a massive development overhead when extending such ideas to other ML algorithms.

In this paper, we show that it is possible to mitigate this overhead by leveraging a popular formal algebra to represent the computations of many ML algorithms: linear algebra. We introduce a new logical data type to represent normalized data and devise a framework of algebraic rewrite rules to convert a large set of linear algebra operations over denormalized data into operations over normalized data. We show how this enables us to automatically "factorize" several popular ML algorithms, thus unifying and generalizing several prior works. We prototype our framework in the popular ML environment R and an industrial R-over-RDBMS tool. Experiments with both synthetic and real normalized data show that our framework also yields significant speed-ups, up to 36x on real data.

By integrating linear algebra with the fundamental and ubiquitous relational join operation, this work sets the stage for a holistic unification of linear and relational algebras for seamless feature engineering and learning over structured data. There is also a long-standing and yet unresolved debate in the data management community as to whether it is better to bring linear algebra to relational systems or relational algebra to linear algebra systems. While this work is largely orthogonal to this debate, we hope and believe that advancing our understanding of the fundamental interactions of these frameworks will lead to more usable and efficient advanced analytics systems.

Blog post on Morpheus