Learning Models over Relational Data: A Brief Tutorial

Maximilian Schleich, Dan Olteanu, Mahmoud Abo Khamis, Hung Q. Ngo, XuanLong NguyenSUM 2019 · OpenReview

TL;DR

This tutorial argues for a paradigm shift in machine learning over relational databases, moving away from expensive data materialization towards a "first-principles" approach that leverages database research advancements. It highlights how exploiting the inherent structure of relational data and queries can lead to significantly more efficient and scalable learning models directly within the database system.

What Problem Does This Paper Address?

Building predictive models (like classification and regression) often relies on large datasets. When this data resides in relational databases, the traditional approach involves extracting the entire training dataset, materializing it into a separate table, and then feeding it to a machine learning library. This process is computationally expensive and time-consuming, especially for massive databases, as it discards the rich structure and semantics of the original relational data. The paper addresses the challenge of efficiently learning models directly from relational data without this costly materialization step, aiming to make machine learning more accessible and performant for data-intensive applications.

Methods

The paper categorizes approaches to learning over relational data into three main types:

  • No Integration of Databases and Machine Learning: This is the most common approach, where the data system and ML library are completely separate. The training data is materialized and exported, then imported into the ML tool.
  • Loose Integration of Databases and Machine Learning: Here, ML tasks are implemented as User-Defined Aggregate Functions (UDAFs) within the database system. This allows for a more direct interface, but requires implementing each ML task as a separate UDAF. MADlib is a prime example.
  • Tight Integration of Databases and Machine Learning: This is the focus of the paper's advocacy. It involves pushing the ML task (or parts of it) directly into the feature extraction query. This allows for a single evaluation plan that exploits database optimizations. The paper emphasizes "structure-aware" learning, which leverages:
  • Algebraic Structure: Using properties like semi-rings for efficient factorization and incremental updates.
  • Combinatorial Structure: Exploiting notions like hypertree width to bound query complexity.
  • Statistical Structure: Employing sampling techniques for large datasets.
  • Geometric Structure: Using distance measures for efficient clustering approximations.

Furthermore, the paper discusses database system considerations like code specialization, query compilation, sharing computation, and parallelization as crucial for optimizing these tightly integrated systems.

Datasets

Not discussed in the paper. The paper focuses on the general problem of learning over relational data and does not specify particular datasets used for evaluation.

Key Insights and Ideas

  • The "First-Principles" Approach: The core idea is to treat machine learning over relational data as a database problem, leveraging decades of database research for optimization, rather than treating it as a separate, disconnected task.
  • Structure is Key: The inherent structure of relational data (algebraic, combinatorial, statistical, geometric) and the feature extraction queries themselves are powerful assets that can be exploited for significant performance gains.
  • Beyond Materialization: The expensive step of materializing the entire training dataset is the primary bottleneck to overcome. Tightly integrated systems can avoid this entirely.
  • Database Optimizations for ML: Standard database optimization techniques (code specialization, query compilation, parallelization) are highly relevant and can dramatically speed up ML workloads.
  • Democratizing ML for Big Data: By making learning over large relational databases more efficient, this approach can bring advanced analytics to a wider range of applications and users without requiring massive computational resources.

Key Results

The paper doesn't present specific quantitative results from experiments but rather overviews existing research and advocates for the "structure-aware" approach. It points to research that has shown "non-trivial speedups (several orders of magnitude)" through techniques like code optimization and factorization. The key qualitative result is the demonstration that by exploiting data and query structure, machine learning tasks can be performed orders of magnitude faster and more efficiently directly within the database.

Limitations and Future Work

Limitations:

  • The tutorial acknowledges that it only covers a subset of representative contributions and does not delve into approaches using massive GPU clusters.
  • While it highlights the benefits of tight integration, it notes that some approaches still require significant implementation effort for new models or optimization methods.

Future Work:

The paper concludes with a call to arms for more research into:

  • The theoretical limits of structure-aware learning.
  • The classes of machine learning models that can best benefit from this approach.
  • Identifying and exploiting other types of structure in relational data for learning.

Summary updated

Abstract

This tutorial overviews the state of the art in learning models over relational databases and makes the case for a first-principles approach that exploits recent developments in database research. The input to learning classification and regression models is a training dataset defined by feature extraction queries over relational databases. The mainstream approach to learning over relational data is to materialize the training dataset, export it out of the database, and then learn over it using a statistical package. This approach can be expensive as it requires the materialization of the training dataset. An alternative approach is to cast the machine learning problem as a database problem by transforming the data-intensive component of the learning task into a batch of aggregates over the feature extraction query and by computing this batch directly over the input database. The tutorial highlights a variety of techniques developed by the database theory and systems communities to improve the performance of the learning task. They rely on structural properties of the relational data and of the feature extraction query, including algebraic (semi-ring), combinatorial (hypertree width), statistical (sampling), or geometric (distance) structure. They also rely on factorized computation, code specialization, query compilation, and parallelization.
BibTeX
@inproceedings{schleich2019learning,
  author = {Maximilian Schleich and Dan Olteanu and Mahmoud Abo Khamis and Hung Q. Ngo and XuanLong Nguyen},
  title = {{Learning Models over Relational Data: A Brief Tutorial}},
  booktitle = {SUM},
  year = {2019},
  url = {https://openreview.net/forum?id=EOwG3JTXNE},
}
Figure