Luận văn Khảo sát quan hệ armstrong trong cơ sở dữ liệu quan hệ

Lu~n van th~c sl chuyen nganh Tin hQc CHuaNG4 - cAI D~TMOTSOTHU~TToAN. Chuangtrlnhsaildayvie'"tbangligonnguC. Chuangtrlnhth€ hi~nhai thu~tmlnchuye'u. 1- Thu~tminFD-Formula.(thongquahamTabPTH(fn)) 4 - Thu~toanFD (hamtaoPTHO) HamtabPTH(fn)nh~nvaomQt~pvanbancotend?ttrongbie'"nt .T~pvan bannaychinhla mQtbangchanly T. hamchoramQt~pcaccongthuclogic Gnh~nT lambangchanly.Ke'"tquaratucla t~pcaccongthuclogicG duQc hi~nthilenmanhlnh. Ne'"ut~pT khongchuavectordonvi e thlh~th6ngtlfdQngthemecho T. Ne'"ut~pT khongdongd6ivoi phepnhandongthl h~th6ngtlfdQngHmT nho nhfttvadongvoi phepnhandong. HamtaoPTHO nh~ngia tri vaola mQtquailh~R va chora la mQtphil G cua TR. Quanh~ R duQcchotruoctrongmQtt~pvanban.Dongd~utienchua thongtinv~quailh~baag6m: 56 thuQctinh(n). Chi~udai m6ithuQctinh(s6byte). 56 bQcuaquailh~. LLop Cao hQc Tin hQc kh6a 6 Trang 50 Lu~n van th:;lC81chuyen nganh Tin hQc Cacdongtie'ptheo1agia tri cuacacbQ.Cac donvi dli 1i~utrongmQtbQduQc liganvoi nhaubdi da'us6cheo\. Duoi daychl1aph~nmangu6n chinhva cac manhlnh xli'1)'chinh trongchuangtrlnh demo.Chuangtrinh con cho phep nguoidungco th~t~omoi d~nh~pcacbangth~hi~nhayc~pnh~tcacgia tfi cuamQtbangth~hi~n,trongvi~ccaid~tcacthu~ttoanthlchuangtrlnhcho phepth1,ichi~ntungbuckvahi~nthike'tquacuam6ibuoclenmanhlnh. L6p CaD hQc Tin hQc kh6a 6 Trang 51 Lu~n van th~c 81chuyen nganh Tin hQc Caebu'oethlfehi~ntu~ntlfthu?ttoanFD : Blioe 1 :hiSnthibangcaethShi~ndu'<;1e1u'utrongt?Ptin .INP Blioc2 : hiSnthibangehan1y. Lop CaD hQc Tin hQc kh6a 6 Trang 52 Lu:%nvan th~c 81chuyen nganh Tin hQc Buck 3 : hi~nthi gi~lllchanly. BliGC4 : hi~nthi t<%tpcacphv thuQchamtlm du<;5c. Lop CaD hQc Tin hQc kh6a 6 Trang 53 Lu~n van th~c sl chuyen nganh Tin hQc Bu'oc5 : hi€n thi t~pcacphl;!thuQchamcuaphilkh6ngdu. ~ M~mhlnh nh~pcac th€ h . i<$ . n . ... ( n .. h .. ~pvapsf)thuQctl . nh . ' . dQd . a . ' i cu . a ... m6i thuQc inhvacacth€ hi<$n). ... ... m . ... I I.~ChII.d"9 .t..r"...".h Demo ROOXQ.u l..i~uVao.. ;csu: LopCaDhQcTin hQckh6a 6 Trang 54 Lu~n van th~c 81chuyen nganh Tin hQc // / // / / / / // / / // / / // / / // / // // // / // /// / / // // / / / / / / / / / / // / /// / ///// ///// / / // // //// // / // // // / / // / // // / // // / Chuangtrinhkhaosatcaeanhxadongtrongly thuyeteSDL quailhe ////////////////////////////////////////////////////////////////////////////////////////////////////// #include #include #include #include #include /*CACHANGTOANcue */ #defineBL ' I #defineKETDONG '\n' #defineKETXAU '\0' #defineKETTRUONG '\\' #defineUI unsignedint #defineUC unsignedchar #defineMAXSOTT 50 #defineMAXSOBO 1000 #defineByte(b)((b»>3) LopCao hQcTin hQckh6a 6 Trang 55 Lu:}n van th~c si chuyen nganh Tin hQc #define Bit(b) ((b)&7) #defineBitOn(x,t)xl=(1«(t» #defineGetBit(x,t)((x»>(t»&l #defineBitOnA(t,i) t[(i»3)]I=(1«((i)&7» #defineGetBitA(t,i) ((t[(i»>3]»>((i)&7»&1 #defineElemA(t,i) ((t[(i»>3]»((i)&7»&OxOOOI) #defineIncludes(x,y)(((x)&(y»==y) //#defineLaPTH(i) ((GhiNhanPTH[(i»>3]»((i)&7»&OxOOOl) //#defineLoaiBoPTH(i)GhiNhanPTH[(i»>3]&=(UC)-1«((i)&7» /* CAC KIEU VA BIEN TOAN CUC */ typedefchar* PAttr; intSoBo,SoTT,SoByte,* LenTT; VI SoDongDu,SoPhanTuGian,SoPTH; PAttr* Data; VC * Mask; Lop Cao hQc Tin hQc kh6a 6 Trang 56 Lu~n van th~c 81chuyen nganh Tin hQc DI * VeTrai; DI * VePhai; II DC * DaDung;II Danhdati1PTH dadung(Tim Baodong) II DC * GhiNhanPTH;II GhiNhanPTHbo 1PTH (Tim philkhongdu) 1*PROTOTYPES *1 voidErr(inte,char*s); IlvoidXemQuanHe(char*fn); voidQuanHePTH(char*fn,char*gn); voidTabPTH(char*fn,char*gn); voidXemBo(char*s); voidXemBin(longi); voidGhiBin(FILE *g,longi); voidTachBo(FILE *g,char*s, intk); voidSanhBo(inti, intj); voidXemTab(DC *t,DI n); voidGhiTab(FILE *g,DC *t,DI n); voidTaoGian(DC *t); voidXemlPTH(DI x,DI y); voidSinhlPTH(DI &m,DI x,DI y); voidGhilPTH(FILE *g,DIx,DIy); voidXemlVe(DI x); Lop CaD hQc Tin hQc kh6a 6 Trang 57 Lu~n van th~c S1chuyen nganh Tin hQc voidGhil Ve(FILE *g,VI x); voidTaoPTH(FILE *g); voidKhongDuO; VI Closure(VI x, VI m,VI i); voidTestlO; voidErr(inte,char*s) { printf(fI\nLOI %d:fI,e); switch(e) { case1:printf(fIkhongmoduoctepdulieu %Sfl,S); break; case2:printf(fIkhongdumiennhodecapphatcho%Sfl,S); break; case3:printf(fI%Sfl,S); break; } getchO; exit(e); Lop Cao hQc Tin hQc kh6a 6 Trang 58 Lu~n van th~c 81chuyen nganh Tin hQc voidTaoGian(UC *t) longi,j; Ulk-, for(i=(1ong)(SoDongDu-I);i>=O;--i) if (ElemA(t,i) forQ=i-1;j>=O;--j) if (ElemA(t,j» BitOnA(t,i&j); BitOnA(t,SoDongDu-I); BitOnA(t,O); SoPhanTuGian=0; for(k=O;k<SoDongDu;++k) if (ElemA(t,k) ++SoPhanTuGian; SoPTH=SoDongDu- SoPhanTuGian; II CapphatchocaePTH if ((VeTrai=newUI[SoPTH])==NULL) Err(2,"VeTraiPTH"); if ((VePhai=newUI[SoPTH])==NULL) Lop Cao hQc Tin hQc kh6a 6 Trang 59 Lu:%nvan th~c sl chuyen nganh Tin hQc Err(2,"Ve PhaiPTH"); } voidGhiBin(FILE *g,UI i) { intb; for (b=O;b<SoTT;++b) fprintf(g,"%d",GetBit(i,b)); } voidXemBin(UI i) { intb; for (b=O;b<SoTT;++b) printf("%d",GetBit(i,b)); } voidGhilVe(FILE *g,UIx) { UI i; for(i=O;i<SoTT;++i) Lop Cao hQc Tin hQc kh6a 6 Trang 60 Lu~n van th~c 81chuyen nganh Tin hQc if (GetBit(x,i)) fprintf(g,"%c",'A'+i); } voidXeml Ve(UI x) { VI i; for(i=O;i<SoTT;++i) if (GetBit(x,i)) printf("%c",'A'+i); voidXemlPTH(UI x,UI y) { XemlVe(x); printf("->"); XemlVe(y); voidGhilPTH(FILE *g,VI x,UI y) Ldp Cao hQc Tin hQc kh6a 6 Trang 61 Lu~n van th~c 81chuyen nganh Tin hQc Ghil Ve(g,x); f . f( II " )prInt g, -> ; Ghil Ve(g,y); fprintf(g,"\n"); voidSinhlPTH(UI &m,UI x,VI y) { VeTrai[m]=x; VePhai[m]=y; ++m; voidGhiTab(FILE *g,UC *t,VI n) { VI i; fprintf(g,"\n"); for(i=O;i<SoTT;++i) fprintf(g,"%c",i+'A'); fprintf(g,"\n"); for(i=O;i<SoTT;++i) Lop Cao hQc Tin hQc khoa 6 Trang 62 Lu:%nvan th~c si chuyen nganh Tin hQc fprintf(g,"-"); for (i=O;i<n;++i) { if (GetBitA(t,i» { fprintf(g,"\n"); GhiBin(g,i); } } voidXemTab(DC *t,DI n) { DI i; printf("\n"); for (i=O;i<SoTT;++i) printf("%c",i+'A'); printf("\n"); for (i=O;i<SoTT;++i) printf("-"); L Lop Cao hQc Tin hQc kh6a 6 Trang 63 Lu~n van th~c 81chuyen nganh Tin hQc /////////////////////////////////////////////// // Tim baodongcuatapthuoctinhx // lIentaprnPTH {fO,fl,...,f(rn-l)}- {fi } //0 <=i <rn ////////////////////////////////////////////// VI Closure(VIx,VI rn,VI i) { VIj,z; do { z=x; forU=O;j<i;++j) Ldp Cao hQc Tin hQc kh6a 6 Trang 64 for (i=O;i<n;++i) { if (GetBitA(t,i)) { printf("\n"); XernBin(i); } } //printf("%d",i); } Lu~n van th~c sl chuyen nganh Tin hQc if (Includes(x,VeTrai[j]) x 1=VePhai[j]; for(j=i+1;j<m;++j) if (Includes(x,VeTrai[j]) x 1=VePhai[j]; }while ( x !=z); returnx; IIIIIIIIIIIIIIIIIIIIIIIIIIIII I I III II I I I I I I I I I I II DuatapPTH vedangkhongdu IIIIII IIIIIIIIIIIIII IIIIIIIIII II II II I I I I I I I II voidKhongDuO { VI m=SoPTH; VI i =O., while(i <m) if (Includes(Closure(VeTrai[i],m,i),VePhai[i]) { VeTrai[i]=VeTrai[m-l]; VePhai[i] =VePhai[m-l]; Lop Cao hQc Tin hQc kh6a 6 Trang 65 Lu~n van th~c 81chuyen nganh Tin hQc urn; } else++i; SoPTH =rn; } I I I I I I I I I I I II I I I I I I I I II I II III I II I III I I II I II I I I II II II I I II II TaocaePhilthuochamtubangchanly Mask II ghiketquavaofileg I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I II I I I I I I I I I I I I I I I I I voidTaoPTH(FILE *g) { VI x,j,b,y,rn=O; fprintf(g,"\n\nPHVTHVOC HAM: \nil); fprintf(g,"\n"); for (x=O;x<SoDongDu;++x) { if (!ElernA(Mask,x))II x thuocT' - phanbucuabangchanly T { j =OxFFFF; for (b=O;b<SoDongDu;++b) if (ElernA(Mask,b)) II b thuocT if (Includes(b,x))II neubchuax Lop Cao hQc Tin hQc kh6a 6 Trang 66 Lu~n van th~c sl chuyen nganh Tin hQc j &=b; Y =j & (~x); II thi lay giaocuacaeb ghivaGj Ily =j - x (tru2taphop) SinhlPTH(m,x,y); Ghi1PTH(g,x,y); } } KhongDuO;II Non-redundantcover fprintf(g,"\nPHUKHONGDU:\n"); fprintf(g,"\n"); for U=O;j<SoPTH;++j) Ghi1PTH(g,VeTraiU],VePhaiU]); } IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII II TachbosdoctuQUAN HE thanhcaetruong II lingvoicaethuoctinh IIIIII IIIIIIIIIIII I I I I I I I I I I I I I I I I I I I I I I I I I I I I I II I I voidTachBo(FILE*g,char*s,intk) { inti,j,t;lit: thuoctinhthumay for(i=O;s[i]!=KETDONG&&s[i] !=KETXAU;++i); Ldp Cao hQcTin hQckh6a 6 Trang 67 Lu~n van th~c 81chuyen nganh Tin hQc s[i++] =KETTRUONG; s[i] =KETXAU; .- fprintf(g, "ill"); for(i=t=O;t<SoTT;++t,+k) { if ((Data[k]=newchar[LenTT[t]+l])==NULL) Err(2,"truongdulieu"); forU=O;(Data[k][j]=s[i])!=KETTRUONG;++i,++j); for(;j<LenTT[t];++j) Data[k][j]=BL; Data[k][j]=KETXAU; ++1; fprintf(g,"%s",Data[k]); } } IIIIIIIIIIIIIIIIIIIIIIIII I I II I I I I I I I I I I I I I I I I I I I I I I II Sosanh2bou= II w= II taoradong0/1;voimoii: 1<=i <=n: II II v= vi = 1, lieu ui =wi Lop Cao hQc Tin hQc kh6a 6 Trang 68 Lu~n van th~c sl chuyen nganh Tin hQc // =0, neuui #wi / / / // / / // / // / / /// / // / // / // // // / / / / /// // // // // // / / / void SanhBo(inti, intj) { int t; VI v =O., for (t=O;t<SoTT;++t) if (strcmp(Data[i*SoTT+t],Data[j*SoTT+t])==O) BitOn(v,t); BitOnA(Mask,v); } ///////////////////////////////////////////////// ///////////////////////////// //////////// voidTabPTH(char*fn,char*gn) { FILE *f,*g; chars[80]; Lop Cao hQc Tin hQc khoa 6 Trang 69 // Doc dulieu tumotbang0/1tutepfn // Tao ra tapphil thuocham, // ghiketquavaGtepgn Lu(ln van th~c 81chuyen nganh Tin hQc int i,j,k,m; UI t; II Mo tepnguonfn if ((f=fopen(fn,"rt"))==NULL)Err(1,fn); if ((g=fopen(gn,"wt"))==NULL)Err(l,gn); II m:Sodongcuabang,SoTT: So thuoctinh fscanf(f,"%d%d",&m,&SoTT); for(SoDongDu=1,i=O;i<SoTT;++i) SoDongDu«= 1; SoByte=(int)(SoDongDu+7)/8; II printf("\nn=%d",n);getchO; if ((Mask=newUC[SoByte])==NULL) Err(2,"Mask"); memset(Mask,O,SoByte); II chuyendongmoi fgets(s,81,f); II Duyettepfn Ldp CaD hQc Tin hQc kh6a 6 Trang 70 Lu~n van th~c si chuyen nganh Tin hQc for(i=O;i<m;++i) { fgets(s,81,f); II Doc 1 dong for (t=O,k=j=O;s[j] !=KETDONG&&s[j] !=KETXAU ;++j) if (s[j]=='l') { BitOn(t,k); ++k-, } elseif (s[j]=='O') ++k; BitOnA(Mask,t); } fclose(f); fprintf(g,"\n\nBANGCHAN LY:\n"); GhiTab(g,Mask,SoDongDu); TaoGian(Mask); fprintf(g,"\n\nGIANCHAN LY:\n"); GhiTab(g,Mask,SoDongDu); TaoPTH(g); deleteLenTT; deleteMask; Lop Cao hQc Tin hQc kh6a 6 Trang 71 Lu~n van th~c si chuyen nganh Tin hQc deleteVeTrai; deleteVePhai; printf("Ket"); fclose(g); } I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I II II TimtapPTH thoaquailheehotruoe II input:Quanheghitrongtepin,dang II Dongdatilien: II II m n a1a2 ...an, trongdo: II II m- sobo n - sothuoetinh II ai - dorangeuathuoetinhthui, i =l..n II Caedongtieptheola caebo,moitruongeachnhauboi dati\ II 1*Thi du,tepQUANHE l.INP 542222 a\l\a\x b\2\a\y e\l\b\z Lop Cao hQcTin hQckh6a 6 Trang 72 Lu~n van th~c sl chuyen nganh Tin hQc d\2\b\x c\1\a\z */ // Dulieuraghitrongtepgn //////////////////////////////////////////////////////////// voidQuanHePTH(char*fn,char*gn) { FILE *f,*g; chars[80]; int i,j,t=O; longn,k; if ((f=fopen(fn,"rt"))==NULL)Err(l,fn); if ((g=fopen(gn,"wt"))==NULL)Err(l,gn); fscanf(f,"%d%d",&SoBo,&SoTT); if (SoTT==O) Err(3,IISoThuoctinh=Oil); for(SoDongDu=1,i=O;i<SoTT;++i) SoDongDu«= 1; SoByte=(int)(SoDongDu+7)/8; Data=NULL; if (SaBa>0) Lop CaDhQcTin hQckh6a 6 Trang 73 Lu~n van th~c sl chuyen nganh Tin hQc { n =SoBo*SoTT; if ((Data=newPAttr[n])==NULL) Err(2,"Data"); } if ((Mask=newUC[SoByte])==NULL) Err(2,"Mask"); memset(Mask,O,SoByte); if ((LenTT =new int[SoTT])==NULL) Err(2,"LenThuocTinh"); for(i=O;i<SoTT;++i) fscanf(f,"%d",&LenTT[i]); fprintf(g,"QUANHE:\n\n"); for(i=O;i<SoTT;++i){ fprintf(g,"%c",'A'+i); for U=O;j<LenTT[i];++j) fprintf(g,"%c",BL); } fprintf(g,"\n"); for(i=O;i<SoTT;++i) for U=O;j<=LenTT[i];++j) Lop Cao hQcTin hQckh6a 6 Trang 74 Lu~n van th~c 81chuyen nganh Tin hQc fprintf(g,"-"); for(i=O;i<SoBo;++i) { fgets(s,80,f); TachBo(g,s,t); t +=SoTT', } fclose(f); //BitOnA(Mask,SoDongDu-l); for (i=O;i<SoBo;++i) for (j=i+1;j<SoBo;++j) SanhBo(i,j); fprintf(g,"\n\nBANGCHAN LY:\n"); GhiTab(g,Mask,SoDongDu); TaoGian(Mask); fprintf(g,"\n\nGIANCHAN LY:\n"); GhiTab(g,Mask,SoDongDu); TaoPTH(g); deleteLenTT; if (Data!=NULL) { for (i=O;i<n;++i) Lop Cao hQc Tin hQc kh6a 6 Trang 75 Lu~n van th~c sl chuyen nganh Tin hQc deleteData[i]; deleteData; } deleteMask; deleteVeTrai; deleteVePhai; fclose(g); printf("Ket"); } voidTestlO { clrscrO; QuanHePTH("QUANHE.INP", "PTH.OUT"); getchO; } voidTest20 { clrscrO; TabPTH("TAB.INP", "PTH.OUT"); getchO; Lop Cao hQcTin hQckh6a 6 Trang 76 Lu~n van th~c 81chuyen nganh Tin hQc } mainO { TestlO; return0; }