Mailing-List: contact user-help@couchdb.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@couchdb.apache.org
Received-SPF: pass (nike.apache.org: domain of awolff@gmail.com designates
 74.125.92.27 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=mime-version:in-reply-to:references:date:message-id:subject:from:to
         :cc:content-type:content-transfer-encoding;
        b=Ya7qhc8uQt8k5ZQSZyNRy86+Jl7c+alDhXuo6kCUmPgUkVCMMBFJtZqQ9qSdE+l3JJ
         mrtKBTeZJuOrLVWNT6hQ1PUSkG13CCUVhrvMsplDHLl0rChzwCIMrrMuKqrgJcdGMi2U
         Ar5KtHomOKjh7fWaGM29jQVhQmmMNxC/QiiUc=
MIME-Version: 1.0
In-Reply-To: <20090426180534.GA6571@uk.tiscali.com>
References: <e2111bbb0904251248o28a4d495xebffb07cec8ebaf3@mail.gmail.com>
	 <20090426180534.GA6571@uk.tiscali.com>
Date: Wed, 29 Apr 2009 13:37:24 -0700
Message-ID: <e8d26ac40904291337m68399496i6577a0b3f69c6b1c@mail.gmail.com>
Subject: Re: Querying by foreign keys
From: Adam Wolff <awolff@gmail.com>
To: user@couchdb.apache.org
Cc: Paul Davis <paul.joseph.davis@gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

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 =A0 =A0*
> 1235
> 1245
> 1345
> 2345
> 123 =A0 =A0 *
> 124 =A0 =A0 *
> 125
> 134 =A0 =A0 *
> 135
> 145
> 234 =A0 =A0 *
> 235
> 245
> 345
> 12 =A0 =A0 =A0*
> 13 =A0 =A0 =A0*
> 14 =A0 =A0 =A0*
> 15
> 23 =A0 =A0 =A0*
> 24 =A0 =A0 =A0*
> 25
> 34 =A0 =A0 =A0*
> 35
> 45
> 1 =A0 =A0 =A0 *
> 2 =A0 =A0 =A0 *
> 3 =A0 =A0 =A0 *
> 4 =A0 =A0 =A0 *
> 5 =A0 =A0 =A0 *
>
> 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=3D[3,4,null]&endkey=3D[3,4,{}] and you w=
ill 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.
>