%!PS-Adobe-2.0 %%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software %%Title: small1.dvi %%Pages: 7 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%DocumentFonts: ZapfDingbats %%EndComments %DVIPSCommandLine: /usr/local/bin/dvips -f small1.dvi %DVIPSParameters: dpi=300, comments removed %DVIPSSource: TeX output 2001.04.06:1050 %%BeginProcSet: tex.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}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{dup dup 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 /IE 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 IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /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 dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{ 128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup 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 /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 sub]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]} if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 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 dup 1 get dup mul exch 0 get dup 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 /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 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 /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail {dup /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 %%BeginProcSet: texps.pro TeXDict begin /rf{findfont dup length 1 add dict begin{1 index /FID ne 2 index /UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics exch def dict begin Encoding{exch dup type /integertype ne{pop pop 1 sub dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def} ifelse}forall Metrics /Metrics currentdict end def[2 index currentdict end definefont 3 -1 roll makefont /setfont load]cvx def}def /ObliqueSlant{dup sin S cos div neg}B /SlantFont{4 index mul add}def /ExtendFont{3 -1 roll mul exch}def /ReEncodeFont{/Encoding exch def}def end %%EndProcSet TeXDict begin 40258431 52099146 1000 300 300 (small1.dvi) @start /Fa 2 2 df0 DI E /Fb 1 50 df49 D E /Fc 2 111 df105 D110 D E /Fd 2 49 df0 D48 D E /Fe 6 111 df83 DI105 DII110 D E /Ff 3 51 df43 D49 DI E /Fg 185[33 70[{}1 41.666668 /ZapfDingbats rf /Fh 33 122 df13 D39 D65 D68 D70 D76 D82 DII97 D99 DIIIIIIIIIIIIIIIIIIIIII E /Fi 27 117 df25 D46 DI58 DI65 DI III71 DI82 DIIII88 DII 105 DII110 D114 DII E /Fj 68 125 df11 DI34 D39 DII44 D46 D48 DIIIIIII58 DI61 D63 D65 DIIIIIII II76 DIIII82 DIII87 D92 D97 DIIIIIIIIIIIIIIIIIIIIIIIII124 D E /Fk 15 107 df0 DI15 D18 D20 D26 D33 D54 D70 D91 DI96 D102 D I106 D E /Fl 45 122 df39 DII44 D49 DII58 D65 DIIIII73 DI76 D78 D80 D82 DII87 D97 DIIIIIIII107 DIIIII114 DIIII120 DI E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 0 42 a Fl(Bac)o(kground:)19 b(F)l(unctional)11 b(Dep)q(endencies)0 153 y Fk(\017)62 b Fj(W)m(e)14 b(are)g(alw)o(a)o (ys)f(talking)f(ab)q(out)i(a)g(relation)f Fi(R)p Fj(,)83 203 y(with)h(a)f(\014xed)h(sc)o(hema)g(\(set)h(of)e(attributes\))i(and) f(a)83 253 y(v)n(arying)f Fh(instanc)n(e)h Fj(\(set)h(of)e(tuples\).)0 335 y Fk(\017)62 b Fj(Con)o(v)o(en)o(tions:)20 b Fi(A;)7 b(B)r(;)g(:)g(:)g(:)12 b Fj(are)i(attributes;)g Fi(:)7 b(:)g(:)f(;)h(Y)r(;)g(Z)83 385 y Fj(are)14 b(sets)h(of)f(attributes.)21 b(Concatenation)14 b(means)83 435 y(union.)0 518 y Fk(\017)62 b Fj(FD)14 b(is)f Fi(X)31 b Fk(!)c Fi(Y)9 b Fj(,)k(where)i Fi(X)j Fj(and)c Fi(Y)23 b Fj(are)14 b(sets)83 567 y(of)f(attributes.)22 b(Tw)o(o)13 b(tuples)h(that)g(agree)h(in)e(all)83 617 y(attributes)i(of)e Fi(X)18 b Fj(m)o(ust)12 b(agree)j(in)e(all)g (attributes)83 667 y(of)g Fi(Y)d Fj(.)0 750 y Fk(\017)62 b Fj(Implication:)18 b(FD)13 b Fi(X)18 b Fk(!)13 b Fi(Y)23 b Fh(fol)r(lows)13 b(fr)n(om)g Fk(F)18 b Fj(i\013)13 b(all)83 800 y(relation)g(instances)i(that)f(satisfy)g Fk(F)k Fj(also)13 b(satisfy)83 849 y Fi(X)i Fk(!)c Fi(Y)f Fj(.)p 0 876 938 2 v 0 979 a Fl(Three)j(W)l(a)o(ys)h(to)f(Reason)g(Ab)q (out)g(FD's)0 1066 y Fj(1.)50 b Fh(Semantic)r Fj(:)21 b(FD)14 b Fi(X)22 b Fk(!)d Fi(Y)k Fj(is)14 b(the)g(set)h(of)e(relation) 83 1115 y(instances)i(that)f(satisfy)g(it.)83 1198 y Fg(F)50 b Fj(Sa)o(y)13 b Fk(F)22 b(j)-7 b Fj(=)17 b Fi(X)k Fk(!)c Fi(Y)23 b Fj(if)13 b(ev)o(ery)h(instance)h(that)166 1248 y(satis\014es)g(all)e(FD's)g(in)h Fk(F)j Fj(also)d(satisfy)f Fi(X)i Fk(!)c Fi(Y)f Fj(.)83 1331 y Fg(F)50 b Fj(All)13 b(approac)o(hes)i(assume)e(there)i(is)f(a)g(\014xed)166 1380 y(relation)f(sc)o(heme)h Fi(R)g Fj(to)g(whic)o(h)g(the)g(FD's)166 1430 y(p)q(ertain.)0 1513 y(2.)50 b Fh(A)o(lgorithmic)r Fj(:)19 b(Giv)o(e)14 b(an)f(algorithm)e(that)j(tells)g(us,)83 1563 y(giv)o(en)f Fk(F)18 b Fj(and)c Fi(X)h Fk(!)c Fi(Y)e Fj(,)14 b(whether)h Fk(F)h(j)-7 b Fj(=)11 b Fi(X)k Fk(!)c Fi(Y)f Fj(.)0 1646 y(3.)50 b Fh(L)n(o)n(gic)n(al)t Fj(:)20 b(Giv)o(e)13 b(a)h(reasoning)g(system)f(that)h(lets)h(us)83 1695 y(deduce)g(an)f(FD)g(lik)o(e)f Fi(X)18 b Fk(!)13 b Fi(Y)23 b Fj(exactly)14 b(when)h Fk(F)j(j)-7 b Fj(=)83 1745 y Fi(X)15 b Fk(!)c Fi(Y)f Fj(.)83 1828 y Fg(F)50 b Fj(Deduction)14 b(indicated)g(b)o(y)g Fk(F)h(`)d Fi(X)j Fk(!)c Fi(Y)f Fj(.)p 0 1862 V 0 1968 a Fl(Closure)i(T)l(est)i(for)f (Implication)d(\(Algorithm)o(ic)0 2018 y(Approac)o(h\))0 2096 y Fj(Start)k(with)g Fi(X)238 2081 y Ff(+)279 2096 y Fj(=)g Fi(X)s Fj(.)21 b(Adjoin)13 b Fi(V)24 b Fj(to)13 b Fi(X)666 2081 y Ff(+)708 2096 y Fj(if)g Fi(U)19 b Fk(!)13 b Fi(V)23 b Fj(is)0 2146 y(in)13 b Fk(F)t Fj(,)h(and)f Fi(U)k Fk(\022)12 b Fi(X)314 2131 y Ff(+)342 2146 y Fj(.)20 b(A)o(t)14 b(end,)g(test)h(if)e Fi(Y)21 b Fk(\022)12 b Fi(X)769 2131 y Ff(+)797 2146 y Fj(.)0 2229 y Fk(\017)62 b Fj(Pro)q(of)14 b(that)g(if)f Fi(Y)28 b Fk(\022)19 b Fi(X)465 2214 y Ff(+)493 2229 y Fj(,)14 b(then)g Fk(F)23 b(j)-7 b Fj(=)19 b Fi(X)k Fk(!)18 b Fi(Y)10 b Fj(:)83 2279 y(Easy)k(induction)g(on)f(the)i(n)o(um)o(b)q(er)e(of)g(additions)g (to)83 2329 y Fi(X)120 2313 y Ff(+)162 2329 y Fj(that)h Fi(X)h Fk(!)c Fi(A)j Fj(for)g(all)e Fi(A)i Fj(in)g Fi(X)651 2313 y Ff(+)679 2329 y Fj(.)0 2411 y Fk(\017)62 b Fj(Pro)q(of)14 b(that)g(if)f Fk(F)k Fj(implies)12 b Fi(X)k Fk(!)11 b Fi(Y)f Fj(,)j(then)h Fi(Y)22 b Fk(\022)12 b Fi(X)896 2396 y Ff(+)924 2411 y Fj(:)83 2461 y(Pro)o(v)o(e)i(the)h(con)o(trap)q (ositiv)o(e;)e(assume)g Fi(Y)24 b Fj(is)13 b(not)h(a)83 2511 y(subset)h(of)f Fi(X)295 2496 y Ff(+)337 2511 y Fj(and)f(pro)o(v)o(e)h Fk(F)k Fj(do)q(es)d(not)f(imply)83 2561 y Fi(X)j Fk(!)12 b Fi(Y)d Fj(.)21 b(Construct)15 b(relation)e Fi(R)h Fj(with)f(t)o(w)o(o)h(tuples)83 2610 y(that)g(agree)g(on)g Fi(X)376 2595 y Ff(+)418 2610 y Fj(and)g(disagree)g(elsewhere.)p 0 2645 V 458 2770 a(1)p eop %%Page: 2 2 2 1 bop 0 42 a Fl(Armstrong's)12 b(Axioms)h(\(Logical)e(Approac)o(h\))0 120 y Fj(A)j Fh(sound)h Fj(\(what)f(ma)o(y)e(b)q(e)i(deduced)i(is)d (correct)j(in)d(the)i Fk(j)-7 b Fj(=)0 170 y(sense\))16 b(and)d Fh(c)n(omplete)h Fj(\(what)g(is)g(true)h(in)e(the)i Fk(j)-7 b Fj(=)13 b(sense)0 219 y(can)h(b)q(e)h(deduced\))g (axiomatization)c(of)i(FD's.)0 302 y(A1:)19 b Fh(T)m(rivial)12 b(FD's)i Fj(or)g Fh(R)n(e\015exivity)p Fj(.)21 b Fi(X)j Fk(!)19 b Fi(Y)k Fj(alw)o(a)o(ys)83 352 y(holds)14 b(if)f Fi(Y)21 b Fk(\022)11 b Fi(X)s Fj(.)0 434 y(A2:)19 b Fh(A)o(ugmentation) p Fj(.)i(If)13 b Fi(X)k Fk(!)11 b Fi(Y)f Fj(,)j(then)i Fi(X)s(Z)h Fk(!)c Fi(Y)d(Z)17 b Fj(for)83 484 y(an)o(y)c(set)i(of)f (attributes)g Fi(Z)s Fj(.)0 566 y(A3:)19 b Fh(T)m(r)n(ansitivity)p Fj(.)g(If)13 b Fi(X)25 b Fk(!)c Fi(Y)i Fj(and)13 b Fi(Y)31 b Fk(!)20 b Fi(Z)s Fj(,)14 b(then)83 616 y Fi(X)h Fk(!)c Fi(Z)s Fj(.)p 0 642 938 2 v 0 745 a Fl(Deductiv)o(e)g(Pro)q(ofs)0 824 y Fj(A)j(series)h(of)f(\\lines.")19 b(Eac)o(h)14 b(line)g(is)g(either:)0 906 y(1.)50 b(A)14 b(giv)o(en)f(statemen)o(t)h (\(FD)g(in)f(the)i(giv)o(en)e(set)i Fk(F)j Fj(for)83 956 y(deductions)d(ab)q(out)f(FD's\),)f(or)0 1038 y(2.)50 b(A)14 b(statemen)o(t)g(that)g(follo)o(ws)e(from)g(previous)i(lines)83 1088 y(b)o(y)g(applying)e(an)i(axiom.)0 1187 y Fl(Example)0 1265 y Fj(Giv)o(en)f Fk(f)p Fi(AB)h Fk(!)d Fi(C)q(;)20 b(C)s(D)13 b Fk(!)e Fi(E)r Fk(g)p Fj(,)i(deduce)i Fi(AB)r(D)f Fk(!)d Fi(E)r Fj(.)0 1348 y Fi(AB)j Fk(!)d Fi(C)17 b Fj(\(Giv)o(en\))0 1405 y Fi(AB)r(D)d Fk(!)d Fi(C)s(D)k Fj(\(A2\))0 1462 y Fi(C)s(D)e Fk(!)e Fi(E)16 b Fj(\(Giv)o(en\))0 1520 y Fi(AB)r(D)e Fk(!)d Fi(E)16 b Fj(\(A3\))p 0 1557 V 0 1660 a Fl(Pro)q(of)d(of)g(Soundness)0 1738 y Fj(Easy)h(observ)n (ations)g(ab)q(out)g(relations.)0 1837 y Fl(Pro)q(of)f(of)g (Completeness)0 1923 y Fj(1.)50 b(Giv)o(en)13 b Fk(F)t Fj(,)h(sho)o(w)f(that)h(if)f Fi(A)h Fj(is)g(in)g Fi(X)666 1908 y Ff(+)694 1923 y Fj(,)f(then)83 1973 y Fi(X)i Fk(!)c Fi(A)j Fj(follo)o(ws)f(from)f Fk(F)17 b Fj(b)o(y)d(AA's.)0 2055 y(2.)50 b(Sho)o(w)14 b(that)g(if)f Fi(X)23 b Fk(!)d Fi(A)471 2061 y Ff(1)490 2055 y Fi(;)7 b(:)g(:)g(:)e(;)i(X)23 b Fk(!)d Fi(A)733 2061 y Fe(n)769 2055 y Fj(follo)o(w)83 2105 y(from)12 b(AA's,)i(then)g(so)g(do)q(es)h Fi(X)g Fk(!)c Fi(A)669 2111 y Ff(1)695 2105 y Fk(\001)c(\001)g(\001)e Fi(A)781 2111 y Fe(n)804 2105 y Fj(.)0 2187 y(3.)50 b(Complete)13 b(the)h(pro)q(of)g(b)o(y)f(observing)h(that)83 2237 y Fi(X)h Fk(!)c Fi(A)216 2243 y Ff(1)242 2237 y Fk(\001)c(\001)g(\001)e Fi(A)328 2243 y Fe(n)365 2237 y Fj(follo)o(ws)12 b(from)g Fk(F)18 b Fj(i\013)c(all)e(of)83 2287 y Fi(A)114 2293 y Ff(1)133 2287 y Fi(;)7 b(:)g(:)g(:)e(;)i(A)257 2293 y Fe(n)293 2287 y Fj(are)14 b(in)f Fi(X)447 2272 y Ff(+)476 2287 y Fj(,)g(and)h(therefore)h(i\013)83 2337 y Fi(X)g Fk(!)c Fi(A)216 2343 y Ff(1)242 2337 y Fk(\001)c(\001)g(\001)e Fi(A)328 2343 y Fe(n)365 2337 y Fj(follo)o(ws)12 b(b)o(y)i(AA's.)p 0 2371 V 0 2476 a Fl(Pro)q(of)f(\(2\))0 2555 y Fj(Induction)h(on)g Fi(i)g Fj(that)g Fi(X)h Fk(!)c Fi(A)497 2561 y Ff(1)523 2555 y Fk(\001)c(\001)g(\001)e Fi(A)609 2561 y Fe(i)637 2555 y Fj(follo)o(ws.)0 2637 y Fk(\017)62 b Fj(Basis:)21 b Fi(i)12 b Fj(=)f(1,)j(giv)o(en.)458 2770 y(2)p eop %%Page: 3 3 3 2 bop 0 42 a Fk(\017)62 b Fj(Induction:)20 b(Assume)14 b Fi(X)h Fk(!)c Fi(A)576 48 y Ff(1)602 42 y Fk(\001)c(\001)g(\001)e Fi(A)688 48 y Fe(i)p Fd(\000)p Ff(1)745 42 y Fj(.)83 119 y Fg(F)50 b Fi(X)20 b Fk(!)c Fi(X)s(A)346 125 y Ff(1)372 119 y Fk(\001)7 b(\001)g(\001)f Fi(A)459 125 y Fe(i)p Fd(\000)p Ff(1)529 119 y Fj(\(A2)14 b(b)o(y)g Fi(X)j Fj(applied)c(to)166 168 y Fi(X)i Fk(!)c Fi(A)299 174 y Ff(1)325 168 y Fk(\001)c(\001)g(\001)e Fi(A)411 174 y Fe(i)p Fd(\000)p Ff(1)468 168 y Fj(\).)83 245 y Fg(F)50 b Fi(X)s(A)234 251 y Ff(1)260 245 y Fk(\001)7 b(\001)g(\001)f Fi(A)347 251 y Fe(i)p Fd(\000)p Ff(1)423 245 y Fk(!)18 b Fi(A)514 251 y Fe(i)542 245 y Fj(\(A2)c(b)o(y)g Fi(A)713 251 y Ff(1)738 245 y Fk(\001)7 b(\001)g(\001)f Fi(A)825 251 y Fe(i)p Fd(\000)p Ff(1)166 295 y Fj(applied)13 b(to)h Fi(X)h Fk(!)c Fi(A)495 301 y Fe(i)509 295 y Fj(\).)83 372 y Fg(F)50 b Fi(X)23 b Fk(!)18 b Fi(A)314 378 y Ff(1)340 372 y Fk(\001)7 b(\001)g(\001)e Fi(A)426 378 y Fe(i)454 372 y Fj(\(A3)14 b(applied)f(to)h(previous)166 422 y(t)o(w)o(o)f (FD's\).)p 0 459 938 2 v 0 559 a Fl(Pro)q(of)g(\(1\))0 632 y Fj(Induction)h(on)g(the)g(n)o(um)o(b)q(er)f(of)h(steps)h(used)g (to)e(add)h Fi(A)g Fj(to)0 682 y Fi(X)37 667 y Ff(+)65 682 y Fj(.)0 759 y Fk(\017)62 b Fj(Basis:)21 b(0)13 b(steps.)22 b(Then)14 b Fi(A)g Fj(is)g(in)g Fi(X)s Fj(,)g(and)f Fi(X)21 b Fk(!)16 b Fi(A)83 809 y Fj(b)o(y)e(A1.)0 886 y Fk(\017)62 b Fj(Induction:)20 b(Assume)14 b Fi(B)474 892 y Ff(1)500 886 y Fk(\001)7 b(\001)g(\001)f Fi(B)587 892 y Fe(k)624 886 y Fk(!)16 b Fi(A)d Fj(in)h Fk(F)k Fj(used)83 935 y(to)c(add)f Fi(A)h Fj(to)g Fi(X)347 920 y Ff(+)375 935 y Fj(.)83 1013 y Fg(F)50 b Fj(By)14 b(the)h(inductiv)o(e)f(h)o(yp)q (othesis,)g Fi(X)24 b Fk(!)d Fi(B)851 1019 y Fe(j)166 1062 y Fj(follo)o(ws)12 b(from)g Fk(F)18 b Fj(for)c(all)e(1)g Fk(\024)g Fi(j)i Fk(\024)d Fi(k)q Fj(.)83 1139 y Fg(F)50 b Fj(By)14 b(part)g(\(2\))g(of)f(the)i(theorem,)166 1189 y Fi(X)g Fk(!)c Fi(B)299 1195 y Ff(1)325 1189 y Fk(\001)c(\001)g(\001)f Fi(B)412 1195 y Fe(k)446 1189 y Fj(follo)o(ws)13 b(from)f Fk(F)t Fj(.)83 1266 y Fg(F)50 b Fj(By)14 b(A3,)f Fi(X)j Fk(!)11 b Fi(A)j Fj(follo)o(ws.)p 0 1301 V 0 1398 a Fl(Bac)o(kground:) 19 b(Normal)13 b(F)l(orms)0 1499 y Fk(\017)62 b Fj(A)14 b Fh(key)g Fj(for)g Fi(R)f Fj(is)h(a)g(minim)o(al)c(set)15 b(of)e(attributes)83 1548 y(suc)o(h)i(that)f Fi(X)19 b Fk(!)d Fi(R)e Fj(\(note:)21 b(I)14 b(use)g Fi(R)g Fj(as)g(b)q(oth)g (the)83 1598 y(instance)h(and)e(sc)o(hema)h(of)f(a)h(relation)f(|)g (shame)g(on)83 1648 y(me\).)19 b(A)14 b Fh(sup)n(erkey)h Fj(is)e(an)o(y)h(sup)q(erset)i(of)d(a)h(k)o(ey)m(.)0 1725 y Fk(\017)62 b Fj(BCNF:)14 b(If)g Fi(X)36 b Fk(!)c Fi(Y)23 b Fj(holds)14 b(for)f Fi(R)h Fj(and)g(is)83 1775 y(non)o(trivial,)e(then)i Fi(X)k Fj(is)c(a)f(sup)q(erk)o(ey)m(.)0 1852 y Fk(\017)62 b Fj(3NF:)13 b(If)h Fi(X)19 b Fk(!)14 b Fi(Y)23 b Fj(holds)14 b(for)f Fi(R)h Fj(and)g(is)g(non)o(trivial,)83 1902 y(then)h(either)f Fi(X)k Fj(is)c(a)f(sup)q(erk)o(ey)i(or)f Fi(Y)23 b Fj(con)o(tains)14 b(a)83 1952 y Fh(prime)f Fj(attribute)i(\(mem)o(b)q(er)d(of)h(some)g(k)o(ey\).)0 2029 y Fk(\017)62 b Fh(De)n(c)n(omp)n(osition)s Fj(:)21 b(W)m(e)14 b(can)g(decomp)q(ose)g Fi(R)f Fj(in)o(to)83 2079 y(sc)o(hemas)h Fi(S)269 2085 y Ff(1)288 2079 y Fi(;)7 b(:)g(:)g(:)e(;)i(S)406 2085 y Fe(n)442 2079 y Fj(if)13 b Fi(S)505 2085 y Ff(1)537 2079 y Fk([)h(\001)7 b(\001)g(\001)k([)i Fi(S)706 2085 y Fe(n)743 2079 y Fj(=)h Fi(R)p Fj(.)20 b(The)83 2128 y(instance)15 b(for)e Fi(S)333 2134 y Fe(i)361 2128 y Fj(is)h Fi(\031)427 2134 y Fe(S)447 2138 y Fc(i)462 2128 y Fj(\()p Fi(R)p Fj(\).)21 b(The)14 b(FD's)g(that)g(hold)83 2178 y(for)g Fi(S)172 2184 y Fe(i)200 2178 y Fj(are)g(those)h Fi(X)20 b Fk(!)d Fi(Y)23 b Fj(suc)o(h)15 b(that)e Fi(X)s(Y)27 b Fk(\022)18 b Fi(S)884 2184 y Fe(i)83 2228 y Fj(and)c Fi(X)h Fk(!)c Fi(Y)23 b Fj(follo)o(ws)12 b(from)h(the)h(giv)o(en)f (FD's)h(for)f Fi(R)p Fj(.)p 0 2263 V 0 2360 a Fl(Co)o(v)o(ers)g(of)g (Sets)g(of)g(FD's)0 2460 y Fk(\017)62 b Fj(Sets)15 b Fk(F)205 2466 y Ff(1)237 2460 y Fj(and)f Fk(F)352 2466 y Ff(2)384 2460 y Fj(of)g(FD's)f(are)i Fh(e)n(quivalent)f Fj(if)f(eac)o(h)83 2510 y(implies)f(the)i(other.)83 2587 y Fg(F)50 b Fj(I.e.,)13 b(exactly)h(the)g(same)f(relation)h(instances) 166 2637 y(satisfy)g(eac)o(h.)458 2770 y(3)p eop %%Page: 4 4 4 3 bop 0 42 a Fk(\017)62 b Fj(An)o(y)14 b(set)h(of)e(FD's)g(equiv)n (alen)o(t)h(to)f Fk(F)18 b Fj(is)c(a)f Fh(c)n(over)h Fj(for)83 91 y Fk(F)t Fj(.)0 166 y Fk(\017)62 b Fj(A)14 b(co)o(v)o(er)g(is)g Fh(minimal)f Fj(if:)0 241 y(1.)50 b(No)14 b(righ)o(t)f(side)h(has)g(more)f(than)h(one)g(attribute.)0 315 y(2.)50 b(W)m(e)14 b(cannot)g(delete)g(an)o(y)g(FD)g(from)e(the)i (co)o(v)o(er)h(and)83 365 y(ha)o(v)o(e)f(an)f(equiv)n(alen)o(t)h(set)g (of)g(FD's.)0 440 y(3.)50 b(W)m(e)14 b(cannot)g(delete)g(an)o(y)g (attribute)g(from)e(an)o(y)i(left)83 490 y(side)g(and)g(ha)o(v)o(e)g (an)f(equiv)n(alen)o(t)h(set)g(of)g(FD's.)p 0 524 938 2 v 0 620 a Fl(Example)0 690 y Fj(Relation)f Fi(C)s(T)6 b(H)s(RS)r(G)13 b Fj(represen)o(ts)k(courses,)e(teac)o(hers,)0 740 y(hours,)f(ro)q(oms,)e(studen)o(ts,)j(and)f(grades.)21 b(The)14 b(FD's:)0 790 y Fi(C)j Fk(!)d Fi(T)6 b Fj(;)13 b Fi(H)s(R)h Fk(!)g Fi(C)s Fj(;)f Fi(H)s(T)20 b Fk(!)13 b Fi(R)p Fj(;)h Fi(H)s(S)j Fk(!)c Fi(R)p Fj(;)h Fi(C)s(S)i Fk(!)e Fi(G)p Fj(;)0 840 y Fi(C)s(H)g Fk(!)d Fi(R)p Fj(.)0 914 y Fk(\017)62 b Fj(W)m(e)14 b(can)g(eliminate)d Fi(C)s(H)k Fk(!)c Fi(R)p Fj(.)83 989 y Fg(F)50 b Fj(Pro)q(of:)20 b(Using)14 b(the)g(other)h(5)e(FD's,)h Fi(C)s(H)813 974 y Ff(+)858 989 y Fj(=)166 1039 y Fi(C)s(H)s(T)6 b(R)p Fj(.)0 1114 y Fk(\017)62 b Fj(Ha)o(ving)13 b(done)h(so,)g(w)o(e)g (cannot)g(eliminate)e(an)o(y)83 1164 y(attribute)i(from)f(an)o(y)g (left)h(side.)83 1238 y Fg(F)50 b Fj(Sample)12 b(pro)q(of:)20 b(Supp)q(ose)15 b(w)o(e)f(tried)g(to)166 1288 y(eliminate)e Fi(T)20 b Fj(from)12 b Fi(H)s(T)25 b Fk(!)20 b Fi(R)p Fj(.)g(W)m(e)13 b(w)o(ould)166 1338 y(need)i(that)f Fi(C)19 b Fk(!)d Fi(T)6 b Fj(,)13 b Fi(H)s(T)22 b Fk(!)16 b Fi(R)p Fj(,)d Fi(H)s(R)k Fk(!)e Fi(C)s Fj(,)166 1388 y Fi(H)s(S)20 b Fk(!)c Fi(R)p Fj(,)d(and)h Fi(C)s(S)19 b Fk(!)d Fi(G)e Fj(imply)d Fi(H)20 b Fk(!)c Fi(R)p Fj(.)166 1437 y(But)e Fi(H)286 1422 y Ff(+)337 1437 y Fj(=)22 b Fi(H)17 b Fj(with)d(resp)q (ect)i(to)e(these)h(5)166 1487 y(FD's.)0 1562 y Fk(\017)62 b Fj(Th)o(us)14 b(the)h(remaining)d(\014v)o(e)i(are)g(a)f(minimal)d(co) o(v)o(er)k(of)83 1612 y(the)h(original)d(six.)0 1687 y Fk(\017)62 b Fj(Note:)21 b(minim)o(al)10 b(co)o(v)o(er)15 b(need)f(not)g(b)q(e)h(unique,)e(or)83 1736 y(ev)o(en)i(ha)o(v)o(e)e (the)i(same)e(n)o(um)o(b)q(er)g(of)g(FD's.)p 0 1763 V 0 1858 a Fl(Lossless)f(Join)0 1929 y Fj(The)i(decomp)q(osition)f(of)g Fi(R)h Fj(in)o(to)f Fi(S)561 1935 y Ff(1)580 1929 y Fi(;)7 b(:)g(:)g(:)e(;)i(S)698 1935 y Fe(n)734 1929 y Fj(has)14 b(a)0 1979 y Fh(lossless)f(join)h Fj(\(with)g(resp)q(ect)i(to)e(some)f (constrain)o(ts)0 2028 y(on)h Fi(R)p Fj(\))f(if)h(for)f(an)o(y)g (instance)i Fi(r)g Fj(of)e Fi(R)h Fj(that)g(satis\014es)h(the)0 2078 y(constrain)o(ts:)233 2169 y Fi(\031)257 2175 y Fe(S)277 2179 y Fb(1)295 2169 y Fj(\()p Fi(r)q Fj(\))d Fi(.)-7 b(/)11 b Fk(\001)c(\001)g(\001)j Fi(.)-7 b(/)11 b(\031)535 2175 y Fe(S)555 2179 y Fc(n)577 2169 y Fj(\()p Fi(r)q Fj(\))h(=)g Fi(r)0 2284 y Fk(\017)62 b Fj(Motiv)n(ation:)19 b(W)m(e)13 b(can)h(replace)h Fi(R)f Fj(b)o(y)f Fi(S)k Fj(and)83 2334 y Fi(T)6 b Fj(,)13 b(kno)o(wing)g(that)h(the)h(instance) f(of)g Fi(R)f Fj(can)h(b)q(e)83 2384 y(reco)o(v)o(ered)i(from)c(the)i (instances)h(of)f Fi(S)i Fj(and)e Fi(T)6 b Fj(.)0 2475 y Fl(Theorem)0 2545 y Fj(A)14 b(decomp)q(osition)e(of)i Fi(R)f Fj(in)o(to)h Fi(S)i Fj(and)e Fi(T)20 b Fj(has)14 b(a)f(lossless)0 2595 y(join)g(wrt)h(FD's)g Fk(F)j Fj(if)c(and)h(only)f (if)g Fi(S)26 b Fk(\\)d Fi(T)30 b Fk(!)22 b Fi(S)17 b Fj(or)0 2645 y Fi(S)d Fk(\\)e Fi(T)17 b Fk(!)11 b Fi(T)6 b Fj(.)458 2770 y(4)p eop %%Page: 5 5 5 4 bop 0 42 938 2 v 0 140 a Fl(Pro)q(of)0 242 y Fk(\017)62 b Fj(First)14 b(note)h(that)e Fi(r)g Fk(\022)f Fi(\031)466 248 y Fe(S)489 242 y Fj(\()p Fi(r)q Fj(\))g Fi(.)-7 b(/)11 b(\031)623 248 y Fe(T)649 242 y Fj(\()p Fi(r)q Fj(\))j(alw)o(a)o(ys.)0 320 y Fk(\017)62 b Fj(Assume)14 b Fi(S)g Fk(\\)d Fi(T)18 b Fk(!)11 b Fi(S)17 b Fj(and)c(sho)o(w)h(that)343 430 y Fi(\031)367 436 y Fe(S)391 430 y Fj(\()p Fi(r)q Fj(\))d Fi(.)-7 b(/)11 b(\031)524 436 y Fe(T)550 430 y Fj(\()p Fi(r)q Fj(\))h Fk(\022)g Fi(r)83 568 y Fg(F)50 b Fj(Supp)q(ose)15 b Fi(s)f Fj(is)g(in)f Fi(\031)476 574 y Fe(S)500 568 y Fj(\()p Fi(r)q Fj(\))h(and)g Fi(t)g Fj(is)f(in)h Fi(\031)790 574 y Fe(T)816 568 y Fj(\()p Fi(r)q Fj(\),)166 618 y(and)g Fi(s)g Fj(and)g Fi(t)g Fj(join)e(\(i.e.,)h(they)h(agree)h(in)166 668 y Fi(S)f Fk(\\)e Fi(T)6 b Fj(\).)83 746 y Fg(F)50 b Fj(Then)14 b Fi(t)g Fj(is)g(the)g(pro)r(jection)h(of)e(a)h(tuple)g Fi(t)817 731 y Fd(0)842 746 y Fj(of)f Fi(r)166 796 y Fj(that)h(agrees)h(with)e Fi(s)i Fj(on)e Fi(S)r Fj(.)83 874 y Fg(F)50 b Fj(So)14 b Fi(t)239 859 y Fd(0)264 874 y Fj(agrees)h(with)f Fi(t)f Fj(on)h Fi(T)20 b Fj(and)14 b(with)f Fi(s)h Fj(on)g Fi(S)r Fj(,)166 924 y(so)g Fi(t)232 909 y Fd(0)257 924 y Fj(is)g Fi(s)e(.)-7 b(/)11 b(t)p Fj(;)j(i.e.,)e Fi(s)g(.)-7 b(/)11 b(t)j Fj(is)g(in)f Fi(r)q Fj(.)0 1002 y Fk(\017)62 b Fj(Similarly)11 b(if)i Fi(S)h Fk(\\)d Fi(T)18 b Fk(!)11 b Fi(T)6 b Fj(.)p 0 1036 V 0 1118 a Fk(\017)62 b Fj(No)o(w)14 b(assume)f(neither)i(FD)e (follo)o(ws)g(from)f Fk(F)t Fj(.)83 1197 y Fg(F)50 b Fj(Then)14 b(there)i(is)d(an)h(instance)h Fi(r)f Fj(consisting)g(of)166 1246 y(t)o(w)o(o)f(tuples)i(that)f(agree)g(on)g(\()p Fi(S)22 b Fk(\\)c Fi(T)6 b Fj(\))778 1231 y Ff(+)819 1246 y Fj(and)166 1296 y(disagree)15 b(elsewhere.)22 b(This)14 b(instance)g(satis\014es)166 1346 y Fk(F)t Fj(.)83 1424 y Fg(F)50 b Fj(Neither)15 b Fi(S)i Fj(nor)c Fi(T)20 b Fj(is)14 b(con)o(tained)g(in)f(\()p Fi(S)k Fk(\\)c Fi(T)6 b Fj(\))897 1409 y Ff(+)166 1474 y Fj(\(or)14 b(else)h(one)f(of)f(the)i(FD's)e(in)h(question)g(w)o(ould)166 1524 y(follo)o(w\).)83 1602 y Fg(F)50 b Fj(Th)o(us,)14 b Fi(r)g Fj(pro)r(jected)i(and)e(rejoined)g(yields)f(four)166 1652 y(distinct)h(tuples,)g(and)g(cannot)g(b)q(e)g Fi(r)q Fj(.)p 0 1686 V 0 1785 a Fl(Theorem)0 1859 y Fj(W)m(e)f(can)i(alw)o(a)o (ys)d(decomp)q(ose)i(a)g(relation)f Fi(R)h Fj(with)g(FD's)0 1909 y Fk(F)k Fj(in)o(to)13 b(BCNF)h(relations)g(with)g(a)f(lossless)i (join.)0 2003 y Fl(Pro)q(of)0 2106 y Fk(\017)62 b Fj(W)m(e)14 b(decomp)q(ose)f(when)i(w)o(e)f(\014nd)g(a)g(BCNF)83 2155 y(violation)e Fi(X)18 b Fk(!)13 b Fi(Y)d Fj(,)j(in)o(to)g Fi(X)18 b Fk([)c Fi(Y)23 b Fj(and)14 b(\()p Fi(R)c Fk(\000)g Fi(Y)g Fj(\))k Fk([)83 2205 y Fi(X)s Fj(.)0 2283 y Fk(\017)62 b Fj(But)165 2250 y Fa(\000)184 2283 y Fj(\()p Fi(R)12 b Fk(\000)g Fi(Y)d Fj(\))18 b Fk([)f Fi(X)437 2250 y Fa(\001)456 2283 y Fk(\\)g Fj(\()p Fi(X)22 b Fk([)17 b Fi(Y)9 b Fj(\))18 b(=)f Fi(X)s Fj(.)k(Th)o(us)83 2333 y(the)15 b(in)o(tersection)f(of)g(the)g(sc)o(hemas)g(functionally)83 2383 y(determines)g(one)g(of)g(them,)e Fi(X)j Fk([)d Fi(Y)d Fj(.)0 2461 y Fk(\017)62 b Fj(T)m(o)13 b(complete)g(the)i(pro)q (of,)e(w)o(e)h(need)h(to)f(sho)o(w)f(that)83 2511 y(when)h(w)o(e)h (decomp)q(ose)e(further,)i(the)f(resulting)g Fi(n)83 2561 y Fj(relations)g(ha)o(v)o(e)f(a)h(lossless)h(join,)d(but)i(that)g (is)g(an)83 2610 y(easy)g(induction)g(on)f Fi(n)p Fj(.)p 0 2645 V 458 2770 a(5)p eop %%Page: 6 6 6 5 bop 0 42 a Fl(Dep)q(endency)12 b(Preserv)m(ation)0 114 y Fj(When)i(w)o(e)g(decomp)q(ose)g Fi(R)g Fj(with)f(FD's)h Fk(F)t Fj(,)f(will)g Fk(F)k Fj(b)q(e)0 163 y(equiv)n(alen)o(t)c(to)h (the)g(union)g(of)f(its)h(pro)r(jections)h(on)o(to)e(the)0 213 y(decomp)q(osed)h(relations?)0 289 y Fk(\017)62 b Fj(One)15 b(w)o(a)o(y)e(to)h(guaran)o(tee)g(dep)q(endency)83 339 y(preserv)n(ation)h(is)e(to)h(use)h(a)e(minima)o(l)e(co)o(v)o(er,)j (and)83 389 y(con)o(v)o(ert)h(eac)o(h)f(FD)g(in)f(the)i(co)o(v)o(er)f Fi(X)k Fk(!)c Fi(A)g Fj(in)o(to)f(the)83 439 y(sc)o(hema)g Fi(X)s(A)p Fj(.)83 515 y Fg(F)50 b Fj(But)14 b(if)g(there)h(are)f(some) f(attributes)i(not)166 565 y(men)o(tioned)e(in)g(an)o(y)h(FD,)f(mak)o (e)f(them)h(a)166 615 y(sc)o(hema)g(b)o(y)h(themselv)o(es.)0 707 y Fl(Theorem)0 779 y Fj(A)g(minim)o(al)c(co)o(v)o(er)15 b Fk(F)j Fj(yields)13 b(3NF)h(relations.)p 0 814 938 2 v 0 911 a Fl(Pro)q(of)0 983 y Fj(Supp)q(ose)h Fi(X)s(A)f Fj(\(the)h(relation)e(from)g Fi(X)19 b Fk(!)d Fi(A)p Fj(\))e(is)f(not)h(in)0 1033 y(3NF,)f(b)q(ecause)j Fi(Y)21 b Fk(!)11 b Fi(B)16 b Fj(is)e(a)g(3NF)f(violation.)0 1109 y Fk(\017)62 b Fj(W)m(e)14 b(kno)o(w)f Fi(Y)23 b Fj(is)14 b(not)g(a)f(sup)q(erk)o(ey)m(,)i(and)e Fi(B)k Fj(is)c(not)83 1159 y(prime.)0 1235 y Fk(\017)62 b Fj(Case)14 b(1:)20 b Fi(A)15 b Fj(=)g Fi(B)r Fj(.)21 b(Then)15 b Fi(Y)24 b Fk(\032)15 b Fi(X)s Fj(.)21 b(Since)14 b Fi(Y)24 b Fk(!)15 b Fi(B)83 1285 y Fj(follo)o(ws)d(from)g Fk(F)t Fj(,)i(and)f Fi(X)25 b Fk(!)c Fi(A)14 b Fj(surely)g(follo)o(ws)83 1335 y(from)e Fi(Y)33 b Fk(!)22 b Fi(B)r Fj(,)14 b(w)o(e)g(kno)o(w)g Fk(F)j Fj(is)d(equiv)n(alen)o(t)f(to)83 1384 y Fk(F)g(\000)d(f)p Fi(X)15 b Fk(!)c Fi(A)p Fk(g)g([)g(f)p Fi(Y)21 b Fk(!)11 b Fi(B)r Fk(g)p Fj(.)83 1461 y Fg(F)50 b Fj(Then)14 b Fk(F)k Fj(w)o(as)c(not)g(a)f(minima)o(l)e(co)o(v)o(er.)0 1537 y Fk(\017)62 b Fj(Case)14 b(2:)20 b Fi(A)12 b Fk(6)p Fj(=)g Fi(B)r Fj(.)21 b(Then)14 b Fi(B)j Fj(is)c(in)h Fi(X)s Fj(.)83 1613 y Fg(F)50 b Fi(X)18 b Fj(is)13 b(surely)i(a)e(sup)q (erk)o(ey)j(for)d Fi(X)s(A)p Fj(,)h(and)g(since)166 1663 y Fi(B)i Fj(is)e(not)g(prime,)e Fi(B)17 b Fj(m)o(ust)c(not)g(b)q(e)i (in)e(an)o(y)h(k)o(ey)166 1713 y Fi(Z)h Fk(\022)d Fi(X)s Fj(.)83 1789 y Fg(F)50 b Fj(Then)14 b(\()p Fi(X)f Fk(\000)d Fi(B)r Fj(\))i Fk(!)f Fi(A)j Fj(can)g(replace)h Fi(X)g Fk(!)d Fi(A)i Fj(in)166 1839 y Fk(F)t Fj(,)f(sho)o(wing)h Fk(F)j Fj(is)d(again)f(not)h(minim)o(al)o(.)p 0 1873 V 0 1970 a Fl(Decomp)q(osition)c(With)j(3NF,)h(Dep)q(endency)0 2020 y(Preserv)m(ation)d(and)i(Lossless)f(Join)0 2092 y Fj(T)m(o)h(the)i(sc)o(hema)e(from)f(a)i(minim)o(al)c(co)o(v)o(er,)k (add)g(a)f(k)o(ey)h(for)0 2142 y(the)g(original)f(relation)g(if)g (there)i(is)f(not)g(already)f(some)0 2191 y(relation)g(sc)o(hema)h (that)g(is)f(a)h(sup)q(erk)o(ey)m(.)0 2284 y Fl(Example)0 2356 y Fi(R)d Fj(=)h Fi(AB)r(C)s(D)q Fj(;)i Fk(F)i Fj(=)c Fk(f)p Fi(A)f Fk(!)g Fi(B)r(;)c(C)14 b Fk(!)d Fi(D)q Fk(g)p Fj(.)0 2433 y Fk(\017)62 b Fj(Start)14 b(with)g Fi(AB)i Fj(and)e Fi(C)s(D)h Fj(from)d(the)j(FD's.)0 2509 y Fk(\017)62 b Fj(Only)14 b(k)o(ey)g(for)f Fi(R)h Fj(is)g Fi(AC)s Fj(.)0 2585 y Fk(\017)62 b Fj(Th)o(us,)14 b(DP)m(,)f(LJ,)g(3NF) h(decomp)q(osition)f(is)83 2635 y Fk(f)p Fi(AB)r(;)7 b(AC)q(;)g(C)s(D)q Fk(g)p Fj(.)458 2770 y(6)p eop %%Page: 7 7 7 6 bop 0 42 a Fk(\017)62 b Fj(Pro)q(of)14 b(that)g(the)g(decomp)q (osition)f(is)g(alw)o(a)o(ys)g(LJ)h(will)83 91 y(ha)o(v)o(e)g(to)f(w)o (ait)h(for)f(the)i(theory)f(of)f(\\generalized)83 141 y(dep)q(endencies.")83 216 y Fg(F)50 b Fj(This)14 b(decomp)q(osition)e (is)i(ob)o(viously)f(LJ,)g(since)166 266 y Fi(AB)i(.)-7 b(/)13 b(AC)j Fj(is)e(lossless)h(b)q(ecause)g Fi(A)e Fk(!)f Fi(B)r Fj(,)i(and)166 315 y(then)h Fi(AB)r(C)22 b(.)-7 b(/)19 b(C)s(D)c Fj(is)e(lossless)i(b)q(ecause)h(of)166 365 y Fi(C)e Fk(!)d Fi(D)q Fj(.)458 2770 y(7)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF