DAG on couch

[Adam Wolff <aw...@gmail.com>]

Hi everyone,
I'm just getting started with CouchDB and I'm really excited about it. I'm
working with a directed acyclic graph, and I'd like to be able to
efficiently
retrieve graph chunks with a single query.

So conceptually, my data looks like this

doc1: {content: ..., ancestor: null}
doc2: {content: ..., ancestor: "doc1"}
doc3: {content: ..., ancestor: "doc2"}
doc4: {content: ..., ancestor: "doc3"}
doc5: {content: ..., ancestor: "doc3"}


Long runs of singly linked ancestors will be common; branches (e.g. after
doc3
in the example above) will be less common but not rare.

I get how you can use couch to retrieve a primary key and foreign key at the
same time (through view collation) but I'm wondering if there's a clever way
to
do this recursively.

If I could pull depths of 5 nodes or so at a time, that'd be fine. I can
always
go back for more if I need it. I can imagine a few hacky solutions, like
retaining a list of ancestors, but that it makes it pretty much impossible
to
reorder the graph.

Is there a clever solution I'm missing?

Thanks in advance,
A

Re: DAG on couch

[Adam Wolff <aw...@gmail.com>]

Guys,This is really helpful. Thanks for the input. I hadn't seen the wiki
page. I think the thing to do is to store the path to the root, and make it
so that node positions are immutable. Deletion is implemented just by
marking a given node as deleted; move is implemented with
copy-then-mark-deleted. These operations should be rare in my app anyway.

A

On Fri, Dec 12, 2008 at 9:34 AM, Randall Leeds <ra...@gmail.com>wrote:

> > Views will never be able to make external calls durring processing.
> > That'd violate the whole 'insert fancy word' that says map output for
> > a doc can only depend on the combination of the document + function
> > source.
> >
> >
> Well. There's nothing really *stopping* you. It breaks indexing if the
> external data you consult can change, though.
>

Re: DAG on couch

[Randall Leeds <ra...@gmail.com>]

> Views will never be able to make external calls durring processing.
> That'd violate the whole 'insert fancy word' that says map output for
> a doc can only depend on the combination of the document + function
> source.
>
>
Well. There's nothing really *stopping* you. It breaks indexing if the
external data you consult can change, though.

Re: DAG on couch

[Paul Davis <pa...@gmail.com>]

Did you see the wiki page on storing hierarchical data?

http://wiki.apache.org/couchdb/How_to_store_hierarchical_data

Alot of the ideas on that page require each node to have it's entire
path to the root node which helps in all cases except when you want to
alter a node's path.

Views will never be able to make external calls durring processing.
That'd violate the whole 'insert fancy word' that says map output for
a doc can only depend on the combination of the document + function
source.

On Fri, Dec 12, 2008 at 11:16 AM, Ayende Rahien <ay...@ayende.com> wrote:
> You need a more complex view processor, I think. One that can make
> additional requests during view processing.
>
> On Fri, Dec 12, 2008 at 11:12 AM, Adam Wolff <aw...@gmail.com> wrote:
>
>> Hi everyone,
>> I'm just getting started with CouchDB and I'm really excited about it. I'm
>> working with a directed acyclic graph, and I'd like to be able to
>> efficiently
>> retrieve graph chunks with a single query.
>>
>> So conceptually, my data looks like this
>>
>> doc1: {content: ..., ancestor: null}
>> doc2: {content: ..., ancestor: "doc1"}
>> doc3: {content: ..., ancestor: "doc2"}
>> doc4: {content: ..., ancestor: "doc3"}
>> doc5: {content: ..., ancestor: "doc3"}
>>
>>
>> Long runs of singly linked ancestors will be common; branches (e.g. after
>> doc3
>> in the example above) will be less common but not rare.
>>
>> I get how you can use couch to retrieve a primary key and foreign key at
>> the
>> same time (through view collation) but I'm wondering if there's a clever
>> way
>> to
>> do this recursively.
>>
>> If I could pull depths of 5 nodes or so at a time, that'd be fine. I can
>> always
>> go back for more if I need it. I can imagine a few hacky solutions, like
>> retaining a list of ancestors, but that it makes it pretty much impossible
>> to
>> reorder the graph.
>>
>> Is there a clever solution I'm missing?
>>
>> Thanks in advance,
>> A
>>
>

Re: DAG on couch

[Ayende Rahien <ay...@ayende.com>]

You need a more complex view processor, I think. One that can make
additional requests during view processing.

On Fri, Dec 12, 2008 at 11:12 AM, Adam Wolff <aw...@gmail.com> wrote:

> Hi everyone,
> I'm just getting started with CouchDB and I'm really excited about it. I'm
> working with a directed acyclic graph, and I'd like to be able to
> efficiently
> retrieve graph chunks with a single query.
>
> So conceptually, my data looks like this
>
> doc1: {content: ..., ancestor: null}
> doc2: {content: ..., ancestor: "doc1"}
> doc3: {content: ..., ancestor: "doc2"}
> doc4: {content: ..., ancestor: "doc3"}
> doc5: {content: ..., ancestor: "doc3"}
>
>
> Long runs of singly linked ancestors will be common; branches (e.g. after
> doc3
> in the example above) will be less common but not rare.
>
> I get how you can use couch to retrieve a primary key and foreign key at
> the
> same time (through view collation) but I'm wondering if there's a clever
> way
> to
> do this recursively.
>
> If I could pull depths of 5 nodes or so at a time, that'd be fine. I can
> always
> go back for more if I need it. I can imagine a few hacky solutions, like
> retaining a list of ancestors, but that it makes it pretty much impossible
> to
> reorder the graph.
>
> Is there a clever solution I'm missing?
>
> Thanks in advance,
> A
>