CouchDB Directed Acyclic Graph (DAG)

Question

If my structure looks like this:

[{Name: 'A', Depends: []},
{Name: 'B', Depends: ['A']},
{Name: 'C', Depends: ['A']},
{Name: 'D', Depends: ['C']},
{Name: 'E', Depends: ['D','B']}]

How would I write the map and reduce functions such that my output is:

[{Key: 'A', Value: []},
{Key: 'B', Value: ['A']},
{Key: 'C', Value: ['A']},
{Key: 'D', Value: ['A','C']}
{Key: 'E', Value: ['D','B','C','A']}]

I get that the map function needs to throw up its dependencies, but I don't know how reduce will hold on to them so that they can be applied further down the tree without throwing performance out the window and waiting for all the mappings to apply. I also can't use paths, because there is not always a unique path (for instance, is D A->C->D or A->D).

Answer 1

If it's really about javascript, then I suppose You don't have a lot to choose from.

You might want to write Your own implementation of this: http://www.electricmonk.nl/log/2008/08/07/dependency-resolving-algorithm/

For storing sets (array with only unique values) i recommend using an associative array and use its keys.

Array.map() function might be of use too.

Answer 2

You need a second or auxiliary couchdb database, let's call it "complete_dependencies". Its documents will be the calculated complete dependencies of each node. Its documents will be of the form

{Name: 'D', CompleteDepends: ['C','A']}

Also this db will have a view 'implies' showing for each element all the elements that depends on him. For the previous element it will emit:

[{Name: 'C', Implies: 'D' } , {Name: 'A', Implies: 'D' }]

You will use the Change Notifications API to actualize this db. It will process each document that is modified in the original db and calculate its complete dependencies. Note that this processing is not a view. Is a program made it your language of choice listening to the modifications api and processing each document. For each document it will do the following:

1) calculate its complete dependencies using our complete_dependencies db.

2) look in the view 'implies' which documents depend on the modified document and recalculate them. Here is one thing to take care. To use the complete_dependencies they must be correctly calculated, so before use the complete_dependencies entry of a document you must be sure that the document is not in the 'implies' list or that it has been calculated.

The important point is that none of this functions is recursive.

It will follow this:

The first document is {Name: 'A', Depends: []}. As there is no dependencies (1) it will do nothing, as the implies view is empty (2) will also do nothing.

The second one {Name: 'B', Depends: ['A']}. It will look at 'A' in the complete_dependencies db to see if it depends on something. As there is no dependencies of 'A' it will only write {Name: 'B', CompleteDepends: ['A']}. (2) will not find element that depend on 'B' so it will do nothing.

The same for {Name: 'C', Depends: ['A']} -> {Name: 'C', CompleteDepends: ['A']}.

When it reads the next document {Name: 'D', Depends: ['C']} it will find that 'C' depends on 'A' so it will write

{Name: 'D', CompleteDepends: ['C','A']}

Important: it does not have to check recursively 'A' dependencies, as it is looking to C "CompleteDependencies" and all A dependencies must be in C complete dependencies.

When it processes next document {Name: 'E', Depends: ['D','B']} it will look to 'D' and 'B' Complete dependencies and it will find that D complete depends on C and A and B only in A. {Name: 'E', CompleteDepends: ['D','B','C','A']}.

Now lets suppose it receives a new version of document 'A': {Name: 'A', Depends: ['Z']}. Now it has to

1) calculate the complete dependencies of 'A' -> {Name: 'A', CompleteDepends: ['Z']}

2) look in the view which elements depends on 'A' and recalculate its complete dependencies documents. It will recalculate the complete dependencies of B,C,D,E.

Let's examine another case. Suppose we receive a new version of document C: { Name: 'C', Depends: ['Z']}.

(1) it will generate the document {Name: 'C', CompleteDepends: ['Z']}.

Looking which elements depend on C will find D and E. Now if it first calculates E it will find that it depends on D and as D is in the C implications it will has to first recalculate D. This is the only thing that function (2) has to care.

To do this I think function "Recalculate" must have a list of "dirty" elements which include all of the 'implies' list and are being eliminated when one is calculated.