traversals

[dominictarr]

Traversing a tree is a bit more complicated than just Array.forEach. In some cases, you may want to traverse links that point in either direction, "documents links that link to X". In that case, you are dealing with a graph.

Ideally, you'd describe a traversal with some sort of canonical expression, like, "every post object reachable from X" or "all posts by user X and all approved comments"

Then, this traversal can be used to describe a dataset! two users would exchange this description (or it's hash) to indicate what dataset they are interested in, and then replicate their sets.

here a few ideas:

• procedural javascript / javascript dsl. Just pass some javascript code which you execute to produce the traversal. this will need to be sandboxed and sanitized.
• logical description of relations! see learndatalogtoday.org I think this has a lot of potential, and it more powerful than SQL.
• @mcollina's levelgraph this already has some ways to query a graph, not sure if it can do recursive queries, though. @mcollina?

Another simple approach would be to just use indexes, like, https://github.com/dominictarr/level-search or @eugeneware's github.com/eugeneware/level-queryengine

[mcollina]

@dominictarr LevelGraph do not support recursion out of the box, but it as a fairly simple structure so it can be quickly extended to add it: let me know if you want to work on it, we can discuss the easiest way/api (I plan to do it sometime in the future anyway...). As for the rest, LevelGraph allows to follow efficiently both inbound and outbound links from a node.

[dominictarr]

@mcollina what would the api look like for a recursive query? say, traverse all the modules by a given author and all the modules that they depend on.

[mcollina]

Recursive query example in joinStream

var stream = db.joinStream([{
    subject: db.v("moduleName"),
    predicate: "author",
    object: "mcollina"
  }, {
    subject: db.v("moduleName"),
    predicate: "dependsOn",
    object: db.v("dependentModule"),
    recursive: true
  }]
);

stream.on("data", function(solution) {

});

It will emit:

• { moduleName: "levelgraph", dependentModule: "levelup" }
• { moduleName: "levelgraph", dependentModule: "leveldown" }

Or we can devise a total new api, the graph model is there: let's figure out what you might need and define a cool API. As far as the API is async, the graph model is accessible in LevelGraph.

[dominictarr]

Hmm, not sure if just having a recursive property would be enough - what if the chain of relations that should recurse is multiple links long?

Like, if the query is "authors of the modules that author X uses, and the modules they use, recursively"

so, all the authors of the modules I use, then repeat the query, but substitute the author returned as X?

[dominictarr]

oh, turns out that "regular paths" is a thing http://sig.biostr.washington.edu/projects/ontviews/gleen/

as mentioned here https://github.com/mcollina/levelgraph/issues/30

[dominictarr]

a regular path for the module example might look like:

Author <-maintiainer (<- depends)*

Author (<- maintainer -> depends -> maintainer)*

<- means incoming, and -> means outgoing.

does that seem like it makes sense?

[alexindigo]

Maybe it's a separate topic, but how author is going to proof it's own validity?

[dominictarr]

@alexindigo not sure what you are meaning exactly. do you mean how do you prove the author created a given document? or how to prove that an author is who they claim?

does this make sense: https://github.com/dominictarr/cyphernet/issues/4

[alexindigo]

You're right my question fits #4 much better. Trying to follow all the conversation here, a little bit overwhelming :) I'll ask my question there and will try to formulate it in better way.

[mcollina]

@dominictarr definitely make sense, more here in than in LG, as cyphernet will be a Tree and not a graph. However your example is a Graph, as it can have loops.

I think the best way of implementing this API in LG is adding kind-of subquery support, so:

var stream = db.joinStream([{
    subject: db.v("moduleName"),
    predicate: "author",
    object: "mcollina"
  }, {
    regularPath: [{ 
      subject: db.v("moduleName"),
      predicate: "dependsOn",
      object: db.v("dependentModule")
    }, {
      // something more...
    }]
  }]
);

stream.on("data", function(solution) {

});

I'm not exactly sure how this can be coded, but it's not an issue right now.

[refset]

@dominictarr Matteo is right, and this is why cyphernet needs indexed tags (and revs) to enable graph traversal

[dominictarr]

Well, modules and deps are not directly linked. you specify modules from a range, so they are loosely coupled. hmm, you are right. a maintainer can depend on a module they wrote.

@mcollina one way to represent it might be to allow a query as a implicit relation.

[mcollina]

Yeah, I'm just saying that the "regularPath" thing might be problematic.