/setpacking where{
pop
currentpacking
true setpacking
}if
/grops 120 dict dup begin
/SC 32 def
/A/show load def
/B{0 SC 3 -1 roll widthshow}bind def
/C{0 exch ashow}bind def
/D{0 exch 0 SC 5 2 roll awidthshow}bind def
/E{0 rmoveto show}bind def
/F{0 rmoveto 0 SC 3 -1 roll widthshow}bind def
/G{0 rmoveto 0 exch ashow}bind def
/H{0 rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
/I{0 exch rmoveto show}bind def
/J{0 exch rmoveto 0 SC 3 -1 roll widthshow}bind def
/K{0 exch rmoveto 0 exch ashow}bind def
/L{0 exch rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
/M{rmoveto show}bind def
/N{rmoveto 0 SC 3 -1 roll widthshow}bind def
/O{rmoveto 0 exch ashow}bind def
/P{rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
/Q{moveto show}bind def
/R{moveto 0 SC 3 -1 roll widthshow}bind def
/S{moveto 0 exch ashow}bind def
/T{moveto 0 exch 0 SC 5 2 roll awidthshow}bind def
/SF{
findfont exch
[exch dup 0 exch 0 exch neg 0 0]makefont
dup setfont
[exch/setfont cvx]cvx bind def
}bind def
/MF{
findfont
[5 2 roll
0 3 1 roll
neg 0 0]makefont
dup setfont
[exch/setfont cvx]cvx bind def
}bind def
/level0 0 def
/RES 0 def
/PL 0 def
/LS 0 def
/MANUAL{
statusdict begin/manualfeed true store end
}bind def
/PLG{
gsave newpath clippath pathbbox grestore
exch pop add exch pop
}bind def
/BP{
/level0 save def
1 setlinecap
1 setlinejoin
72 RES div dup scale
LS{
90 rotate
}{
0 PL translate
}ifelse
1 -1 scale
}bind def
/EP{
level0 restore
showpage
}bind def
/DA{
newpath arcn stroke
}bind def
/SN{
transform
.25 sub exch .25 sub exch
round .25 add exch round .25 add exch
itransform
}bind def
/DL{
SN
moveto
SN
lineto stroke
}bind def
/DC{
newpath 0 360 arc closepath
}bind def
/TM matrix def
/DE{
TM currentmatrix pop
translate scale newpath 0 0 .5 0 360 arc closepath
TM setmatrix
}bind def
/RC/rcurveto load def
/RL/rlineto load def
/ST/stroke load def
/MT/moveto load def
/CL/closepath load def
/FL{
currentgray exch setgray fill setgray
}bind def
/BL/fill load def
/LW/setlinewidth load def
/RE{
findfont
dup maxlength 1 index/FontName known not{1 add}if dict begin
{
1 index/FID ne{def}{pop pop}ifelse
}forall
/Encoding exch def
dup/FontName exch def
currentdict end definefont pop
}bind def
/DEFS 0 def
/EBEGIN{
moveto
DEFS begin
}bind def
/EEND/end load def
/CNT 0 def
/level1 0 def
/PBEGIN{
/level1 save def
translate
div 3 1 roll div exch scale
neg exch neg exch translate
0 setgray
0 setlinecap
1 setlinewidth
0 setlinejoin
10 setmiterlimit
[]0 setdash
/setstrokeadjust where{
pop
false setstrokeadjust
}if
/setoverprint where{
pop
false setoverprint
}if
newpath
/CNT countdictstack def
userdict begin
/showpage{}def
}bind def
/PEND{
clear
countdictstack CNT sub{end}repeat
level1 restore
}bind def
end def
/setpacking where{
pop
setpacking
}if
grops begin/DEFS 1 dict def DEFS begin/u{.001 mul}bind def end/RES 72
def/PL 792 def/LS false def/ENC0[/asciicircum/asciitilde/Scaron/Zcaron
/scaron/zcaron/Ydieresis/trademark/quotesingle/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/space/exclam/quotedbl/numbersign/dollar/percent
/ampersand/quoteright/parenleft/parenright/asterisk/plus/comma/hyphen
/period/slash/zero/one/two/three/four/five/six/seven/eight/nine/colon
/semicolon/less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N/O
/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright/circumflex
/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y
/z/braceleft/bar/braceright/tilde/.notdef/quotesinglbase/guillemotleft
/guillemotright/bullet/florin/fraction/perthousand/dagger/daggerdbl
/endash/emdash/ff/fi/fl/ffi/ffl/dotlessi/dotlessj/grave/hungarumlaut
/dotaccent/breve/caron/ring/ogonek/quotedblleft/quotedblright/oe/lslash
/quotedblbase/OE/Lslash/.notdef/exclamdown/cent/sterling/currency/yen
/brokenbar/section/dieresis/copyright/ordfeminine/guilsinglleft
/logicalnot/minus/registered/macron/degree/plusminus/twosuperior
/threesuperior/acute/mu/paragraph/periodcentered/cedilla/onesuperior
/ordmasculine/guilsinglright/onequarter/onehalf/threequarters
/questiondown/Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE
/Ccedilla/Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex
/Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis
/multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute/Thorn
/germandbls/agrave/aacute/acircumflex/atilde/adieresis/aring/ae/ccedilla
/egrave/eacute/ecircumflex/edieresis/igrave/iacute/icircumflex/idieresis
/eth/ntilde/ograve/oacute/ocircumflex/otilde/odieresis/divide/oslash
/ugrave/uacute/ucircumflex/udieresis/yacute/thorn/ydieresis]def
/Courier@0 ENC0/Courier RE/Times-Italic@0 ENC0/Times-Italic RE
/Times-Roman@0 ENC0/Times-Roman RE/Times-Bold@0 ENC0/Times-Bold RE
BP
/F0 14/Times-Bold@0 SF(Berk)275.358 100.8 Q(eley DB)-.14 E/F1 12
/Times-Roman@0 SF(Michael A. Olson)270.372 129.6 Q -.3(Ke)283.182 144 S
(ith Bostic).3 E(Mar)279.15 158.4 Q(go Seltzer)-.216 E/F2 12
/Times-Italic@0 SF(Sleepycat Softwar)255.492 174.24 Q .24 -.12(e, I)
-.444 H(nc.).12 E/F3 12/Times-Bold@0 SF(Abstract)290.874 210.24 Q/F4 10
/Times-Roman@0 SF(Berk)79.2 226.44 Q(ele)-.1 E 2.925(yD)-.15 G 2.925(Bi)
-2.925 G 2.924(sa)-2.925 G 2.924(nO)-2.924 G .424
(pen Source embedded database system with a number of k)-2.924 F .724
-.15(ey a)-.1 H(dv).15 E .424(antages o)-.25 F -.15(ve)-.15 G 2.924(rc)
.15 G .424(omparable sys-)-2.924 F 3.102(tems. It)79.2 238.44 R .602(is simple to use, supports concurrent access by multiple users, and pro)
3.102 F .602(vides industrial-strength transaction)-.15 F 1.555
(support, including survi)79.2 250.44 R 1.555
(ving system and disk crashes.)-.25 F 1.554
(This paper describes the design and technical features of)6.555 F(Berk)
79.2 262.44 Q(ele)-.1 E 2.5(yD)-.15 G(B, the distrib)-2.5 E
(ution, and its license.)-.2 E F3 3(1. Intr)79.2 286.44 R(oduction)-.216
E F4 .691(The Berk)79.2 302.64 R(ele)-.1 E 3.191(yD)-.15 G .691
(atabase \(Berk)-3.191 F(ele)-.1 E 3.191(yD)-.15 G .692
(B\) is an embedded)-3.191 F .253
(database system that can be used in applications requir)79.2 314.64 R
(-)-.2 E 1.636(ing high-performance concurrent storage and retrie)79.2
326.64 R -.25(va)-.25 G(l).25 E 2.619(of k)79.2 338.64 R -.15(ey)-.1 G
(/v).15 E 2.619(alue pairs.)-.25 F 2.619(The softw)7.619 F 2.619
(are is distrib)-.1 F 2.618(uted as a)-.2 F .057
(library that can be link)79.2 350.64 R .058
(ed directly into an application.)-.1 F(It)5.058 E(pro)79.2 362.64 Q
1.454(vides a v)-.15 F 1.453(ariety of programmatic interf)-.25 F 1.453
(aces, includ-)-.1 F .237
(ing callable APIs for C, C++, Perl, Tcl and Ja)79.2 374.64 R -.25(va)
-.2 G 5.237(.U).25 G(sers)-5.237 E .327(may do)79.2 386.64 R .327
(wnload Berk)-.25 F(ele)-.1 E 2.827(yD)-.15 G 2.827(Bf)-2.827 G .326
(rom Sleep)-2.827 F .326(ycat Softw)-.1 F(are')-.1 E(s)-.55 E -.8(We)
79.2 398.64 S 2.5(bs).8 G(ite, at)-2.5 E/F5 10/Times-Italic@0 SF(www)2.5
E(.sleepycat.com)-.74 E F4(.)A(Sleep)79.2 414.84 Q 1.33(ycat distrib)-.1
F 1.33(utes Berk)-.2 F(ele)-.1 E 3.83(yD)-.15 G 3.83(Ba)-3.83 G 3.83(sa)
-3.83 G 3.83(nO)-3.83 G 1.33(pen Source)-3.83 F 3.3(product. The)79.2
426.84 R(compan)3.3 E 3.3(yc)-.15 G .8(ollects license fees for certain)
-3.3 F(uses of the softw)79.2 438.84 Q
(are and sells support and services.)-.1 E F3 3(1.1. History)79.2 468.84
R F4(Berk)79.2 485.04 Q(ele)-.1 E 3.057(yD)-.15 G 3.057(Bb)-3.057 G
-2.25 -.15(eg a)-3.057 H 3.058(na).15 G 3.058(san)-3.058 G 1.058 -.25
(ew i)-3.058 H .558(mplementation of a hash).25 F .843
(access method to replace both)79.2 497.04 R/F6 10/Courier@0 SF(hsearch)
3.342 E F4 .842(and the v)3.342 F(ari-)-.25 E(ous)79.2 509.04 Q F6(dbm)
5.466 E F4 2.967(implementations \()5.466 F F6(dbm)A F4 2.967(from A)
5.467 F(T&T)-1.11 E(,)-.74 E F6(ndbm)5.467 E F4 1.334(from Berk)79.2
521.04 R(ele)-.1 E 2.634 -.65(y, a)-.15 H(nd).65 E F6(gdbm)3.834 E F4
1.334(from the GNU project\).)3.834 F(In)6.333 E .367
(1990 Seltzer and Y)79.2 533.04 R .368
(igit produced a package called Hash)-.55 F(to do this [Selt91].)79.2
545.04 Q 3.106(The \214rst general release of Berk)79.2 561.24 R(ele)-.1
E 5.606(yD)-.15 G 3.106(B, in 1991,)-5.606 F 3.038(included some interf)
79.2 573.24 R 3.039(ace changes and a ne)-.1 F 5.539(wB)-.25 G(+tree)
-5.539 E .887(access method.)79.2 585.24 R .886
(At roughly the same time, Seltzer and)5.887 F 1.201(Olson de)79.2
597.24 R -.15(ve)-.25 G 1.202
(loped a prototype transaction system based).15 F 3.356(on Berk)79.2
609.24 R(ele)-.1 E 5.856(yD)-.15 G 3.356(B, called LIBTP [Selt92], b)
-5.856 F 3.355(ut ne)-.2 F -.15(ve)-.25 G(r).15 E(released the code.)
79.2 621.24 Q .653(The 4.4BSD UNIX release included Berk)79.2 637.44 R
(ele)-.1 E 3.153(yD)-.15 G 3.153(B1)-3.153 G(.85)-3.153 E .602(in 1992.)
79.2 649.44 R .601(Seltzer and Bostic maintained the code in the)5.601 F
1.545(early 1990s in Berk)79.2 661.44 R(ele)-.1 E 4.046(ya)-.15 G 1.546
(nd in Massachusetts.)-4.046 F(Man)6.546 E(y)-.15 E
(users adopted the code during this period.)79.2 673.44 Q .432
(By mid-1996, users w)79.2 689.64 R .431
(anted commercial support for the)-.1 F(softw)79.2 701.64 Q 7.033
(are. In)-.1 F 4.533(response, Bostic and Seltzer formed)7.033 F(Sleep)
79.2 713.64 Q 10.128(ycat Softw)-.1 F 12.628(are. The)-.1 F(compan)
12.627 E 15.127(ye)-.15 G(nhances,)-15.127 E(distrib)323.2 286.44 Q
1.623(utes, and supports Berk)-.2 F(ele)-.1 E 4.123(yD)-.15 G 4.124(Ba)
-4.123 G 1.624(nd supporting)-4.124 F(softw)323.2 298.44 Q 2.2
(are and documentation.)-.1 F(Sleep)7.2 E 2.2(ycat released v)-.1 F(er)
-.15 E(-)-.2 E 1.677(sion 2.1 of Berk)323.2 310.44 R(ele)-.1 E 4.177(yD)
-.15 G 4.178(Bi)-4.177 G 4.178(nm)-4.178 G 1.678(id-1997 with important)
-4.178 F(ne)323.2 322.44 Q 2.56(wf)-.25 G .06
(eatures, including support for concurrent access to)-2.56 F 4.176
(databases. The)323.2 334.44 R(compan)4.176 E 4.177(ym)-.15 G(ak)-4.177
E 1.677(es about three commer)-.1 F(-)-.2 E .958(cial releases a year)
323.2 346.44 R 3.458(,a)-.4 G .957(nd most recently shipped v)-3.458 F
(ersion)-.15 E(2.8.)323.2 358.44 Q F3 3(1.2. Ov)323.2 388.44 R(er)-.12 E
(view of Berk)-.12 E(eley DB)-.12 E F4 3.094(The C interf)323.2 404.64 R
3.094(aces in Berk)-.1 F(ele)-.1 E 5.594(yD)-.15 G 5.595(Bp)-5.594 G
(ermit)-5.595 E F6(dbm)5.595 E F4(-style)A 4.586
(record management for databases, with signi\214cant)323.2 416.64 R -.15
(ex)323.2 428.64 S 1.273(tensions to handle duplicate data items ele).15
F -.05(ga)-.15 G(ntly).05 E 3.773(,t)-.65 G(o)-3.773 E 2.427
(deal with concurrent access, and to pro)323.2 440.64 R 2.427
(vide transac-)-.15 F .71
(tional support so that multiple changes can be simulta-)323.2 452.64 R
1.273(neously committed \(so that the)323.2 464.64 R 3.773(ya)-.15 G
1.273(re made permanent\))-3.773 F 1.848
(or rolled back \(so that the database is restored to its)323.2 476.64 R
(state at the be)323.2 488.64 Q(ginning of the transaction\).)-.15 E
1.034(C++ and Ja)323.2 504.84 R 1.534 -.25(va i)-.2 H(nterf).25 E 1.033
(aces pro)-.1 F 1.033(vide a small set of classes)-.15 F 1.961
(for operating on a database.)323.2 516.84 R 1.961
(The main class in both)6.961 F .587(cases is called)323.2 528.84 R F6
(Db)3.086 E F4 3.086(,a)C .586(nd pro)-3.086 F .586
(vides methods that encapsu-)-.15 F 1.128(late the)323.2 540.84 R F6
(dbm)3.628 E F4 1.129(-style interf)B 1.129(aces that the C interf)-.1 F
1.129(aces pro-)-.1 F(vide.)323.2 552.84 Q 2.565(Tcl and Perl interf)
323.2 569.04 R 2.564(aces allo)-.1 F 5.064(wd)-.25 G -2.15 -.25(ev e)
-5.064 H 2.564(lopers w).25 F 2.564(orking in)-.1 F 1.716
(those languages to use Berk)323.2 581.04 R(ele)-.1 E 4.216(yD)-.15 G
4.216(Bi)-4.216 G 4.217(nt)-4.216 G 1.717(heir applica-)-4.217 F 3.419
(tions. Bindings)323.2 593.04 R .919
(for both languages are included in the)3.419 F(distrib)323.2 605.04 Q
(ution.)-.2 E(De)323.2 621.24 Q -.15(ve)-.25 G 1.069
(lopers may compile their applications and link in).15 F(Berk)323.2
633.24 Q(ele)-.1 E 2.5(yD)-.15 G 2.5(Bs)-2.5 G(tatically or dynamically)
-2.5 E(.)-.65 E F3 3(1.3. Ho)323.2 663.24 R 3(wB)-.12 G(erk)-3 E
(eley DB is used)-.12 E F4 .655(The Berk)323.2 679.44 R(ele)-.1 E 3.155
(yD)-.15 G 3.154(Bl)-3.155 G .654(ibrary supports concurrent access to)
-3.154 F 5.115(databases. It)323.2 691.44 R 2.616(can be link)5.115 F
2.616(ed into standalone applica-)-.1 F 1.487
(tions, into a collection of cooperating applications, or)323.2 703.44 R
4.21(into serv)323.2 715.44 R 4.21
(ers that handle requests and do database)-.15 F EP
BP
/F0 10/Times-Roman@0 SF(operations on behalf of clients.)79.2 84 Q .858
(Compared to using a standalone database management)79.2 100.2 R .846
(system, Berk)79.2 112.2 R(ele)-.1 E 3.346(yD)-.15 G 3.346(Bi)-3.346 G
3.346(se)-3.346 G .846(asy to understand and simple)-3.346 F 3.826
(to use.)79.2 124.2 R 3.826(The softw)8.826 F 3.826
(are stores and retrie)-.1 F -.15(ve)-.25 G 6.325(sr).15 G(ecords,)
-6.325 E 2.77(which consist of k)79.2 136.2 R -.15(ey)-.1 G(/v).15 E
2.77(alue pairs.)-.25 F -2.15 -.25(Ke y)7.77 H 5.27(sa).25 G 2.77
(re used to)-5.27 F .698(locate items and can be an)79.2 148.2 R 3.198
(yd)-.15 G .698(ata type or structure sup-)-3.198 F
(ported by the programming language.)79.2 160.2 Q .813
(The programmer can pro)79.2 176.4 R .813(vide the functions that Berk)
-.15 F(e-)-.1 E(le)79.2 188.4 Q 3.264(yD)-.15 G 3.264(Bu)-3.264 G .763
(ses to operate on k)-3.264 F -.15(ey)-.1 G 3.263(s. F).15 F .763(or e)
-.15 F .763(xample, B+trees)-.15 F 1.72
(can use a custom comparison function, and the Hash)79.2 200.4 R .519
(access method can use a custom hash function.)79.2 212.4 R(Berk)5.518 E
(e-)-.1 E(le)79.2 224.4 Q 5.222(yD)-.15 G 5.222(Bu)-5.222 G 2.722
(ses def)-5.222 F 2.723(ault functions if none are supplied.)-.1 F .873
(Otherwise, Berk)79.2 236.4 R(ele)-.1 E 3.373(yD)-.15 G 3.373(Bd)-3.373
G .873(oes not e)-3.373 F .873(xamine or interpret)-.15 F .934(either k)
79.2 248.4 R -.15(ey)-.1 G 3.434(so).15 G 3.434(rv)-3.434 G .934
(alues in an)-3.684 F 3.434(yw)-.15 G(ay)-3.534 E 5.934(.V)-.65 G .934
(alues may be arbi-)-7.044 F(trarily long.)79.2 260.4 Q .69
(It is also important to understand what Berk)79.2 276.6 R(ele)-.1 E
3.19(yD)-.15 G 3.19(Bi)-3.19 G(s)-3.19 E 4.365(not. It)79.2 288.6 R
1.865(is not a database serv)4.365 F 1.866(er that handles netw)-.15 F
(ork)-.1 E 2.797(requests. It)79.2 300.6 R .297
(is not an SQL engine that e)2.797 F -.15(xe)-.15 G .296(cutes queries.)
.15 F 1.547(It is not a relational or object-oriented database man-)79.2
312.6 R(agement system.)79.2 324.6 Q 1.101(It is possible to b)79.2
340.8 R 1.101(uild an)-.2 F 3.601(yo)-.15 G 3.601(ft)-3.601 G 1.101
(hose on top of Berk)-3.601 F(ele)-.1 E(y)-.15 E 2.116(DB, b)79.2 352.8
R 2.116(ut the package, as distrib)-.2 F 2.117(uted, is an embedded)-.2
F 1.444(database engine.)79.2 364.8 R 1.444
(It has been designed to be portable,)6.444 F(small, f)79.2 376.8 Q
(ast, and reliable.)-.1 E/F1 12/Times-Bold@0 SF 3(1.4. A)79.2 406.8 R
(pplications that use Berk)-.3 E(eley DB)-.12 E F0(Berk)79.2 423 Q(ele)
-.1 E 4.248(yD)-.15 G 4.248(Bi)-4.248 G 4.249(se)-4.248 G 1.749
(mbedded in a v)-4.249 F 1.749(ariety of proprietary)-.25 F 3.84
(and Open Source softw)79.2 435 R 3.84(are packages.)-.1 F 3.84
(This section)8.84 F(highlights a fe)79.2 447 Q 2.5(wo)-.25 G 2.5(ft)
-2.5 G(he products that use it.)-2.5 E 1.467(Directory serv)79.2 463.2 R
1.467(ers, which do data storage and retrie)-.15 F -.25(va)-.25 G(l).25
E 2.823(using the Local Directory Access Protocol \(LD)79.2 475.2 R
(AP\),)-.4 E(pro)79.2 487.2 Q .956
(vide naming and directory lookup service on local-)-.15 F 2.837
(area netw)79.2 499.2 R 5.337(orks. This)-.1 F 2.837
(service is, essentially)5.337 F 5.336(,d)-.65 G(atabase)-5.336 E .039
(query and update, b)79.2 511.2 R .039
(ut uses a simple protocol rather than)-.2 F 2.202(SQL or ODBC.)79.2
523.2 R(Berk)7.201 E(ele)-.1 E 4.701(yD)-.15 G 4.701(Bi)-4.701 G 4.701
(st)-4.701 G 2.201(he embedded data)-4.701 F 1.288
(manager in the majority of deplo)79.2 535.2 R 1.289(yed directory serv)
-.1 F(ers)-.15 E(today)79.2 547.2 Q 4.855(,i)-.65 G 2.355(ncluding LD)
-4.855 F 2.355(AP serv)-.4 F 2.355(ers from Netscape, Mes-)-.15 F
(sageDirect \(formerly Isode\), and others.)79.2 559.2 Q(Berk)79.2 575.4
Q(ele)-.1 E 4.385(yD)-.15 G 4.385(Bi)-4.385 G 4.385(sa)-4.385 G 1.886
(lso embedded in a lar)-4.385 F 1.886(ge number of)-.18 F 5.302
(mail serv)79.2 587.4 R 7.802(ers. Intermail,)-.15 F 5.302(from Softw)
7.802 F 5.302(are.com, uses)-.1 F(Berk)79.2 599.4 Q(ele)-.1 E 4.613(yD)
-.15 G 4.613(Ba)-4.613 G 4.613(sam)-4.613 G 2.114
(essage store and as the backing)-4.613 F 3.597
(store for its directory serv)79.2 611.4 R(er)-.15 E 8.597(.T)-.55 G
3.597(he sendmail serv)-8.597 F(er)-.15 E 1.175
(\(including both the commercial Sendmail Pro of)79.2 623.4 R(fering)
-.25 E 3.283(from Sendmail, Inc. and the v)79.2 635.4 R 3.283
(ersion distrib)-.15 F 3.282(uted by)-.2 F(sendmail.or)79.2 647.4 Q
2.304(g\) uses Berk)-.18 F(ele)-.1 E 4.804(yD)-.15 G 4.804(Bt)-4.804 G
4.804(os)-4.804 G 2.305(tore aliases and)-4.804 F 9.01
(other information.)79.2 659.4 R(Similarly)14.01 E 11.51(,P)-.65 G 9.01
(ost\214x \(formerly)-11.51 F 3.465(VMailer\) uses Berk)79.2 671.4 R
(ele)-.1 E 5.965(yD)-.15 G 5.965(Bt)-5.965 G 5.965(os)-5.965 G 3.465
(tore administrati)-5.965 F -.15(ve)-.25 G(information.)79.2 683.4 Q
.134(In addition, Berk)79.2 699.6 R(ele)-.1 E 2.634(yD)-.15 G 2.633(Bi)
-2.634 G 2.633(se)-2.633 G .133(mbedded in a wide v)-2.633 F(ariety)-.25
E 4.994(of other softw)79.2 711.6 R 4.994(are products.)-.1 F 4.994
(Example applications)9.994 F .373
(include managing access control lists, storing user k)323.2 84 R -.15
(ey)-.1 G(s).15 E 2.75(in a public-k)323.2 96 R 3.05 -.15(ey i)-.1 H
2.75(nfrastructure, recording machine-to-).15 F(netw)323.2 108 Q .519
(ork-address mappings in address serv)-.1 F .518(ers, and stor)-.15 F(-)
-.2 E .411(ing con\214guration and de)323.2 120 R .412
(vice information in video post-)-.25 F(production softw)323.2 132 Q
(are.)-.1 E(Finally)323.2 148.2 Q 4.978(,B)-.65 G(erk)-4.978 E(ele)-.1 E
4.978(yD)-.15 G 4.978(Bi)-4.978 G 4.978(sap)-4.978 G 2.478(art of man)
-4.978 F 4.977(yo)-.15 G 2.477(ther Open)-4.977 F .005(Source softw)
323.2 160.2 R .005(are packages a)-.1 F -.25(va)-.2 G .006
(ilable on the Internet.).25 F -.15(Fo)5.006 G(r).15 E -.15(ex)323.2
172.2 S .604(ample, the softw).15 F .604
(are is embedded in the Apache W)-.1 F(eb)-.8 E(serv)323.2 184.2 Q
(er and the Gnome desktop.)-.15 E F1 3(2. Access)323.2 214.2 R(Methods)3
E F0 .828(In database terminology)323.2 230.4 R 3.329(,a)-.65 G 3.329
(na)-3.329 G .829(ccess method is the disk-)-3.329 F 1.964
(based structure used to store data and the operations)323.2 242.4 R -.2
(av)323.2 254.4 S 6.053(ailable on that structure.)-.05 F -.15(Fo)11.053
G 8.554(re).15 G 6.054(xample, man)-8.704 F(y)-.15 E 3.853
(database systems support a B+tree access method.)323.2 266.4 R 1.203
(B+trees allo)323.2 278.4 R 3.703(we)-.25 G 1.203
(quality-based lookups \(\214nd k)-3.703 F -.15(ey)-.1 G 3.704(se).15 G
(qual)-3.704 E 4(to some constant\), range-based lookups \(\214nd k)
323.2 290.4 R -.15(ey)-.1 G(s).15 E 1.188(between tw)323.2 302.4 R 3.688
(oc)-.1 G 1.189(onstants\) and record insertion and dele-)-3.688 F
(tion.)323.2 314.4 Q(Berk)323.2 330.6 Q(ele)-.1 E 4.729(yD)-.15 G 4.729
(Bs)-4.729 G 2.228(upports three access methods: B+tree,)-4.729 F 1.553
(Extended Linear Hashing \(Hash\), and Fix)323.2 342.6 R 1.553(ed- or V)
-.15 F(ari-)-1.11 E 3.639(able-length Records \(Recno\).)323.2 354.6 R
3.638(All three operate on)8.638 F 1.956(records composed of a k)323.2
366.6 R 2.256 -.15(ey a)-.1 H 1.956(nd a data v).15 F 4.456(alue. In)
-.25 F(the)4.456 E 1.301(B+tree and Hash access methods, k)323.2 378.6 R
-.15(ey)-.1 G 3.801(sc).15 G 1.301(an ha)-3.801 F 1.601 -.15(ve a)-.2 H
(rbi-).15 E 3.595(trary structure.)323.2 390.6 R 3.596
(In the Recno access method, each)8.595 F .266
(record is assigned a record number)323.2 402.6 R 2.765(,w)-.4 G .265
(hich serv)-2.765 F .265(es as the)-.15 F -.1(ke)323.2 414.6 S 4.106
-.65(y. I)-.05 H 2.806(na).65 G .306(ll the access methods, the v)-2.806
F .306(alue can ha)-.25 F .606 -.15(ve a)-.2 H(rbi-).15 E 1.417
(trary structure.)323.2 426.6 R 1.417
(The programmer can supply compari-)6.417 F 2.129
(son or hashing functions for k)323.2 438.6 R -.15(ey)-.1 G 2.129
(s, and Berk).15 F(ele)-.1 E 4.629(yD)-.15 G(B)-4.629 E
(stores and retrie)323.2 450.6 Q -.15(ve)-.25 G 2.5(sv).15 G
(alues without interpreting them.)-2.75 E 1.069
(All of the access methods use the host \214lesystem as a)323.2 466.8 R
(backing store.)323.2 478.8 Q F1 3(2.1. Hash)323.2 508.8 R F0(Berk)323.2
525 Q(ele)-.1 E 6.485(yD)-.15 G 6.485(Bi)-6.485 G 3.986
(ncludes a Hash access method that)-6.485 F 9.863(implements e)323.2 537
R 9.862(xtended linear hashing [Litw80].)-.15 F .017
(Extended linear hashing adjusts the hash function as the)323.2 549 R
.507(hash table gro)323.2 561 R .506(ws, attempting to k)-.25 F .506
(eep all b)-.1 F(uck)-.2 E .506(ets under)-.1 F(-)-.2 E
(full in the steady state.)323.2 573 Q 1.649
(The Hash access method supports insertion and dele-)323.2 589.2 R .259
(tion of records and lookup by e)323.2 601.2 R .259(xact match only)-.15
F 5.258(.A)-.65 G(ppli-)-5.258 E .038(cations may iterate o)323.2 613.2
R -.15(ve)-.15 G 2.538(ra).15 G .038(ll records stored in a table, b)
-2.538 F(ut)-.2 E(the order in which the)323.2 625.2 Q 2.5(ya)-.15 G
(re returned is unde\214ned.)-2.5 E F1 3(2.2. B+tr)323.2 655.2 R(ee)
-.216 E F0(Berk)323.2 671.4 Q(ele)-.1 E 7.184(yD)-.15 G 7.184(Bi)-7.184
G 4.683(ncludes a B+tree [Come79] access)-7.184 F 2.502(method. B+trees)
323.2 683.4 R .002(store records of k)2.502 F -.15(ey)-.1 G(/v).15 E
.003(alue pairs in leaf)-.25 F .52(pages, and pairs of \(k)323.2 695.4 R
-.15(ey)-.1 G 3.02(,c)-.5 G .52(hild page address\) at internal)-3.02 F
5.384(nodes. K)323.2 707.4 R -.15(ey)-.25 G 5.384(si).15 G 5.384(nt)
-5.384 G 2.885(he tree are stored in sorted order)-5.384 F(,)-.4 E EP
BP
/F0 10/Times-Roman@0 SF .576
(where the order is determined by the comparison func-)79.2 84 R .815
(tion supplied when the database w)79.2 96 R .815(as created.)-.1 F -.15
(Pa)5.815 G .815(ges at).15 F .389(the leaf le)79.2 108 R -.15(ve)-.25 G
2.889(lo).15 G 2.889(ft)-2.889 G .389
(he tree include pointers to their neigh-)-2.889 F 1.444
(bors to simplify tra)79.2 120 R -.15(ve)-.2 G 3.944(rsal. B+trees).15 F
1.445(support lookup by)3.944 F -.15(ex)79.2 132 S .068
(act match \(equality\) or range \(greater than or equal to).15 F 2.891
(ak)79.2 144 S -.15(ey)-2.991 G 2.891(\). Lik).15 F 2.891(eH)-.1 G .391
(ash tables, B+trees support record inser)-2.891 F(-)-.2 E
(tion, deletion, and iteration o)79.2 156 Q -.15(ve)-.15 G 2.5(ra).15 G
(ll records in the tree.)-2.5 E .646
(As records are inserted and pages in the B+tree \214ll up,)79.2 172.2 R
(the)79.2 184.2 Q 2.722(ya)-.15 G .223(re split, with about half the k)
-2.722 F -.15(ey)-.1 G 2.723(sg).15 G .223(oing into a ne)-2.723 F(w)
-.25 E 1.603(peer page at the same le)79.2 196.2 R -.15(ve)-.25 G 4.103
(li).15 G 4.103(nt)-4.103 G 1.603(he tree.)-4.103 F 1.603(Most B+tree)
6.603 F .387(implementations lea)79.2 208.2 R .687 -.15(ve b)-.2 H .387
(oth nodes half-full after a split.).15 F 2.763
(This leads to poor performance in a common case,)79.2 220.2 R 1.522
(where the caller inserts k)79.2 232.2 R -.15(ey)-.1 G 4.022(si).15 G
4.022(no)-4.022 G(rder)-4.022 E 6.522(.T)-.55 G 4.023(oh)-7.322 G 1.523
(andle this)-4.023 F 1.643(case, Berk)79.2 244.2 R(ele)-.1 E 4.143(yD)
-.15 G 4.143(Bk)-4.143 G 1.642(eeps track of the insertion order)-4.243
F(,)-.4 E 2.023(and splits pages une)79.2 256.2 R -.15(ve)-.25 G 2.024
(nly to k).15 F 2.024(eep pages fuller)-.1 F 7.024(.T)-.55 G(his)-7.024
E 2.3(reduces tree size, yielding better search performance)79.2 268.2 R
(and smaller databases.)79.2 280.2 Q 3.177
(On deletion, empty pages are coalesced by re)79.2 296.4 R -.15(ve)-.25
G(rse).15 E 2.03(splits into single pages.)79.2 308.4 R 2.03
(The access method does no)7.03 F .347
(other page balancing on insertion or deletion.)79.2 320.4 R -2.15 -.25
(Ke y)5.348 H 2.848(sa).25 G(re)-2.848 E 1.927(not mo)79.2 332.4 R -.15
(ve)-.15 G 4.427(da).15 G 1.927(mong pages at e)-4.427 F -.15(ve)-.25 G
1.926(ry update to k).15 F 1.926(eep the)-.1 F 2.206
(tree well-balanced.)79.2 344.4 R 2.207(While this could impro)7.206 F
2.507 -.15(ve s)-.15 H(earch).15 E 2.341
(times in some cases, the additional code comple)79.2 356.4 R(xity)-.15
E(leads to slo)79.2 368.4 Q(wer updates and is prone to deadlocks.)-.25
E -.15(Fo)79.2 384.6 S 2.948(rs).15 G(implicity)-2.948 E 2.948(,B)-.65 G
(erk)-2.948 E(ele)-.1 E 2.949(yD)-.15 G 2.949(BB)-2.949 G .449
(+trees do no pre\214x com-)-2.949 F(pression of k)79.2 396.6 Q -.15(ey)
-.1 G 2.5(sa).15 G 2.5(ti)-2.5 G(nternal or leaf nodes.)-2.5 E/F1 12
/Times-Bold@0 SF 3(2.3. Recno)79.2 426.6 R F0(Berk)79.2 442.8 Q(ele)-.1
E 2.736(yD)-.15 G 2.736(Bi)-2.736 G .236(ncludes a \214x)-2.736 F .236
(ed- or v)-.15 F .235(ariable-length record)-.25 F 5.075
(access method, called)79.2 454.8 R/F2 10/Times-Italic@0 SF(Recno)7.575
E F0 10.075(.T)C 5.075(he Recno access)-10.075 F .896
(method assigns logical record numbers to each record,)79.2 466.8 R .978
(and can search for and update records by record num-)79.2 478.8 R(ber)
79.2 490.8 Q 5.037(.R)-.55 G .037(ecno is able, for e)-5.037 F .037
(xample, to load a te)-.15 F .036(xt \214le into a)-.15 F 1.514
(database, treating each line as a record.)79.2 502.8 R 1.514
(This permits)6.514 F -.1(fa)79.2 514.8 S 1.313
(st searches by line number for applications lik).1 F 3.812(et)-.1 G
-.15(ex)-3.812 G(t).15 E(editors [Ston82].)79.2 526.8 Q 2.59
(Recno is actually b)79.2 543 R 2.59(uilt on top of the B+tree access)
-.2 F 3.192(method and pro)79.2 555 R 3.191(vides a simple interf)-.15 F
3.191(ace for storing)-.1 F 3.14(sequentially-ordered data v)79.2 567 R
5.64(alues. The)-.25 F 3.14(Recno access)5.64 F 2.266
(method generates k)79.2 579 R -.15(ey)-.1 G 4.766(si).15 G(nternally)
-4.766 E 7.266(.T)-.65 G 2.266(he programmer')-7.266 F(s)-.55 E(vie)79.2
591 Q 4.102(wo)-.25 G 4.102(ft)-4.102 G 1.602(he v)-4.102 F 1.602
(alues is that the)-.25 F 4.102(ya)-.15 G 1.603(re numbered sequen-)
-4.102 F .254(tially from one.)79.2 603 R(De)5.254 E -.15(ve)-.25 G .254
(lopers can choose to ha).15 F .553 -.15(ve r)-.2 H(ecords).15 E 9
(automatically renumbered when lo)79.2 615 R(wer)-.25 E(-numbered)-.2 E
.041(records are added or deleted.)79.2 627 R .041(In this case, ne)
5.041 F 2.541(wk)-.25 G -.15(ey)-2.641 G 2.541(sc).15 G(an)-2.541 E
(be inserted between e)79.2 639 Q(xisting k)-.15 E -.15(ey)-.1 G(s.).15
E F1 3(3. F)79.2 669 R(eatur)-.3 E(es)-.216 E F0 1.827
(This section describes important features of Berk)79.2 685.2 R(ele)-.1
E(y)-.15 E 3.456(DB. In)79.2 697.2 R .956(general, de)3.456 F -.15(ve)
-.25 G .956(lopers can choose which features).15 F .488
(are useful to them, and use only those that are required)79.2 709.2 R
(by their application.)323.2 84 Q -.15(Fo)323.2 100.2 S 3.529(re).15 G
1.029(xample, when an application opens a database, it)-3.679 F .101
(can declare the de)323.2 112.2 R .101(gree of concurrenc)-.15 F 2.601
(ya)-.15 G .102(nd reco)-2.601 F -.15(ve)-.15 G .102(ry that).15 F .049
(it requires.)323.2 124.2 R .048
(Simple stand-alone applications, and in par)5.049 F(-)-.2 E .491
(ticular ports of applications that used)323.2 136.2 R/F3 10/Courier@0
SF(dbm)2.991 E F0 .491(or one of its)2.991 F -.25(va)323.2 148.2 S 1.093
(riants, generally do not require concurrent access or).25 F .975
(crash reco)323.2 160.2 R -.15(ve)-.15 G(ry).15 E 5.975(.O)-.65 G .975
(ther applications, such as enterprise-)-5.975 F 3.08
(class database management systems that store sales)323.2 172.2 R 2.643
(transactions or other critical data, need full transac-)323.2 184.2 R
3.93(tional service.)323.2 196.2 R 3.93(Single-user operation is f)8.93
F 3.93(aster than)-.1 F 1.175(multi-user operation, since no o)323.2
208.2 R -.15(ve)-.15 G 1.176(rhead is incurred by).15 F 3.156
(locking. Running)323.2 220.2 R .656(with the reco)3.156 F -.15(ve)-.15
G .655(ry system disabled is).15 F -.1(fa)323.2 232.2 S 1.732
(ster than running with it enabled, since log records).1 F 2.703
(need not be written when changes are made to the)323.2 244.2 R
(database.)323.2 256.2 Q .851
(In addition, some core subsystems, including the lock-)323.2 272.4 R
.345(ing system and the logging f)323.2 284.4 R(acility)-.1 E 2.844(,c)
-.65 G .344(an be used outside)-2.844 F 1.772(the conte)323.2 296.4 R
1.772(xt of the access methods as well.)-.15 F(Although)6.773 E(fe)323.2
308.4 Q 4.284(wu)-.25 G 1.784(sers ha)-4.284 F 2.084 -.15(ve c)-.2 H
1.784(hosen to do so, it is possible to use).15 F .939
(only the lock manager in Berk)323.2 320.4 R(ele)-.1 E 3.439(yD)-.15 G
3.439(Bt)-3.439 G 3.439(oc)-3.439 G .939(ontrol con-)-3.439 F(currenc)
323.2 332.4 Q 4.743(yi)-.15 G 4.743(na)-4.743 G 4.743(na)-4.743 G 2.242
(pplication, without using an)-4.743 F 4.742(yo)-.15 G 4.742(ft)-4.742 G
(he)-4.742 E .158(standard database services.)323.2 344.4 R(Alternati)
5.158 E -.15(ve)-.25 G(ly).15 E 2.658(,t)-.65 G .159(he caller can)
-2.658 F(inte)323.2 356.4 Q .07
(grate locking of non-database resources with Berk)-.15 F(e-)-.1 E(le)
323.2 368.4 Q 5.201(yD)-.15 G(B')-5.201 E 5.201(st)-.55 G 2.702
(ransactional tw)-5.201 F 2.702(o-phase locking system, to)-.1 F 2.892
(impose transaction semantics on objects outside the)323.2 380.4 R
(database.)323.2 392.4 Q F1 3(3.1. Pr)323.2 422.4 R
(ogrammatic interfaces)-.216 E F0(Berk)323.2 438.6 Q(ele)-.1 E 4.008(yD)
-.15 G 4.008(Bd)-4.008 G 1.509(e\214nes a simple API for database man-)
-4.008 F 3.452(agement. The)323.2 450.6 R .952
(package does not include industry-stan-)3.452 F 1.898
(dard programmatic interf)323.2 462.6 R 1.898
(aces such as Open Database)-.1 F(Connecti)323.2 474.6 Q .852
(vity \(ODBC\), Object Linking and Embedding)-.25 F .817
(for Databases \(OleDB\), or Structured Query Language)323.2 486.6 R
4.027(\(SQL\). These)323.2 498.6 R(interf)4.027 E 1.527
(aces, while useful, were designed)-.1 F 2.477
(to promote interoperability of database systems, and)323.2 510.6 R
(not simplicity or performance.)323.2 522.6 Q 3.192
(In response to customer demand, Berk)323.2 538.8 R(ele)-.1 E 5.691(yD)
-.15 G 5.691(B2)-5.691 G(.5)-5.691 E .538
(introduced support for the XA standard [Open94].)323.2 550.8 R(XA)5.539
E .52(permits Berk)323.2 562.8 R(ele)-.1 E 3.02(yD)-.15 G 3.02(Bt)-3.02
G 3.02(op)-3.02 G .52(articipate in distrib)-3.02 F .52(uted trans-)-.2
F 3.373(actions under a transaction processing monitor lik)323.2 574.8 R
(e)-.1 E -.45(Tu)323.2 586.8 S -.15(xe).45 G 1.31(do from BEA Systems.)
.15 F(Lik)6.31 E 3.81(eX)-.1 G 1.31(A, other standard)-3.81 F(interf)
323.2 598.8 Q .99(aces can be b)-.1 F .99
(uilt on top of the core system.)-.2 F(The)5.99 E .846
(standards do not belong inside Berk)323.2 610.8 R(ele)-.1 E 3.346(yD)
-.15 G .846(B, since not)-3.346 F(all applications need them.)323.2
622.8 Q F1 3(3.2. W)323.2 652.8 R(orking with r)-.9 E(ecords)-.216 E F0
3.134(Ad)323.2 669 S .634
(atabase user may need to search for particular k)-3.134 F -.15(ey)-.1 G
(s).15 E .908(in a database, or may simply w)323.2 681 R .908
(ant to bro)-.1 F .907(wse a)-.25 F -.25(va)-.2 G(ilable).25 E 4.101
(records. Berk)323.2 693 R(ele)-.1 E 4.101(yD)-.15 G 4.101(Bs)-4.101 G
1.601(upports both k)-4.101 F -.15(ey)-.1 G 1.602(ed access, to).15 F
.173(\214nd one or more records with a gi)323.2 705 R -.15(ve)-.25 G
2.673(nk).15 G -.15(ey)-2.773 G 2.673(,o)-.5 G 2.673(rs)-2.673 G
(equential)-2.673 E .53(access, to retrie)323.2 717 R .83 -.15(ve a)-.25
H .53(ll the records in the database one at).15 F EP
BP
/F0 10/Times-Roman@0 SF 6.34(at)79.2 84 S 6.34(ime. The)-6.34 F 3.84
(order of the records returned during)6.34 F .208
(sequential scans depends on the access method.)79.2 96 R(B+tree)5.209 E
1.495(and Recno databases return records in sort order)79.2 108 R 3.995
(,a)-.4 G(nd)-3.995 E .023
(Hash databases return them in apparently random order)79.2 120 R(.)-.55
E(Similarly)79.2 136.2 Q 4.959(,B)-.65 G(erk)-4.959 E(ele)-.1 E 4.959
(yD)-.15 G 4.958(Bd)-4.959 G 2.458(e\214nes simple interf)-4.958 F 2.458
(aces for)-.1 F
(inserting, updating, and deleting records in a database.)79.2 148.2 Q
/F1 12/Times-Bold@0 SF 3(3.3. Long)79.2 178.2 R -.12(ke)3 G(ys and v).12
E(alues)-.12 E F0(Berk)79.2 194.4 Q(ele)-.1 E 3.553(yD)-.15 G 3.553(Bm)
-3.553 G 1.053(anages k)-3.553 F -.15(ey)-.1 G 3.553(sa).15 G 1.053
(nd v)-3.553 F 1.053(alues as lar)-.25 F 1.054(ge as 2)-.18 F/F2 8
/Times-Roman@0 SF(32)-5 I F0 3.192(bytes. Since)79.2 206.4 R .692
(the time required to cop)3.192 F 3.192(yar)-.1 G .692(ecord is pro-)
-3.192 F 1.895(portional to its size, Berk)79.2 218.4 R(ele)-.1 E 4.396
(yD)-.15 G 4.396(Bi)-4.396 G 1.896(ncludes interf)-4.396 F(aces)-.1 E
4.507(that operate on partial records.)79.2 230.4 R 4.507
(If an application)9.507 F 1.273(requires only part of a lar)79.2 242.4
R 1.274(ge record, it requests partial)-.18 F .026(record retrie)79.2
254.4 R -.25(va)-.25 G .026(l, and recei).25 F -.15(ve)-.25 G 2.526(sj)
.15 G .025(ust the bytes that it needs.)-2.526 F(The smaller cop)79.2
266.4 Q 2.5(ys)-.1 G -2.25 -.2(av e)-2.5 H 2.5(sb).2 G
(oth time and memory)-2.5 E(.)-.65 E(Berk)79.2 282.6 Q(ele)-.1 E 3.206
(yD)-.15 G 3.206(Ba)-3.206 G(llo)-3.206 E .706
(ws the programmer to de\214ne the data)-.25 F 2.72(types of k)79.2
294.6 R -.15(ey)-.1 G 5.22(sa).15 G 2.72(nd v)-5.22 F 5.22(alues. De)
-.25 F -.15(ve)-.25 G 2.72(lopers use an).15 F 5.22(yt)-.15 G(ype)-5.22
E -.15(ex)79.2 306.6 S(pressible in the programming language.).15 E F1 3
(3.4. Lar)79.2 336.6 R(ge databases)-.12 E F0 3.255(As)79.2 352.8 S .755
(ingle database managed by Berk)-3.255 F(ele)-.1 E 3.256(yD)-.15 G 3.256
(Bc)-3.256 G .756(an be up)-3.256 F 1.716(to 2)79.2 364.8 R F2(48)-5 I
F0 1.716(bytes, or 256 petabytes, in size.)4.216 5 N(Berk)6.715 E(ele)
-.1 E 4.215(yD)-.15 G(B)-4.215 E 2.144
(uses the host \214lesystem as the backing store for the)79.2 376.8 R
2.668(database, so lar)79.2 388.8 R 2.667
(ge databases require big \214le support)-.18 F 3.113
(from the operating system.)79.2 400.8 R(Sleep)8.113 E 3.114(ycat Softw)
-.1 F 3.114(are has)-.1 F 5.712(customers using Berk)79.2 412.8 R(ele)
-.1 E 8.212(yD)-.15 G 8.212(Bt)-8.212 G 8.211(om)-8.212 G 5.711
(anage single)-8.211 F(databases in e)79.2 424.8 Q(xcess of 100 gig)-.15
E(abytes.)-.05 E F1 3(3.5. Main)79.2 454.8 R(memory databases)3 E F0
1.171(Applications that do not require persistent storage can)79.2 471 R
.119(create databases that e)79.2 483 R .119(xist only in main memory)
-.15 F 5.118(.T)-.65 G(hese)-5.118 E .542(databases bypass the o)79.2
495 R -.15(ve)-.15 G .543(rhead imposed by the I/O sys-).15 F
(tem altogether)79.2 507 Q(.)-.55 E 2.144
(Some applications do need to use disk as a backing)79.2 523.2 R 2.248
(store, b)79.2 535.2 R 2.249(ut run on machines with v)-.2 F 2.249
(ery lar)-.15 F 2.249(ge memory)-.18 F(.)-.65 E(Berk)79.2 547.2 Q(ele)
-.1 E 2.799(yD)-.15 G 2.799(Bi)-2.799 G 2.799(sa)-2.799 G .299
(ble to manage v)-2.799 F .299(ery lar)-.15 F .299(ge shared mem-)-.18 F
.128(ory re)79.2 559.2 R .129
(gions for cached data pages, log records, and lock)-.15 F 3.938
(management. F)79.2 571.2 R 1.437(or e)-.15 F 1.437
(xample, the cache re)-.15 F 1.437(gion used for)-.15 F .033
(data pages may be gig)79.2 583.2 R .034
(abytes in size, reducing the lik)-.05 F(eli-)-.1 E .639(hood that an)
79.2 595.2 R 3.139(yr)-.15 G .639
(ead operation will need to visit the disk)-3.139 F 1.201
(in the steady state.)79.2 607.2 R 1.201
(The programmer declares the size)6.201 F(of the cache re)79.2 619.2 Q
(gion at startup.)-.15 E(Finally)79.2 635.4 Q 7.048(,m)-.65 G(an)-7.048
E 7.048(yo)-.15 G 4.548(perating systems pro)-7.048 F 4.548
(vide memory-)-.15 F 2.532(mapped \214le services that are much f)79.2
647.4 R 2.533(aster than their)-.1 F 2.602
(general-purpose \214le system interf)79.2 659.4 R 5.102(aces. Berk)-.1
F(ele)-.1 E 5.102(yD)-.15 G(B)-5.102 E 5.118
(can memory-map its database \214les for read-only)79.2 671.4 R 3.917
(database use.)79.2 683.4 R 3.917(The application operates on records)
8.917 F 2.069(stored directly on the pages, with no cache manage-)79.2
695.4 R 1.557(ment o)79.2 707.4 R -.15(ve)-.15 G 4.057(rhead. Because)
.15 F 1.556(the application gets pointers)4.057 F 1.265
(directly into the Berk)323.2 84 R(ele)-.1 E 3.765(yD)-.15 G 3.765(Bp)
-3.765 G 1.265(ages, writes cannot be)-3.765 F 3.775
(permitted. Otherwise,)323.2 96 R 1.275(changes could bypass the lock-)
3.775 F .23(ing and logging systems, and softw)323.2 108 R .23
(are errors could cor)-.1 F(-)-.2 E 4.007(rupt the database.)323.2 120 R
4.006(Read-only applications can use)9.007 F(Berk)323.2 132 Q(ele)-.1 E
2.893(yD)-.15 G(B')-2.893 E 2.893(sm)-.55 G .393
(emory-mapped \214le service to impro)-2.893 F -.15(ve)-.15 G
(performance on most architectures.)323.2 144 Q F1 3
(3.6. Con\214gurable)323.2 174 R(page size)3 E F0 .111
(Programmers declare the size of the pages used by their)323.2 190.2 R
.403(access methods when the)323.2 202.2 R 2.903(yc)-.15 G .403
(reate a database.)-2.903 F(Although)5.403 E(Berk)323.2 214.2 Q(ele)-.1
E 4.046(yD)-.15 G 4.046(Bp)-4.046 G(ro)-4.046 E 1.546
(vides reasonable def)-.15 F 1.546(aults, de)-.1 F -.15(ve)-.25 G
(lopers).15 E 3.64(may o)323.2 226.2 R -.15(ve)-.15 G 3.64
(rride them to control system performance.).15 F .793
(Small pages reduce the number of records that \214t on a)323.2 238.2 R
.353(single page.)323.2 250.2 R(Fe)5.353 E .353
(wer records on a page means that fe)-.25 F(wer)-.25 E .724
(records are lock)323.2 262.2 R .724(ed when the page is lock)-.1 F .723
(ed, impro)-.1 F(ving)-.15 E(concurrenc)323.2 274.2 Q 5.262 -.65(y. T)
-.15 H 1.462(he per).65 F 1.462(-page o)-.2 F -.15(ve)-.15 G 1.462
(rhead is proportionally).15 F 2.29
(higher with smaller pages, of course, b)323.2 286.2 R 2.29(ut de)-.2 F
-.15(ve)-.25 G(lopers).15 E(can trade of)323.2 298.2 Q 2.5(fs)-.25 G
(pace for time as an application requires.)-2.5 E F1 3(3.7. Small)323.2
328.2 R -.3(fo)3 G(otprint).3 E F0(Berk)323.2 344.4 Q(ele)-.1 E 3.973
(yD)-.15 G 3.973(Bi)-3.973 G 3.974(sac)-3.973 G 1.474(ompact system.)
-3.974 F 1.474(The full package,)6.474 F .832
(including all access methods, reco)323.2 356.4 R -.15(ve)-.15 G
(rability).15 E 3.331(,a)-.65 G .831(nd trans-)-3.331 F 1.235
(action support is roughly 175K of te)323.2 368.4 R 1.236
(xt space on com-)-.15 F(mon architectures.)323.2 380.4 Q F1 3
(3.8. Cursors)323.2 410.4 R F0 1.57(In database terminology)323.2 426.6
R 4.07(,ac)-.65 G 1.57(ursor is a pointer into an)-4.07 F 1.806
(access method that can be called iterati)323.2 438.6 R -.15(ve)-.25 G
1.807(ly to return).15 F 3.68(records in sequence.)323.2 450.6 R(Berk)
8.68 E(ele)-.1 E 6.18(yD)-.15 G 6.18(Bi)-6.18 G 3.68(ncludes cursor)
-6.18 F(interf)323.2 462.6 Q 2.814(aces for all access methods.)-.1 F
2.815(This permits, for)7.814 F -.15(ex)323.2 474.6 S .34
(ample, users to tra).15 F -.15(ve)-.2 G .34(rse a B+tree and vie).15 F
2.84(wr)-.25 G .34(ecords in)-2.84 F(order)323.2 486.6 Q 6.233(.P)-.55 G
1.234(ointers to records in cursors are persistent, so)-6.233 F 1.779
(that once fetched, a record may be updated in place.)323.2 498.6 R
(Finally)323.2 510.6 Q 4.438(,c)-.65 G 1.939
(ursors support access to chains of duplicate)-4.438 F
(data items in the v)323.2 522.6 Q(arious access methods.)-.25 E F1 3
(3.9. J)323.2 552.6 R(oins)-.18 E F0 2.703(In database terminology)323.2
568.8 R 5.203(,aj)-.65 G 2.702(oin is an operation that)-5.203 F .616
(spans multiple separate tables \(or in the case of Berk)323.2 580.8 R
(e-)-.1 E(le)323.2 592.8 Q 4.518(yD)-.15 G 2.018
(B, multiple separate DB \214les\).)-4.518 F -.15(Fo)7.017 G 4.517(re)
.15 G 2.017(xample, a)-4.667 F(compan)323.2 604.8 Q 3.372(ym)-.15 G .873
(ay store information about its customers in)-3.372 F 1.545
(one table and information about sales in another)323.2 616.8 R 6.545
(.A)-.55 G(n)-6.545 E 1.498(application will lik)323.2 628.8 R 1.499
(ely w)-.1 F 1.499(ant to look up sales informa-)-.1 F .933
(tion by customer name; this requires matching records)323.2 640.8 R
2.28(in the tw)323.2 652.8 R 4.78(ot)-.1 G 2.28
(ables that share a common customer ID)-4.78 F 2.515(\214eld. This)323.2
664.8 R .015(combining of records from multiple tables is)2.515 F
(called a join.)323.2 676.8 Q(Berk)323.2 693 Q(ele)-.1 E 5.561(yD)-.15 G
5.561(Bi)-5.561 G 3.061(ncludes interf)-5.561 F 3.062
(aces for joining tw)-.1 F 5.562(oo)-.1 G(r)-5.562 E(more tables.)323.2
705 Q EP
BP
/F0 12/Times-Bold@0 SF 3(3.10. T)79.2 84 R(ransactions)-.888 E/F1 10
/Times-Roman@0 SF -.35(Tr)79.2 100.2 S(ansactions ha).35 E .3 -.15(ve f)
-.2 H(our properties [Gray93]:).15 E/F2 8/Times-Roman@0 SF<83>84.2 116.4
Q F1(The)17.2 E 5.489(ya)-.15 G 2.989(re atomic.)-5.489 F 2.989
(That is, all of the changes)7.989 F 1.475
(made in a single transaction must be applied at)104.2 128.4 R 1.31
(the same instant or not at all.)104.2 140.4 R 1.31(This permits, for)
6.31 F -.15(ex)104.2 152.4 S 3.565(ample, the transfer of mone).15 F
6.065(yb)-.15 G 3.565(etween tw)-6.065 F(o)-.1 E 3.68
(accounts to be accomplished, by making the)104.2 164.4 R 1.27
(reduction of the balance in one account and the)104.2 176.4 R
(increase in the other into a single, atomic action.)104.2 188.4 Q F2
<83>84.2 204.6 Q F1(The)17.2 E 3.125(ym)-.15 G .625(ust be consistent.)
-3.125 F .625(That is, changes to the)5.625 F 3.628(database by an)104.2
216.6 R 6.128(yt)-.15 G 3.628(ransaction cannot lea)-6.128 F 3.929 -.15
(ve t)-.2 H(he).15 E(database in an ille)104.2 228.6 Q -.05(ga)-.15 G
2.5(lo).05 G 2.5(rc)-2.5 G(orrupt state.)-2.5 E F2<83>84.2 244.8 Q F1
(The)17.2 E 3.006(ym)-.15 G .506(ust be isolatable.)-3.006 F(Re)5.506 E
-.05(ga)-.15 G .505(rdless of the num-).05 F .8(ber of users w)104.2
256.8 R .8(orking in the database at the same)-.1 F 1.88(time, e)104.2
268.8 R -.15(ve)-.25 G 1.88(ry user must ha).15 F 2.18 -.15(ve t)-.2 H
1.88(he illusion that no).15 F(other acti)104.2 280.8 Q
(vity is going on.)-.25 E F2<83>84.2 297 Q F1(The)17.2 E 5.54(ym)-.15 G
3.04(ust be durable.)-5.54 F(Ev)8.04 E 3.04(en if the disk that)-.15 F
.877(stores the database is lost, it must be possible to)104.2 309 R
(reco)104.2 321 Q -.15(ve)-.15 G 2.668(rt).15 G .168
(he database to its last transaction-consis-)-2.668 F(tent state.)104.2
333 Q 2.49(This combination of properties \212 atomicity)79.2 349.2 R
4.99(,c)-.65 G(onsis-)-4.99 E(tenc)79.2 361.2 Q 4.542 -.65(y, i)-.15 H
3.243(solation, and durability \212 is referred to as).65 F -.4(AC)79.2
373.2 S 3.459(IDity in the literature.).4 F(Berk)8.459 E(ele)-.1 E 5.958
(yD)-.15 G 3.458(B, lik)-5.958 F 5.958(em)-.1 G(ost)-5.958 E .993
(database systems, pro)79.2 385.2 R .993(vides A)-.15 F .994
(CIDity using a collection)-.4 F(of core services.)79.2 397.2 Q .257
(Programmers can choose to use Berk)79.2 413.4 R(ele)-.1 E 2.757(yD)-.15
G(B')-2.757 E 2.757(st)-.55 G(ransac-)-2.757 E
(tion services for applications that need them.)79.2 425.4 Q F0 3
(3.10.1. Write-ahead)79.2 455.4 R(logging)3 E F1 .479
(Programmers can enable the logging system when the)79.2 471.6 R(y)-.15
E .918(start up Berk)79.2 483.6 R(ele)-.1 E 3.418(yD)-.15 G 3.418
(B. During)-3.418 F 3.417(at)3.417 G .917(ransaction, the appli-)-3.417
F .493(cation mak)79.2 495.6 R .493
(es a series of changes to the database.)-.1 F(Each)5.494 E .552
(change is captured in a log entry)79.2 507.6 R 3.052(,w)-.65 G .552
(hich holds the state)-3.052 F .207
(of the database record both before and after the change.)79.2 519.6 R
2.208(The log record is guaranteed to be \215ushed to stable)79.2 531.6
R .871(storage before an)79.2 543.6 R 3.371(yo)-.15 G 3.371(ft)-3.371 G
.871(he changed data pages are writ-)-3.371 F 3.989(ten. This)79.2 555.6
R(beha)3.989 E 1.489(vior \212 writing the log before the data)-.2 F
(pages \212 is called)79.2 567.6 Q/F3 10/Times-Italic@0 SF
(write-ahead lo)2.5 E -.1(gg)-.1 G(ing).1 E F1(.)A .835(At an)79.2 583.8
R 3.335(yt)-.15 G .835(ime during the transaction, the application can)
-3.335 F F3(commit)79.2 595.8 Q F1 4.202(,m)C 1.702
(aking the changes permanent, or)-4.202 F F3 -.45(ro)4.201 G 1.701
(ll bac).45 F(k)-.2 E F1(,)A .852
(cancelling all changes and restoring the database to its)79.2 607.8 R
1.57(pre-transaction state.)79.2 619.8 R 1.57
(If the application rolls back the)6.57 F 1.003
(transaction, then the log holds the state of all changed)79.2 631.8 R
.5(pages prior to the transaction, and Berk)79.2 643.8 R(ele)-.1 E 3(yD)
-.15 G 3(Bs)-3 G(imply)-3 E .226(restores that state.)79.2 655.8 R .226
(If the application commits the trans-)5.226 F .538(action, Berk)79.2
667.8 R(ele)-.1 E 3.038(yD)-.15 G 3.038(Bw)-3.038 G .538
(rites the log records to disk.)-3.038 F(In-)5.537 E 2.312
(memory copies of the data pages already re\215ect the)79.2 679.8 R
1.399(changes, and will be \215ushed as necessary during nor)79.2 691.8
R(-)-.2 E 2.35(mal processing.)79.2 703.8 R 2.35
(Since log writes are sequential, b)7.35 F(ut)-.2 E 8.732
(data page writes are random, this impro)79.2 715.8 R -.15(ve)-.15 G(s)
.15 E(performance.)323.2 84 Q F0 3(3.10.2. Crashes)323.2 114 R(and r)3 E
(eco)-.216 E -.12(ve)-.12 G(ry).12 E F1(Berk)323.2 130.2 Q(ele)-.1 E
3.592(yD)-.15 G(B')-3.592 E 3.592(sw)-.55 G 1.093
(rite-ahead log is used by the transac-)-3.592 F .415
(tion system to commit or roll back transactions.)323.2 142.2 R .414
(It also)5.414 F(gi)323.2 154.2 Q -.15(ve)-.25 G 3.23(st).15 G .73
(he reco)-3.23 F -.15(ve)-.15 G .73
(ry system the information that it needs).15 F .824(to protect ag)323.2
166.2 R .824(ainst data loss or corruption from crashes.)-.05 F(Berk)
323.2 178.2 Q(ele)-.1 E 2.703(yD)-.15 G 2.703(Bi)-2.703 G 2.704(sa)
-2.703 G .204(ble to survi)-2.704 F .504 -.15(ve a)-.25 H .204
(pplication crashes, sys-).15 F .408(tem crashes, and e)323.2 190.2 R
-.15(ve)-.25 G 2.908(nc).15 G .407(atastrophic f)-2.908 F .407
(ailures lik)-.1 F 2.907(et)-.1 G .407(he loss)-2.907 F
(of a hard disk, without losing an)323.2 202.2 Q 2.5(yd)-.15 G(ata.)-2.5
E(Survi)323.2 218.4 Q .538(ving crashes requires data stored in se)-.25
F -.15(ve)-.25 G .539(ral dif).15 F(fer)-.25 E(-)-.2 E 2.52(ent places.)
323.2 230.4 R 2.52(During normal processing, Berk)7.52 F(ele)-.1 E 5.02
(yD)-.15 G(B)-5.02 E .766(has copies of acti)323.2 242.4 R 1.066 -.15
(ve l)-.25 H .766(og records and recently-used data).15 F 1.539
(pages in memory)323.2 254.4 R 6.539(.L)-.65 G 1.539
(og records are \215ushed to the log)-6.539 F .694
(disk when transactions commit.)323.2 266.4 R .695
(Data pages trickle out)5.694 F .008(to the data disk as pages mo)323.2
278.4 R .308 -.15(ve t)-.15 H .008(hrough the b).15 F(uf)-.2 E .008
(fer cache.)-.25 F(Periodically)323.2 290.4 Q 2.691(,t)-.65 G .191
(he system administrator backs up the data)-2.691 F .278
(disk, creating a safe cop)323.2 302.4 R 2.778(yo)-.1 G 2.778(ft)-2.778
G .278(he database at a particular)-2.778 F 2.609(instant. When)323.2
314.4 R .109(the database is back)2.609 F .109(ed up, the log can be)-.1
F 3.838(truncated. F)323.2 326.4 R 1.337(or maximum rob)-.15 F 1.337
(ustness, the log disk and)-.2 F(data disk should be separate de)323.2
338.4 Q(vices.)-.25 E(Dif)323.2 354.6 Q 1.29(ferent system f)-.25 F 1.29
(ailures can destro)-.1 F 3.79(ym)-.1 G(emory)-3.79 E 3.79(,t)-.65 G
1.29(he log)-3.79 F 1.106(disk, or the data disk.)323.2 366.6 R(Berk)
6.106 E(ele)-.1 E 3.606(yD)-.15 G 3.606(Bi)-3.606 G 3.606(sa)-3.606 G
1.106(ble to survi)-3.606 F -.15(ve)-.25 G .679(the loss of an)323.2
378.6 R 3.179(yo)-.15 G .679(ne of these repositories without losing)
-3.179 F(an)323.2 390.6 Q 2.5(yc)-.15 G(ommitted transactions.)-2.5 E
1.372(If the computer')323.2 406.8 R 3.871(sm)-.55 G 1.371
(emory is lost, through an applica-)-3.871 F 1.619
(tion or operating system crash, then the log holds all)323.2 418.8 R
1.789(committed transactions.)323.2 430.8 R 1.788(On restart, the reco)
6.789 F -.15(ve)-.15 G 1.788(ry sys-).15 F .49(tem rolls the log forw)
323.2 442.8 R .49(ard ag)-.1 F .49(ainst the database, reapply-)-.05 F
.682(ing an)323.2 454.8 R 3.181(yc)-.15 G .681
(hanges to on-disk pages that were in memory)-3.181 F .14
(at the time of the crash.)323.2 466.8 R .14
(Since the log contains pre- and)5.14 F .957
(post-change state for transactions, the reco)323.2 478.8 R -.15(ve)-.15
G .956(ry system).15 F 1.14(also uses the log to restore an)323.2 490.8
R 3.64(yp)-.15 G 1.14(ages to their original)-3.64 F 1.615(state if the)
323.2 502.8 R 4.115(yw)-.15 G 1.615
(ere modi\214ed by transactions that ne)-4.115 F -.15(ve)-.25 G(r).15 E
(committed.)323.2 514.8 Q 2.051
(If the data disk is lost, the system administrator can)323.2 531 R .887
(restore the most recent cop)323.2 543 R 3.386(yf)-.1 G .886
(rom backup.)-3.386 F .886(The reco)5.886 F(v-)-.15 E 1.298
(ery system will roll the entire log forw)323.2 555 R 1.298(ard ag)-.1 F
1.298(ainst the)-.05 F 2.64
(original database, reapplying all committed changes.)323.2 567 R 4.363
(When it \214nishes, the database will contain e)323.2 579 R -.15(ve)
-.25 G(ry).15 E .535(change made by e)323.2 591 R -.15(ve)-.25 G .534
(ry transaction that e).15 F -.15(ve)-.25 G 3.034(rc).15 G(ommitted.)
-3.034 E .494(If the log disk is lost, then the reco)323.2 607.2 R -.15
(ve)-.15 G .495(ry system can use).15 F 1.853
(the in-memory copies of log entries to roll back an)323.2 619.2 R(y)
-.15 E .026(uncommitted transactions, \215ush all in-memory database)
323.2 631.2 R 1.659(pages to the data disk, and shut do)323.2 643.2 R
1.659(wn gracefully)-.25 F 6.658(.A)-.65 G(t)-6.658 E 2.204
(that point, the system administrator can back up the)323.2 655.2 R .039
(database disk, install a ne)323.2 667.2 R 2.539(wl)-.25 G .039
(og disk, and restart the sys-)-2.539 F(tem.)323.2 679.2 Q EP
BP
/F0 12/Times-Bold@0 SF 3(3.10.3. Checkpoints)79.2 84 R/F1 10
/Times-Roman@0 SF(Berk)79.2 100.2 Q(ele)-.1 E 6.085(yD)-.15 G 6.085(Bi)
-6.085 G 3.585(ncludes a checkpointing service that)-6.085 F .263
(interacts with the reco)79.2 112.2 R -.15(ve)-.15 G .263(ry system.).15
F .263(During normal pro-)5.263 F 2.415
(cessing, both the log and the database are changing)79.2 124.2 R
(continually)79.2 136.2 Q 5.925(.A)-.65 G 3.425(ta)-5.925 G 1.224 -.15
(ny g)-3.425 H -2.15 -.25(iv e).15 H 3.424(ni).25 G .924
(nstant, the on-disk v)-3.424 F(ersions)-.15 E .414(of the tw)79.2 148.2
R 2.914(oa)-.1 G .414(re not guaranteed to be consistent.)-2.914 F .414
(The log)5.414 F 3.838
(probably contains changes that are not yet in the)79.2 160.2 R
(database.)79.2 172.2 Q .085(When an application mak)79.2 188.4 R .086
(es a)-.1 F/F2 10/Times-Italic@0 SF -.15(ch)2.586 G(ec).15 E(kpoint)-.2
E F1 2.586(,a)C .086(ll committed)-2.586 F .443
(changes in the log up to that point are guaranteed to be)79.2 200.4 R
.631(present on the data disk, too.)79.2 212.4 R .632
(Checkpointing is moder)5.631 F(-)-.2 E .046(ately e)79.2 224.4 R
(xpensi)-.15 E .346 -.15(ve d)-.25 H .046(uring normal processing, b).15
F .045(ut limits the)-.2 F(time spent reco)79.2 236.4 Q -.15(ve)-.15 G
(ring from crashes.).15 E 3.117
(After an application or operating system crash, the)79.2 252.6 R(reco)
79.2 264.6 Q -.15(ve)-.15 G 7.419(ry system only needs to go back tw).15
F(o)-.1 E(checkpoints)79.2 278.6 Q/F3 7/Times-Roman@0 SF(1)-4 I F1 1.376
(to start rolling the log forw)3.876 4 N 3.875(ard. W)-.1 F(ithout)-.4 E
3.264(checkpoints, there is no w)79.2 290.6 R 3.265(ay to be sure ho)-.1
F 5.765(wl)-.25 G(ong)-5.765 E .395(restarting after a crash will tak)
79.2 302.6 R 2.895(e. W)-.1 F .395(ith checkpoints, the)-.4 F .088
(restart interv)79.2 314.6 R .089(al can be \214x)-.25 F .089
(ed by the programmer)-.15 F 5.089(.R)-.55 G(eco)-5.089 E(v-)-.15 E .668
(ery processing can be guaranteed to complete in a sec-)79.2 326.6 R
(ond or tw)79.2 338.6 Q(o.)-.1 E(Softw)79.2 354.8 Q 2.457
(are crashes are much more common than disk)-.1 F -.1(fa)79.2 366.8 S
3.385(ilures. Man).1 F 3.385(yd)-.15 G -2.15 -.25(ev e)-3.385 H .884
(lopers w).25 F .884(ant to guarantee that soft-)-.1 F -.1(wa)79.2 378.8
S .158(re b).1 F .158(ugs do not destro)-.2 F 2.658(yd)-.1 G .158
(ata, b)-2.658 F .158(ut are willing to restore)-.2 F .631
(from tape, and to tolerate a day or tw)79.2 390.8 R 3.131(oo)-.1 G
3.131(fl)-3.131 G .63(ost w)-3.131 F .63(ork, in)-.1 F .89(the unlikle)
79.2 402.8 R 3.39(ye)-.15 G -.15(ve)-3.64 G .89(nt of a disk crash.).15
F -.4(Wi)5.89 G .89(th Berk).4 F(ele)-.1 E 3.39(yD)-.15 G(B,)-3.39 E
1.093(programmers may truncate the log at checkpoints.)79.2 414.8 R(As)
6.092 E .09(long as the tw)79.2 426.8 R 2.59(om)-.1 G .09
(ost recent checkpoints are present, the)-2.59 F(reco)79.2 438.8 Q -.15
(ve)-.15 G .106(ry system can guarantee that no committed trans-).15 F
.611(actions are lost after a softw)79.2 450.8 R .611(are crash.)-.1 F
.611(In this case, the)5.611 F(reco)79.2 462.8 Q -.15(ve)-.15 G 1.439
(ry system does not require that the log and the).15 F 1.328
(data be on separate de)79.2 474.8 R 1.329
(vices, although separating them)-.25 F(can still impro)79.2 486.8 Q .3
-.15(ve p)-.15 H(erformance by spreading out writes.).15 E F0 3
(3.10.4. T)79.2 516.8 R -.12(wo)-.888 G(-phase locking).12 E F1(Berk)
79.2 533 Q(ele)-.1 E 4.416(yD)-.15 G 4.416(Bp)-4.416 G(ro)-4.416 E 1.916
(vides a service kno)-.15 F 1.915(wn as tw)-.25 F(o-phase)-.1 E 3.017
(locking. In)79.2 545 R .517(order to reduce the lik)3.017 F .518
(elihood of deadlocks)-.1 F 2.547(and to guarantee A)79.2 557 R 2.546
(CID properties, database systems)-.4 F .063(manage locks in tw)79.2 569
R 2.564(op)-.1 G 2.564(hases. First,)-2.564 F .064(during the operation)
2.564 F 1.574(of a transaction, the)79.2 581 R 4.074(ya)-.15 G 1.574
(cquire locks, b)-4.074 F 1.573(ut ne)-.2 F -.15(ve)-.25 G 4.073(rr).15
G(elease)-4.073 E 6.147(them. Second,)79.2 593 R 3.648
(at the end of the transaction, the)6.147 F(y)-.15 E .235
(release locks, b)79.2 605 R .235(ut ne)-.2 F -.15(ve)-.25 G 2.735(ra)
.15 G .235(cquire them.)-2.735 F .235(In practice, most)5.235 F 4.69
(database systems, including Berk)79.2 617 R(ele)-.1 E 7.19(yD)-.15 G
4.69(B, acquire)-7.19 F 2.314(locks on demand o)79.2 629 R -.15(ve)-.15
G 4.814(rt).15 G 2.314(he course of the transaction,)-4.814 F
(then \215ush the log, then release all locks.)79.2 641 Q .32 LW 83.2
650.6 79.2 650.6 DL 87.2 650.6 83.2 650.6 DL 91.2 650.6 87.2 650.6 DL
95.2 650.6 91.2 650.6 DL 99.2 650.6 95.2 650.6 DL 103.2 650.6 99.2 650.6
DL 107.2 650.6 103.2 650.6 DL 111.2 650.6 107.2 650.6 DL 115.2 650.6
111.2 650.6 DL 119.2 650.6 115.2 650.6 DL 123.2 650.6 119.2 650.6 DL
127.2 650.6 123.2 650.6 DL 131.2 650.6 127.2 650.6 DL 135.2 650.6 131.2
650.6 DL 139.2 650.6 135.2 650.6 DL 143.2 650.6 139.2 650.6 DL 147.2
650.6 143.2 650.6 DL 151.2 650.6 147.2 650.6 DL 155.2 650.6 151.2 650.6
DL 159.2 650.6 155.2 650.6 DL 163.2 650.6 159.2 650.6 DL 167.2 650.6
163.2 650.6 DL 171.2 650.6 167.2 650.6 DL 175.2 650.6 171.2 650.6 DL
179.2 650.6 175.2 650.6 DL 183.2 650.6 179.2 650.6 DL 187.2 650.6 183.2
650.6 DL 191.2 650.6 187.2 650.6 DL 195.2 650.6 191.2 650.6 DL 199.2
650.6 195.2 650.6 DL 203.2 650.6 199.2 650.6 DL 207.2 650.6 203.2 650.6
DL 211.2 650.6 207.2 650.6 DL 215.2 650.6 211.2 650.6 DL 219.2 650.6
215.2 650.6 DL 223.2 650.6 219.2 650.6 DL/F4 5/Times-Roman@0 SF(1)100.8
661 Q/F5 8/Times-Roman@0 SF .338(One checkpoint is not f)2.338 3.2 N
.338(ar enough.)-.08 F .338(The reco)4.338 F -.12(ve)-.12 G .338
(ry system can-).12 F .211
(not be sure that the most recent checkpoint completed \212 it may ha)
79.2 673.8 R -.12(ve)-.16 G .734
(been interrupted by the crash that forced the reco)79.2 683.4 R -.12
(ve)-.12 G .734(ry system to run).12 F(in the \214rst place.)79.2 693 Q
F1(Berk)323.2 84 Q(ele)-.1 E 3.306(yD)-.15 G 3.306(Bc)-3.306 G .806
(an lock entire database \214les, which cor)-3.306 F(-)-.2 E .845
(respond to tables, or indi)323.2 96 R .844(vidual pages in them.)-.25 F
.844(It does)5.844 F 2.141(no record-le)323.2 108 R -.15(ve)-.25 G 4.641
(ll).15 G 4.641(ocking. By)-4.641 F 2.142(shrinking the page size,)4.641
F(ho)323.2 120 Q(we)-.25 E -.15(ve)-.25 G 4.427 -.4(r, d).15 H -2.15
-.25(ev e).4 H 3.627(lopers can guarantee that e).25 F -.15(ve)-.25 G
3.626(ry page).15 F 2.101(holds only a small number of records.)323.2
132 R 2.102(This reduces)7.102 F(contention.)323.2 144 Q .388
(If locking is enabled, then read and write operations on)323.2 160.2 R
5.317(ad)323.2 172.2 S 2.817(atabase acquire tw)-5.317 F 2.817
(o-phase locks, which are held)-.1 F 3.635
(until the transaction completes.)323.2 184.2 R 3.635(Which objects are)
8.635 F(lock)323.2 196.2 Q .738
(ed and the order of lock acquisition depend on the)-.1 F -.1(wo)323.2
208.2 S .503(rkload for each transaction.).1 F .502
(It is possible for tw)5.502 F 3.002(oo)-.1 G(r)-3.002 E 1.315
(more transactions to deadlock, so that each is w)323.2 220.2 R(aiting)
-.1 E(for a lock that is held by another)323.2 232.2 Q(.)-.55 E(Berk)
323.2 248.4 Q(ele)-.1 E 3.307(yD)-.15 G 3.307(Bd)-3.307 G .807
(etects deadlocks and automatically rolls)-3.307 F 1.825
(back one of the transactions.)323.2 260.4 R 1.825
(This releases the locks)6.825 F 1.926(that it held and allo)323.2 272.4
R 1.925(ws the other transactions to con-)-.25 F 3.346(tinue. The)323.2
284.4 R .847(caller is noti\214ed that its transaction did not)3.346 F
1.747(complete, and may restart it.)323.2 296.4 R(De)6.747 E -.15(ve)
-.25 G 1.747(lopers can specify).15 F .646
(the deadlock detection interv)323.2 308.4 R .647(al and the polic)-.25
F 3.147(yt)-.15 G 3.147(ou)-3.147 G .647(se in)-3.147 F
(choosing a transaction to roll back.)323.2 320.4 Q 6.686(The tw)323.2
336.6 R 6.686(o-phase locking interf)-.1 F 6.686(aces are separately)-.1
F .927(callable by applications that link Berk)323.2 348.6 R(ele)-.1 E
3.427(yD)-.15 G .928(B, though)-3.427 F(fe)323.2 360.6 Q 5.64(wu)-.25 G
3.14(sers ha)-5.64 F 3.44 -.15(ve n)-.2 H 3.14(eeded to use that f).15 F
3.14(acility directly)-.1 F(.)-.65 E 2.211(Using these interf)323.2
372.6 R 2.211(aces, Berk)-.1 F(ele)-.1 E 4.711(yD)-.15 G 4.712(Bp)-4.711
G(ro)-4.712 E 2.212(vides a f)-.15 F(ast,)-.1 E 2.4
(platform-portable locking system for general-purpose)323.2 384.6 R
2.917(use. It)323.2 396.6 R .418
(also lets users include non-database objects in a)2.917 F 3.497
(database transaction, by controlling access to them)323.2 408.6 R -.15
(ex)323.2 420.6 S(actly as if the).15 E 2.5(yw)-.15 G
(ere inside the database.)-2.5 E .583(The Berk)323.2 436.8 R(ele)-.1 E
3.083(yD)-.15 G 3.084(Bt)-3.083 G -.1(wo)-3.084 G .584(-phase locking f)
.1 F .584(acility is b)-.1 F .584(uilt on)-.2 F .609(the f)323.2 448.8 R
.609(astest correct locking primiti)-.1 F -.15(ve)-.25 G 3.108(st).15 G
.608(hat are supported)-3.108 F 1.967(by the underlying architecture.)
323.2 460.8 R 1.967(In the current imple-)6.967 F .593
(mentation, this means that the locking system is dif)323.2 472.8 R(fer)
-.25 E(-)-.2 E 1.709(ent on the v)323.2 484.8 R 1.709
(arious UNIX platforms, and is still more)-.25 F(dif)323.2 496.8 Q .695
(ferent on W)-.25 F(indo)-.4 E .695(ws NT)-.25 F 5.695(.I)-.74 G 3.195
(no)-5.695 G .695(ur e)-3.195 F .695(xperience, the most)-.15 F(dif)
323.2 508.8 Q 2.634
(\214cult aspect of performance tuning is \214nding the)-.25 F -.1(fa)
323.2 520.8 S .883(stest locking primiti).1 F -.15(ve)-.25 G 3.383(st)
.15 G .883(hat w)-3.383 F .882(ork correctly on a par)-.1 F(-)-.2 E 1.26
(ticular architecture and then inte)323.2 532.8 R 1.26(grating the ne)
-.15 F 3.76(wi)-.25 G(nter)-3.76 E(-)-.2 E -.1(fa)323.2 544.8 S
(ce with the se).1 E -.15(ve)-.25 G(ral that we already support.).15 E
.536(The w)323.2 561 R .536(orld w)-.1 F .536
(ould be a better place if the operating sys-)-.1 F 2.096
(tems community w)323.2 573 R 2.096(ould uniformly implement POSIX)-.1 F
1.31(locking primiti)323.2 585 R -.15(ve)-.25 G 3.81(sa).15 G 1.31(nd w)
-3.81 F 1.31(ould guarantee that acquiring)-.1 F 1.085
(an uncontested lock w)323.2 597 R 1.085(as a f)-.1 F 1.085
(ast operation.)-.1 F 1.085(Locks must)6.085 F -.1(wo)323.2 609 S 3.641
(rk both among threads in a single process and).1 F(among processes.)
323.2 621 Q F0 3(3.11. Concurr)323.2 651 R(ency)-.216 E F1 .383
(Good performance under concurrent operation is a crit-)323.2 667.2 R
.766(ical design point for Berk)323.2 679.2 R(ele)-.1 E 3.266(yD)-.15 G
3.265(B. Although)-3.266 F(Berk)3.265 E(ele)-.1 E(y)-.15 E 1.961
(DB is itself not multi-threaded, it is thread-safe, and)323.2 691.2 R
.547(runs well in threaded applications.)323.2 703.2 R(Philosophically)
5.546 E 3.046(,w)-.65 G(e)-3.046 E(vie)323.2 715.2 Q 4.764(wt)-.25 G
2.264(he use of threads and the choice of a threads)-4.764 F EP
BP
/F0 10/Times-Roman@0 SF .066(package as a polic)79.2 84 R 2.566(yd)-.15
G .065(ecision, and prefer to of)-2.566 F .065(fer mecha-)-.25 F .042
(nism \(the ability to run threaded or not\), allo)79.2 96 R .043
(wing appli-)-.25 F(cations to choose their o)79.2 108 Q(wn policies.)
-.25 E 1.947(The locking, logging, and b)79.2 124.2 R(uf)-.2 E 1.947
(fer pool subsystems all)-.25 F .711
(use shared memory or other OS-speci\214c sharing f)79.2 136.2 R(acili-)
-.1 E 1.713(ties to communicate.)79.2 148.2 R 1.713(Locks, b)6.713 F(uf)
-.2 E 1.713(fer pool fetches, and)-.25 F 1.061(log writes beha)79.2
160.2 R 1.361 -.15(ve i)-.2 H 3.561(nt).15 G 1.061(he same w)-3.561 F
1.061(ay across threads in a)-.1 F .033(single process as the)79.2 172.2
R 2.532(yd)-.15 G 2.532(oa)-2.532 G .032(cross dif)-2.532 F .032
(ferent processes on a)-.25 F(single machine.)79.2 184.2 Q .896
(As a result, concurrent database applications may start)79.2 200.4 R
1.651(up a ne)79.2 212.4 R 4.151(wp)-.25 G 1.651(rocess for e)-4.151 F
-.15(ve)-.25 G 1.651(ry single user).15 F 4.151(,m)-.4 G 1.651
(ay create a)-4.151 F 2.848(single serv)79.2 224.4 R 2.848(er which spa)
-.15 F 2.849(wns a ne)-.15 F 5.349(wt)-.25 G 2.849(hread for e)-5.349 F
-.15(ve)-.25 G(ry).15 E(client request, or may choose an)79.2 236.4 Q
2.5(yp)-.15 G(olic)-2.5 E 2.5(yi)-.15 G 2.5(nb)-2.5 G(etween.)-2.5 E
(Berk)79.2 252.6 Q(ele)-.1 E 3.629(yD)-.15 G 3.629(Bh)-3.629 G 1.128
(as been carefully designed to minimize)-3.629 F .07
(contention and maximize concurrenc)79.2 264.6 R 3.87 -.65(y. T)-.15 H
.07(he cache man-).65 F .57(ager allo)79.2 276.6 R .57
(ws all threads or processes to bene\214t from I/O)-.25 F 2.917
(done by one.)79.2 288.6 R 2.917(Shared resources must sometimes be)
7.917 F(lock)79.2 300.6 Q 1.804(ed for e)-.1 F(xclusi)-.15 E 2.104 -.15
(ve a)-.25 H 1.804(ccess by one thread of control.).15 F 1.757 -.8(We h)
79.2 312.6 T -2.25 -.2(av e).8 H -.1(ke)2.857 G .158
(pt critical sections small, and are careful not).1 F 1.199
(to hold critical resource locks across system calls that)79.2 324.6 R
.538(could deschedule the locking thread or process.)79.2 336.6 R
(Sleep-)5.539 E .979(ycat Softw)79.2 348.6 R .979
(are has customers with hundreds of concur)-.1 F(-)-.2 E(rent users w)
79.2 360.6 Q(orking on a single database in production.)-.1 E/F1 12
/Times-Bold@0 SF 3(4. Engineering)79.2 390.6 R(Philosoph)3 E(y)-.18 E F0
(Fundamentally)79.2 406.8 Q 3.998(,B)-.65 G(erk)-3.998 E(ele)-.1 E 3.998
(yD)-.15 G 3.998(Bi)-3.998 G 3.999(sac)-3.998 G 1.499
(ollection of access)-3.999 F .19(methods with important f)79.2 418.8 R
.19(acilities, lik)-.1 F 2.69(el)-.1 G .19(ogging, locking,)-2.69 F
1.251(and transactional access underlying them.)79.2 430.8 R 1.252
(In both the)6.252 F .992(research and the commercial w)79.2 442.8 R
.991(orld, the techniques for)-.1 F -.2(bu)79.2 454.8 S 2.727
(ilding systems lik).2 F 5.227(eB)-.1 G(erk)-5.227 E(ele)-.1 E 5.227(yD)
-.15 G 5.227(Bh)-5.227 G -2.25 -.2(av e)-5.227 H 2.728(been well-)5.427
F(kno)79.2 466.8 Q(wn for a long time.)-.25 E .443(The k)79.2 483 R .743
-.15(ey a)-.1 H(dv).15 E .442(antage of Berk)-.25 F(ele)-.1 E 2.942(yD)
-.15 G 2.942(Bi)-2.942 G 2.942(st)-2.942 G .442(he careful atten-)-2.942
F 1.059(tion that has been paid to engineering details through-)79.2 495
R 1.039(out its life.)79.2 507 R 2.639 -.8(We h)6.039 H -2.25 -.2(av e)
.8 H 1.039(carefully designed the system so)3.739 F .452
(that the core f)79.2 519 R .452(acilities, lik)-.1 F 2.952(el)-.1 G
.452(ocking and I/O, surf)-2.952 F .453(ace the)-.1 F .972(right interf)
79.2 531 R .971(aces and are otherwise opaque to the caller)-.1 F(.)-.55
E .294(As programmers, we understand the v)79.2 543 R .295
(alue of simplicity)-.25 F .206(and ha)79.2 555 R .506 -.15(ve w)-.2 H
(ork).05 E .206(ed hard to simplify the interf)-.1 F .205(aces we sur)
-.1 F(-)-.2 E -.1(fa)79.2 567 S(ce to users of the database system.).1 E
(Berk)79.2 583.2 Q(ele)-.1 E 4.531(yD)-.15 G 4.531(Ba)-4.531 G -.2(vo)
-4.731 G 2.031(ids limits in the code.).2 F 2.031(It places no)7.031 F
.474(practical limit on the size of k)79.2 595.2 R -.15(ey)-.1 G .473
(s, v).15 F .473(alues, or databases;)-.25 F(the)79.2 607.2 Q 2.5(ym)
-.15 G(ay gro)-2.5 E 2.5(wt)-.25 G 2.5(oo)-2.5 G(ccup)-2.5 E 2.5(yt)-.1
G(he a)-2.5 E -.25(va)-.2 G(ilable storage space.).25 E 1.857
(The locking and logging subsystems ha)79.2 623.4 R 2.157 -.15(ve b)-.2
H 1.858(een care-).15 F .184
(fully crafted to reduce contention and impro)79.2 635.4 R .484 -.15
(ve t)-.15 H(hrough-).15 E 2.16
(put by shrinking or eliminating critical sections, and)79.2 647.4 R
(reducing the sizes of lock)79.2 659.4 Q(ed re)-.1 E
(gions and log entries.)-.15 E 2.238
(There is nothing in the design or implementation of)79.2 675.6 R(Berk)
79.2 687.6 Q(ele)-.1 E 2.818(yD)-.15 G 2.818(Bt)-2.818 G .318
(hat pushes the state of the art in database)-2.818 F 3.545
(systems. Rather)79.2 699.6 R 3.545(,w)-.4 G 3.545(eh)-3.545 G -2.25 -.2
(av e)-3.545 H 1.044(been v)3.745 F 1.044(ery careful to get the)-.15 F
4.321(engineering right.)79.2 711.6 R 4.321
(The result is a system that is)9.321 F(superior)323.2 84 Q 2.867(,a)-.4
G 2.867(sa)-2.867 G 2.866(ne)-2.867 G .366
(mbedded database system, to an)-2.866 F 2.866(yo)-.15 G(ther)-2.866 E
(solution a)323.2 96 Q -.25(va)-.2 G(ilable.).25 E .811
(Most database systems trade of)323.2 112.2 R 3.312(fs)-.25 G .812
(implicity for correct-)-3.312 F 4.151(ness. Either)323.2 124.2 R 1.651
(the system is easy to use, or it supports)4.151 F 1.17
(concurrent use and survi)323.2 136.2 R -.15(ve)-.25 G 3.67(ss).15 G
1.17(ystem f)-3.67 F 3.67(ailures. Berk)-.1 F(ele)-.1 E(y)-.15 E 1.013
(DB, because of its careful design and implementation,)323.2 148.2 R(of)
323.2 160.2 Q(fers both simplicity and correctness.)-.25 E .759
(The system has a small footprint, mak)323.2 176.4 R .759
(es simple opera-)-.1 F 1.012
(tions simple to carry out \(inserting a ne)323.2 188.4 R 3.512(wr)-.25
G 1.012(ecord tak)-3.512 F(es)-.1 E 1.16(just a fe)323.2 200.4 R 3.66
(wl)-.25 G 1.16(ines of code\), and beha)-3.66 F -.15(ve)-.2 G 3.66(sc)
.15 G 1.16(orrectly in the)-3.66 F -.1(fa)323.2 212.4 S .528(ce of hea)
.1 F .527(vy concurrent use, system crashes, and e)-.2 F -.15(ve)-.25 G
(n).15 E(catastrophic f)323.2 224.4 Q(ailures lik)-.1 E 2.5(el)-.1 G
(oss of a hard disk.)-2.5 E F1 3(5. The)323.2 254.4 R(Berk)3 E
(eley DB 2.x Distrib)-.12 E(ution)-.24 E F0(Berk)323.2 270.6 Q(ele)-.1 E
4.171(yD)-.15 G 4.171(Bi)-4.171 G 4.171(sd)-4.171 G(istrib)-4.171 E
1.671(uted in source code form from)-.2 F/F2 10/Times-Italic@0 SF(www)
323.2 282.6 Q(.sleepycat.com)-.74 E F0 7.322(.U)C 2.322
(sers are free to do)-7.322 F 2.321(wnload and)-.25 F -.2(bu)323.2 294.6
S(ild the softw).2 E(are, and to use it in their applications.)-.1 E F1
3(5.1. What)323.2 324.6 R(is in the distrib)3 E(ution)-.24 E F0 4.827
(The distrib)323.2 340.8 R 4.827(ution is a compressed archi)-.2 F 5.127
-.15(ve \214)-.25 H 7.328(le. It).15 F .057
(includes the source code for the Berk)323.2 352.8 R(ele)-.1 E 2.556(yD)
-.15 G 2.556(Bl)-2.556 G(ibrary)-2.556 E 2.556(,a)-.65 G(s)-2.556 E .453
(well as documentation, test suites, and supporting utili-)323.2 364.8 R
(ties.)323.2 376.8 Q 2.613(The source code includes b)323.2 393 R 2.612
(uild support for all sup-)-.2 F .254(ported platforms.)323.2 405 R .254
(On UNIX systems Berk)5.254 F(ele)-.1 E 2.755(yD)-.15 G 2.755(Bu)-2.755
G(ses)-2.755 E 1.28(the GNU autocon\214guration tool,)323.2 417 R/F3 10
/Courier@0 SF(autoconf)3.78 E F0 3.78(,t)C 3.78(oi)-3.78 G(den-)-3.78 E
.992(tify the system and to b)323.2 429 R .992
(uild the library and supporting)-.2 F 3.589(utilities. Berk)323.2 441 R
(ele)-.1 E 3.589(yD)-.15 G 3.588(Bi)-3.589 G 1.088(ncludes speci\214c b)
-3.588 F 1.088(uild en)-.2 F(viron-)-.4 E .515
(ments for other platforms, such as VMS and W)323.2 453 R(indo)-.4 E
(ws.)-.25 E F1 3(5.1.1. Documentation)323.2 483 R F0 5.008(The distrib)
323.2 499.2 R 5.008(uted system includes documentation in)-.2 F 1.626
(HTML format.)323.2 511.2 R 1.626(The documentation is in tw)6.626 F
4.127(op)-.1 G 1.627(arts: a)-4.127 F .725
(UNIX-style reference manual for use by programmers,)323.2 523.2 R
(and a reference guide which is tutorial in nature.)323.2 535.2 Q F1 3
(5.1.2. T)323.2 565.2 R(est suite)-1.104 E F0 1.107(The softw)323.2
581.4 R 1.108(are also includes a complete test suite, writ-)-.1 F .155
(ten in Tcl.)323.2 593.4 R 1.754 -.8(We b)5.154 H(elie).8 E .454 -.15
(ve t)-.25 H .154(hat the test suite is a k).15 F .454 -.15(ey a)-.1 H
(dv).15 E(an-)-.25 E(tage of Berk)323.2 605.4 Q(ele)-.1 E 2.5(yD)-.15 G
2.5(Bo)-2.5 G -.15(ve)-2.65 G 2.5(rc).15 G(omparable systems.)-2.5 E
2.612(First, the test suite allo)323.2 621.6 R 2.613(ws users who do)
-.25 F 2.613(wnload and)-.25 F -.2(bu)323.2 633.6 S 1.731(ild the softw)
.2 F 1.731(are to be sure that it is operating cor)-.1 F(-)-.2 E(rectly)
323.2 645.6 Q(.)-.65 E .893(Second, the test suite allo)323.2 661.8 R
.894(ws us, lik)-.25 F 3.394(eo)-.1 G .894(ther commercial)-3.394 F(de)
323.2 673.8 Q -.15(ve)-.25 G .536(lopers of database softw).15 F .536
(are, to e)-.1 F -.15(xe)-.15 G .535(rcise the system).15 F 2.256
(thoroughly at e)323.2 685.8 R -.15(ve)-.25 G 2.256(ry release.).15 F
2.256(When we learn of ne)7.256 F(w)-.25 E -.2(bu)323.2 697.8 S 1.719
(gs, we add them to the test suite.).2 F 3.319 -.8(We r)6.719 H 1.719
(un the test).8 F 5.692(suite continually during de)323.2 709.8 R -.15
(ve)-.25 G 5.692(lopment c).15 F 5.692(ycles, and)-.15 F EP
BP
/F0 10/Times-Roman@0 SF(al)79.2 84 Q -.1(wa)-.1 G .314
(ys prior to release.).1 F .314(The result is a much more reli-)5.314 F
(able system by the time it reaches beta release.)79.2 96 Q/F1 12
/Times-Bold@0 SF 3(5.2. Binary)79.2 126 R(distrib)3 E(ution)-.24 E F0
(Sleep)79.2 142.2 Q .893(ycat mak)-.1 F .893
(es compiled libraries and general binary)-.1 F(distrib)79.2 154.2 Q
(utions a)-.2 E -.25(va)-.2 G(ilable to customers for a fee.).25 E F1 3
(5.3. Supported)79.2 184.2 R(platf)3 E(orms)-.3 E F0(Berk)79.2 200.4 Q
(ele)-.1 E 5.623(yD)-.15 G 5.623(Br)-5.623 G 3.123(uns on an)-5.623 F
5.622(yo)-.15 G 3.122(perating system with a)-5.622 F .816
(POSIX 1003.1 interf)79.2 212.4 R .817(ace [IEEE96], which includes vir)
-.1 F(-)-.2 E 1.998(tually e)79.2 224.4 R -.15(ve)-.25 G 1.997
(ry UNIX system.).15 F 1.997(In addition, the softw)6.997 F(are)-.1 E
2.85(runs on VMS, W)79.2 236.4 R(indo)-.4 E 2.85(ws/95, W)-.25 F(indo)
-.4 E 2.85(ws/98, and W)-.25 F(in-)-.4 E(do)79.2 248.4 Q(ws/NT)-.25 E
10.21(.S)-.74 G(leep)-10.21 E 5.21(ycat Softw)-.1 F 5.21
(are no longer supports)-.1 F(deplo)79.2 260.4 Q(yment on sixteen-bit W)
-.1 E(indo)-.4 E(ws systems.)-.25 E F1 3(6. Berk)79.2 290.4 R
(eley DB 2.x Licensing)-.12 E F0(Berk)79.2 306.6 Q(ele)-.1 E 2.627(yD)
-.15 G 2.627(B2)-2.627 G .128(.x is distrib)-2.627 F .128
(uted as an Open Source prod-)-.2 F 4.709(uct. The)79.2 318.6 R(softw)
4.709 E 2.209(are is freely a)-.1 F -.25(va)-.2 G 2.209
(ilable from us at our).25 F -.8(We)79.2 330.6 S 3.372(bs).8 G .872
(ite, and in other media.)-3.372 F .872(Users are free to do)5.872 F
(wn-)-.25 E(load the softw)79.2 342.6 Q(are and b)-.1 E
(uild applications with it.)-.2 E 1.023(The 1.x v)79.2 358.8 R 1.022
(ersions of Berk)-.15 F(ele)-.1 E 3.522(yD)-.15 G 3.522(Bw)-3.522 G
1.022(ere co)-3.522 F -.15(ve)-.15 G 1.022(red by the).15 F 3.763
(UC Berk)79.2 370.8 R(ele)-.1 E 6.263(yc)-.15 G(op)-6.263 E 3.763
(yright that co)-.1 F -.15(ve)-.15 G 3.764(rs softw).15 F 3.764
(are freely)-.1 F(redistrib)79.2 382.8 Q 1.742(utable in source form.)
-.2 F 1.741(When Sleep)6.742 F 1.741(ycat Soft-)-.1 F -.1(wa)79.2 394.8
S .906(re w).1 F .907(as formed, we needed to draft a license consis-)
-.1 F 2.319(tent with the cop)79.2 406.8 R 2.319(yright go)-.1 F -.15
(ve)-.15 G 2.318(rning the e).15 F 2.318(xisting, older)-.15 F(softw)
79.2 418.8 Q 5.328(are. Because)-.1 F 2.828(of important dif)5.328 F
2.828(ferences between)-.25 F .497(the UC Berk)79.2 430.8 R(ele)-.1 E
2.997(yc)-.15 G(op)-2.997 E .497(yright and the GPL, it w)-.1 F .496
(as impos-)-.1 F .884(sible for us to use the GPL.)79.2 442.8 R 3.384
(As)5.884 G .884(econd cop)-3.384 F .884(yright, with)-.1 F .87
(terms contradictory to the \214rst, simply w)79.2 454.8 R .87
(ould not ha)-.1 F -.15(ve)-.2 G -.1(wo)79.2 466.8 S(rk).1 E(ed.)-.1 E
(Sleep)79.2 483 Q 2.533(ycat w)-.1 F 2.533
(anted to continue Open Source de)-.1 F -.15(ve)-.25 G(lop-).15 E 2.079
(ment of Berk)79.2 495 R(ele)-.1 E 4.579(yD)-.15 G 4.579(Bf)-4.579 G
2.079(or se)-4.579 F -.15(ve)-.25 G 2.079(ral reasons.).15 F 3.678 -.8
(We a)7.078 H(gree).8 E .853
(with Raymond [Raym98] and others that Open Source)79.2 507 R(softw)79.2
519 Q .763(are is typically of higher quality than proprietary)-.1 F(,)
-.65 E 2.616(binary-only products.)79.2 531 R 2.617
(Our customers bene\214t from a)7.616 F .983(community of de)79.2 543 R
-.15(ve)-.25 G .983(lopers who kno).15 F 3.483(wa)-.25 G .983
(nd use Berk)-3.483 F(ele)-.1 E(y)-.15 E 1.317
(DB, and can help with application design, deb)79.2 555 R(ugging,)-.2 E
1.65(and performance tuning.)79.2 567 R -.4(Wi)6.65 G 1.65
(despread distrib).4 F 1.65(ution and)-.2 F 1.017
(use of the source code tends to isolate b)79.2 579 R 1.017(ugs early)
-.2 F 3.517(,a)-.65 G(nd)-3.517 E .032(to get \214x)79.2 591 R .031
(es back into the distrib)-.15 F .031(uted system quickly)-.2 F 5.031
(.A)-.65 G(s)-5.031 E 3.553(ar)79.2 603 S 1.053(esult, Berk)-3.553 F
(ele)-.1 E 3.553(yD)-.15 G 3.553(Bi)-3.553 G 3.553(sm)-3.553 G 1.053
(ore reliable.)-3.553 F 1.054(Just as impor)6.054 F(-)-.2 E(tantly)79.2
615 Q 3.695(,i)-.65 G(ndi)-3.695 E 1.195
(vidual users are able to contrib)-.25 F 1.195(ute ne)-.2 F 3.695(wf)
-.25 G(ea-)-3.695 E 1.056
(tures and performance enhancements, to the bene\214t of)79.2 627 R
-2.15 -.25(ev e)79.2 639 T .359(ryone who uses Berk).25 F(ele)-.1 E
2.859(yD)-.15 G 2.859(B. From)-2.859 F 2.858(ab)2.859 G .358
(usiness per)-3.058 F(-)-.2 E(specti)79.2 651 Q -.15(ve)-.25 G 3.115(,O)
.15 G .615(pen Source and free distrib)-3.115 F .615(ution of the soft-)
-.2 F -.1(wa)79.2 663 S 1.605(re creates share for us, and gi).1 F -.15
(ve)-.25 G 4.105(su).15 G 4.105(sam)-4.105 G(ark)-4.105 E 1.605(et into)
-.1 F .412(which we can sell products and services.)79.2 675 R(Finally)
5.413 E 2.913(,m)-.65 G(ak-)-2.913 E .148(ing the source code freely a)
79.2 687 R -.25(va)-.2 G .147(ilable reduces our support).25 F 2.436
(load, since customers can \214nd and \214x b)79.2 699 R 2.437
(ugs without)-.2 F(recourse to us, in man)79.2 711 Q 2.5(yc)-.15 G
(ases.)-2.5 E 4.727 -.8(To p)323.2 84 T(reserv).8 E 5.627(et)-.15 G
3.126(he Open Source heritage of the older)-5.627 F(Berk)323.2 96 Q(ele)
-.1 E 3.003(yD)-.15 G 3.003(Bc)-3.003 G .504(ode, we drafted a ne)-3.003
F 3.004(wl)-.25 G .504(icense go)-3.004 F -.15(ve)-.15 G(rning).15 E
.417(the distrib)323.2 108 R .417(ution of Berk)-.2 F(ele)-.1 E 2.916
(yD)-.15 G 2.916(B2)-2.916 G 2.916(.x. W)-2.916 F 2.916(ea)-.8 G .416
(dopted terms)-2.916 F .411(from the GPL that mak)323.2 120 R 2.911(ei)
-.1 G 2.911(ti)-2.911 G .411(mpossible to turn our Open)-2.911 F 1.289
(Source code into proprietary code o)323.2 132 R 1.288(wned by someone)
-.25 F(else.)323.2 144 Q(Brie\215y)323.2 160.2 Q 3.18(,t)-.65 G .68
(he terms go)-3.18 F -.15(ve)-.15 G .68(rning the use and distrib).15 F
.68(ution of)-.2 F(Berk)323.2 172.2 Q(ele)-.1 E 2.5(yD)-.15 G 2.5(Ba)
-2.5 G(re:)-2.5 E/F2 8/Times-Roman@0 SF<83>328.2 188.4 Q F0
(your application must be internal to your site, or)17.2 E F2<83>328.2
204.6 Q F0 .612(your application must be freely redistrib)17.2 F .611
(utable in)-.2 F(source form, or)348.2 216.6 Q F2<83>328.2 232.8 Q F0
(you must get a license from us.)17.2 E -.15(Fo)323.2 249 S 2.631(rc).15
G .131(ustomers who prefer not to distrib)-2.631 F .132(ute Open Source)
-.2 F 1.493(products, we sell licenses to use and e)323.2 261 R 1.492
(xtend Berk)-.15 F(ele)-.1 E(y)-.15 E(DB at a reasonable cost.)323.2 273
Q 2.675 -.8(We w)323.2 289.2 T 1.076
(ork hard to accommodate the needs of the Open).7 F .606
(Source community)323.2 301.2 R 5.606(.F)-.65 G .606(or e)-5.756 F .606
(xample, we ha)-.15 F .905 -.15(ve c)-.2 H .605(rafted spe-).15 F 1.415
(cial licensing arrangements with Gnome to encourage)323.2 313.2 R
(its use and distrib)323.2 325.2 Q(ution of Berk)-.2 E(ele)-.1 E 2.5(yD)
-.15 G(B.)-2.5 E(Berk)323.2 341.4 Q(ele)-.1 E 4.103(yD)-.15 G 4.103(Bc)
-4.103 G 1.603(onforms to the Open Source de\214nition)-4.103 F 4.867
([Open99]. The)323.2 353.4 R 2.367
(license has been carefully crafted to)4.867 F -.1(ke)323.2 365.4 S .643
(ep the product a).1 F -.25(va)-.2 G .642(ilable as an Open Source of)
.25 F(fering,)-.25 E(while pro)323.2 377.4 Q
(viding enough of a return on our in)-.15 E -.15(ve)-.4 G(stment to).15
E 1.546(fund continued de)323.2 389.4 R -.15(ve)-.25 G 1.546
(lopment and support of the prod-).15 F 3.033(uct. The)323.2 401.4 R
.534(current license has created a b)3.033 F .534(usiness capable)-.2 F
.916(of funding three years of de)323.2 413.4 R -.15(ve)-.25 G .916
(lopment on the softw).15 F(are)-.1 E(that simply w)323.2 425.4 Q
(ould not ha)-.1 E .3 -.15(ve h)-.2 H(appened otherwise.).15 E F1 3
(7. Summary)323.2 455.4 R F0(Berk)323.2 471.6 Q(ele)-.1 E 2.991(yD)-.15
G 2.991(Bo)-2.991 G -.25(ff)-2.991 G .491
(ers a unique collection of features, tar).25 F(-)-.2 E .175
(geted squarely at softw)323.2 483.6 R .174(are de)-.1 F -.15(ve)-.25 G
.174(lopers who need simple,).15 F .492
(reliable database management services in their applica-)323.2 495.6 R
5.3(tions. Good)323.2 507.6 R 2.8(design and implementation and careful)
5.3 F 1.633(engineering throughout mak)323.2 519.6 R 4.133(et)-.1 G
1.633(he softw)-4.133 F 1.634(are better than)-.1 F(man)323.2 531.6 Q
2.5(yo)-.15 G(ther systems.)-2.5 E(Berk)323.2 547.8 Q(ele)-.1 E 4.1(yD)
-.15 G 4.1(Bi)-4.1 G 4.1(sa)-4.1 G 4.1(nO)-4.1 G 1.6
(pen Source product, a)-4.1 F -.25(va)-.2 G 1.6(ilable at).25 F/F3 10
/Times-Italic@0 SF(www)323.2 559.8 Q(.sleepycat.com)-.74 E F0 .654
(for do)3.154 F 3.154(wnload. The)-.25 F(distrib)3.154 E .654(uted sys-)
-.2 F .383(tem includes e)323.2 571.8 R -.15(ve)-.25 G .383
(rything needed to b).15 F .382(uild and deplo)-.2 F 2.882(yt)-.1 G(he)
-2.882 E(softw)323.2 583.8 Q(are or to port it to ne)-.1 E 2.5(ws)-.25 G
(ystems.)-2.5 E(Sleep)323.2 600 Q 2.633(ycat Softw)-.1 F 2.633
(are distrib)-.1 F 2.633(utes Berk)-.2 F(ele)-.1 E 5.133(yD)-.15 G 5.134
(Bu)-5.133 G 2.634(nder a)-5.134 F .764(license agreement that dra)323.2
612 R .764(ws on both the UC Berk)-.15 F(ele)-.1 E(y)-.15 E(cop)323.2
624 Q 2.377(yright and the GPL.)-.1 F 2.377(The license guarantees that)
7.377 F(Berk)323.2 636 Q(ele)-.1 E 3.384(yD)-.15 G 3.384(Bw)-3.384 G
.884(ill remain an Open Source product and)-3.384 F(pro)323.2 648 Q
1.493(vides Sleep)-.15 F 1.493(ycat with opportunities to mak)-.1 F
3.994(em)-.1 G(one)-3.994 E(y)-.15 E(to fund continued de)323.2 660 Q
-.15(ve)-.25 G(lopment on the softw).15 E(are.)-.1 E EP
BP
/F0 12/Times-Bold@0 SF 3(8. Refer)79.2 84 R(ences)-.216 E/F1 10
/Times-Roman@0 SF([Come79])79.2 100.2 Q(Comer)104.2 112.2 Q 3.127(,D)-.4
G .627(., \231The Ubiquitous B-tree,)-3.127 F<9a>-.7 E/F2 10
/Times-Italic@0 SF -.3(AC)3.126 G 3.126(MC).3 G(om-)-3.126 E .404
(puting Surve)104.2 124.2 R(ys)-.3 E F1 -1.29(Vo)2.904 G .404
(lume 11, number 2, June 1979.)1.29 F([Gray93])79.2 140.4 Q(Gray)104.2
152.4 Q 2.982(,J)-.65 G .482(., and Reuter)-2.982 F 2.982(,A)-.4 G(.,)
-2.982 E F2 -1.55 -.55(Tr a)2.981 H .481(nsaction Pr).55 F(ocessing:)
-.45 E 6.776(Concepts and T)104.2 164.4 R(ec)-.92 E(hniques)-.15 E F1
9.277(,M)C(or)-9.277 E -.05(ga)-.18 G(n-Kaufman).05 E(Publishers, 1993.)
104.2 176.4 Q([IEEE96])79.2 192.6 Q .364
(Institute for Electrical and Electronics Engineers,)104.2 204.6 R F2
(IEEE/ANSI Std 1003.1)104.2 216.6 Q F1 2.5(,1)C(996 Edition.)-2.5 E
([Litw80])79.2 232.8 Q 2.365(Litwin, W)104.2 244.8 R 2.366
(., \231Linear Hashing: A Ne)-.92 F 4.866(wT)-.25 G 2.366(ool for)-5.666
F 1.784(File and T)104.2 256.8 R 1.783(able Addressing,)-.8 F<9a>-.7 E
F2(Pr)4.283 E 1.783(oceedings of the)-.45 F 4.804
(6th International Confer)104.2 268.8 R 4.804(ence on V)-.37 F 4.804
(ery Lar)-1.11 F -.1(ge)-.37 G 1.983(Databases \(VLDB\))104.2 280.8 R F1
4.483(,M)C 1.982(ontreal, Quebec, Canada,)-4.483 F(October 1980.)104.2
292.8 Q([Open94])79.2 309 Q 4.068(The Open Group,)104.2 321 R F2
(Distrib)6.568 E 4.069(uted TP: The XA+)-.2 F .78(Speci\214cation, V)
104.2 333 R(er)-1.11 E .78(sion 2)-.1 F F1 3.28(,T)C .78
(he Open Group, 1994.)-3.28 F([Open99])79.2 349.2 Q(Opensource.or)104.2
361.2 Q 8.307(g, \231Open Source De\214nition,)-.18 F<9a>-.7 E F2(www)
104.2 373.2 Q(.opensour)-.74 E(ce)-.37 E(.or)-.15 E(g/osd.html)-.37 E F1
3.13(,v)C .63(ersion 1.4, 1999.)-3.28 F([Raym98])79.2 389.4 Q .718
(Raymond, E.S., \231The Cathedral and the Bazaar)104.2 401.4 R -.7<2c9a>
-.4 G F2(www)104.2 413.4 Q(.tuxedo.or)-.74 E(g/~esr/writings/cathedr)
-.37 E(al-)-.15 E(bazaar/cathedr)104.2 425.4 Q(al-bazaar)-.15 E(.html)
-1.11 E F1 2.5(,J)C(anuary 1998.)-2.5 E([Selt91])79.2 441.6 Q(Seltzer)
104.2 453.6 Q 2.578(,M)-.4 G .078(., and Y)-2.578 F .079(igit, O., \231)
-.55 F 2.579(AN)-.8 G .579 -.25(ew H)-2.579 H .079(ashing P).25 F(ack-)
-.15 E 6.704(age for UNIX,)104.2 465.6 R<9a>-.7 E F2(Pr)9.204 E 6.704
(oceedings 1991 W)-.45 F(inter)-.55 E(USENIX Confer)104.2 477.6 Q(ence)
-.37 E F1 2.5(,D)C(allas, TX, January 1991.)-2.5 E([Selt92])79.2 493.8 Q
(Seltzer)104.2 505.8 Q 5.365(,M)-.4 G 2.865
(., and Olson, M., \231LIBTP: Portable)-5.365 F 2.845(Modular T)104.2
517.8 R 2.845(ransactions for UNIX,)-.35 F<9a>-.7 E F2(Pr)5.345 E
(oceedings)-.45 E 1.49(1992 W)104.2 529.8 R 1.49(inter Usenix Confer)
-.55 F(ence)-.37 E F1 3.99(,S)C 1.49(an Francisco,)-3.99 F
(CA, January 1992.)104.2 541.8 Q([Ston82])79.2 558 Q(Stonebrak)104.2 570
Q(er)-.1 E 10.04(,M)-.4 G 7.54(., Stettner)-10.04 F 10.04(,H)-.4 G 7.54
(., Kalash, J.,)-10.04 F .763(Guttman, A., and L)104.2 582 R .764
(ynn, N., \231Document Process-)-.55 F .557
(ing in a Relational Database System,)104.2 594 R 3.056<9a4d>-.7 G
(emoran-)-3.056 E .825(dum No. UCB/ERL M82/32, Uni)104.2 606 R -.15(ve)
-.25 G .825(rsity of Cali-).15 F(fornia at Berk)104.2 618 Q(ele)-.1 E
1.3 -.65(y, B)-.15 H(erk).65 E(ele)-.1 E 1.3 -.65(y, C)-.15 H
(A, May 1982.).65 E EP
end