%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: trees.dvi %%Pages: 7 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -f trees.dvi %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2000.05.06:2055 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[ matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{ statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0] N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin /FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array /BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr 1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{ rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B /chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse} ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17 {2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{ 1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put }if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{ bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{ SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{ userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X 1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N /p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M} B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{ p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end %%EndProcSet TeXDict begin 39158280 55380996 1000 600 600 (trees.dvi) @start %DVIPSBitmapFont: Fa cmr10 10 6 /Fa 6 55 df<146014E0EB01C0EB0380EB0700130E131E5B5BA25B485AA2485AA212075B 120F90C7FCA25A121EA2123EA35AA65AB2127CA67EA3121EA2121F7EA27F12077F1203A2 6C7EA26C7E1378A27F7F130E7FEB0380EB01C0EB00E01460135278BD20>40 D<12C07E12707E7E7E120F6C7E6C7EA26C7E6C7EA21378A2137C133C133E131EA2131F7F A21480A3EB07C0A6EB03E0B2EB07C0A6EB0F80A31400A25B131EA2133E133C137C1378A2 5BA2485A485AA2485A48C7FC120E5A5A5A5A5A13527CBD20>I<15301578B3A6007FB812 F8B912FCA26C17F8C80078C8FCB3A6153036367BAF41>43 D48 DI54 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb cmr7 7 3 /Fb 3 55 df48 D<13381378EA01F8121F12FE12E01200B3AB487EB512F8A2 15267BA521>I54 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc cmmi10 10 1 /Fc 1 69 df<0103B7FC4916E018F8903B0007F80007FE4BEB00FFF03F80020FED1FC018 0F4B15E0F007F0021F1503A24B15F81801143F19FC5DA2147FA292C8FCA25C18035CA213 0119F84A1507A2130319F04A150FA2010717E0181F4A16C0A2010FEE3F80A24AED7F0018 7E011F16FE4D5A4A5D4D5A013F4B5A4D5A4A4A5A057FC7FC017F15FEEE03FC91C7EA0FF0 49EC7FC0B8C8FC16FC16C03E397DB845>68 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd ectt1000 10 73 /Fd 73 126 df37 D39 D<143814FC13011303EB07F8EB0FF0EB1FC0EB3F80EB7F0013FE485A485A5B12075B120F 5B485AA2123F90C7FCA25A127EA312FE5AAC7E127EA3127F7EA27F121FA26C7E7F12077F 12037F6C7E6C7E137FEB3F80EB1FC0EB0FF0EB07F8EB03FC130113001438164272B92C> I<127012FC7E7E6C7E6C7EEA0FE06C7E6C7E6C7E6C7E137F7F1480131F14C0130FEB07E0 A214F01303A214F81301A314FC1300AC130114F8A3130314F0A2130714E0A2EB0FC0131F 1480133F14005B13FE485A485A485A485AEA3FC0485A48C7FC5A5A1270164279B92C>I< EB0380497EA60020140800F8143E00FE14FE00FF13C1EBC7C7EBE7CF003FB512F8000F14 E0000314806C140038007FFCA248B5FC481480000F14E0003F14F839FFE7CFFEEBC7C7EB 07C100FE13C000F8143E0020140800001400A66D5A1F247AAA2C>I<147014F8AF003FB6 12E0B712F8A4C700F8C7FCB0147025267DAB2C>II<121FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80EA1F000B0B708A2C>46 D<1507ED0F80A2151F16005D153E157E157CA215FC5D14015D14035D14075D140F5D141F 92C7FC5C143EA2147E147C14FC5C13015C13035C13075C130F5C131F91C8FC5B133EA213 7E137C13FC5B12015B12035B12075B120F5B121F90C9FCA25A123E127E127C12FC5AA212 7021417BB92C>II<1307497EA2131F A2133F137F13FF5A1207127FB5FC13DF139FEA7C1F1200B3AE007FB512E0B612F0A36C14 E01C3477B32C>II<000FB512FE4880A35D0180C8FCADEB83FE90389FFF8090B512E015F881 9038FE03FE9038F000FF01C07F49EB3F8090C7121F6C15C0C8120FA2ED07E0A4123C127E B4FC150F16C0A248141F007EEC3F80007FEC7F006C6C5B6D485A391FF80FFC6CB55A6C5C 000114C06C6C90C7FCEB0FF823347CB22C>53 DI<1278B712C016E0A316C000FCC7EA3F80ED7F0015FE00785CC712014A 5A4A5A5D140F5D4A5A143F92C7FC5C147E14FE5C13015CA2495AA213075CA3495AA4495A A5133F91C8FCAA131E23357CB32C>I59 D<1502ED0F80151F157F15 FF913803FE00EC0FFCEC1FF0EC7FE0ECFF80D903FEC7FC495AEB1FF0495AEBFF80000390 C8FCEA07FCEA1FF8EA3FE0EAFF8090C9FCA27FEA3FE0EA1FF8EA07FC6CB4FCC67FEB3FE0 6D7EEB07FC6D7E903800FF80EC7FE0EC1FF0EC0FFCEC03FE913800FF80157F151F150FED 0200212A7BAD2C>I<007FB612F0B712F8A36C15F0CAFCA8007FB612F0B712F8A36C15F0 25127DA12C>I<122012F87EB4FC7FEA3FE0EA1FF8EA07FC6CB4FCC67FEB3FE06D7EEB07 FC6D7E903800FF80EC7FE0EC1FF0EC0FFCEC03FE913800FF80157FA215FF913803FE00EC 0FFCEC1FF0EC7FE0ECFF80D903FEC7FC495AEB1FF0495AEBFF80000390C8FCEA07FCEA1F F8EA3FE0EAFF8090C9FC12FC5A1220212A7BAD2C>I<14FE497EA4497FA214EFA2130781 A214C7A2010F7FA314C390381F83F0A590383F01F8A490387E00FCA549137E90B512FEA3 4880A29038F8003FA34848EB1F80A4000715C049130FD87FFEEBFFFC6D5AB514FE6C15FC 497E27347EB32C>65 D<007FB512E015F8B612FE6C8016C03903F0003FED0FE0ED07F015 03A2ED01F8A6ED03F0A21507ED0FE0ED1FC0EDFF8090B612005D5D15FF16C09039F0001F E0ED07F0ED03F81501ED00FCA216FE167EA616FE16FC1501ED03F8150FED3FF0007FB612 E016C0B712806CECFE0015F027337FB22C>I<02FF13700107EBE0F84913F9013F13FD49 13FFEBFF813901FE007F4848131FD807F0130F1507485A491303485A150148C7FCA25A00 7EEC00F01600A212FE5AAB7E127EA3007F15F06CEC01F8A26C7EA26C6C13036D14F06C6C 130716E0D803FC131F6C6CEB3FC03A00FF81FF806DB512006D5B010F5B6D13F001001380 25357DB32C>I<007FB5FCB612C015F0816C803907E003FEEC00FFED7F80153FED1FC0ED 0FE0A2150716F0150316F81501A4ED00FCACED01F8A3150316F0A2150716E0150FED1FC0 153FED7F80EDFF00EC03FE007FB55AB65A5D15C06C91C7FC26337EB22C>I<007FB612F0 B712F8A37E3903F00001A7ED00F01600A4EC01E04A7EA490B5FCA5EBF003A46E5A91C8FC A5163C167EA8007FB612FEB7FCA36C15FC27337EB22C>I<007FB612F8B712FCA37ED803 F0C7FCA716781600A515F04A7EA490B5FCA5EBF001A46E5A92C7FCAD387FFFE0B5FC805C 7E26337EB22C>I<903901FC038090390FFF87C04913EF017F13FF90B6FC4813073803FC 01497E4848137F4848133F49131F121F5B003F140F90C7FCA2127EED078092C7FCA212FE 5AA8913803FFF84A13FCA27E007E6D13F89138000FC0A36C141FA27F121F6D133F120F6D 137F6C7E6C6C13FF6D5A3801FF076C90B5FC6D13EF011F13CF6DEB0780D901FCC7FC2635 7DB32C>II<007FB512F8B612FCA36C14 F839000FC000B3B3A5007FB512F8B612FCA36C14F81E3379B22C>I75 D<387FFFE0B57EA36C5BD803F0C8FCB3AE16F0 ED01F8A8007FB6FCB7FCA36C15F025337DB22C>IIII<007FB512C0B612 F88115FF6C15802603F00013C0153FED0FE0ED07F0A2150316F81501A6150316F01507A2 ED0FE0ED3FC015FF90B61280160015FC5D15C001F0C8FCB0387FFF80B57EA36C5B25337E B22C>II<387FFFFCB67E15E015F86C803907E007FE1401EC007F6F7E151FA2 6F7EA64B5AA2153F4BC7FCEC01FE140790B55A5D15E081819038E007FCEC01FE1400157F 81A8160FEE1F80A5D87FFEEB1FBFB5ECFF00815E6C486D5AC8EA01F029347EB22C>I<90 381FF80790B5EA0F804814CF000714FF5A381FF01F383FC003497E48C7FC007E147F00FE 143F5A151FA46CEC0F00007E91C7FC127F7FEA3FE0EA1FFCEBFFC06C13FC0003EBFFC06C 14F06C6C7F01077F9038007FFEEC07FF02001380153FED1FC0A2ED0FE0A20078140712FC A56CEC0FC0A26CEC1F806D133F01E0EB7F009038FE01FF90B55A5D00F914F0D8F83F13C0 D8700790C7FC23357CB32C>I<007FB612FCB712FEA43AFC007E007EA70078153CC71400 B3AF90383FFFFCA2497F6D5BA227337EB22C>I<3B7FFF803FFFC0B56C4813E0A36C496C 13C03B03F00001F800B3AF6D130300015DA26D130700005D6D130F017F495A6D6C485AEC E0FF6DB5C7FC6D5B010313F86D5B9038003F802B3480B22C>III<3A3FFF03FFE0484913F0148714076C6D13E03A01 F800FE007F0000495A13FE017E5BEB7F03013F5B1487011F5B14CF010F5B14FF6D5BA26D 90C7FCA26D5AA26D5AA2497EA2497EA2497F81EB0FCF81EB1FC7EC87F0EB3F83EC03F8EB 7F01017E7FEBFE00497F0001147E49137F000380491480151FD87FFEEBFFFC6D5AB514FE 6C15FC497E27337EB22C>II<387FFFFCB512FEA314FC00FCC7FCB3B3B3B512FC14FEA36C13FC 17416FB92C>91 D<127012F8A27E127C127E123E123F7EA27F120F7F12077F12037F1201 7F12007F137C137E133EA2133F7F80130F80130780130380130180130080147C147E143E A2143F8081140F81140781140381140181140081157CA2157E153E153F811680150FA2ED 070021417BB92C>I<387FFFFCB512FEA37EC7127EB3B3B3387FFFFEB5FCA36C13FC1741 7DB92C>II<007FB6FCB71280A46C150021067B7D 2C>I<1338137CEA01FC1203EA07F813F0EA0FC0EA1F80A2EA3F00123E127E127CA212FC 5AA3EAFFC013E013F013F8A2127FA2123F13F0EA1FE0EA07C00E1D72B82C>I<3801FFF0 000713FE001F6D7E15E048809038C01FF81407EC01FC381F80000006C77EC8127EA3ECFF FE131F90B5FC1203120F48EB807E383FF800EA7FC090C7FC12FE5AA47E007F14FEEB8003 383FE01F6CB612FC6C15FE6C14BF0001EBFE1F3A003FF007FC27247CA32C>II<90 3803FFE0011F13F8017F13FE48B5FC48804848C6FCEA0FF0485A49137E4848131890C9FC 5A127EA25AA8127EA2127F6C140F6DEB1F806C7E6D133F6C6CEB7F003907FE03FF6CB55A 6C5C6C6C5B011F13E0010390C7FC21247AA32C>III103 DI< 1307EB1FC0A2497EA36D5AA20107C7FC90C8FCA7387FFFC080B5FC7EA2EA0007B3A8007F B512FCB612FEA36C14FC1F3479B32C>I107 D<387FFFE0B57EA37EEA0003B3B3A5007F B61280B712C0A36C158022337BB22C>I<3A7F83F007E09039CFFC1FF83AFFDFFE3FFCD8 7FFF13FF91B57E3A07FE1FFC3E01FCEBF83F496C487E01F013E001E013C0A301C01380B3 3B7FFC3FF87FF0027F13FFD8FFFE6D13F8D87FFC4913F0023F137F2D2481A32C>I<397F F01FE039FFF87FFC9038F9FFFE01FB7F6CB6FC00019038F03F80ECC01F02807FEC000F5B 5BA25BB3267FFFE0B5FCB500F11480A36C01E0140029247FA32C>II<397FF01FE0 39FFF8FFF801FB13FE90B6FC6C158000019038F07FC09138801FE091380007F049EB03F8 5BED01FC491300A216FE167EA816FE6D14FCA2ED01F86D13036DEB07F0150F9138801FE0 9138E07FC091B51280160001FB5B01F813F8EC3FC091C8FCAD387FFFE0B57EA36C5B2736 7FA32C>I<903903FC078090391FFF0FC0017F13CF48B512EF4814FF3807FE07380FF001 48487E49137F4848133F90C7FC48141F127E150F5AA87E007E141FA26C143F7F6C6C137F 6D13FF380FF0033807FC0F6CB6FC6C14EF6C6C138F6D130FEB07F890C7FCAD0203B5FC4A 1480A36E140029367DA32C>II<90387FF8700003B512F8120F5A5A387FC00F387E00034813015AA36CEB 00F0007F140013F0383FFFC06C13FE6CEBFF80000314E0C66C13F8010113FCEB0007EC00 FE0078147F00FC143F151F7EA26C143F6D133E6D13FE9038F007FC90B5FC15F815E000F8 148039701FFC0020247AA32C>I<131E133FA9007FB6FCB71280A36C1500D8003FC8FCB1 ED03C0ED07E0A5EC800F011FEB1FC0ECE07F6DB51280160001035B6D13F89038003FE023 2E7EAD2C>I<3A7FF003FF80486C487FA3007F7F0001EB000FB3A3151FA2153F6D137F39 00FE03FF90B7FC6D15807F6D13CF902603FE07130029247FA32C>I<3A3FFF03FFF04801 8713F8A36C010313F03A00FC007E005D90387E01F8013F5BEB1F83EC87E090380FCFC090 3807EF80EB03FF6D90C7FC5C6D5A147C14FE130180903803EF80903807CFC0EB0FC7EC83 E090381F01F0013F7FEB7E00017C137C49137E0001803A7FFF01FFFC1483B514FE6C15FC 140127247EA32C>120 D<3A7FFF01FFFCB5008113FE148314816C010113FC3A03E0000F 806C7E151F6D140012005D6D133E137C017E137E013E137CA2013F13FC6D5BA2EB0F815D A2EB07C1ECC3E0A2EB03E3ECE7C0130114F75DEB00FFA292C7FC80A2143EA2147E147CA2 14FC5CA2EA0C01003F5BEA7F83EB87E0EA7E0F495A387FFF806C90C8FC6C5A6C5AEA07E0 27367EA32C>I<15FF02071380141F147F91B512004913C04AC7FCEB03F85CB31307EB1F E013FF007F5BB55A49C8FC6D7E6C7FC67F131FEB07F01303B380EB01FEECFFC06D13FF6E 1380141F14070200130021417BB92C>123 D<127812FCB3B3B3A9127806416DB92C>II E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe ecti1000 10 33 /Fe 33 122 df28 D<150C151C153815F0EC01E0EC03C0EC0780EC0F00141E5C147C5C5C495A1303 495A5C130F49C7FCA2133EA25BA25BA2485AA212035B12075BA2120F5BA2121FA290C8FC A25AA2123EA2127EA2127CA412FC5AAD1278A57EA3121C121EA2120E7EA26C7E6C7EA212 001E5274BD22>40 D<140C140E80EC0380A2EC01C015E0A2140015F0A21578A4157C153C AB157CA715FCA215F8A21401A215F0A21403A215E0A21407A215C0140F1580A2141F1500 A2143EA25CA25CA2495AA2495A5C1307495A91C7FC5B133E133C5B5B485A12035B48C8FC 120E5A12785A12C01E527FBD22>I<4B7EA3150393C8FCA35D1506A3150E150CA3151C15 18A315381530A31570B912E0A2C80060C8FC15E05DA314015DA3140392C9FCA35C1406A3 140E140CA3141C1418A2333275AD40>43 DI<120E EA3F80127F12FFA31300127E123C0909778819>46 D<0103B612FEEFFFC018F0903B0007 F8000FF84BEB03FCEF00FE020F157FF03F804B141F19C0021F150F19E05D1807143F19F0 5DA2147FA292C8FCA25C180F5CA2130119E04A151FA2130319C04A153FA201071780187F 4A1600A2010F16FEA24A4A5A60011F15034D5A4A5D4D5A013F4B5A173F4A4AC7FC17FC01 7FEC03F84C5A91C7EA1FC04949B45A007F90B548C8FCB712F016803C397CB83F>68 D<0103B512F8A390390007F8005DA2140FA25DA2141FA25DA2143FA25DA2147FA292C7FC A25CA25CA21301A25CA21303A25CA21307A25CA2130FA25CA2131FA25CA2133FA25CA213 7FA291C8FC497EB6FCA25C25397CB820>73 D<0107B512FCA25E9026000FF8C7FC5D5D14 1FA25DA2143FA25DA2147FA292C8FCA25CA25CA21301A25CA21303A25CA21307A25CA213 0F170C4A141CA2011F153C17384A1478A2013F157017F04A14E01601017F140317C091C7 1207160F49EC1F80163F4914FF000102071300B8FCA25E2E397BB834>76 D79 D81 D<92383FC00E913901FFF01C020713FC91 391FC07E3C91393F001F7C027CEB0FF84A130749481303495A4948EB01F0A2495AA2011F 15E091C7FCA34915C0A36E90C7FCA2806D7E14FCECFF806D13F015FE6D6D7E6D14E00100 80023F7F14079138007FFC150F15031501A21500A2167C120EA3001E15FC5EA3003E4A5A A24B5AA2007F4A5A4B5A6D49C7FC6D133ED8F9F013FC39F8FC03F839F07FFFE0D8E01F13 8026C003FCC8FC2F3D7ABA2F>83 D<0007B812E0A25AD9F800EB001F01C049EB07C0485A D900011403121E001C5C003C17801403123800785C00701607140700F01700485CA2140F C792C7FC5DA2141FA25DA2143FA25DA2147FA292C9FCA25CA25CA21301A25CA21303A25C A21307A25CA2130FA25CEB3FF0007FB512F8B6FCA2333971B83B>I<14F8EB07FE90381F 871C90383E03FE137CEBF801120148486C5A485A120FEBC001001F5CA2EA3F801403007F 5C1300A21407485C5AA2140F5D48ECC1C0A2141F15831680143F1587007C017F1300ECFF 076C485B9038038F8E391F0F079E3907FE03FC3901F000F0222677A42A>97 D<133FEA1FFFA3C67E137EA313FE5BA312015BA312035BA31207EBE0F8EBE7FE9038EF0F 80390FFC07C013F89038F003E013E0D81FC013F0A21380A2123F1300A214075A127EA214 0F12FE4814E0A2141F15C05AEC3F80A215005C147E5C387801F8007C5B383C03E0383E07 C0381E1F80D80FFEC7FCEA01F01C3B77B926>I<147F903803FFC090380FC1E090381F00 70017E13784913383901F801F83803F003120713E0120FD81FC013F091C7FC485AA2127F 90C8FCA35A5AA45AA3153015381578007C14F0007EEB01E0003EEB03C0EC0F806CEB3E00 380F81F83803FFE0C690C7FC1D2677A426>II<147F903803FFC090380FC1E09038 3F00F0017E13785B485A485A485A120F4913F8001F14F0383F8001EC07E0EC1F80397F81 FF00EBFFF8148090C8FC5A5AA55AA21530007C14381578007E14F0003EEB01E0EC03C06C EB0F806CEB3E00380781F83803FFE0C690C7FC1D2677A426>IIIII108 DII<147F903803FFC090380FC1F090381F00F8 017E137C5B4848137E4848133E0007143F5B120F485AA2485A157F127F90C7FCA215FF5A 4814FEA2140115FC5AEC03F8A2EC07F015E0140F007C14C0007EEB1F80003EEB3F00147E 6C13F8380F83F03803FFC0C648C7FC202677A42A>I<9039078007C090391FE03FF09039 3CF0787C903938F8E03E9038787FC00170497EECFF00D9F0FE148013E05CEA01E113C15C A2D80003143FA25CA20107147FA24A1400A2010F5C5E5C4B5A131F5EEC80035E013F495A 6E485A5E6E48C7FC017F133EEC70FC90387E3FF0EC0F8001FEC9FCA25BA21201A25BA212 03A25B1207B512C0A3293580A42A>I<3903C003F0390FF01FFC391E783C0F381C7C703A 3C3EE03F8038383FC0EB7F800078150000701300151CD8F07E90C7FCEAE0FE5BA2120012 015BA312035BA312075BA3120F5BA3121F5BA3123F90C9FC120E212679A423>114 D<14FE903807FF8090380F83C090383E00E04913F00178137001F813F00001130313F0A2 15E00003EB01C06DC7FC7FEBFFC06C13F814FE6C7F6D13807F010F13C01300143F141F14 0F123E127E00FE1480A348EB1F0012E06C133E00705B6C5B381E03E06CB45AD801FEC7FC 1C267AA422>II<01F013 0ED803FC133FD8071EEB7F80EA0E1F121C123C0038143F49131F0070140FA25BD8F07E14 0000E08013FEC6485B150E12015B151E0003141C5BA2153C000714385B5DA35DA24A5A14 0300035C6D48C7FC0001130E3800F83CEB7FF8EB0FC0212679A426>118 D<903907E007C090391FF81FF89039787C383C9038F03E703A01E01EE0FE3803C01F0180 13C0D8070014FC481480000E1570023F1300001E91C7FC121CA2C75AA2147EA214FEA25C A21301A24A1370A2010314F016E0001C5B007E1401010714C000FEEC0380010F1307010E EB0F0039781CF81E9038387C3C393FF03FF03907C00FC027267CA427>120 D<13F0D803FCEB01C0D8071EEB03E0D80E1F1307121C123C0038140F4914C01270A24913 1FD8F07E148012E013FEC648133F160012015B5D0003147E5BA215FE00075C5BA214015D A314035D14070003130FEBF01F3901F87FE038007FF7EB1FC7EB000F5DA2141F003F5C48 133F92C7FC147E147C007E13FC387001F8EB03E06C485A383C1F80D80FFEC8FCEA03F023 3679A428>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff cmsy10 10 1 /Ff 1 16 df15 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg ecbx1000 10 36 /Fg 36 119 df<913803FFC0027F13F00103B512FC010FEB00FED93FF8133FD97FE0EBFF 8049485A5A1480484A13C04A6C1380A36F1300167E93C7FCA592383FFFC0B8FCA4000390 C7FCB3ABB5D8FC3F13FFA4303A7EB935>28 D45 DI<141E143E 14FE1307137FB5FCA3138FEA000FB3B3A5007FB61280A4213679B530>49 DI54 D58 D66 DII73 D76 DII< EDFFF8020FEBFF80027F14F0903A01FFC01FFC010790380007FFD91FFC010113C0D93FF0 6D6C7E49486E7E49486E7E48496E7E48834890C86C7EA248486F1380A248486F13C0A200 3F18E0A348486F13F0A400FF18F8AC007F18F06D5DA3003F18E0A26D5D001F18C0A26C6C 4B13806C18006E5C6C6D4A5A6C5F6C6D4A5A6D6C4A5AD93FFC49485A6DB401075B0107D9 C01F90C7FC010190B512FC6D6C14F0020F1480020001F8C8FC3D3B7BB948>III83 D85 DII<13 FFB5FCA412077EAF4AB47E020F13F0023F13FC9138FE03FFDAF00013804AEB7FC00280EB 3FE091C713F0EE1FF8A217FC160FA217FEAA17FCA3EE1FF8A217F06E133F6EEB7FE06E14 C0903AFDF001FF80903AF8FC07FE009039F03FFFF8D9E00F13E0D9C00390C7FC2F3A7EB9 35>98 D100 D<903803FF80011F13F0017F13FC3901FF83FE3A03FE007F804848133F484814C0001FEC 1FE05B003FEC0FF0A2485A16F8150712FFA290B6FCA301E0C8FCA4127FA36C7E1678121F 6C6C14F86D14F000071403D801FFEB0FE06C9038C07FC06DB51200010F13FC010113E025 257DA42C>II<161FD907FEEBFFC090387FFFE348B6EAEFE02607FE07138F260FF801131F48486C13 8F003F15CF4990387FC7C0EEC000007F81A6003F5DA26D13FF001F5D6C6C4890C7FC3907 FE07FE48B512F86D13E0261E07FEC8FC90CAFCA2123E123F7F6C7E90B512F8EDFF8016E0 6C15F86C816C815A001F81393FC0000F48C8138048157F5A163FA36C157F6C16006D5C6C 6C495AD81FF0EB07FCD807FEEB3FF00001B612C06C6C91C7FC010713F02B377DA530>I< EA01F0EA07FC487EA2487EA56C5AA26C5AEA01F0C8FCA913FF127FA412077EB3A9B512F8 A4153B7DBA1B>105 D<13FFB5FCA412077EAF92380FFFE0A4923803FC0016F0ED0FE0ED 1F804BC7FC157E5DEC03F8EC07E04A5A141FEC7FE04A7E8181A2ECCFFEEC0FFF496C7F80 6E7F6E7F82157F6F7E6F7E82150F82B5D8F83F13F8A42D3A7EB932>107 D<13FFB5FCA412077EB3B3ACB512FCA4163A7DB91B>I<01FED97FE0EB0FFC00FF902601 FFFC90383FFF80020701FF90B512E0DA1F81903983F03FF0DA3C00903887801F000749DA CF007F00034914DE6D48D97FFC6D7E4A5CA24A5CA291C75BB3A3B5D8FC1FB50083B512F0 A44C257DA451>I<01FEEB7FC000FF903803FFF8020F13FE91381F03FFDA3C0113800007 13780003497E6D4814C05CA25CA291C7FCB3A3B5D8FC3F13FFA430257DA435>I<903801 FFC0010F13F8017F13FFD9FF807F3A03FE003FE048486D7E48486D7E48486D7EA2003F81 491303007F81A300FF1680A9007F1600A3003F5D6D1307001F5DA26C6C495A6C6C495A6C 6C495A6C6C6CB45A6C6CB5C7FC011F13FC010113C029257DA430>I<9038FE03F000FFEB 0FFEEC3FFF91387C7F809138F8FFC000075B6C6C5A5CA29138807F80ED3F00150C92C7FC 91C8FCB3A2B512FEA422257EA427>114 D<90383FF0383903FFFEF8000F13FF381FC00F 383F0003007E1301007C130012FC15787E7E6D130013FCEBFFE06C13FCECFF806C14C06C 14F06C14F81203C614FC131F9038007FFE140700F0130114007E157E7E157C6C14FC6C14 F8EB80019038F007F090B512C000F8140038E01FF81F257DA426>I<130FA55BA45BA25B 5BA25A1207001FEBFFE0B6FCA3000390C7FCB21578A815F86CEB80F014816CEBC3E09038 3FFFC06D1380903803FE001D357EB425>I118 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fh ecrm1000 10 89 /Fh 89 126 df<486C1360000314E039070001C0000EEB038048EB070000181306003813 0E0030130C0070131C00601318A200E01338481330A400CEEB338039FF803FE001C013F0 A3007F131FA2393F800FE0390E0003801C1981B91C>16 D<001C1307007FEB1FC039FF80 3FE0A201C013F0A3007F131F001CEB073000001300A400011470491360A2000314E090C7 12C048130100061480000E130348EB070048130E485B006013181C1980B91C>I21 D27 DI30 D36 D<141FEC7FC0903801F0 E0903803C0600107137090380F803090381F00381518A25BA2133E133F15381530A21570 5D5D140190381F838092CAFC1487148E02DC49B51280EB0FF85C4A9039003FF8000107ED 0FC06E5D71C7FC6E140E010F150CD91DFC141C01391518D970FE143801E015302601C07F 1470D803805D00076D6C5BD80F00EBC00148011F5C4890380FE003003E6E48C8FC007E90 3807F8060203130E00FE6E5A6E6C5A1400ED7F706C4B13036F5A6F7E6C6C6D6C5B701306 6C6C496C130E6DD979FE5B281FF001F07F133C3C07F80FE03FC0F86CB539800FFFF0C690 26FE000313C0D91FF0D9007FC7FC393E7DBB41>38 D<121C127FEAFF80A213C0A3127F12 1C1200A412011380A2120313005A1206120E5A5A5A12600A1979B917>I<146014E0EB01 C0EB0380EB0700130E131E5B5BA25B485AA2485AA212075B120F90C7FCA25A121EA2123E A35AA65AB2127CA67EA3121EA2121F7EA27F12077F1203A26C7EA26C7E1378A27F7F130E 7FEB0380EB01C0EB00E01460135278BD20>I<12C07E12707E7E7E120F6C7E6C7EA26C7E 6C7EA21378A2137C133C133E131EA2131F7FA21480A3EB07C0A6EB03E0B2EB07C0A6EB0F 80A31400A25B131EA2133E133C137C1378A25BA2485A485AA2485A48C7FC120E5A5A5A5A 5A13527CBD20>I<1530B3A8B912FCA2C80030C8FCB3A836367BAF41>43 D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A 12600A19798817>II<121C127FEAFF80A5EA7F00121C09097988 17>I<1506A2150E150CA2151C151815381530A215701560A215E015C0A214011580A214 0315005C1406A2140E140CA2141C1418A214381430A21470146014E05CA213015CA21303 91C7FCA25B1306A2130E130C131C1318A213381330A213701360A213E05BA212015B1203 90C8FCA25A1206A2120E120CA2121C1218A21238123012701260A212E05AA21F537BBD2A >II III<1538A2157815F8A214011403 1407A2140F141F141B14331473146314C313011483EB030313071306130C131C13181330 1370136013C01201EA038013005A120E120C5A123812305A12E0B712F8A3C73803F800AA 4A7E0103B512F8A325387EB72A>I<0006140CD80780133C9038F003F890B5FC5D5D1580 92C7FC14FC38067FE090C9FCAAEB07F8EB1FFE9038780F809038E007E03907C003F0496C 7E130000066D7E81C8FC8181A21680A4121C127F5A7FA390C713005D12FC00605C12704A 5A6C5C6C1303001E495A6C6C485A3907E03F800001B5C7FC38007FFCEB1FE021397CB62A >II<12301238123E003FB612E0A316C05A168016 000070C712060060140E5D5D00E014304814705D5DC712014A5A4AC7FC1406140E5CA25C 1478147014F05C1301A213035C1307A2130FA3131F5CA2133FA5137FA96DC8FC131E233A 7BB72A>III<121C127FEAFF80A5 EA7F00121CC7FCB2121C127FEAFF80A5EA7F00121C092479A317>I<121C127FEAFF80A5 EA7F00121CC7FCB2121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A 1206120E5A5A5A12600A3479A317>II<007FB812F8B912FCCCFCB0B912FC6C17F836147B9E41>I<12E01278121EEA07C0 EA01F0EA003C130FEB03C0EB00F0143C140FEC03E0EC00F8151EED0780ED01E0ED007816 1EEE07C0EE01F0EE003C170FEF03C0A2EF0F00173CEE01F0EE07C0041EC7FC1678ED01E0 ED0780031EC8FC15F8EC03E0020FC9FC143C14F0EB03C0010FCAFC133CEA01F0EA07C000 1ECBFC127812E0322E79AB41>II<1538A3157CA315FEA34A7EA34A6C7EA202077FEC063FA202 0E7FEC0C1FA2021C7FEC180FA202387FEC3007A202707FEC6003A202C07F1501A2D90180 7F81A249C77F167FA20106810107B6FCA24981010CC7121FA2496E7EA3496E7EA3496E7E A213E0707E1201486C81D80FFC02071380B56C90B512FEA3373C7DBB3E>65 DI<913A01FF800180020FEBE003027F13F8903A01FF807E07903A03 FC000F0FD90FF0EB039F4948EB01DFD93F80EB00FF49C8127F01FE153F12014848151F48 48150FA248481507A2485A1703123F5B007F1601A35B00FF93C7FCAD127F6DED0180A312 3F7F001F160318006C7E5F6C7E17066C6C150E6C6C5D00001618017F15386D6C5CD91FE0 5C6D6CEB03C0D903FCEB0F80902701FF803FC7FC9039007FFFFC020F13F002011380313D 7BBA3C>IIIIIII<013FB512 E0A39039001FFC00EC07F8B3B3A3123FEA7F80EAFFC0A44A5A1380D87F005B0070131F6C 5C6C495A6C49C7FC380781FC3801FFF038007F80233B7DB82B>IIIIIIIII< D90FF813C090383FFE0190B512813903F807E33907E000F74848137F4848133F48C7121F 003E140F007E1407A2007C140312FC1501A36C1400A37E6D14006C7E7F13F86CB47E6C13 F8ECFF806C14E06C14F86C14FEC680013F1480010714C0EB007F020713E0EC007FED3FF0 151F150FED07F8A200C01403A21501A37EA216F07E15036C15E06C14076C15C06C140F6D EB1F80D8FBF0EB3F00D8F0FE13FE39E03FFFF8010F13E0D8C00190C7FC253D7CBA2E>I< 003FB812E0A3D9C003EB001F273E0001FE130348EE01F00078160000701770A300601730 A400E01738481718A4C71600B3B0913807FF80011FB612E0A335397DB83C>IIII89 D<003FB7FCA39039FC0001FE 01C0130349495A003EC7FC003C4A5A5E0038141F00784A5A12704B5A5E006014FF4A90C7 FCA24A5A5DC712074A5AA24A5A5D143F4A5AA24A5A92C8FC5B495AA2495A5C130F4948EB 0180A2495A5C137F495A16034890C7FC5B1203485AEE0700485A495C001F5D48485C5E48 48495A49130FB8FCA329397BB833>II93 D<007FB81280B912C0A26C17 803204797041>95 D97 DIIII<147E903803FF8090 380FC1E0EB1F8790383F0FF0137EA213FCA23901F803C091C7FCADB512FCA3D801F8C7FC B3AB487E387FFFF8A31C3B7FBA19>IIIIIII<2703F00FF0EB1FE000FFD93FFCEB 7FF8913AF03F01E07E903BF1C01F83803F3D0FF3800FC7001F802603F70013CE01FE14DC 49D907F8EB0FC0A2495CA3495CB3A3486C496CEB1FE0B500C1B50083B5FCA340257EA445 >I<3903F00FF000FFEB3FFCECF03F9039F1C01F803A0FF3800FC03803F70013FE496D7E A25BA35BB3A3486C497EB500C1B51280A329257EA42E>II<3903F01F E000FFEB7FF89038F1E07E9039F3801F803A07F7000FC0D803FEEB07E049EB03F04914F8 49130116FC150016FEA3167FAA16FEA3ED01FCA26DEB03F816F06D13076DEB0FE001F614 C09039F7803F009038F1E07E9038F0FFF8EC1FC091C8FCAB487EB512C0A328357EA42E> II<3807E01F00FFEB7FC09038E1E3E09038E387F0380FE707EA03E613EE9038EC03E0 9038FC0080491300A45BB3A2487EB512F0A31C257EA421>II<1318A51338A31378A313F812011203 1207001FB5FCB6FCA2D801F8C7FCB215C0A93800FC011580EB7C03017E13006D5AEB0FFE EB01F81A347FB220>IIIIII<003FB512FCA2EB8003D83E0013F8003CEB07F00038 EB0FE012300070EB1FC0EC3F800060137F150014FE495AA2C6485A495AA2495A495A495A A290387F000613FEA2485A485A0007140E5B4848130C4848131CA24848133C48C7127C48 EB03FC90B5FCA21F247EA325>II<126012F0B3B3B3 B3A91260045377BD17>I<12FCEAFFC0EA07F0EA01FCEA007E7F80131F80130FB3A78013 07806D7E6D7EEB007EEC1FF0EC07F8EC1FF0EC7E00495A495A495A5C130F5CB3A7131F5C 133F91C7FC137E485AEA07F0EAFFC000FCC8FC1D537ABD2A>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi ecbx1440 14.4 34 /Fi 34 118 df28 D45 D<151E153E15FE1403140F147FEB07FF00 03B5FCB6FCA3EBF87FEAFC00C7FCB3B3B3A6007FB712FCA52E4E76CD42>49 DI<913807FFC0027F13FC0103B67E010F15E090 261FF80313F890267FC0007F01FEC7EA3FFE48488148486E138013FE486C6C6D13C08048 17E080A66C5B18C06C5B6C90C75AD80038168090C8FC4C1300A24C5A5F4C5A4B5B4B13C0 030F5BDB7FFEC7FC91387FFFF816C016FCEEFF80DA000313E09238007FF8EE3FFE707E70 138018C07013E018F07013F8A218FC82A218FEA3EA03C0EA0FF0EA3FFC487EA2B5FCA218 FCA25E18F8A26C4816F0495C4916E0D83FE04A13C06C485CD80FF04A1380D807FE91387F FE003B03FFE003FFFC6C90B65A6C6C15E0010F92C7FC010114FCD9001F1380374F7BCD42 >I<17FC1601A216031607160FA2161F163F167FA216FF5D5DA25D5D5D167F153E157E15 FC15F8EC01F01403EC07E015C0EC0F80141FEC3F00143E5C14FC495A5C495A1307495A5C 49C7FC5B137E137C5B1201485A5B485A120F485A90C8FC123E127E5ABA1280A5C901FCC7 FCAF021FB71280A5394F7CCE42>I<486C150601F0153E01FEEC01FED9FFF0133F91B65A 5F5F5F5F5F94C7FC16FC5E16E093C8FC15FC01F0138091CAFCAC913807FF80023F13F891 B512FE01F36E7E9026FFFC0113E09139E0007FF891C76C7E496E7E01F86E7E5B70138049 16C0C9FC18E08218F0A418F8A31203EA0FE0EA3FF8487EA212FF7FA218F0A25B5E6C4816 E05B01C016C06CC85A18806C6C4A13007FD80FF04A5A6C6CECFFFCD803FE4913F02701FF E00F5B6C6CB612806D92C7FC010F14F8010114C09026003FFCC8FC354F7ACD42>I58 D<932603FFF01407047F01FF5C0307B600E05B033F03F85B92B700FE5B02039126C003FF 5B020F01F8C7EA3FC1023F01C0EC0FE391B5C80003B5FC4901FC814949814901E082011F 498249498292CA7E4948834948835A4A83485B4885A2484984A2485B87A2485B87A25AA2 98C8FC91CFFCA2B5FCAE7E067FB7128080A37E95C76C90C7FC807EA36C7FA26C7FA26C7F 7E806C7F137F6D7E816D6D93B5FC01077F6D01F85D6D7F6D01FF5D023F01E0EC0FEF020F 01FCEC3FE30203903AFFE001FF81020091B6C6FC033F03FC133F030703F0130FDB007F02 801303040301F8CAFC595479D267>71 D73 D76 D78 D80 D<93381FFF800303B512FC033FECFFC0 92B712F00207D9F80113FE021F903AC0003FFF804A48C700077FDAFFF8020113F049496E 7F49496F7E49496F7E49496F7E4990C96C7F4948707F4948707F01FF854849707F4A8248 86A24849717E48864A83A2481B80A248497113C0A4481BE0A291CB7EA3B51AF0AF6C1BE0 A36E5FA26C1BC0A36C1B806E5FA26C1B006E5F6C62A26C6DD903FC4A5A6CDB0FFF5D6E49 EBC0016C4B01E05C6D6C90277E07F0035B6E9039F801F807902A3FFF01F000780F5B6D04 7C5C6DD981E06D4890C7FC6D01E191381F7FFE010101F1EDFFF86DD9F9F06D5BDA3FFF16 C06E6D013F5B02079027FE01FFFEC8FC020190B612F8DA003F4B141003071838DB001FEB 83F893C7EA03FC1C7885726C14F8F2C003F2F01F97B512F084A31CE085A27314C01C8085 1C00735B735B735B735B9638003FC0556A79D263>III<003FBB12FCA59126C0007FEB000301FCC7ED003FD87FF0F00FFE491807 49180349180190C81600A2007E1A7EA3007C1A3EA500FC1A3F481A1FA6C91700B3B3AC49 B912C0A550517BD05B>I97 D<913803FFE0023F13FE91B67E010315E0010F9038003FF8D93FFCEB 07FC4948497E4948131F4849497E485B485BA24890C7FC5A5B003F6F5A705A705A007F92 C8FC5BA312FFAD127F7FA3123F7F6CEE0F80A26C6D141F18006C6D5C6C6D143E6C6D147E 6C6D5C6D6C495A6DB4EB07F0010F9038C01FE06D90B5128001014AC7FCD9003F13F80203 138031387CB63A>99 D<943803FF80040FB5FCA5EE003F170FB3A4913803FF80023F13F8 49B512FE0107ECFF8F011F9038C03FEF90273FFE0007B5FCD97FF8130149487F48498048 4980484980488291C8FC5A5B123FA2127F5BA312FFAD127FA37F123FA3121F7F6C5E6C6D 5C5F6C6D91B5FC6C6D5B6C6D4914E0D97FFCD90FEFEBFF80D91FFFEB7F8F010790B5120F 010114FC6D6C13E00207010049C7FC41547CD249>I<913807FF80027F13F849B512FE01 076E7E011F010313E0903A3FFC007FF0D97FF06D7E49486D7E4849130F48496D7E488248 90C77E1880485A82003F17C0A3485A18E082A212FFA290B8FCA401FCCAFCA6127FA37F12 3FA2EF03E06C7E17076C17C06C6D140F18806C6D141F6C6DEC3F006C6D147ED97FFC495A D91FFFEB07F86D9038E03FF0010390B512C001005D023F01FCC7FC020113E033387CB63C >IIII<133FEBFFC0 487F487FA2487FA66C5BA26C5B6C5B013FC7FC90C8FCAEEB1FF8B5FCA512017EB3B3A6B6 12F0A51C547CD324>I108 DII<913801FFC0023F13FE91B67E010315E001 0F018013F8903A3FFC001FFED97FF0EB07FF49486D7F48496D7F48496D7F91C8127F4883 488349153F001F83A2003F8349151FA2007F83A400FF1880AC007F1800A3003F5F6D153F A2001F5FA26C6C4B5AA26C6D4A5A6C5F6C6D495B6C6D495B6D6C4990C7FCD93FFCEB1FFE 6DB46CB45A010790B512F0010115C0D9003F49C8FC020313E039387CB642>II<90393FF001FCB590 380FFF804B13E0037F13F09238FE1FF89138F1F83F00019138F07FFC6CEBF3E015C0ECF7 80A2ECFF00EE3FF84AEB1FF0EE0FE093C7FC5CA45CB3ABB612FEA52E367DB535>114 D<903903FFC00E011FEBFC1E90B6127E000315FE3907FE003FD80FF0130F484813034848 1301491300127F90C8127EA248153EA27FA27F01F091C7FC13FCEBFF806C13FEECFFF06C 14FE6F7E6C15E06C816C15FC6C81C681133F010F15801301D9000F14C0EC003F030713E0 150100F880167F6C153FA2161F7EA217C07E6D143F17807F6DEC7F0001F85C6DEB03FE90 39FF801FFC486CB512F0D8F81F14C0D8F00791C7FC39E0007FF02B387CB634>I<147CA6 14FCA41301A31303A21307A2130F131F133F137F13FF1203000F90B512FEB7FCA426007F FCC8FCB3A9EE0F80ABEE1F006D7EA2011F143E806D6D5A6DEBC1F86DEBFFF001005C023F 1380DA03FEC7FC294D7ECB33>II E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj ecrm0900 9 5 /Fj 5 109 df<123C127E12FFA4127E123C08087A8715>46 D97 DI104 D108 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fk ecbx0900 9 7 /Fk 7 117 df65 D97 DI<903807FF80013F13F090B512FC3903FE01FE4848487EEA0FF8EA1FF0EA3FE0 A2007F6D5A496C5A153000FF91C7FCA9127F7FA2003FEC07807F6C6C130F000FEC1F00D8 07FE133E3903FF80FCC6EBFFF8013F13E0010790C7FC21217DA027>I<3901F81F8000FF EB7FF0ECFFF89038F9E3FC9038FBC7FE380FFF876C1307A213FEEC03FCEC01F8EC006049 1300B1B512F0A41F217EA024>114 D<9038FFE1C0000713FF5A383F803F387E000F1407 5A14037EA26C6CC7FC13FCEBFFE06C13FC806CEBFF80000F14C06C14E0C6FC010F13F0EB 007F140F00F0130714037EA26C14E06C13076CEB0FC09038C01F8090B5120000F913FC38 E03FE01C217DA023>I<133CA5137CA313FCA21201A212031207001FB51280B6FCA3D807 FCC7FCB0EC03C0A79038FE078012033901FF0F006C13FEEB3FFCEB0FF01A2F7EAE22>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fl ecrm1200 12 25 /Fl 25 122 df<121EEA7F8012FF13C0A213E0A3127FEA1E601200A413E013C0A3120113 80120313005A1206120E5A5A5A12600B1D78891B>44 D<14FF010713E090381F81F89038 3E007C01FC133F4848EB1F8049130F4848EB07C04848EB03E0A2000F15F0491301001F15 F8A2003F15FCA390C8FC4815FEA54815FFB3A46C15FEA56D1301003F15FCA3001F15F8A2 6C6CEB03F0A36C6CEB07E0000315C06D130F6C6CEB1F806C6CEB3F00013E137C90381F81 F8903807FFE0010090C7FC28447CC131>48 D50 D54 D<16C04B7EA34B7EA34B7EA34B7EA3ED 19FEA3ED30FFA203707FED607FA203E07FEDC03FA2020180ED801FA2DA03007F160FA202 06801607A24A6D7EA34A6D7EA34A6D7EA20270810260147FA202E08191B7FCA249820280 C7121FA249C87F170FA20106821707A2496F7EA3496F7EA3496F7EA201788313F8486C83 D80FFF03037FB500E0027FEBFFC0A342477DC649>65 DI68 D77 D<003FB912F8A3903BF0001FF8001F01806D481303003EC7150048187C0078183CA20070 181CA30060180CA5481806A5C81600B3B3A54B7EED7FFE49B77EA33F447DC346>84 D I97 D99 D<167FED3FFFA315018182B3EC7F80903803 FFF090380FC07C90383F000E017E1307496D5AD803F87F48487F5B000F81485AA2485AA2 127FA290C8FC5AAB7E7FA2123FA26C7EA2000F5D7F6C6C5B00035C6C6C9038077F806C6C 010E13C0013F011C13FE90380FC0F8903803FFE09026007F0013002F467DC436>II103 D105 D108 D<3901FC01FE00FF903807FFC091381E 07F091383801F8000701707F0003EBE0002601FDC07F5C01FF147F91C7FCA25BA35BB3A8 486CECFF80B5D8F83F13FEA32F2C7DAB36>110 DI<3903F803F000FFEB1FFCEC3C3EEC707F0007EBE0FF3803F9C000015B13FBEC00 7E153C01FF13005BA45BB3A748B4FCB512FEA3202C7DAB26>114 D<90383FE0183901FFFC383907E01F78390F0003F8001E1301481300007C1478127800F8 1438A21518A27EA27E6C6C13006C7E13FC383FFFE06C13FC6C13FF6C14C06C14E0C614F0 011F13F81300EC0FFC140300C0EB01FE1400157E7E153EA27EA36C143C6C147C15786C14 F86CEB01F039F38003E039F1F00F8039E07FFE0038C00FF01F2E7DAC26>I<1306A5130E A4131EA3133E137EA213FE12011207001FB512F0B6FCA2C648C7FCB3A4150CAA017E131C 017F1318A26D133890381F8030ECC070903807E0E0903801FFC09038007F001E3E7EBC26 >III< B539F001FFFCA3000790C7EA7FE06C48EC1F8000011600160E0000150C6D141C6D1418A2 6E1338013F1430A26D6C5BA26E13E0010F5CA26D6C485AA2ECF803010391C7FCA2903801 FC06A2ECFE0E0100130CA2EC7F18A215B8EC3FB0A2EC1FE0A36E5AA26E5AA36EC8FCA214 06A35CA25CA2123C007E5BB4FC5CA25CEAFE01387C0380D87007C9FCEA3C1EEA0FFCEA03 F02E3F7EAA33>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm ecbx1200 12 47 /Fm 47 123 df<0118140C017C143E01FC147E48485C4848495A495C4848495A4848495A 001F140F90C75B003E4AC7FCA2003C141E007C143E0078143CA200F8147CA2481478D8F1 F014F8D8F7FCEB7BFEB46CEB7FFF6D1580028014C0A36C80A36C806C496C13806C486D13 006C486D5AD801F0EB00F82A2283C427>16 DI28 D46 D48 DIII<163FA25E5E5D5DA25D5D5D5DA25D92B5FCEC01F7EC03E7140715 C7EC0F87EC1F07143E147E147C14F8EB01F0EB03E0130714C0EB0F80EB1F00133E5BA25B 485A485A485A120F5B48C7FC123E5A12FCB91280A5C8000F90C7FCAC027FB61280A53141 7DC038>I<0007150301E0143F01FFEB07FF91B6FC5E5E5E5E5E16804BC7FC5D15E092C8 FC01C0C9FCAAEC3FF001C1B5FC01C714C001DF14F09039FFE03FFC9138000FFE01FC6D7E 01F06D13804915C0497F6C4815E0C8FC6F13F0A317F8A4EA0F80EA3FE0487E12FF7FA317 F05B5D6C4815E05B007EC74813C0123E003F4A1380D81FC0491300D80FF0495AD807FEEB FFFC6CB612F0C65D013F1480010F01FCC7FC010113C02D427BC038>I<4AB47E021F13F0 027F13FC49B6FC01079038807F8090390FFC001FD93FF014C04948137F4948EBFFE04849 5A5A1400485A120FA248486D13C0EE7F80EE1E00003F92C7FCA25B127FA2EC07FC91381F FF8000FF017F13E091B512F89039F9F01FFC9039FBC007FE9039FF8003FF17804A6C13C0 5B6F13E0A24915F0A317F85BA4127FA5123FA217F07F121FA2000F4A13E0A26C6C15C06D 4913806C018014006C6D485A6C9038E01FFC6DB55A011F5C010714C0010191C7FC903800 3FF02D427BC038>I<121E121F13FC90B712FEA45A17FC17F817F017E017C0A248168000 7EC8EA3F00007C157E5E00785D15014B5A00F84A5A484A5A5E151FC848C7FC157E5DA24A 5A14035D14074A5AA2141F5D143FA2147F5D14FFA25BA35B92C8FCA35BA55BAA6D5A6D5A 6D5A2F447AC238>I58 D<1A60F101F01907191FF17FC0953801FF00F007FCF01FF0F07FC04D48C7FCEF07 FCEF3FF0EFFFC0040390C8FCEE0FFCEE3FE0EEFF80DB03FEC9FCED0FF8ED3FE0EDFF80DA 07FECAFCEC1FF8EC7FE0903801FF80D907FCCBFCEB1FF0EB7FC04848CCFCEA07FCEA1FF0 EA7FC048CDFCA2EA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07FC903801FF809038 007FE0EC1FF8EC07FE913800FF80ED3FE0ED0FF8ED03FE923800FF80EE3FE0EE0FFCEE03 FF040013C0EF3FF0EF07FCEF01FF9438007FC0F01FF0F007FCF001FF9538007FC0F11FF0 19071901F10060444277B957>60 D<126012F812FE6C7EEA3FE0EA0FF8EA03FEC66C7EEB 3FE0EB0FF8EB03FE903800FFC0EC3FF0EC0FFCEC03FF9138007FC0ED1FF0ED07FCED01FF 9238007FC0EE1FF0EE07FE933801FF809338007FE0EF1FF8EF03FE943800FF80F03FE0F0 0FF8F003FE953800FF80F13FE0F10FF0A2F13FE0F1FF80953803FE00F00FF8F03FE0F0FF 80DD03FEC7FCEF1FF8EF7FE0933801FF80DC07FEC8FCEE1FF0EE7FC04B48C9FCED07FCED 1FF0ED7FC0DA03FFCAFCEC0FFCEC3FF0ECFFC0D903FECBFCEB0FF8EB3FE0EBFF80D803FE CCFCEA0FF8EA3FE0EAFF8048CDFC12F81260444277B957>62 D<923803FFF0037FEBFF80 0203B612F0020F15FC913A3FFC000FFFDAFFC0010013C0D903FEC8EA1FF0D907F0ED03F8 D91FC0ED00FE4948167F017ECAEA1F8049717E4848717E49DAFF8013034848010F01F06D 7E4848013F01FC6D7E92B6FC4848489026C07F80137C49489026001FC0133C484948D907 E0133E001E49486D6C131E003E49480101141F023F913800FFE0003C4A82007C017F1880 007819074A5AA300F81AC04848491603AB6C6C7F12781B801A076E7E127C003C133F003E 6E1700021F4A5C001E6D6C5B001F6D6C49EBF01E6C6D6C011F143E6D6CD9C07F6D5A6C6C 6C90B5383FFFF8033FD9FC0F5B6C6C010FD9F0035B6C6C0100903980007F806D91CBFC6C 7E137E6D7E6D6CEF7FC0D907F0EE03FFD903FE043F1300902600FFC0913803FFF8DA3FFC 49B512C0020FB748C7FC020316E0DA007F02FCC8FC030349C9FC4A477AC557>64 DIIII73 D77 D<923807FFC092B512FE0207ECFFC0021F15F0 91267FFE0013FC902601FFF0EB1FFF01070180010313C04990C76C7FD91FFC6E6C7E4948 6F7E49486F7E01FF8348496F7E48496F1380A248496F13C0A24890C96C13E0A24819F049 82003F19F8A3007F19FC49177FA400FF19FEAD007F19FC6D17FFA3003F19F8A26D5E6C19 F0A26E5D6C19E0A26C6D4B13C06C19806E5D6C6D4B13006C6D4B5A6D6C4B5A6D6C4B5A6D 6C4A5B6D01C001075B6D01F0011F5B010101FE90B5C7FC6D90B65A023F15F8020715C002 004AC8FC030713C047467AC454>79 D83 D<007FBA12E0BB12F0A46C19E04406776757>95 D<903801FFE0011F13FE017F6D 7E48B612E03A03FE007FF84848EB1FFC6D6D7E486C6D7EA26F7FA36F7F6C5A6C5AEA00F0 90C7FCA40203B5FC91B6FC1307013F13F19038FFFC01000313E0481380381FFE00485A5B 127F5B12FF5BA35DA26D5B6C6C5B4B13F0D83FFE013EEBFFC03A1FFF80FC7F0007EBFFF8 6CECE01FC66CEB8007D90FFCC9FC322F7DAD36>97 DIIIIIII<137C48B4FC4813804813C0A24813E0A56C13 C0A26C13806C1300EA007C90C7FCAAEB7FC0EA7FFFA512037EB3AFB6FCA518467CC520> I108 D<90277F8007FEEC0FFC B590263FFFC090387FFF8092B5D8F001B512E002816E4880913D87F01FFC0FE03FF8913D 8FC00FFE1F801FFC0003D99F009026FF3E007F6C019E6D013C130F02BC5D02F86D496D7E A24A5D4A5DA34A5DB3A7B60081B60003B512FEA5572D7CAC5E>I<90397F8007FEB59038 3FFF8092B512E0028114F8913987F03FFC91388F801F000390399F000FFE6C139E14BC02 F86D7E5CA25CA35CB3A7B60083B512FEA5372D7CAC3E>II<90397FC00FF8B590B57E02C314E002CF14F89139DFC03F FC9139FF001FFE000301FCEB07FF6C496D13804A15C04A6D13E05C7013F0A2EF7FF8A4EF 3FFCACEF7FF8A318F017FFA24C13E06E15C06E5B6E4913806E4913006E495A9139DFC07F FC02CFB512F002C314C002C091C7FCED1FF092C9FCADB67EA536407DAC3E>II<90387F807FB53881FFE002 8313F0028F13F8ED8FFC91389F1FFE000313BE6C13BC14F8A214F0ED0FFC9138E007F8ED 01E092C7FCA35CB3A5B612E0A5272D7DAC2E>I<90391FFC038090B51287000314FF120F 381FF003383FC00049133F48C7121F127E00FE140FA215077EA27F01E090C7FC13FE387F FFF014FF6C14C015F06C14FC6C800003806C15806C7E010F14C0EB003F020313E0140000 F0143FA26C141F150FA27EA26C15C06C141FA26DEB3F8001E0EB7F009038F803FE90B55A 00FC5CD8F03F13E026E007FEC7FC232F7CAD2C>II< D97FC049B4FCB50103B5FCA50003EC000F6C81B3A85EA25EA25E7E6E491380017FD901F7 13FE9138F807E76DB512C7010F1407010313FE9026007FF0EBFC00372E7CAC3E>I I120 D<001FB71280A49026FC001F130001E0495A5B49495A90C7485A48495B123E4A5B4A5B00 3C495BA24A90C7FC4A5A4A5AC7FC4A5A495B495BA2495B499038800780491300A2495A49 48130F49481400A2485B48495B485BA248495B4890C75A48485C15034848EB1FFEB7FCA4 292C7DAB32>122 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fn ecrm1728 17.28 8 /Fn 8 117 df68 D70 D97 D102 D<1378EA01FE487E487FA66C 90C7FC6C5AEA007890C8FCB3A2EB0780EA0FFFB5FCA41203C6FCA2137FB3B3AC497E487F B61280A4195F7BDE25>105 D<010FEB07F8D80FFFEB1FFEB590387FFF809238F81FC091 3801E03F913903C07FE00003EB0780C6EB0F00140E6D5A0218EB3FC00238EB1F800230EB 0600027090C7FCA2146014E0A25CA55CB3B0497E4813F0B612F8A42B3F7BBE34>114 D<9138FFC003010FEBF807017FEBFE0F3A01FF003F9FD803F0EB07DF48486DB4FCD80F80 1300001F8148C8FC003E81007E81127C00FC81A4827EA27E7F6C7E6D91C7FC13F8EA3FFE 381FFFE06C13FF15F0000314FE6C6E7E6C6C14E0011F14F801078001008002077FDA003F 13801507030113C0ED007F00E0ED3FE0161F17F06C150F1607A36C1503A37EA26C16E016 077E17C06D140F6D15806D141FD8FDF0EC3F00D8F8F8147E017C495A3AF01F801FF06DB5 12C0D8E00391C7FC39C0007FF02C417CBF35>I<1470A714F0A51301A31303A21307A213 0FA2131F133F137F13FF1203000F90B6FCB8FCA326000FF0C8FCB3AEEE01C0AE6D6CEB03 80A316076D6C14005E6D6C130E6D6C131E6E6C5A91383FE0F86EB45A020713C0020090C7 FC2A597ED734>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fo ecbx1728 17.28 18 /Fo 18 117 df68 D<942603FFF8151C94B66C 143C040F03F0147C047F03FC14FC0303B81301030FDAC00113C0033F01F8C7381FF00392 B500C0913807F807020349C83801FE0F020F01F89238007F1F4A01E0EE3FBF4A49EE0FFF 91B5CA7E494983494983494983495B4949187F4B183F491A1F495B90B5CC120FA2484919 075A4A19035A4A19015AA24A19005AA348491A7CA35A9AC8FCA35CA2B5FCB07EA26E043F B81280A47E96C7000701FCC7FCA26C7FA37E80A27E807E807E6C7FA26D7F6D7F7F816D7F 6D6D5F6D7F6D6D5F6D6D7E023F6D5E6E01F05E6E6DEEFE7F020301FF923801FC3F020002 C0913807F80F033F01FC91381FF007030F903BFFE001FFC001030391B6EA8000DB007F4B C7123C040F03F8140C040003C091C8FC050301F8CBFC696677E37A>71 D82 D<001FBD12F0A59126F8000191C7123F4801C0 060713F849C71700491A7F01F01A1F491A0F491A07A2491A03A290C81801A2007EF300FC A4007C1C7CA7481C3EA5C91900B3B3B3A5023FB912F8A55F617AE06C>84 D<913803FFF0027F13FF0103B612E0010F15F890263FFC0013FED97FC090381FFF8049C7 6C7F4801C06D7F486D6D7F6E6D7F48836E7F84177F84A36C496E7FA26C5B6C5B013FC8FC 90C9FCA75F0307B6FC4AB7FC141F91B5EAF03F0103EBFE00010F13F0013F1380D9FFFEC7 FC485B485B485B485B485B485BA24890C8FC1A7CA2485AA35FA394B5FC7F6C5D6EEB03DF 6CDB07CFEBC0F86C6DEB0F8F6C6DD91F07EBF3F06C01F8017E14FF6C9027FE01FC0314E0 C690B5D8F00114C0013F9126C0007F1380010791C7383FFE009026003FF8EC07F846437B C14D>97 D<903807FF80B6FCA5C6FC7F7FB3A9933801FFE0041F13FE047FEBFFC00381B6 12F0922687FC0113FC923A9FE0003FFEDBBF8090380FFF8003FEC76C7F4B6E7F4B6E7F4B 6E7F4B824B157F4B82737EA21B80851BC0A31BE085A41BF0AE1BE0A44F13C0A31B80A24F 1300A262197F6F5E6F4B5A4E5B6F4A5BDAFCF84A5BDAF87E4A5B4A6C4A90C7FC9126E01F C0EB7FFC913BC00FF803FFF8DA8003B612E091C71580013E023F01FCC8FC90C800031380 4C657CE356>II101 DII105 D<903807FF80B6FCA5C6FC7F7FB3B3B3B3AFB7 12E0A523647CE32A>108 D110 D<92381FFF804AB512F8020F 14FF023F15C09126FFFC0313F001039039E0007FFC490180EB1FFED91FFEC73807FF8049 486E7F49486E7F49486E7F48496F7EA248496F7E4884A248496F7EA2481980A24819C091 C97EA24819E0A5B518F0AD6C19E0A46C6D4B13C0A36C1980A26C6D4B1300A26C606E157F 6C606C6D4B5A6C606D6C4A5B6D6C4A5B6D6C4A5B6D6C6C011F90C7FC010301E0EB7FFC6D 9039FC03FFF86D6CB612E0020F92C8FC020114F8DA001F138044437CC14D>I<903B07FF 8001FFE0B6011F13FE047FEBFFC00381B612F0922687FC0313FC923A9FE0007FFEC6DABF 806D6C7E6D01FEC7000F7F6D496E7F4B824B6E7F4B6E7F4B804B82737EA21B80851BC0A2 851BE0A4851BF0AE4F13E0A41BC061A21B80A24F1300A24F5AA26F4A5B6F4A5B626F4A5B 6F4A5B03FE4A5B03BF027F90C7FCDB9FC0EBFFFC92268FF8075B0383B612E00380158004 3F01FCC8FC0403138093CBFCB3A4B712E0A54C5D7CC056>I114 DII E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: A4 %%EndSetup %%Page: 1 1 1 0 bop 290 639 a Fo(Genealogical)56 b(Represen)l(tation)e(of)f(T)-13 b(rees)52 b(in)g(Databases)1686 822 y Fn(First)46 b(Draft)1247 1063 y Fm(Miguel)36 b(Sofer)i()1359 1179 y Fl(Univ)m(ersidad)33 b(T)-8 b(orcuato)33 b(Di)f(T)-8 b(ella)1728 1295 y(Buenos)33 b(Aires)1797 1411 y(Argen)m(tina)1746 1606 y(Ma)m(y)h(6,)e(2000)1839 1905 y Fk(Abstract)441 2035 y Fj(blah)25 b(blah)h(.)13 b(.)g(.)118 2310 y Fi(1)131 b(In)l(tro)t(duction)118 2491 y Fh(T)-7 b(rees)28 b(are)h(a)g(v)n(ery)f (frequen)n(t)h(data)f(structure.)41 b(They)30 b(are)e(the)h(natural)g (represen)n(tation)e(for)i(instance)g(for)f(organiza-)118 2591 y(tional)f(c)n(harts,)g(threaded)g(discussion)g(groups,)f(some)h (bills)g(of)h(materials,)e(.)14 b(.)g(.)243 2691 y(A)n(t)28 b(least)f(t)n(w)n(o)f(alternativ)n(e)h(represen)n(tations)e(for)i (trees)g(in)h(RDBMs)g(are)e(kno)n(wn)h(and)h(used:)220 2857 y(1.)41 b Fg(P)m(oin)m(ters:)k Fh(a)31 b(\034eld)h(in)h(the)f(c)n (hild)g(record)e(references)h(the)h(paren)n(t)f(no)r(de.)50 b(This)32 b(seems)g(to)f(b)r(e)i(the)f(canonical)326 2956 y(represen)n(tation.)38 b(Some)29 b(DB)g(engines)f(pro)n(vide)g (sp)r(ecial)g(SQL)g(extensions)g(to)h(simplify)g(tree)g(searc)n(hes;)e (Oracle)326 3056 y(tree)d(extensions)g(are)g(an)h(example)f(\(see)h (for)f(instance)g([1]\);)i(DB2's)f(WITH)g(can)f(b)r(e)i(used)e(for)h (this)g(purp)r(ose)f(to)r(o)326 3156 y(\(see)j([3],)g(pp)h(139-162\).) 220 3322 y(2.)41 b Fg(Nested)35 b(Sets:)43 b Fh(t)n(w)n(o)30 b(n)n(umeric)h(\034elds)g(in)g(ev)n(ery)f(no)r(de)h(record)f(co)r(de)h (the)g(tree)g(structure.)47 b(I)31 b(can't)g(pro)n(vide)f(a)326 3421 y(b)r(etter)e(or)e(briefer)h(description)g(of)h(this)g(metho)r(d)g (than)f(the)h(four)f(articles)g([2].)118 3587 y(These)g(t)n(w)n(o)g (metho)r(ds)h(o\033er)f(di\033eren)n(t)h(adv)-5 b(an)n(tages)25 b(and)j(disadv)-5 b(an)n(tages:)243 3753 y Ff(\017)41 b Fh(P)n(oin)n(ters)30 b(are)g(extremely)g(e\036cien)n(t)h(for)f(no)r (de)h(insertion)f(and/or)g(deletion,)h(but)h(require)e(recursiv)n(e)f (table)i(ac-)326 3853 y(cesses)e(to)h(searc)n(h)f(the)h(tree)g(\(I)h (do)f(not)g(kno)n(w)f(the)i(implemen)n(tation)f(details)g(of)g(the)h (Oracle)e(tree)g(extensions,)326 3953 y(whic)n(h)e(as)g(far)g(as)g(I)g (kno)n(w)g(ma)n(y)g(solv)n(e)f(this)i(problem)f(in)n(ternally;)g(they)g (de\034nitely)h(solv)n(e)f(it)g(for)g(the)h(end)g(user\).)243 4119 y Ff(\017)41 b Fh(Nested)30 b(sets)g(are)f(v)n(ery)f(e\036cien)n (t)i(for)g(tree)f(searc)n(hes,)g(but)i(are)e(rather)f(exp)r(ensiv)n(e)i (for)f(no)r(de)h(insertion)f(and/or)326 4218 y(deletion:)37 b(they)27 b(require)g(up)r(dating)g(p)r(oten)n(tially)h(man)n(y)f(no)r (des.)243 4384 y(W)-7 b(e)30 b(prop)r(ose)f(here)h(a)g(di\033eren)n(t)h (represen)n(tation,)e(based)g(on)i(no)r(de)f(iden)n(ti\034ers)g(whic)n (h)g(are)f(\020genealogical)f(iden)n(ti-)118 4484 y(\034ers\021:)44 b(they)32 b(con)n(tain)f(the)h(complete)f(genealogy)f(of)h(the)h(no)r (de,)h(i.e.,)g(the)f(list)g(of)g(ancestors)d(up)j(to)g(the)g(ro)r(ot)f (of)g(the)118 4584 y(tree.)243 4683 y(This)j(allo)n(ws)f(to)i(replace)e (man)n(y)h(searc)n(hes)f(in)h(database)g(tables)g(with)h(string)f(op)r (erations)f(on)h(the)h(index.)58 b(The)118 4783 y(result,)24 b(as)f(explained)h(in)g(Section)g(3)f(is)h(that)g(tree)f(searc)n(hes)f (pro)r(ceed)h(at)h(\020nested)f(sets\021)30 b(sp)r(eed,)25 b(while)f(no)r(de)g(insertions)118 4882 y(and)k(deletions)f(are)f(as)h (fast)h(as)f(with)h(p)r(oin)n(ters.)243 4982 y(The)i(ob)n(vious)f(do)n (wnside)h(of)h(the)g(metho)r(d)g(is)f(that)h(the)g(primary)f(k)n(ey)f (in)i(the)g(tree)f(needs)h(to)f(b)r(e)h(a)g(v)-5 b(ariable)29 b(size)118 5082 y(text)j(\034eld,)h(and)f(that)g(the)g(iden)n (ti\034ers)f(ma)n(y)g(b)r(e)i(extremelly)e(long)g(for)g(deep)h(trees.) 49 b(W)-7 b(e)32 b(will)g(pro)n(vide)e(estimates)i(of)118 5181 y(the)c(size)f(required)g(as)g(a)g(function)h(of)g(the)f (magnitude)h(of)f(the)h(tree.)1987 5653 y(1)p eop %%Page: 2 2 2 1 bop 118 291 a Fi(2)131 b(Genealogical)45 b(iden)l(ti\034ers)g(for)f (trees)118 489 y Fm(2.1)112 b(De\034nition)118 642 y Fh(W)-7 b(e)28 b(de\034ne)g Fe(gene)l(alo)l(gic)l(al)k(identi\034ers)j Fh(recursiv)n(ely)25 b(as)i(follo)n(ws:)326 808 y Fg(De\034nition:)59 b Fe(The)42 b(gene)l(alo)l(gic)l(al)h(identi\034er)f(\(gID\))e(of)i(a)f (no)l(de)h(is)f(obtaine)l(d)h(by)g(app)l(ending)g(a)f(child)326 908 y(identi\034er)30 b(to)g(the)g(gene)l(alo)l(gic)l(al)h (identi\034er)g(of)f(the)g(p)l(ar)l(ent)f(no)l(de.)243 1074 y Fh(Remark)40 b(that)h(genealogical)e(iden)n(ti\034ers)i(are)f (rather)g(w)n(ell)h(kno)n(wn)f(and)h(used;)48 b(common)41 b(examples)f(are)g(the)118 1174 y(\020path+\034le-name\021)33 b(in)28 b(a)f(computer)g(\034le)h(system)f(and)h(the)f(URLs)h(within)g (a)f(WWW.)243 1273 y(The)d(name)g(\020genealogical)e(iden)n (ti\034er\021)30 b(is)24 b(suggested)g(b)n(y)g(the)g(fact)h(that)f(the) h(v)-5 b(alue)24 b(of)g(the)h(iden)n(ti\034er)f(con)n(tains)f(the)118 1373 y(complete)30 b(genealogy)d(of)j(the)g(no)r(de:)41 b(it)30 b(con)n(tains)e(as)h(a)h(substring)f(the)h(gID)f(of)h(its)g (father,)g(whic)n(h)f(in)h(turn)g(con)n(tains)118 1472 y(as)d(a)g(substring)g(the)h(gID)g(of)f(the)h(grandfather,)e(.)14 b(.)g(.)243 1572 y(The)27 b(ro)r(ot)g(no)r(de)h(of)f(the)h(tree)f(has)g (a)h(gID)f(with)h(v)-5 b(alue)28 b(\021)34 b(\(the)28 b(empt)n(y)g(string\),)f(as)g(it)h(has)f(no)g(paren)n(t.)118 1804 y Fm(2.2)112 b(Child)36 b(iden)m(ti\034ers)118 1958 y Fh(The)26 b(ob)n(vious)e(c)n(hild)i(iden)n(ti\034er)g(is)f(a)h (zero-based)d(coun)n(ter:)35 b(iden)n(tify)26 b(the)h(c)n(hild)e(b)n(y) h(the)g(n)n(um)n(b)r(er)f(of)h(older)f(brethren)g(it)118 2057 y(has.)243 2157 y(W)-7 b(e)25 b(could)f(represen)n(t)g(the)h(coun) n(ter)f(in)h(base)f(10;)h(this)g(ho)n(w)n(ev)n(er)e(is)i(extremely)f(w) n(asteful)g(of)h(resources.)34 b(It)25 b(is)g(m)n(uc)n(h)118 2257 y(b)r(etter)33 b(to)f(represen)n(t)f(the)h(coun)n(ter)g(in)g(as)g (large)e(a)i(base)g(as)f(p)r(ossible:)46 b(in)n(terpret)32 b(as)f(n)n(um)n(b)r(ers)h(a)g(set)g(of)g(c)n(haracters)118 2356 y(larger)26 b(than)h({0,1,.)14 b(.)g(.)g(9}.)243 2456 y(As)26 b(tree)f(op)r(erations)f(will)i(in)n(v)n(olv)n(e)f(string) g(op)r(erations)f(on)i(the)g(indices,)g(in)g(order)f(to)g(a)n(v)n(oid)g (a)g(\020quoting)g(hell\021)33 b(it)26 b(is)118 2555 y(desirable)d(to)h(a)n(v)n(oid)e(using)h(an)n(y)g(c)n(haracter)f(with)i (a)g(sp)r(ecial)f(meaning)h(in)g(LIKE)g(expressions)e(or)g(regular)g (expressions;)118 2655 y(i.e.,)28 b(w)n(e)f(will)h(not)f(use)h(an)n(y)f (of)g(the)h(sym)n(b)r(ols)70 b Fd(.)44 b(*)f(^)g(\\)g([)g(])g({)h(})f (\()g(\))g(<)g(>)71 b Fh(?)37 b(|)28 b(&)f($)243 2755 y(W)-7 b(e)28 b(prop)r(ose)e(to)h(reserv)n(e)f(also)g(/)i(as)f(a)g (separator)e(\(see)i(\020V)-7 b(ariable)27 b(Sized)g(gID\021)34 b(b)r(elo)n(w\).)243 2854 y(If)g(w)n(e)f(limit)i(ourselv)n(es)d(to)i (ascii)f(c)n(haracters,)g(and)h(a)n(v)n(oid)e(to)i(b)r(e)g(safe)f(a)h (lot)g(of)g(other)f(c)n(haracters,)g(w)n(e)g(can)h(use)118 2954 y(n)n(um)n(b)r(ers)27 b(in)h(base)f(64)g(b)n(y)g(represen)n(ting) 243 3120 y Ff(\017)41 b Fh(0-9)26 b(with)i('0'-'9')f(\(dec)g(ascii)g (co)r(de)h(48-57\))243 3286 y Ff(\017)41 b Fh(10)26 b(with)i(':')37 b(\(dec)28 b(ascii)f(co)r(de)h(58\))243 3452 y Ff(\017)41 b Fh(11)26 b(with)i(';')g(\(dec)g(ascii)f(co)r(de)g(59\))243 3618 y Ff(\017)41 b Fh(12-37)25 b(with)j('A'-'Z')g(\(dec)f(ascii)g(co)r (de)h(65-90\))243 3784 y Ff(\017)41 b Fh(38-63)25 b(with)j('a'-'z')f (\(dec)h(ascii)f(co)r(de)g(97-122\))118 3950 y(By)g(using)g(base)f(64,) h(up)g(to)h(4096)d(c)n(hildren)i(can)f(b)r(e)i(represen)n(ted)e(using)h (t)n(w)n(o)f(suc)n(h)h(digits,)g(up)h(to)f(262144)d(with)k(three)118 4050 y(digits,)g(and)f(up)h(to)f(16777216)d(with)k(four)f(digits.)243 4149 y(If)37 b(the)g(RDBMs)g(supp)r(orts)f(in)n(ternational)g(c)n (haracters,)h(it)g(is)g(p)r(ossible)f(to)h(further)f(increase)g(the)h (base;)k(as)36 b(an)118 4249 y(example,)30 b(b)n(y)f(using)g(the)h(95)f (additional)g(c)n(haracters)e(of)i(the)h(latin-1)f(c)n(haracter)e(set,) k(w)n(e)e(could)g(co)r(de)g(n)n(um)n(b)r(ers)g(in)h(a)118 4349 y(base)f(up)g(to)g(160)f(\025)g(remark)g(that)h(ev)n(ery)f(single) h(digit)g(is)g(still)h(one)e(b)n(yte)h(in)h(this)f(represen)n(tation.) 40 b(This)29 b(means)f(that)118 4448 y(w)n(e)f(expand)h(the)f(sym)n(b)r (ols)g(ab)r(o)n(v)n(e)f(b)n(y)i(represen)n(ting)243 4614 y Ff(\017)41 b Fh(64-159)25 b(with)j(dec)f(latin1)g(co)r(de)h(160-255) 243 4780 y(In)23 b(base)g(160,)g(up)g(to)h(25600)d(c)n(hildren)i(can)f (b)r(e)i(represen)n(ted)e(using)h(t)n(w)n(o)g(digits,)h(up)g(to)f (4096000)d(with)k(three)f(digits,)118 4880 y(and)28 b(up)f(to)h (6.5E+08)e(with)i(four)f(digits.)243 4980 y(Remark)g(that)h(base)f(con) n(v)n(ersions)f(only)h(need)i(to)e(b)r(e)i(p)r(erformed)e(at)h (insertion)g(time,)g(when)h(the)f(index)g(of)g(a)g(new)118 5079 y(no)r(de)g(is)f(computed.)37 b(They)28 b(will)f(therefore)g(only) g(ha)n(v)n(e)f(an)i(impact)f(on)h(insertion)f(timings.)1987 5653 y(2)p eop %%Page: 3 3 3 2 bop 118 291 a Fm(2.3)112 b(Coun)m(ters:)50 b(\020delimited\021)44 b(vs.)51 b(\020\034xed)38 b(size\021)118 444 y Fh(The)33 b(standard)g(represen)n(tation)e(of)i(gID)h(uses)e(a)h(v)-5 b(ariable)32 b(size)h(c)n(hild)h(iden)n(ti\034er,)g(and)f(delimiters)g (to)h(separate)d(the)118 543 y(gID)f(of)g(the)h(c)n(hild)f(no)r(de)g (from)f(the)i(gID)f(of)g(its)g(paren)n(t.)43 b(F)-7 b(or)30 b(example,)g(w)n(e)g(can)f(represen)n(t)g(the)i(\034fth)g(c)n(hild)f (of)g(no)r(de)118 643 y('/23/27/1')24 b(as)j('/23/27/1/4'.)32 b(Let)c(us)f(call)g(this)h(a)f Fg(vgID)h Fh(represen)n(tation)e(\(V)-7 b(ariable)27 b(Size)h(Genealogical)d(ID\).)243 743 y(This)30 b(represen)n(tation)f(allo)n(ws)f(for)i(an)n(y)g(n)n(um)n(b)r(er)g(of)g (c)n(hildren)g(of)h(a)f(no)r(de,)h(sub)5 b(ject)30 b(only)g(to)g(the)h (limitations)f(the)118 842 y(RDBMS)e(ma)n(y)f(ha)n(v)n(e)f(as)h(to)h (the)g(length)f(of)h(a)f(v)-5 b(ariable)27 b(sized)g(string.)243 942 y(Alternativ)n(ely)-7 b(,)24 b(w)n(e)f(could)h(c)n(ho)r(ose)f(to)h (limit)g(from)g(the)g(outset)g(the)g(quan)n(tit)n(y)g(of)f(c)n(hildren) h(that)g(a)g(no)r(de)g(ma)n(y)f(ha)n(v)n(e;)118 1042 y(this)28 b(limit)g(w)n(ould)f(dep)r(end)i(of)e(course)f(on)i(the)g (application.)36 b(Let)27 b(us)h(call)f(this)h(a)f Fg(fgID)h Fh(represen)n(tation.)243 1141 y(F)-7 b(or)25 b(example,)h(if)g(no)g (no)r(de)f(is)h(allo)n(w)n(ed)f(to)g(ha)n(v)n(e)g(more)g(than)h(25600)d (c)n(hildren,)j(w)n(e)g(could)f(represen)n(t)g(the)h(coun)n(ters)118 1241 y(alw)n(a)n(ys)36 b(with)i(2)f(digits.)67 b(The)38 b(no)r(de)f(whic)n(h)h(w)n(as)f(previously)f('/23/27/1/4')d(is)k(no)n (w)g('23270104'.)64 b(If)38 b(w)n(e)f(require)118 1340 y(a)g(three)g(digit)h(represen)n(tation)d(of)i(no)r(des)g(\(up)h(to)f (ab)r(out)h(4)f(million)g(c)n(hildren\),)j(then)d(it)h(will)g(b)r(e)f (represen)n(ted)f(as)118 1440 y('023027001004'.)118 1672 y Fm(2.4)112 b(Ordering)37 b(of)h(no)s(des)118 1825 y Fh(F)-7 b(or)35 b(some)g(applications)g(it)h(is)f(necessary)f(to)i (obtain)f(subtrees)g(ordered)f(according)g(to)i(some)f(sp)r(ecial)g (rules.)60 b(F)-7 b(or)118 1925 y(instance:)220 2090 y(1.)41 b(the)34 b(complete)g(subtree)f(starting)g(at)h(a)f(no)r(de)h (is)g(listed)g(immediately)g(after)f(the)i(no)r(de)f(in)g(question)f (\(\020depth)326 2189 y(\034rst\021\))220 2354 y(2.)41 b(no)r(des)27 b(with)h(a)f(common)g(paren)n(t)g(are)g(listed)g(c)n (hronologically)243 2519 y(F)-7 b(or)39 b(instance,)k(the)d(displa)n(y) f(of)h(an)f(organization)f(c)n(hart)h(is)g(usually)h(required)e(to)i (satisfy)g(at)f(least)h(the)g(\034rst)118 2619 y(condition.)h(In)29 b(a)g(threaded)f(discussion)h(group)e(one)i(wishes)g(to)f(satisfy)h(b)r (oth)h(conditions)e(to)h(displa)n(y)f(the)h(messages)118 2718 y(in)20 b(a)g(thread)g(\025)f(the)i(threads)e(themselv)n(es)h (\(i.e.,)i(c)n(hildren)e(of)g(the)g(ro)r(ot)f(no)r(de\))i(are)e (usually)g(listed)i(in)f(in)n(v)n(erse)f(c)n(hronolical)118 2818 y(order.)243 2917 y(T)-7 b(o)35 b(mak)n(e)f(a)h(particular)f (ordering)g(e\036cien)n(t,)j(it)f(w)n(ould)f(b)r(e)h(a)f(nice)g (feature)g(if)h(it)g(could)f(b)r(e)h(made)f(to)g(coincide)118 3017 y(with)28 b(a)f(lexicographic)f(ordering)f(of)j(the)g(indices)f (\025i.e.,)g(as)g(pro)r(duced)g(b)n(y)h(an)f(\020ORDER)h(BY)f(id)h (ASC\021)35 b(in)27 b(SQL.)h(The)118 3117 y(lexicographic)d(ordering)h (of)h(fgID)h(satis\034es)e(b)r(oth)i(conditions.)36 b(The)27 b(lexicographic)f(ordering)f(of)i(vgID)g(as)g(describ)r(ed)118 3216 y(ab)r(o)n(v)n(e)34 b(satis\034es)g(the)h(\034rst)g(requisite)f (if)i(the)f(separator)d(has)j(the)g(minimal)g(binary)g(represen)n (tation)e(of)i(all)f(allo)n(w)n(ed)118 3316 y(sym)n(b)r(ols)c(in)h(an)f (index)h(\025)f(this)h(is)g(wh)n(y)f(w)n(e)g(reserv)n(ed)f(/)h(for)g (the)i(separator.)43 b(But)31 b(the)g(second)f(prop)r(ert)n(y)g(is)g (missing:)118 3416 y(for)d(instance,)g(the)h(index)g('/1/10')d(is)j (lexicographically)d(b)r(efore)i('/1/2'.)243 3515 y(If)c(the)h(second)e (prop)r(ert)n(y)g(is)i(also)e(required)g(for)h(vgID,)g(w)n(e)f(can)h (sp)r(ecify)h(the)f(c)n(hild)h(iden)n(ti\034ers)e(with)i(coun)n(ters)e (built)118 3615 y(in)28 b(the)g(follo)n(wing)e(w)n(a)n(y:)36 b(represen)n(t)26 b(a)h(n)n(um)n(b)r(er)h(b)n(y)f(a)g(string)g(of)g (digits,)h(where)243 3779 y Ff(\017)41 b Fh(the)25 b(\034rst)g(digit)h Fc(D)896 3791 y Fb(0)958 3779 y Fh(represen)n(ts)e(the)i(length)f(in)h (digits)f(of)g(the)h(decimal)f(expansion)f(of)i(the)f(n)n(um)n(b)r(er,) h(min)n(us)f(one)243 3945 y Ff(\017)41 b Fh(the)28 b(follo)n(wing)e Fa(\()p Fc(D)920 3957 y Fb(0)976 3945 y Fa(+)18 b(1\))27 b Fh(digits)h(are)e(the)i(decimal)g(expansion)e(of)i(the)g(n)n(um)n(b)r (er)118 4109 y(Let)g(us)f(call)h(these)f(iden)n(ti\034ers)g Fg(m-vgID)p Fh(,)g(\020m\021)34 b(for)27 b(mo)r(di\034ed.)243 4209 y(As)e(an)f(example,)h(the)g(no)r(de)g(whic)n(h)g(w)n(as)f (previously)f(represen)n(ted)h(b)n(y)g(/15/3/182)d(will,)k(after)g (this)g(mo)r(di\034cation,)118 4309 y(ha)n(v)n(e)h(the)i(index)g (/115/03/2182.)243 4408 y(The)37 b(lexicographic)f(ordering)g(of)i (m-vgID)f(is)h(the)g(desired)f(ordering)f(of)h(the)h(tree)g(no)r(des.) 67 b(The)38 b(cost)f(of)g(this)118 4508 y(prop)r(ert)n(y)31 b(is)i(that)f(\(a\))h(the)g(ID)f(are)g(no)n(w)g(longer,)g(\(b\))h(no)f (no)r(de)g(can)g(ha)n(v)n(e)g(more)f(than)i Fa(160)3106 4478 y Fb(160)3240 4508 y Fh(c)n(hildren)f(\(actually)-7 b(,)118 4607 y(this)32 b(is)g(a)f(non-issue\),)h(and)f(\(c\))h(the)g (index)g(structure)f(is)h(redundan)n(t,)g(some)f(formally)f(correct)h (indices)g(are)g(in)n(v)-5 b(alid)118 4707 y(\025e.g.,)24 b(/316/013/11.)30 b(The)24 b(third)g(issue)g(can)g(b)r(e)g(addressed)f (b)n(y)g(k)n(eeping)g(a)h(strict)g(con)n(trol)e(on)i(the)g(generation)f (of)h(new)118 4807 y(indices)k(to)f(insure)g(that)h(all)f(indices)h (are)e(formally)h(correct.)243 4906 y(The)32 b(issue)f(of)h(the)g(rev)n (erse)e(c)n(hronological)f(indexing)j(of)f(threads)h(in)g(threaded)f (discussion)g(groups)g(can)g(b)r(e)h(ad-)118 5006 y(dressed)d(easily)f (enough)h(in)h(fgID:)f(coun)n(t)g(\020do)n(wn\021)36 b(instead)29 b(of)g(\020up\021)36 b(the)30 b(c)n(hildren)f(of)g(the)h (ro)r(ot)e(no)r(de)i(\025)f(this)h(implies)118 5106 y(only)e(an)g (inconsequen)n(tial)f(mo)r(di\034cation)h(of)g(the)g(no)r(de)h (insertion)e(routine,)h(as)g(sho)n(wn)f(b)r(elo)n(w.)38 b(The)29 b(problem)e(is)h(less)118 5205 y(trivial)i(with)g(vgID;)h(in)f (this)h(case,)f(ma)n(yb)r(e)f(a)h(thread)g(iden)n(ti\034er)g(should)g (b)r(e)h(k)n(ept)f(in)g(a)g(di\033eren)n(t)g(\034eld)h(-)f(i.e.,)h (repre-)118 5305 y(sen)n(ting)h(the)h(structure)f(as)g(a)h(forest)f (rather)f(than)i(a)f(tree,)i(where)e(the)h(thread_id)f(\034eld)h (selects)f(the)h(\020tree\021)38 b(in)33 b(the)118 5404 y(forest.)1987 5653 y(3)p eop %%Page: 4 4 4 3 bop 118 291 a Fi(3)131 b(T)-11 b(ree)45 b(op)t(erations)e(using)h (genealogical)g(indices)118 472 y Fh(In)32 b(this)f(section)g(w)n(e)g (sho)n(w)g(ho)n(w)g(to)g(implemen)n(t)h(v)-5 b(arious)30 b(tree)h(op)r(erations)f(using)h(gID)g(as)g(the)h(primary)e(k)n(ey)h (in)g(the)118 572 y(no)r(de)d(table.)243 672 y(Some)h(implemen)n (tation)h(issues)g(are)f(relev)-5 b(an)n(t)29 b(here,)h(esp)r(ecially)f (concerning)g(the)h(utilisation)g(of)g(indices)g(b)n(y)f(the)118 771 y(DB)f(engine.)243 871 y(W)-7 b(e)28 b(discuss)f(a)g(tree)g (represen)n(ted)f(in)i(a)f(table)h(of)f(the)h(form)326 1034 y Fd(CREATE)41 b(TABLE)g(tree)h(\()456 1134 y(gid)304 b(text)42 b(PRIMARY)f(KEY,)456 1234 y(nchildren)f(integer)h(DEFAULT)f (0,)456 1333 y(\\ldots)h(the)i(actual)e(node)h(data)326 1433 y(\);)118 1597 y Fh(The)26 b(\034eld)g(\020nc)n(hildren\021)32 b(is)26 b(a)f(coun)n(ter)g(for)g(the)i(n)n(um)n(b)r(er)e(of)h(c)n (hildren)f(that)h(the)h(no)r(de)f(has)f Fe(ever)35 b Fh(had;)27 b(w)n(e)e(assume)g(here)118 1696 y(it)j(is)g(not)f(up)r (dated)h(when)g(no)r(des)f(or)g(subtrees)g(are)f(deleted.)243 1796 y(Section)h(4)g(pro)n(vides)f(a)i(complete)f(implemen)n(tation)h (of)f(these)h(op)r(erations)e(for)h(fgID)h(in)g(P)n(ostgreSQL.)118 2028 y Fm(3.1)112 b(Computing)37 b(the)g(lev)m(el)f(of)h(a)h(no)s(de) 118 2181 y Fg(Cost:)f Fe(string)30 b(op)l(er)l(ations)g(\(no)g(table)g (ac)l(c)l(ess\))243 2280 y Fh(This)d(is)h(a)f(pure)g(string)g(op)r (eration,)f(no)i(table)f(access)g(is)g(required.)243 2460 y Ff(\017)41 b Fg(vgID:)27 b Fh(coun)n(t)h(the)g(n)n(um)n(b)r(er)f (of)g(separators)e(\('/'\))j(in)g(the)g(PK)243 2625 y Ff(\017)41 b Fg(fgID:)27 b Fh(coun)n(t)g(the)h(n)n(um)n(b)r(er)g(of)f (c)n(haracters)e(in)j(the)g(PK,)g(divide)g(b)n(y)f(the)h(\034xed)f (size)h(of)f(the)h(coun)n(ters.)118 2857 y Fm(3.2)112 b(Selecting)36 b(or)h(deleting)f(a)i(subtree)118 3010 y Fg(Cost:)f Fe(index)30 b(sc)l(an)g(of)g(the)g(tr)l(e)l(e)243 3173 y Ff(\017)41 b Fg(vgID:)27 b Fh(The)h(subtree)f(ro)r(oted)g(at)g (/26/5/7)e(is)i(selected)g(b)n(y)508 3338 y Fd(...)43 b(WHERE)e(id)i(LIKE)f('/26/5/7\045')d(AND)j(id)h(<)g('/26/5/70')243 3503 y Ff(\017)e Fg(m-vgID:)26 b Fh(The)h(subtree)h(ro)r(oted)e(at)i (/126/05/07)22 b(is)28 b(selected)f(b)n(y)508 3668 y Fd(...)43 b(WHERE)e(id)i(LIKE)f('/126/06/07\045')243 3833 y Ff(\017)f Fg(fgID:)27 b Fh(The)h(subtree)f(ro)r(oted)g(at)g (260507)e(is)i(selected)h(b)n(y)508 3997 y Fd(...)43 b(WHERE)e(id)i(LIKE)f('260507\045')118 4229 y Fm(3.3)112 b(Selecting)36 b(the)h(direct)f(c)m(hildren)g(of)i(a)g(no)s(de)118 4382 y Fg(Cost:)f Fe(index)30 b(sc)l(an)g(of)g(the)g(tr)l(e)l(e)243 4562 y Ff(\017)41 b Fg(vgID:)27 b Fh(The)h(direct)f(c)n(hildren)g(of)h (/26/5/7)c(are)j(selected)g(b)n(y)508 4727 y Fd(...)43 b(WHERE)e(id)i(LIKE)f('/26/5/7/\045')d(AND)j(id)h(NOT)f(LIKE)g ('26/5/7/\045/\045')243 4892 y Ff(\017)f Fg(m-vgID:)26 b Fh(The)h(direct)h(c)n(hildren)f(of)g(/26/5/7)e(are)h(selected)i(b)n (y)508 5056 y Fd(...)43 b(WHERE)e(id)i(LIKE)f('/126/06/07/\045')37 b(AND)43 b(id)f(NOT)h(LIKE)f('/126/05/07/\045/\045)o(')243 5221 y Ff(\017)f Fg(fgID:)27 b Fh(The)h(direct)f(c)n(hildren)g(of)h (260507)c(are)j(selected)g(b)n(y)508 5386 y Fd(...)43 b(WHERE)e(id)i(LIKE)f('260507\045')d(AND)k(char_length\(id\))37 b(=)43 b(\(char_length\('26)o(05)o(07')o(\)+)o(2\))1987 5653 y Fh(4)p eop %%Page: 5 5 5 4 bop 118 291 a Fm(3.4)112 b(Inserting)37 b(a)h(no)s(de)g(or)f(a)h (subtree)118 444 y Fg(Cost:)f Fe(index)30 b(sc)l(an)g(of)g(the)g(tr)l (e)l(e)f(+)h(string)f(and)h(math)g(op)l(er)l(ations)243 543 y Fh(Insertion)f(is)g(a)h(pro)r(cedural)e(op)r(eration.)42 b(As)30 b(eac)n(h)f(RDBMS)h(has)f(a)h(di\033eren)n(t)f(w)n(a)n(y)g(of)g (de\034ning)h(pro)r(cedures,)f(w)n(e)118 643 y(will)f(just)g(describ)r (e)f(here)g(the)h(necessary)e(steps.)37 b(Examples)27 b(for)g(P)n(ostgreSQL)f(are)h(pro)n(vided)f(in)i(4.)243 743 y(In)22 b(order)f(to)h(insert)g(a)g(new)g(c)n(hild)h(of)f (\020daddy\021)28 b(\(either)23 b(one)f(of)g(/26/5/7,)e(/126/05/07)d (or)22 b(260507)d(in)k(the)f(examples)118 842 y(ab)r(o)n(v)n(e\))27 b(y)n(ou)f(ha)n(v)n(e)h(to)220 1008 y(1.)41 b(add)27 b(one)g(to)h(the)g(n)n(um)n(b)r(er)f(of)g(c)n(hildren)h(of)f (\020daddy\021)508 1174 y Fd(UPDATE)41 b(tree)h(SET)h(nchildren)c(=)k (\(nchildren)d(+)j(1\))g(WHERE)e(ID)i(=)g(``daddy'';)220 1340 y Fh(2.)e(enco)r(de)27 b(the)h(n)n(um)n(b)r(er)f(of)g(c)n(hildren) g(of)h(\020daddy\021)33 b(in)28 b(base)f(160,)f(bring)h(it)h(to)f(the)h (correct)e(format)h(dep)r(ending)h(on)326 1440 y(the)c(v)-5 b(arian)n(t)23 b(of)h(gID)g(\(pad)g(with)h(0)e(or)g(not,)i(prep)r(end)f (a)g(digit)g(coun)n(ter)f(or)g(not,)i(prep)r(end)f(/)g(or)f(not,)i (coun)n(t)e(do)n(wn)326 1540 y(or)j(up,)i(.)14 b(.)g(.)g(\))37 b(and)28 b(app)r(end)f(it)h(to)g(daddy's)f(gID)g(to)h(obtain)f(the)h (new)g(no)r(de's)f(gID.)220 1706 y(3.)41 b(insert)27 b(the)h(new)f(no)r(de)243 1872 y(When)35 b(inserting)g(a)f(subtree,)j (the)e(index)g(of)g(the)h(ro)r(ot)e(of)h(the)g(subtree)g(has)f(to)h(b)r (e)h(computed)f(as)f(ab)r(o)n(v)n(e,)i(and)118 1971 y(prep)r(ended)28 b(to)f(the)h(index)g(of)f(eac)n(h)g(no)r(de)h(of)f(the)h(subtree)f(b)r (efore)h(insertion.)243 2071 y(Remark)e(that)i(only)f(the)h(paren)n(t)f (no)r(de)h(has)f(to)g(b)r(e)h(up)r(dated)g(on)f(insertion.)118 2303 y Fm(3.5)112 b(Selecting)36 b(the)h(ancestors)h(of)g(a)g(no)s(de) 118 2457 y Fg(Cost:)f Fe(index)30 b(sc)l(an)g(of)g(the)g(tr)l(e)l(e)243 2556 y Fh(Y)-7 b(ou)27 b(can)g(sp)r(ecify)h(all)g(ancestors)d(of)j(a)f (no)r(de)h(in)f(a)h(single)f(SQL)g(statemen)n(t;)g(for)g(instance)h (for)f(vgID)326 2722 y Fd(...)42 b(WHERE)f('/25/6/7')f(LIKE)i(\(id)g (||)h('/\045'\))f(AND)g(id)h(<)g('/25/6/7')118 2888 y Fh(The)31 b(second)e(part)h(of)h(the)g(clause,)f(while)h(logically)e (redundan)n(t,)h(is)h(a)f(\020hin)n(t\021)37 b(to)30 b(the)h(optimizer.)45 b(A)n(t)31 b(least)f(in)g(P)n(ost-)118 2988 y(greSQL,)c(without)i(it)g(the)g(optimizer)f(will)h(c)n(ho)r(ose)e (a)i(sequen)n(tial)e(scan)h(of)h(the)g(table)f(and)h(disregard)d(the)j (index.)118 3220 y Fm(3.6)112 b(Selecting)36 b(all)g(lea)m(v)m(es)118 3374 y Fg(Cost:)h Fe(sc)l(an)30 b(of)g(the)g(tr)l(e)l(e)243 3473 y Fh(A)e(leaf)f(is)g(a)h(no)r(de)f(without)h(descendan)n(ts:)36 b(it)28 b(has)f(0)g(c)n(hildren.)37 b(Hence)326 3639 y Fd(...)42 b(WHERE)f(nchildren)f(=)j(0)118 3805 y Fh(If)28 b(this)g(t)n(yp)r(e)g(of)f(query)g(is)h(often)f(necessary)-7 b(,)26 b(y)n(ou)h(ma)n(y)g(b)r(e)h(w)n(ell)f(advised)g(to)g(k)n(eep)g (an)h(index)f(on)h(tree\(nc)n(hildren\).)118 4038 y Fm(3.7)112 b(Determining)35 b(if)i(A)g(is)g(a)h(descendan)m(t)g(of)g(B)118 4191 y Fg(Cost:)f Fe(string)30 b(op)l(er)l(ations,)h(no)f(table)g(ac)l (c)l(ess)243 4291 y Fh(This)d(is)h(a)f(pure)g(string)g(op)r(eration)f (on)i(the)g(indices,)f(no)g(table)h(access)e(is)i(necessary)-7 b(.)118 4565 y Fi(4)131 b(Putting)45 b(it)f(all)h(together:)57 b(a)44 b(P)l(ostgreSQL)f(implemen)l(tation)118 4747 y Fh(h)n(ttp://www.p)r(ostgresql.org/mhonarc/pgsq)o(l-sql/)o(20)o(00)o (-0)o(4/)o(msg0)o(02)o(67)o(.h)n(tml)243 4847 y(W)-7 b(e)30 b(describ)r(e)g(here)g(a)g(small)f(pac)n(k)-5 b(age)29 b(that)i(can)e(b)r(e)i(used)f(for)g(implemen)n(ting)g(gID)g (on)g(P)n(ostgreSQL.)f(It)i(can)e(b)r(e)118 4946 y(found)f(at)f()243 5046 y(The)21 b(pac)n(k)-5 b(age)21 b(uses)g(the)h(pro) r(cedural)e(language)h(PL/PGsql.)35 b(A)22 b(b)r(etter)g(implemen)n (tation)g(w)n(ould)f(probably)g(de\034ne)118 5145 y(the)28 b(gID)g(as)f(new)g(P)n(ostgres)f(t)n(yp)r(es,)i(and)f(co)r(de)g(all)h (this)g(in)f(C.)243 5245 y(The)g(\034les)h(should)f(b)r(e)h(loaded)f (in)h(alphab)r(etical)f(order.)1987 5653 y(5)p eop %%Page: 6 6 6 5 bop 118 291 a Fm(4.1)112 b(tree0_enco)s(ding.sql)118 444 y Fh(This)28 b(\034le)f(de\034nes)h(and)f(p)r(opulates)h(the)f (table)h(_b160_digits)d(of)j(\020digits\021)33 b(in)28 b(base)f(160,)326 604 y Fd(CREATE)41 b(TABLE)g(\\_b160\\_digits)d (\(deci)j(integer,)f(code)i(char\);)118 764 y Fh(and)28 b(the)f(t)n(w)n(o)g(functions)326 924 y Fd(CREATE)41 b(FUNCTION)f(\\_b160\\_encode\(i)o(nt)o(eg)o(er\))d(RETURNS)j(string) 413 1024 y(AS)j('....')e(LANGUAGE)f('plpgsql';)326 1124 y(CREATE)h(FUNCTION)f(\\_b160\\_encode\(i)o(nt)o(eg)o(er,)o(in)o(te)o (ger)o(\))d(RETURNS)k(string)413 1223 y(AS)i('....')e(LANGUAGE)f ('plpgsql';)118 1384 y Fh(The)22 b(\034rst)h(function)f(returns)g(a)g (v)-5 b(ariable)21 b(size)h(enco)r(ding;)i(the)f(second)e(a)h(\034xed)h (size)f(enco)r(ding)g(\(the)h(second)e(parameter)118 1483 y(is)g(the)h(size\),)g(and)f(raises)e(an)i(exception)g(if)h(the)f (n)n(um)n(b)r(er)g(is)g(to)r(o)g(large)e(to)i(b)r(e)h(represen)n(ted)e (with)h(the)h(requested)e(n)n(um)n(b)r(er)118 1583 y(of)28 b(digits.)118 1814 y Fm(4.2)112 b(tree1_de\034ne.sql)118 1967 y Fh(This)28 b(\034le)f(pro)n(vides)f(a)i(function)326 2127 y Fd(CREATE)41 b(FUNCTION)f(_tree_create\(tex)o(t,)o(in)o(teg)o (er)o(,t)o(ext)o(,t)o(ex)o(t\))d(RETURNS)k(bpchar)413 2227 y(AS)i('....')e(LANGUAGE)f('plpgsql';)118 2387 y Fh(that)e(creates)f(a)h(tree)f(infrastructure)g(of)h(either)g(fgID)g (or)f(vgID.)h(Assuming)f(y)n(ou)g(ha)n(v)n(e)g(a)h(table)f(\020m)n (ytable\021)44 b(with)118 2487 y(primary)26 b(k)n(ey)h(\020m)n (yid\021,)g(then)h(calling)326 2647 y Fd(SELECT)41 b(_tree_create\('m)o (yt)o(ree)o(',)o(2,')o(my)o(ta)o(ble)o(',)o('m)o(yid)o('\))o(;)118 2807 y Fh(will)28 b(cause:)220 2967 y(1.)41 b(the)28 b(creation)e(of)i(a)f(table)508 3131 y Fd(CREATE)41 b(TABLE)h (mytree_bkg\()683 3230 y(gid)g(text)g(PRIMARY)e(KEY,)683 3330 y(nchildren)f(int,)683 3429 y(sid)j(integer)f(REFERENCES)e (mytable\(myid\))508 3529 y(\);)508 3629 y(CREATE)i(UNIQUE)g(INDEX)h (mytree_bkg_sid)37 b(ON)43 b(mytree_bkg\(sid\);)326 3792 y Fh(for)27 b(the)h(tree)f(structure.)220 3955 y(2.)41 b(the)28 b(creation)e(of)i(a)f(view)508 4118 y Fd(CREATE)41 b(VIEW)h(mytree)f(AS)639 4218 y(SELECT)g(t.gid,n.*)900 4317 y(FROM)h(mytable)f(n,)i(mytree_bkg)c(t)900 4417 y(WHERE)j(t.sid=n.myid;)326 4580 y Fh(with:)35 b(a)23 b(trigger)e(on)i(UPD)n(A)-7 b(TE)25 b(that)e(blo)r(c)n(ks)g(up)r (dating)g(the)h(gid)f(and)g(allo)n(ws)f(up)r(dating)h(the)g(no)r(de)h (data,)f(a)g(rule)326 4680 y(on)k(DELETE)i(that)f(deletes)f(the)h (corresp)r(onding)e(en)n(try)h(b)r(oth)h(in)g(m)n(ytree_bkg)d(and)j(m)n (ytable,)f(and)g(a)g(trigger)326 4779 y(ON)h(INSER)-7 b(T)30 b(that)f(raises)e(an)h(exception)g(and)g(informs)h(the)f(user)g (to)h(use)f(the)h(insertion)f(function)h(describ)r(ed)326 4879 y(b)r(elo)n(w.)220 5042 y(3.)41 b(t)n(w)n(o)26 b(insertion)h (functions)h(that)g(compute)g(automatically)e(the)i(gID)g(of)f(the)h (new)g(no)r(de:)425 5205 y Ff(\017)41 b Fh(a)27 b(function)i(m)n (ytree_insert\(text,text,in)n(teger,text\))d(for)h(insertion)g(sim)n (ultaneosly)f(in)i(b)r(oth)g(tables:)508 5305 y(m)n (ytree_insert\('2201','hello',0,'not)15 b(m)n(uc)n(h'\))j(inserts)g(a)g (new)g(c)n(hild)h(of)f(2201)f(with)h(data1='hello',)h(data2=0)508 5404 y(and)28 b(data3='not)e(m)n(uc)n(h')1987 5653 y(6)p eop %%Page: 7 7 7 6 bop 425 291 a Ff(\017)41 b Fh(a)27 b(function)i(m)n (ytree_insert_no)r(de\(text,in)n(teger\))c(for)i(insertion)g(in)h(m)n (ytree_bkg)508 390 y(m)n(ytree_insert\('2201',25\))c(inserts)j(in)h(m)n (ytree_bkg)e(a)h(new)h(c)n(hild)f(of)h(2201)d(with)j(sid=25)220 556 y(4.)41 b(a)27 b(function)h(m)n(ytree_mo)n(v)n(e\(text,text\))e (that)i(mo)n(v)n(es)e(subtrees:)326 656 y(m)n(ytree_mo)n(v)n (e\('2201','23'\))d(mo)n(v)n(es)j(the)i(subtree)f(ro)r(oted)g(at)g (2201)f(to)h(a)h(place)f(b)r(elo)n(w)g(23)f(\(ma)n(yb)r(e)i(2307\))220 822 y(5.)41 b(a)c(function)g(m)n(ytree_len\(\))g(that)h(returns)e(the)i (length)f(of)g(the)h(enco)r(dings)f(used)g(in)h(the)f(gID)g(\(2)h (here;)j(0)c(if)326 922 y(v)-5 b(ariable)26 b(size\).)118 1196 y Fi(5)131 b(Non-tree)44 b(hierarc)l(hies)118 1378 y Fh(sequence)22 b(as)f(id,)j(table)e(with)h(\(id,g-index\))f(with)g(p) r(ossibly)g(man)n(y)g(g-indices)f(for)h(eac)n(h)f(id)h(\(if)h(TOO)f (man)n(y)-7 b(,)23 b(bad)f(mo)r(del:)118 1478 y(list)28 b(all)f(genealogies,)f(i.e.,)h(paths)h(from)f(the)h(ro)r(ot\))118 1752 y Fi(References)160 1934 y Fh([1])41 b(Philip)28 b(Greenspun,)g Fe(T)-6 b(r)l(e)l(es)29 b(in)h(Or)l(acle)g(SQL)p Fh(,)d(in)h Fg(SQL)k(for)g(W)-8 b(eb)31 b(Nerds)289 2033 y Fh()160 2200 y([2])41 b(Jo)r(e)27 b(Celk)n(o,)f Fe(SQL)j(for)i(Smarties)p Fh(,)d(in)g Fg(DBMS)j(Online)p Fh(,)26 b(Marc)n(h)h(to)g(June)h(1996) 289 2299 y()289 2399 y()289 2498 y()289 2598 y()160 2764 y([3])41 b(Graeme)26 b(Birc)n(hall,)h Fg(DB2)32 b(UDB)g(V6.1)f(SQL)h(Co)s(okb)s(o)s(ok)p Fh(,)289 2864 y()1987 5653 y(7)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF