← Back to branch summary

~ubuntu-branches/ubuntu/maverick/evolution-data-server/maverick-proposed

« back to all changes in this revision

Viewing changes to libdb/docs/ref/am/join.html

  • Committer: Bazaar Package Importer
  • Author(s): Didier Roche
  • Date: 2010-05-17 17:02:06 UTC
  • mfrom: (1.1.79 upstream) (1.6.12 experimental)
  • Revision ID: james.westby@ubuntu.com-20100517170206-4ufr52vwrhh26yh0
Tags: 2.30.1-1ubuntu1
https://launchpad.net/bugs/42199
https://launchpad.net/bugs/229669
https://launchpad.net/bugs/173703
https://launchpad.net/bugs/360344
https://launchpad.net/bugs/508494
* Merge from debian experimental. Remaining change:
  (LP: #42199, #229669, #173703, #360344, #508494)
  + debian/control:
    - add Vcs-Bzr tag
    - don't use libgnome
    - Use Breaks instead of Conflicts against evolution 2.25 and earlier.
  + debian/evolution-data-server.install,
    debian/patches/45_libcamel_providers_version.patch:
    - use the upstream versioning, not a Debian-specific one 
  + debian/libedata-book1.2-dev.install, debian/libebackend-1.2-dev.install,
    debian/libcamel1.2-dev.install, debian/libedataserverui1.2-dev.install:
    - install html documentation
  + debian/rules:
    - don't build documentation it's shipped with the tarball

Show diffs side-by-side

added added

removed removed

Lines of Context:
libdb/docs/ref/am/join.html
1
 
<!--$Id$-->
2
 
<!--Copyright 1997-2002 by Sleepycat Software, Inc.-->
3
 
<!--All rights reserved.-->
4
 
<!--See the file LICENSE for redistribution information.-->
5
 
<html>
6
 
<head>
7
 
<title>Berkeley DB Reference Guide: Equality Join</title>
8
 
<meta name="description" content="Berkeley DB: An embedded database programmatic toolkit.">
9
 
<meta name="keywords" content="embedded,database,programmatic,toolkit,b+tree,btree,hash,hashing,transaction,transactions,locking,logging,access method,access methods,java,C,C++">
10
 
</head>
11
 
<body bgcolor=white>
12
 
<a name="2"><!--meow--></a><a name="3"><!--meow--></a><a name="4"><!--meow--></a>
13
 
<table width="100%"><tr valign=top>
14
 
<td><h3><dl><dt>Berkeley DB Reference Guide:<dd>Access Methods</dl></h3></td>
15
 
<td align=right><a href="../../ref/am/curdup.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../../reftoc.html"><img src="../../images/ref.gif" alt="Ref"></a><a href="../../ref/am/count.html"><img src="../../images/next.gif" alt="Next"></a>
16
 
</td></tr></table>
17
 
<p>
18
 
<h1 align=center>Equality Join</h1>
19
 
<p>Berkeley DB supports "equality" (also known as "natural"), joins on secondary
20
 
indices.  An equality join is a method of retrieving data from a primary
21
 
database using criteria stored in a set of secondary indices.  It
22
 
requires the data be organized as a primary database which contains the
23
 
primary key and primary data field, and a set of secondary indices.
24
 
Each of the secondary indices is indexed by a different secondary key,
25
 
and, for each key in a secondary index, there is a set of duplicate data
26
 
items that match the primary keys in the primary database.
27
 
<p>For example, let's assume the need for an application that will return
28
 
the names of stores in which one can buy fruit of a given color.  We
29
 
would first construct a primary database that lists types of fruit as
30
 
the key item, and the store where you can buy them as the data item:
31
 
<p><blockquote><p><table border=1>
32
 
<tr><th>Primary key:</th><th>Primary data:</th></tr>
33
 
<tr>    <td align=left>apple</td>    <td align=left>Convenience Store</td>    </tr>
34
 
<tr>    <td align=left>blueberry</td>    <td align=left>Farmer's Market</td>    </tr>
35
 
<tr>    <td align=left>peach</td>    <td align=left>Shopway</td>    </tr>
36
 
<tr>    <td align=left>pear</td>    <td align=left>Farmer's Market</td>    </tr>
37
 
<tr>    <td align=left>raspberry</td>    <td align=left>Shopway</td>    </tr>
38
 
<tr>    <td align=left>strawberry</td>    <td align=left>Farmer's Market</td>    </tr>
39
 
</table></blockquote>
40
 
<p>We would then create a secondary index with the key <b>color</b>, and,
41
 
as the data items, the names of fruits of different colors.
42
 
<p><blockquote><p><table border=1>
43
 
<tr><th>Secondary key:</th><th>Secondary data:</th></tr>
44
 
<tr>    <td align=left>blue</td>    <td align=left>blueberry</td>    </tr>
45
 
<tr>    <td align=left>red</td>    <td align=left>apple</td>    </tr>
46
 
<tr>    <td align=left>red</td>    <td align=left>raspberry</td>    </tr>
47
 
<tr>    <td align=left>red</td>    <td align=left>strawberry</td>    </tr>
48
 
<tr>    <td align=left>yellow</td>    <td align=left>peach</td>    </tr>
49
 
<tr>    <td align=left>yellow</td>    <td align=left>pear</td>    </tr>
50
 
</table></blockquote>
51
 
<p>This secondary index would allow an application to look up a color, and
52
 
then use the data items to look up the stores where the colored fruit
53
 
could be purchased.  For example, by first looking up <b>blue</b>,
54
 
the data item <b>blueberry</b> could be used as the lookup key in the
55
 
primary database, returning <b>Farmer's Market</b>.
56
 
<p>Your data must be organized in the following manner in order to use the
57
 
<a href="../../api_c/db_join.html">DB-&gt;join</a> method:
58
 
<p><ol>
59
 
<p><li>The actual data should be stored in the database represented by the
60
 
<a href="../../api_c/db_class.html">DB</a> object used to invoke this function.  Generally, this
61
 
<a href="../../api_c/db_class.html">DB</a> object is called the <i>primary</i>.
62
 
<p><li>Secondary indices should be stored in separate databases, whose keys
63
 
are the values of the secondary indices and whose data items are the
64
 
primary keys corresponding to the records having the designated
65
 
secondary key value.  It is acceptable (and expected) that there may be
66
 
duplicate entries in the secondary indices.
67
 
<p>These duplicate entries should be sorted for performance reasons, although
68
 
it is not required.  For more information see the <a href="../../api_c/db_set_flags.html#DB_DUPSORT">DB_DUPSORT</a> flag
69
 
to the <a href="../../api_c/db_set_flags.html">DB-&gt;set_flags</a> method.
70
 
</ol>
71
 
<p>What the <a href="../../api_c/db_join.html">DB-&gt;join</a> method does is review a list of secondary keys, and,
72
 
when it finds a data item that appears as a data item for all of the
73
 
secondary keys, it uses that data items as a lookup into the primary
74
 
database, and returns the associated data item.
75
 
<p>If there were a another secondary index that had as its key the
76
 
<b>cost</b> of the fruit, a similar lookup could be done on stores
77
 
where inexpensive fruit could be purchased:
78
 
<p><blockquote><p><table border=1>
79
 
<tr><th>Secondary key:</th><th>Secondary data:</th></tr>
80
 
<tr>    <td align=left>expensive</td>    <td align=left>blueberry</td>    </tr>
81
 
<tr>    <td align=left>expensive</td>    <td align=left>peach</td>    </tr>
82
 
<tr>    <td align=left>expensive</td>    <td align=left>pear</td>    </tr>
83
 
<tr>    <td align=left>expensive</td>    <td align=left>strawberry</td>    </tr>
84
 
<tr>    <td align=left>inexpensive</td>    <td align=left>apple</td>    </tr>
85
 
<tr>    <td align=left>inexpensive</td>    <td align=left>pear</td>    </tr>
86
 
<tr>    <td align=left>inexpensive</td>    <td align=left>raspberry</td>    </tr>
87
 
</table></blockquote>
88
 
<p>The <a href="../../api_c/db_join.html">DB-&gt;join</a> method provides equality join functionality.  While not
89
 
strictly cursor functionality, in that it is not a method off a cursor
90
 
handle, it is more closely related to the cursor operations than to the
91
 
standard <a href="../../api_c/db_class.html">DB</a> operations.
92
 
<p>It is also possible to do lookups based on multiple criteria in a single
93
 
operation.  For example, it is possible to look up fruits that are both
94
 
red and expensive in a single operation.  If the same fruit appeared as
95
 
a data item in both the color and expense indices, then that fruit name
96
 
would be used as the key for retrieval from the primary index, and would
97
 
then return the store where expensive, red fruit could be purchased.
98
 
<h3>Example</h3>
99
 
<p>Consider the following three databases:
100
 
<p><dl compact>
101
 
<p><dt>personnel<dd><p><ul type=disc>
102
 
<li>key = SSN
103
 
<li>data = record containing name, address, phone number, job title
104
 
</ul>
105
 
<p><dt>lastname<dd><p><ul type=disc>
106
 
<li>key = lastname
107
 
<li>data = SSN
108
 
</ul>
109
 
<p><dt>jobs<dd><p><ul type=disc>
110
 
<li>key = job title
111
 
<li>data = SSN
112
 
</ul>
113
 
</dl>
114
 
<p>Consider the following query:
115
 
<p><blockquote><pre>Return the personnel records of all people named smith with the job
116
 
title manager.</pre></blockquote>
117
 
<p>This query finds are all the records in the primary database (personnel)
118
 
for whom the criteria <b>lastname=smith and job title=manager</b> is
119
 
true.
120
 
<p>Assume that all databases have been properly opened and have the
121
 
handles:  pers_db, name_db, job_db.  We also assume that we have an
122
 
active transaction to which the handle txn refers.
123
 
<p><blockquote><pre>DBC *name_curs, *job_curs, *join_curs;
124
 
DBC *carray[3];
125
 
DBT key, data;
126
 
int ret, tret;
127
 
<p>
128
 
name_curs = NULL;
129
 
job_curs = NULL;
130
 
memset(&key, 0, sizeof(key));
131
 
memset(&data, 0, sizeof(data));
132
 
<p>
133
 
if ((ret =
134
 
    name_db-&gt;cursor(name_db, txn, &name_curs, 0)) != 0)
135
 
        goto err;
136
 
key.data = "smith";
137
 
key.size = sizeof("smith");
138
 
if ((ret =
139
 
    name_curs-&gt;c_get(name_curs, &key, &data, DB_SET)) != 0)
140
 
        goto err;
141
 
<p>
142
 
if ((ret = job_db-&gt;cursor(job_db, txn, &job_curs, 0)) != 0)
143
 
        goto err;
144
 
key.data = "manager";
145
 
key.size = sizeof("manager");
146
 
if ((ret =
147
 
    job_curs-&gt;c_get(job_curs, &key, &data, DB_SET)) != 0)
148
 
        goto err;
149
 
<p>
150
 
carray[0] = name_curs;
151
 
carray[1] = job_curs;
152
 
carray[2] = NULL;
153
 
<p>
154
 
if ((ret =
155
 
    pers_db-&gt;join(pers_db, carray, &join_curs, 0)) != 0)
156
 
        goto err;
157
 
while ((ret =
158
 
    join_curs-&gt;c_get(join_curs, &key, &data, 0)) == 0) {
159
 
        /* Process record returned in key/data. */
160
 
}
161
 
<p>
162
 
/*
163
 
 * If we exited the loop because we ran out of records,
164
 
 * then it has completed successfully.
165
 
 */
166
 
if (ret == DB_NOTFOUND)
167
 
        ret = 0;
168
 
<p>
169
 
err:
170
 
if (join_curs != NULL &&
171
 
    (tret = join_curs-&gt;c_close(join_curs)) != 0 && ret == 0)
172
 
        ret = tret;
173
 
if (name_curs != NULL &&
174
 
    (tret = name_curs-&gt;c_close(name_curs)) != 0 && ret == 0)
175
 
        ret = tret;
176
 
if (job_curs != NULL &&
177
 
    (tret = job_curs-&gt;c_close(job_curs)) != 0 && ret == 0)
178
 
        ret = tret;
179
 
<p>
180
 
return (ret);
181
 
</pre></blockquote>
182
 
<p>The name cursor is positioned at the beginning of the duplicate list
183
 
for <b>smith</b> and the job cursor is placed at the beginning of
184
 
the duplicate list for <b>manager</b>.  The join cursor is returned
185
 
from the join method.  This code then loops over the join cursor getting
186
 
the personnel records of each one until there are no more.
187
 
<table width="100%"><tr><td><br></td><td align=right><a href="../../ref/am/curdup.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../../reftoc.html"><img src="../../images/ref.gif" alt="Ref"></a><a href="../../ref/am/count.html"><img src="../../images/next.gif" alt="Next"></a>
188
 
</td></tr></table>
189
 
<p><font size=1><a href="http://www.sleepycat.com">Copyright Sleepycat Software</a></font>
190
 
</body>
191
 
</html>