Homomorphism Calculus for User-Defined Aggregations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915454376738816 |
|---|---|
| author | Wang, Ziteng Fang, Ruijie Zheng, Linus Tang, Dixin Dillig, Isil |
| author_facet | Wang, Ziteng Fang, Ruijie Zheng, Linus Tang, Dixin Dillig, Isil |
| contents | Data processing frameworks like Apache Spark and Flink provide built-in support for user-defined aggregation functions (UDAFs), enabling the integration of domain-specific logic. However, for these frameworks to support \emph{efficient} UDAF execution, the function needs to satisfy a \emph{homomorphism property}, which ensures that partial results from independent computations can be merged correctly. Motivated by this problem, this paper introduces a novel \emph{homomorphism calculus} that can both verify and refute whether a UDAF is a dataframe homomorphism. If so, our calculus also enables the construction of a corresponding merge operator which can be used for incremental computation and parallel execution. We have implemented an algorithm based on our proposed calculus and evaluate it on real-world UDAFs, demonstrating that our approach significantly outperforms two leading synthesizers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_15109 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Homomorphism Calculus for User-Defined Aggregations Wang, Ziteng Fang, Ruijie Zheng, Linus Tang, Dixin Dillig, Isil Programming Languages D.3.0; F.3.1 Data processing frameworks like Apache Spark and Flink provide built-in support for user-defined aggregation functions (UDAFs), enabling the integration of domain-specific logic. However, for these frameworks to support \emph{efficient} UDAF execution, the function needs to satisfy a \emph{homomorphism property}, which ensures that partial results from independent computations can be merged correctly. Motivated by this problem, this paper introduces a novel \emph{homomorphism calculus} that can both verify and refute whether a UDAF is a dataframe homomorphism. If so, our calculus also enables the construction of a corresponding merge operator which can be used for incremental computation and parallel execution. We have implemented an algorithm based on our proposed calculus and evaluate it on real-world UDAFs, demonstrating that our approach significantly outperforms two leading synthesizers. |
| title | Homomorphism Calculus for User-Defined Aggregations |
| topic | Programming Languages D.3.0; F.3.1 |
| url | https://arxiv.org/abs/2508.15109 |