couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Adam Wolff <awo...@gmail.com>
Subject Re: Querying by foreign keys
Date Wed, 29 Apr 2009 20:37:24 GMT
Ok, I've updated the wiki page as promised:
http://wiki.apache.org/couchdb/EntityRelationship  under "Querying by
multiple keys"

A minor correction to the preceding discussion: I think the number of
keys is 2^(n-1). Brian, in your example, you would have to emit "5" as
a key. My analysis of the three key case seems to confirm this.

Thanks again for the input,
Adam

On Sun, Apr 26, 2009 at 11:05 AM, Brian Candler <B.Candler@pobox.com> wrote:
> On Sat, Apr 25, 2009 at 03:48:02PM -0400, Paul Davis wrote:
>> I've contemplated something like this, but I'm pretty sure it breaks
>> when you start contemplating that a key may end up being [a, e] in
>> which case your querying needs to account for all possible values
>> between a and e.
>
> For a document which contains five values 1,2,3,4,5 you'd need to emit
> naively the following combinations:
>
> 12345
> 1234    *
> 1235
> 1245
> 1345
> 2345
> 123     *
> 124     *
> 125
> 134     *
> 135
> 145
> 234     *
> 235
> 245
> 345
> 12      *
> 13      *
> 14      *
> 15
> 23      *
> 24      *
> 25
> 34      *
> 35
> 45
> 1       *
> 2       *
> 3       *
> 4       *
> 5       *
>
> That's 31 keys; however you don't need to emit the keys marked * because
> they are prefixes of existing keys. That is, if you want to search for [3,4]
> then you can search for startkey=[3,4,null]&endkey=[3,4,{}] and you will hit
> the other entry for 345, which by definition includes the values 3 and 4.
>
> Hence this gets you down to 15 keys to emit, but it's still exponential:
> 2^(n-1) - 1
>
> Regards,
>
> Brian.
>

Mime
View raw message