Green-Marl: A DSL for Easy and Efficient Graph Analysis by Sungpack Hong, Hassan Chafi, Eric Sedlar, and Kunle Olukotun.
I previously reported on the Green-Marl website/software and mentioned this paper: Green-Marl. Catching up on a severe backlog of papers during a slow summer weekend and read in Green-Marl paper:
The above mathematical descriptions imply two important assumptions that Green-Marl makes:
1. The graph is immutable and is not modified during analysis.
2. There are no aliases between graph instances nor between graph properties.
We assume an immutable graph so that we can focus on the task of graph analysis, rather than worry about orthogonal issues such as how graphs are constructed or modified. Since Green-Marl is designed to be used in re-writting only parts of the user application (Section 3.1), one can construct or modify the graph in their own preferred way (e.g. from data file, from a database, etc.) but when a Green-Marl generated implementation is handed a graph, the assumption is that the graph will not be modified while a Green-Marl procedure is analyizing it.
I can imagine assumption #1 being in place for processing a topic map but certainly not assumption #2.
But given the type of graph analysis they want to perform, the assumptions are justifiable.
Given a graph, \( G = (V;E) \), and a set of properties defined on the graph, \( \amalg = \{P_1; P_2; \ldots P_n\} \), our language is specifically designed for the following types of graph analysis:
- Computing a scalar value from \( (G,\amalg) \), e.g. the conductance of a sub-graph
- Computing a new property \( P_{n+1} \) from \( (G, \amalg ) \), e.g. the pagerank of each node of a graph
- Selecting a subgraph of interest out of the original graph \( (V^’,E^’) \subset (V,E) \), e.g. strongly connected components of a graph
What if we share the assumption:
1. The graph is immutable and is not modified during analysis.
And have a different second assumption:
There are aliases between nodes and graph properties.
We want to say:
Given a graph, \( G = (V;E) \), and a set of properties defined on the graph, \( \amalg = \{P_1; P_2; \ldots P_n\} \),
- Compute the aliases for each property defined on the graph
- Compute the aliases for each node of the graph
(My suspicion being that aliases of properties must be computed before aliases on nodes, although that would depend upon how aliases between nodes are defined.)
Where actions based on the computation of aliases for both properties and nodes are a separate step in the analysis.
(There are some other complexities that I haven’t fully teased out so suggestions/comments welcome. But then that is always the case.)