[Book Idea] Graph Computing Theory

[Marko Rodriguez]

Hello,

These days, I’m reading “Introduction to Topology” by Bert Mendelson (https://www.amazon.com/Introduction-Topology-Third-Dover-Mathematics/dp/0486663523). This book is especially pleasing because he writes very clearly/mathematically about topology/spaces using solely the constructs of set theory (i.e. objects, sets, functions, relations, categories). There is a subset of Dover Mathematics books that are of this form. I call them “contextualized set theory” books. Such books are just “one abstraction level” above set theory. They constrain set theory in some way in order to create a universe of discourse, and then they proceed to deduce within that universe. For instance: group theory, graph theory, field theory, …

I believe that it would serve the #graphdb community well to set-theorize graph computing. The theory of graph computing would generalize graph theory because it would be about not only the structure of graphs (i.e. vertices and edges), but also about it’s processes (i.e. traversers and traversals).

What are the axioms of graph computing theory?

* What is a traverser exactly?

* What is a traversal exactly?

* How are traversals and traversers related?

* How are traversals/traversers and graphs related?

Over the years, I’ve discussed traversals/traversers as graphs themselves and thus, within the language of graph theory.

http://arxiv.org/abs/0803.4355

https://arxiv.org/abs/0704.3395

http://arxiv.org/abs/0802.3492

http://arxiv.org/abs/1508.03843

https://www.datastax.com/dev/blog/a-gremlin-implementation-of-the-gremlin-traversal-machine

In these articles, both the structure and process of graphs are simply graphs! However, it may prove useful to think about not only processes as functions (typical) but then also, structure as function (atypical). In this way, a categorical isomorphism can be made between relations and functions as it relates to the constraints of the domain of graph computing theory, where both structure and process are different facets of the same underlying phenomena.

During such this exploration, it will be proved, one way or another, what are the absolutely necessary fundamental constructs of a graph traversal engine. This will have echoing effects on the design and development of TinkerPop4.

* What is a graph traversal engine?

- How does it interact with the graph?

- How do traversers relate to both the traversal and the graph?

- Are traversals something ‘real’ or just a type of traverser?

* Can we think of the traverser as threaded?

- In TinkerPop3, we currently think of the traversals as threaded.

- Such a shift would elegantly “massively” parallelize graph processing.

* Can we completely remove state from steps?

- dedup(), range(), group(), etc. still maintain state.

- What are the ramification of completely stateless steps?

* Can we serialize/freeze traversals in mid-computation?

- If all state was completely within traversers, then yes!

- Your traversers would be a complete description of the state of computation.

- If traversals are just types of traversers then you can borrow from swarm theory and collective intelligence.

* What are the fundamental operations from which all other operations are simply a composition?

- It has been proved that the truly fundamental step is the flatMap().

- What is the non-lambda set of flatMap()s that can be composed to form every other “expressive-step.”

- I have proved the limits for Turing Completeness: http://arxiv.org/abs/1508.03843 (section 6)

* What is the ultimate nature of a traverser?

- Can we map from particle physics — spin, mass, charge, charm, … ?

- Can traversers interact with one another directly? (not just via a barrier in a step)

- Can traversers be entangled?

- Can we come up with a "traverser physics”?

* What are property graphs?

* What are properties really?

* What are labeled relations?

Thus, during my sabbatical starting at the end of this year, I plan to focus on writing a book of this form. I had originally planned on a “science-fiction graph theory”-book in a vein similar to Tales from the TinkerPop (https://www.datastax.com/dev/blog/tales-from-the-tinkerpop). However, I believe that would be too “creatively stressing” and perhaps of less theoretical and applied use than a formalization of graph computing theory in LaTeX. Ultimately, I want to come back from sabbatical with a deeper insight into our field for the next development phase of TinkerPop — TinkerPop4: Rise of Enki.

Thank you for your time,

Marko.

http://markorodriguez.com