Marko A. Rodriguez created TINKERPOP3-693:
---------------------------------------------
Summary: [Proposal] Local Nested Traversals Beyond the Star Graph
in OLAP
Key: TINKERPOP3-693
URL: https://issues.apache.org/jira/browse/TINKERPOP3-693
Project: TinkerPop 3
Issue Type: Brainstorming
Components: process
Reporter: Marko A. Rodriguez
Assignee: Marko A. Rodriguez
Here is a half-baked solution to the "local star graph"-problem in Gremlin OLAP.
A {{Traverser}} not only maintains a pointer to its current object, but also to
its "local traversal spawn object." For instance:
{code}
g.V.where(out('knows').has('name','bob')).name
{code}
The {{Traverser}} going into the {{where()}} step will, lets say, be at
{{v[1]}}. Thus:
{code}
Traverser.get() == v[1]
Traverser.spawn() == v[1]
Traverser.stepId() == "out('knows')"-stepId
{code}
At the next step, the {{Traverser[v[1]]}} hits up the {{out("knows")}}-step.
This will trigger a message pass. Lets say {{v[1]--knows-->v[2]}}.
{code}
Traverser.get() == v[2]
Traverser.spawn() == v[1]
Traverser.stepId() == "has('name','bob')"-stepId
{code}
At this point, the {{Traverser[v[2]]}} is shoved into {{has("name","bob")}} and
lets say that {{v[2]}} is "bob." What is the next step? There is none because
its at the end of the local traversal. So, {{TraverserExecutor}} looks up
{{step.getTraversal().getTraversalParent()}} and executes the local
{{where()}}-step with a behavior of "v[1] went into , and v[2] came out." Thus,
a "simulated local traversal" is "v[1] --> v[2]" and {{where()}}-step simply
says "ah, v[2], then let me emit v[1]". This yields a {{Traverser}} of:
{code}
Traverser.get() == v[1]
Traverser.spawn() == null
Traverser.stepId() == {{values('name')}}-stepId
{code}
The {{Traverser}} is sent back to {{v[1]}} to solve the {{values('name')}}-step
function.
This notion of a "simulated local traversal" is that the {{where()-step}} local
traversal can be "wrapped" on the fly by {{TraverserExecutor}} such that:
{code}
out('knows').has('name','bob') --> directMap(v[1],v[2])
{code}
So this is doable for a single local traversal. What about parallel local
traversals like {{and(a,b,c)}}. In this situation, {{a}}, {{b}}, and {{c}} must
all come back before {{and()}} is complete. I think it might work something
like this:
{code}
Traverser.get() == v[1]
Traverser.spawn() == v[1]
Traverser.sessionId() == uuid:123-456-789(3)
{code}
In this way, before the {{spawn}} is "released" by {{and()}}, three
uuid:123-456-789 session ids must be returned with {{Traverser.get() != null}}.
If that happens, the {{and()}} released {{v[1]}} to the next step.
Note that in this model all the state is in the {{Traverser}}. There is no step
state required. Given that {{Traversers}} are stored at the local vertex during
iterations, looking up a {{Traverser}} by {{sessionId}} can be just as easy as
looking it up by {{Traverser.get()}}. In this way, a placeholder {{Traverser}}
exists at the {{and()}}-ing vertex waiting for its {{sessionId}} to complete.
.......................... a little sketchy and involved. But I think with some
more mulling we can come up with a simple "ah, that is just a that which makes
this just that and I can delete the entire codebase because there never was a
problem to begin with. I can die yielding no intent. Finally."
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
