Foundations of the GraphAlg Language
This work provides a formal foundation for a graph algorithm DSL, benefiting researchers and practitioners in graph databases and query languages.
The paper presents GraphAlg, a domain-specific language for graph algorithms built on the formal MATLANG language, and proves that any GraphAlg Core expression can be simulated in an extension of for-MATLANG supporting simultaneous induction.
The GraphAlg domain-specific language for graph algorithms enables user-defined algorithms in graph databases. In this work we show how GraphAlg is built on top of the formal MATLANG language for matrix manipulation. Starting from MATLANG, we describe the extensions to MATLANG needed to derive GraphAlg Core, a simplified version of GraphAlg that is used as the internal representation in the GraphAlg compiler. Furthermore, we prove that any GraphAlg Core expression can be simulated in an extension of for-MATLANG that supports simultaneous induction.