Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper formalizes the foundations of GraphAlg, a domain-specific language for graph algorithms, by showing its derivation from MATLANG, a language for matrix manipulation. They define GraphAlg Core, a simplified intermediate representation, as an extension of MATLANG. The paper proves that GraphAlg Core expressions can be simulated within an extension of MATLANG that supports simultaneous induction, thus providing a formal basis for the language's expressiveness.
Graph database algorithms can now be formally grounded in matrix algebra, opening the door to potential optimizations and cross-pollination of techniques.
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.