BigData Applications from Graph Analytics to Machine Learning by Aggregates in Recursion

Ariyam Das, Youfu Li, Jin Wang, Mingda Li, Carlo Zaniolo

Abstract

The integration of aggregates within recursive queries has long been a challenge for declarative database languages. This paper explores how the mathematical property of Pre-mappability (PreM) enables the safe and efficient use of aggregates like min, max, and count inside recursion. By bridging the gap between high-level declarative logic and high-performance execution, this approach allows complex Big Data tasks—ranging from graph analytics to machine learning—to be expressed concisely while matching or exceeding the performance of specialized procedural engines.

Introduction

In Big Data processing, a persistent divide exists between declarative languages (such as SQL and Datalog) and procedural languages (such as Java or C++). While declarative languages offer ease of use and automatic optimization, they have historically struggled with "aggregates in recursion." This limitation often forces developers to resort to procedural User-Defined Functions (UDFs) for complex tasks like shortest-path algorithms or iterative machine learning models. However, UDFs are difficult to maintain and opaque to database optimizers. This paper presents a framework to bring these complex analytics back into the declarative fold using the principle of Pre-mappability.

The Challenge of Recursive Aggregates

The primary obstacle to using aggregates in recursion is the property of monotonicity. Standard logic programming requires that all recursive computations reach a fixed point before an aggregate (like min) can be applied. In a shortest-path problem, this would mean exploring every possible path in a graph before selecting the minimum distance—an approach that is computationally prohibitive for large-scale data.

To achieve efficiency, a system must be able to prune the search space by applying the aggregate during the recursion. However, doing so blindly can lead to incorrect results or non-terminating loops.

Pre-mappability (PreM): The Mathematical Foundation

The authors introduce Pre-mappability (PreM) as the solution to this dilemma. PreM is a mathematical property that ensures pushing an aggregate constraint inside a recursive loop does not alter the final result.

  1. Pruning and Efficiency: If a program satisfies PreM, the execution engine can discard sub-optimal intermediate results immediately. For instance, if a path is already longer than the current known minimum, it is discarded before further exploration.
  2. Formal Semantics: The paper utilizes Datalog to demonstrate that PreM-compliant programs maintain "perfect-model semantics." This provides a rigorous guarantee that the declarative code will produce predictable and mathematically sound outcomes.
  3. Verification: To assist developers, the authors provide "templatized" strategies to verify PreM. This allows data scientists to ensure their logic is sound without requiring deep expertise in formal semantics.

Declarative Expressiveness and "Syntactic Sugar"

The framework significantly simplifies the implementation of complex algorithms. A notable example is the K-Nearest Neighbors (KNN) classifier, which the authors express in just seven lines of Datalog. In contrast, equivalent procedural implementations in libraries like Scikit-learn often exceed 150 lines.

To further enhance readability, the paper introduces constructs like cMin and cMax. These are "syntactic sugar" that allow developers to project specific columns (such as a Point ID) associated with an aggregated value (such as the minimum distance). This avoids the verbose "join-back" patterns typically required in standard SQL.

Case Studies: From Graphs to Machine Learning

The paper demonstrates the versatility of the PreM framework through several classic algorithmic problems:

  • Graph Analytics: Efficiently solving shortest-path and reachability problems.
  • Dynamic Programming: The authors observe that the "optimal substructure" property in Dynamic Programming is essentially a specific instance of PreM. Consequently, Datalog can express DP problems (like the "coin change" optimization) with the same efficiency as procedural memoization.
  • Machine Learning: Beyond KNN, the framework supports iterative-convergent models such as Support Vector Machines (SVM) and Linear Regression, treating the convergence criteria as a recursive aggregate process.

Results and Performance

While the paper's primary focus is theoretical and architectural, it references implementations in systems like RaSQL and BigDatalog. These systems, built on PreM principles, have demonstrated the ability to outperform specialized graph engines like Spark’s GraphX. By maintaining a declarative approach, the applications remain system-agnostic, allowing the underlying engine to optimize for multi-core or distributed environments without code changes.

Conclusion and Future Work

The PreM framework provides a unified model for expressing graph analytics, dynamic programming, and machine learning within a single declarative environment. While it bridges a significant gap in Big Data processing, challenges remain. Currently, proving the PreM property requires some manual logical reasoning. Future research aims to automate the detection of PreM in arbitrary queries. Additionally, while the framework handles linear models well, further exploration is needed to determine how effectively it can support non-convex optimization problems common in deep learning.

Summary updated

Abstract

In the past, the semantic issues raised by the non-monotonic nature of aggregates often prevented their use in the recursive statements of logic programs and deductive databases. However, the recently introduced notion of Pre-mappability (PreM) has shown that, in key applications of interest, aggregates can be used in recursion to optimize the perfect-model semantics of aggregate-stratified programs. Therefore we can preserve the declarative formal semantics of such programs while achieving a highly efficient operational semantics that is conducive to scalable implementations on parallel and distributed platforms. In this paper, we show that with PreM, a wide spectrum of classical algorithms of practical interest, ranging from graph analytics and dynamic programming based optimization problems to data mining and machine learning applications can be concisely expressed in declarative languages by using aggregates in recursion. Our examples are also used to show that PreM can be checked using simple techniques and templatized verification strategies. A wide range of advanced BigData applications can now be expressed declaratively in logic-based languages, including Datalog, Prolog, and even SQL, while enabling their execution with superior performance and scalability.
BibTeX
@inproceedings{das2019bigdata,
  author = {Ariyam Das and Youfu Li and Jin Wang and Mingda Li and Carlo Zaniolo},
  title = {{BigData Applications from Graph Analytics to Machine Learning by Aggregates in Recursion}},
  booktitle = {ICLP Technical Communications},
  year = {2019},
  url = {https://openreview.net/forum?id=LuBm4t8Nt_R},
}
Figure