Cơ sở dữ liệu nâng cao

Nội dung text: Cơ sở dữ liệu nâng cao

1. o0o Cơ sở dữ liệu nâng cao
2. CHƯƠNG 1 TNG QUAN V H QUN TR CƠ S D LIU QUAN H Trong chương này chúng ta h thng li các khái nim cơ bn ca cơ s d liu quan h. Mc đích là đnh ngh ĩa các thut ng, đưa ra b khung cơ s cho các phn sau. Vi c chn mơ hình cơ s d li u quan h làm h thng cơ s cĩ nhiu lý do: th nh t là cơ s tốn hc vng chc ca mơ hình quan h làm nĩ tr thành mơ hình lý tưng trong vic gii quyt các vn đ lý thuy t, hai là phn ln các vn đ trình bày trong các chương sau cĩ th mơ t d dàng bi mơ hình quan h, ba là th trưng h qu n tr cơ s d li u quan h rt phát trin và vn đang m rng và cui cùng là ph n ln các h cơ s d liu sau này cũng thu c loi quan h. Mơ hình quan h cĩ ba đc tr ưng cơ bn: 1. Cu trúc d li u đơn gin. Chúng là các quan h (relation), đưc biu din nh ư các bng 2 chiu vi ph n t là các bn ghi (record, data item). Nĩ cung cp đc tính đc lp mc đ cao so vi dng biu th vt lý ca d liu. 2. Mơ hình quan h cung cp mt nn tng vng chc, bo đm đưc tính nh t quán d li u (data consistency). Thit k cơ s d li u đưc h tr bi quá trình chu n hố, giúp loi b các bt thưng d li u. Các trng thái nh t quán ca mt cơ s d liu cĩ th đưc đnh nghĩa và duy trì mt cách thng nht qua các quy tc tồn vn cơ s d liu (integrity rules). 3. Mơ hình quan h cho phép các thao tác trên quan h theo kiu tp hp. ðc tính này đã dn đn vic phát trin các ngơn ng phi th tc mnh m vi nn tng là lý thuyt tp hp (đi s quan h) ho c lơgic (phép tính quan h). 1. Khái nim cơ s d li u 1.1. Cơ s d li u D liu đưc lưu tr trên các thit b lưu tr theo mt cu trúc nào đĩ đ cĩ th phc v cho nhiu ng ưi s dng vi nhiu mc đích khác nhau gi là cơ s d li u. 1.2. H qun tr cơ s d li u Phn mm cho phép mt ho c nhiu ngưi to lp, lưu tr, cp nht và khai thác cơ s d li u gi là h qu n tr cơ s d li u (DataBase Management Systems - DBMS). Vai trị chính ca h qun tr cơ s d liu là cho phép ngưi dùng thao tác vi d li u thơng qua các thut ng trìu tưng, khác vi vic máy tính lưu tr d liu. Theo nghĩa này h qu n tr cơ s d li u cĩ nhim v như là mt b thơng dch (interpreter) vi ngơn ng bc cao nh m giúp ngưi dùng s dng h thng mà khơng cn quan tâm đn cách biu din d li u trong máy ho c các thut tốn chi tit. Ví d ngưi dùng khơng cn bit h qun tr cơ s d li u Access t chc d li u theo kiu hàm băm, kiu file ch mc hay kiu cây cân bng, và cũng khơng cn bit thut tốn thc hin lnh sp xp là Quick Sort, thu t tốn ni bt hay sp xp nh phân Mt cơ s d li u gm mt ho c nhiu tp tin đưc thit k theo mt cu trúc nh t đnh và cĩ quan h cht ch vi nhau. Cơ s d liu đưc dùng chung cho Chương 1. Tng quan v h qun tr cơ s d li u quan h 3
3. nhiu ng ưi và nhiu mc đích khác nhau, vì vy s ti t kim đưc tài nguyên, gim thiu s trùng lp thơng tin, bo đm tính nht quán thơng tin. 1.3. Các đc trưng ca ph ương pháp cơ s d li u + Chia s d li u. Mc đích chính ca cách tip cn cơ s d li u là d li u đưc chia s bi nhiu ng ưi dùng hp pháp. + Gim thiu dư tha d liu. D li u dùng chung cho nhiu b phn, thay vì đưc lưu tr phân tán trùng lp nay đưc lưu tr tp trung mt ch theo mt cu trúc thng nht. + Tính tương thích d liu. Vic loi b s dư tha d li u kéo theo h qu là s tương thích d li u. Ví d khi đa ch nhân viên thay đi thì tt c các b phn đu đưc cp nht đa ch mi. + Tính tồn vn d li u (data integrity). Mi cơ s d liu cn đm bo mt s loi ràng buc tồn vn (integrity constraints). ðc bit khi ng ưi dùng thc hin các thao tác như chèn, xố hay sa đi d liu thì các ràng buc đĩ cn ph i đưc kim tra mt cách cht ch. + Bo mt d liu (data security) . Khi cĩ nhiu ngưi cùng chia s d liu, vic bo đm an tồn d liu và bo mt thơng tin là ti quan trng. Cn ph i cĩ cơ ch bo mt nh ư mt khu (password) và phân quyn truy cp d liu (data access rights ). + Tính đng b d li u (synchronization). Thơng thưng cơ s d li u đưc nhiu ngưi dùng truy cp đng thi, gây nên s cnh tranh d li u. Vì vy cn cĩ cơ ch bo v chng s khơng tương thích bi các thao tác cùng lúc lên d liu. + Tính đc lp d li u. S tách bit cu trúc mơ t d liu kh i chương trình ng dng s dng d liu gi là đc lp d liu. ðiu này cho phép phát trin t chc d liu mà khơng cn sa đi chương trình ng dng. S đc lp d liu là mt trong mc tiêu chính ca cách tip cn cơ s d li u. Tương t như mt phn mm, vịng đi ca cơ s d liu gm cĩ các giai đon chính sau: - Lp k ho ch cơ s d li u (database planning). - Kho sát, phân tích (study and analysis). - Thit k cơ s d li u (database design). - Cài đt cơ s d liu (database implementation). - Bo trì c ơ s d liu (post-implementation). 1.4. Lưc đ d liu và th hin d li u Khi thit k cơ s d liu ta to ra cu trúc cơ s d liu, cái đĩ gi là lưc đ d li u. Ví d lưc đ d li u h sơ nhân s gm các thành phn sau: H tên, ngày sinh, h s lương Các thành ph n ca lưc đ d li u gi là thu c tính ho c trưng. Khi s dng cơ s d liu thì ta làm vic vi d liu tht s, đĩ là s th hin d li u. Ví d đi vi lưc đ trên ta cĩ th cĩ các th hi n d liu sau: Nguyn Văn A, 20/08/1970, 3.40 Chương 1. Tng quan v h qun tr cơ s d li u quan h 4
4. Trn Th B, 15/05/1962, 4.12 Mi th hin d liu gi là b hay bn ghi. 1.5. Các mc trìu tưng d liu Gia máy tính thao tác vi các bit, ngưi thit k cơ s d liu và ngưi dùng cĩ cách nhìn khác nhau đi vi d liu, đĩ chính là các mc trìu tưng d liu. Sơ đ chu n v các mc trìu tưng nh ư sau: Nhĩm ngưi dùng 1 khung nhìn 1 Nhĩm ngưi dùng 2 khung nhìn 2 CSDL CSDL khái vt nim lý Nhĩm ngưi dùng n khung nhìn n a. Cơ s d liu vt lý: nm c đnh trong các thit b lưu tr như đĩa và băng t. Bn thân cơ s d li u vt lý cũng cĩ nhiu mc trìu tưng khác nhau: t mc bn ghi và file trong ngơn ng lp trình nh ư PASCAL, qua mc bn ghi lơgic đưc h tr bi h điu hành, đn mc các bit và đa ch vt lý trong các thit b lưu tr. b. Cơ s d li u khái nim (schema): là s trìu tưng th gii thc đi vi mt đi tưng nào đĩ. H qu n tr cơ s d li u cung cp ngơn ng thit k d li u đ thit k sơ đ khái nim. ðây là ngơn ng bc cao cho phép mơ t cơ s d li u khái nim bng ngơn ng "mơ hình d liu". Mt ví d đin hình là đ th cĩ hưng trong mơ hình mng, trong đĩ các nút biu din các đơ n th và các cung biu din quan h. c. Khung nhìn hoc lưc đ con (subschema): là mơ hình trìu tưng mt phn ca cơ s d li u khái nim. Cĩ nh ng h trang b cơng c gi là ngơn ng thit k khung nhìn cho phép khai báo khung nhìn, và cơng c gi là ngơn ng thao tác d liu khung nhìn đ din t câu hi và các thao tác đi vi khung nhìn. Theo mt ngh ĩa nào đĩ, khung nhìn là cơ s d li u khái nim và cùng mc trìu tưng nh ư cơ s d liu khái nim. Mt khác khung nhìn cĩ th trìu tưng hơn theo ngh ĩa d li u ca nĩ đưc suy ra t cơ s d li u khái nim. d. ðc lp d li u ðc lp d li u d liu gia các mc trìu tưng cĩ ý ngh ĩa rt quan trng đi vi cơ s d liu. Chương 1. Tng quan v h qun tr cơ s d li u quan h 5
5. - ðc lp d li u mc vt lý: S thay đi lưc đ d li u vt lý khơng làm thay đi lưc đ d li u mc khái nim và mc khung nhìn. Ta cn hiu rng s thay đi t chc vt lý d li u cĩ th làm nh hưng đn hiu qu chương trình ng dng. S đc lp d li u mc vt lý đm bo khơng ph i vit li chương trình ch vì lý do thay đi cách t chc d liu. ý ngh ĩa ca tính đc lp d li u mc vt lý là nĩ cho phép ta tinh chnh cơ s d liu mc vt lý đ tăng hiu qu s dng trong khi các chương trình ng dng vn chy bình thưng như khơng cĩ vn đ gì xy ra. - ðc lp d li u lơgic: S thay đi lưc đ d liu khái nim khơng làm thay đi khung nhìn. Trong quá trình s dng cơ s d liu cĩ th ta phi sa đi hiu chnh lưc đ khái nim, chng hn thêm thơng tin v thc th mà cơ s d liu mơ t. 1.6. Ngơn ng d li u Mi h qu n tr cơ s d liu cn phi cĩ ngơn ng riêng ca mình. Cĩ hai loi ngơn ng cơ s d li u. a. Ngơn ng mơ t d liu (Data Definition Language - DDL). Gm các lnh cho phép khai báo, hiu chnh cu trúc cơ s d liu, mơ t các mi quan h ca d liu cũng như các quy tc áp đt lên d liu. Ngơn ng mơ t d liu đưc xây dng da trên loi mơ hình d li u (mơ hình quan h, mơ hình mng, mơ hình phân cp, mơ hình hưng đi tưng ) mà h qu n tr cơ s d liu tương ng đưc thit k. b. Ngơn ng thao tác d li u (Data Manipulation Language - DML). Là b lnh cho phép ng ưi dùng thc hin các cơng vic: - Cp nht d liu nh ư thêm, sa, xố. - Truy vn, tng hp d liu. - Các hàm tính tốn. - Bo mt d liu. * Giao tip ngơn ng ch : là kh năng cho phép chương trình vit trong các ngơn ng bc cao nh ư COBOL, C , cĩ th truy cp x lý d li u trong cơ s d liu. * Ngơn ng truy vn SQL : là ngơn ng cĩ cú pháp ting Anh, giúp ng ưi dùng cĩ th thao tác d li u d dàng mà khơng cn lp trình. ðây là loi ngơn ng th h th 4 vi đc trưng phi th tc. 2. Khái nim cơ s d li u quan h 2.1. Mi n Min là tp hp các giá tr. Ngưi ta thưng dùng ch hoa đ ký hiu min. ◊ Ví d. Các tp hp sau là các min: - Tp các s nguyên. - Tp các xâu ký t đ dài khơng quá 30 ký t. - A = {0,1}. Chương 1. Tng quan v h qun tr cơ s d li u quan h 6
6. 2.2. Tích ð-các Tích ð-các ca các min D1, D 2, , Dn, ký hiu là D1 × D2 × × Dn, là tp hp tt c n-b (v1, v2, , vn) tho mãn v1∈D1, v2∈D2, , vn∈Dn. Tc là D1 × D2 × × Dn = {(v1, v2, , vn) | v1∈D1, v2∈D2, , vn∈Dn }. ◊ Ví d. Cho D1 = {0,1}, D2 = {a,b,c}. Khi đĩ tích đ-các D1× D2 = {(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)} 2.3. Quan h Quan h là tp con ca tích đ-các ca 1 ho c nhiu mi n. Quan h cĩ th cĩ hu hn ho c vơ hn s ph n t. Trong giáo trình này ta gi thit rng quan h cĩ hu hn ph n t. ◊ Ví d Cho D1 = {0,1}, D2 = {a,b,c}. Tp r = {(0,a),(1,b),(1,c)}⊂ D1×D2, vy r là quan h trên D1 và D2. Ta nĩi quan h r cĩ bc n nu r là tp con ca tích đ-các ca n min. Mi ph n t ca quan h gi là b. Mi b ca quan h bc n, cịn gi là n-b, cĩ n thành phn. Mi thành ph n ca b là nguyên t, cĩ nghĩa khơng th phân tách đưc thành các thành ph n nh hơn. ð trc quan ta cĩ th coi quan h như mt bng trong đĩ mi hàng là mt b và mi ct ng vi mt thành phn. D li u đưc t chc dưi dng các quan h cĩ liên quan vi nhau gi là cơ s d li u quan h. Mi ct ca quan h đưc gán mt tên gi là thuc tính. Tp hp tt c các tên thu c tính ca quan h gi là lưc đ quan h. Tp hp các lưc đ quan h ca mt cơ s d liu gi là lưc đ cơ s d liu quan h. • Các tính cht ca quan h - Các giá tr trên ct phi cùng mt min giá tr và đơn tr. Giá tr trên giao ca ct và hàng đơ n tr, khơng chp nh n nhiu giá tr. - Mi hàng là duy nh t. Khơng cho phép hai hàng hồn tồn ging nhau. ◊ Ký hiu Lưc đ quan h R cĩ các thuc tính A1, A2, , An ký hiu là R = (A1, A2, , An) Quan h r vi lưc đ R = (A1, A2, , An) cĩ th vit Chương 1. Tng quan v h qun tr cơ s d li u quan h 7
7. r(R) hoc r(A1, A2, , An) Cho r là quan h vi lưc đ R = (A1, A2, , An), t là mt b ca r, A ⊂ {A1, A2, , An}. Khi đĩ t(A) ký hiu b các thành ph n ca t ng vi các thu c tính trong tp A. Nu A là 1 thu c tính thì t(A) chính là giá tr thành ph n ng vi thu c tính A. ◊ Ví d ðây là ví d s dùng làm cơ s d li u mu đ mơ hình hố mt cơng ty. Các thc th đưc mơ hình hố là: - Các nhân viên, ký hiu EMP, vit tt t employee . - Các d án, ký hiu PROJ, vit tt t project. ði vi mi nhân viên chúng ta mun theo dõi các thơng tin sau: - Mã s nhân viên, ký hiu ENO, vit tt t employee number. - Tên nhân viên, ký hiu ENAME, vit tt t employee name. - Ch c v, ký hiu TITLE. - Lương , ký hiu SAL, vit tt t salary. - Mã s d án , ký hiu PNO, vit tt t project number. - Nhim v d án , ký hiu RESP, vit tt t responsibility. - Thi gian làm vic trong d án, ký hiu DUR, vit tt t duration. ði vi mi d án chúng ta mun theo dõi các thơng tin sau: - Mã s d án , ký hiu PNO, vit tt t project number. - Tên d án, ký hiu PNAME, vit tt t project name. - Kinh phí d án , ký hiu BUDGET. Các lưc đ quan h (relation scheme) cho cơ s d liu này cĩ th đnh ngh ĩa nh ư sau: EMP(ENO, ENAME, TITLE, SAL, PNO, RESP, DUR) PROJ(PNO, PNAME, BUDGET) Lưc đ EMP cĩ 7 thuc tính (attribute): ENO, ENAME, TITLE, SAL, PNO, RESP, DUR. Giá tr ca ENO ly t min cha các mã s nhân viên, gi s là D1, Giá tr ca ENAME ly t mi n cha các tên nhân viên hp l, gi s là D 2, ðây là mt th hin cơ s d li u mu ca chúng ta gm hai bng như sau: EMP ENO ENAME TITLE SAL PNO RESP DUR E1 J.Doe Elect.Eng. 40000 P1 Manager 12 E2 M.Smith Syst.Anal. 34000 P1 Analyst 24 E2 M.Smith Syst.Anal. 34000 P2 Analyst 6 E3 A.Lee Mech.Eng. 27000 P3 Consultant 10 E3 A.Lee Mech.Eng. 27000 P4 Engineer 48 E4 J.Miller Programmer 24000 P2 Programmer 18 E5 B.Casey Syst.Anal. 34000 P2 Manager 24 Chương 1. Tng quan v h qun tr cơ s d li u quan h 8
8. E6 L.Chu Elect.Eng. 40000 P4 Manager 48 E7 R.David Mech.Eng. 27000 P3 Engineer 36 E8 J.Jones Syst.Anal. 34000 P3 Manager 40 PROJ PNO PNAME BUDGET P1 Instrumentation 150000 P2 Database Development 135000 P3 CAD/CAM 250000 P4 Maintenance 310000 Các ct ca bng tương ng các thuc tính ca quan h. Các thơng tin nhp theo hàng tương ng vi các b hay bn ghi. Dịng trên cùng biu din lưc đ quan h ca bng. Mt giá tr ca thu c tính, chng hn lương ca nhân viên, thi gian tham gia d án, ti thi đim nào đĩ cĩ th chưa đưc xác đnh. Khi đĩ cĩ nhiu cách din gii khác nhau như “chưa đưc bit” hay “chưa áp dng đưc”. “Giá tr đc bit” thưng đưc gi là null. Giá tr null ph i khác các giá tr trong min thuc tính, và cũng cn phân bêt nĩ vi giá tr zero (v i thu c tính kiu s) hay giá tr rng (vi thu c tính kiu ký t). 2.4. Khố a) Siêu khố Cho lưc đ quan h R=(A1, A2, , An) và tp con S ⊂ { A1, A2, , An }. Tp S gi là siêu khố (superkey) ca lưc đ R nu các thu c tính ca S xác đnh duy nh t các b ca mi quan h ca lưc đ R, tc là vi mi quan h r ca lưc đ R phi tho mãn: ∀ t1, t2 ∈ r: t1 ≠ t2 ⇒ ∃ A∈ S: t1(A) ≠ t2(A) Lưu ý rng theo đnh ngh ĩa, mi b là duy nht nên đi vi mi lưc đ quan h, tp hp tt c thu c tính là siêu khố. Siêu khố là cơ s đ phân bit 2 b khác nhau trong 1 quan h. Mt lưc đ cĩ th cĩ nhi u siêu khố. Tính cht ca siêu khố là quy lut đưc xác đnh trong quá trình phân tích thit k cơ s d liu. ◊ Ghi chú (1) Tp tt c thu c tính R là siêu khố (tm thưng). (2) S ⊂ T ⊂ R & S là siêu khố ⇒ T là siêu khố. b) Khố Tp K các thu c tính ca lưc đ R là khố (key) nu K là siêu khố cc tiu, tc là mi tp con thc s ca K khơng ph i là siêu khố. • Mnh đ: Mi lưc đ quan h luơn cĩ khĩa. Chương 1. Tng quan v h qun tr cơ s d li u quan h 9
9. Ch ng minh. Mnh đ suy ra t s tn ti ph n t cc ti u trong tp cĩ quan h th t. ◊ Ví d Lưc đ PROJ cĩ khố là PNO. Lưc đ EMP cĩ khố là (ENO, PNO). Các thu c tính thuc khố nào đĩ gi là thuc tính khố hay thu c tính nguyên t. Thu c tính khơng phi thu c tính khố gi là thuc tính khơng khố. Mi quan h cĩ ít nh t mt khố. Tr ưng hp cĩ nhi u khố thì gi các khố đĩ là khố d tuyn (candidate key), trong đĩ cĩ mt khố là khố chính (primary key). c) Khố ngo i Cho lưc đ R và lưc đ Q. Tp con H các thu c tính ca R gi là khố ngo i ca R tham chiu đn lưc đ Q, nu Q cĩ khố K gm các thu c tính (cĩ th dưi tên khác) ca H tho mãn: Vi mi quan h r và q là các quan h ca 1 cơ s d li u ng vi lưc đ R và Q ta cĩ: ∀x∈r ∃y∈q: x(H) = y(K) ◊ Ví d Lưc đ EMP cĩ khố ngoi PNO tham chiu đn khố PNO ca lưc đ PROJ. dng bng cơ s d liu mu ca chúng ta gm 2 bng nh ư sau EMP ENO ENAME TITLE SAL PNO RESP DUR P1 PROJ PNO PNAME BUDGET P1 3. Quy tc tồn vn Qui tc tồn vn (integrity rule ) là các ràng buc đm bo trng thái nh t quán ca cơ s d liu. Chúng thưng đưc din t nh ư là các ràng buc tồn vn. Cĩ các loi qui tc tồn vn sau: Tồn vn thc th (Entity integrity), Min giá tr (Domains integrity), Tồn vn tham chiu (Referential integrity), Thao tác by (Triggering operations). 3.1. Qui tc tồn vn thc th Chương 1. Tng quan v h qun tr cơ s d li u quan h 10
10. Qui tc tồn vn thc th yêu cu thc th ph i cĩ khố chính, các thu c tính khố ph i cĩ giá tr duy nh t và khác null. Qui tc này khơng cho phép hai bn ghi trùng khố. ◊ Ví d. Xét cơ s d liu EMP(ENO, ENAME, TITLE, SAL, PNO, RESP, DUR) PROJ(PNO, PNAME, BUDGET) Qui tc tồn vn thc th ràng bu c: - Trong lưc đ PROJ thuc tính khố PNO khơng th nhn giá tr null và cĩ giá tr khơng trùng nhau. - Trong lưc đ EMP cp thu c tính khố (EMP, PNO) khơng th nh n giá tr null và cĩ giá tr khơng trùng nhau. 3.2. Qui tc min giá tr ðây là loi ràng buc lên các giá tr hp l ca thu c tính. Min giá tr là tp hp tt c các loi d liu và phm vi giá tr đưc thu c tính tha nh n. ðnh ngh ĩa min giá tr xác đnh các tham s đc trưng ca thu c tính: kiu d liu (data type), đ dài (length), khuơn dng (format), ph m vi (range), giá tr cho phép (allowable values), ý ngh ĩa (meaning), tính duy nh t (uniqueness), chp nh n giá tr null (null support). ◊ Ví d. Xét quan h PROJ( PNO, PNAME, BUDGET) Các thu c tính PNAME và BUDGET cĩ ràng bu c min giá tr như sau Tên thu c tính : PNAME BUDGET Ý ngh ĩa : Tên d án Kinh phí d án Kiu d liu : Ký t (Character) S (numeric) ð dài : 20 10 Format : 9,999,999 Phm vi : > 1000 & <10,000,000 Giá tr cho phép : Duy nht : Cĩ Khơng Null support : Non-null Null 3.3. Qui tc tồn vn tham chiu Tồn vn tham chiu là ràng bu c đm bo tính hp l ca s tham chiu ca mt đi tưng trong cơ s d liu (gi là đi tưng tham chiu) đn đi tưng khác (g i là đi tưng đưc tham chiu) trong cơ s d liu đĩ. Các thuc tính tương ng gi thu c tính cp ghép ca ràng buc tham chiu. Chương 1. Tng quan v h qun tr cơ s d li u quan h 11
11. ◊ Ví d. Xét các quan h EMP(ENO, ENAME, TITLE, SAL, PNO, RESP, DUR) PROJ(PNO, PNAME, BUDGET) Vi mi b e ∈ EMP ph i tn ti b p∈ PROJ sao cho e(PNO) = p(PNO) Thu c tính PNO ca quan h EMP là khố ngo i tham chiu đn khố chính PNO ca quan h PROJ: EMP.PNO→PROJ.PNO Quan h EMP là quan h tham chiu và quan h PROJ là quan h đưc tham chiu, vi thuc tính cp ghép là (EMP.PNO, PROJ.PNO). Qui tc tồn vn tham chiu đưc xét đn trong khi cp nh t quan h tham chiu ho c quan h đưc tham chiu. Ta xét các qui tc con sau. • Qui tc chèn: Khơng th chèn hàng mi vào quan h tham chiu nu quan h đưc tham chiu chưa cĩ d li u thu c tính cp ghép tương ng. ◊ Ví d. Xét các quan h EMP và PROJ. Gi s ta mun chèn bn ghi e = (E1, J.Doe, Elect.Eng., 40000, P5, Manager, 20) trong đĩ P5 là d án Elect.Commerce (thương mi đin t) vi kinh phí 500000 USD. Khi đĩ, nu quan h PROJ chưa cĩ bn ghi p = (P5, Elect.Commerce, 500000) thì qui tc chèn đm bo khơng th chèn bn ghi e vào quan h EMP đưc. Mun chèn bn ghi e vào quan h EMP, trưc ht ta phi chèn bn ghi p vào quan h PROJ. • Qui tc xố : Khơng th xố hàng ca quan h đưc tham chiu nu hàng đĩ cĩ d liu thu c tính cp ghép tương ng trong quan h tham chiu. ◊ Ví d. Xét các quan h EMP và PROJ. EMP ENO ENAME TITLE SAL PNO RESP DUR E1 J.Doe Elect.Eng. 40000 P1 Manager 12 E2 M.Smith Syst.Anal. 34000 P1 Analyst 24 E2 M.Smith Syst.Anal. 34000 P2 Analyst 6 PROJ PNO PNAME BUDGET Chương 1. Tng quan v h qun tr cơ s d li u quan h 12
12. P1 Instrumentation 150000 P2 Database Development 135000 P3 CAD/CAM 250000 P4 Maintenance 310000 Gi s d án P1 đã kt thúc và ta mun xố nĩ kh i quan h PROJ. Tuy nhiên các bn ghi mt và hai ca EMP tham chiu đn d án P1, vì th ta khơng th xố d án P1 đưc. Tuy nhiên, qui tc tồn vn tham chiu cho phép các ph ương án la chn sau: 1) Restrict: Khơng cho xố. 2) Nullify : Gán giá tr null cho thu c tính cp ghép ca các bn ghi ca quan h tham chiu tham chiu đn bn ghi b xố. 3) Cascade: Xố tt c các bn ghi ca quan h tham chiu tham chiu đn bn ghi b xố. 3.4. Qui tc thao tác by Qui tc thao tác by là qui tc yêu cu tính hp pháp ca d li u trong các tác nghip cp nh t như xố, chèn và sa. Thao tác by cĩ th liên quan đn các thuc tính ca mt quan h hoc nhiu quan h. Các ràng bu c ph c tp thưng đưc phát biu dng thao tác by. Mt thao tác by thưng cĩ các thành ph n sau: 1) Qui tc ng ưi dùng : là yêu cu ng n gn ca ràng bu c. 2) S ki n: là các thao tác x lý d li u (chèn, sa hoc xố) kích hot thao tác by. 3) Tên quan h: tên các quan h liên quan. 4) ðiu ki n: là các lý do dn đn vic kích ho t thao tác by. 5) Hành đng: là cơng vic thc thi khi thao tác by đưc kích ho t. ◊ Ví d. Cho quan h NHANVIEN(Manv, HoTen, NgaySinh, NgayBC, ). Hin nhiên là NgayBC (ngày vào biên ch) khơng đưc sm hơn NgaySinh . Ta cĩ th đm bo điu kin này bng thao tác by sau: Qui tc ngưi dùng : NgayBC khơng sm hơn NgaySinh. S ki n: Chèn, Sa. Tên quan h: NHANVIEN ðiu kin: NgayBC < NgaySinh. Hành đng : Ph nh n thao tác cp nh t. ◊ Ví d. Xét hai quan h KHACH(Makhach , TenKhach, TaiKhoan, SoDu) THANHTOAN(MaKhach, SoTien) Ta thy rng SoTien ca THANHTOAN khơng th vưt quá SoDu ca KHACH. Ta cĩ th đm bo điu kin này bng thao tác by sau: Chương 1. Tng quan v h qun tr cơ s d li u quan h 13
13. Qui tc ngưi dùng : SoTien khơng ln hơn SoDu. S ki n: Chèn, Sa. Tên quan h: THANHTOAN, KHACH ðiu kin: THANHTOAN.SoTien > KHACH.SoDu Hành đng : Ph nh n thao tác cp nh t. 4. Các ngơn ng d liu quan h Các ngơn ng thao tác d li u đưc phát trin cho mơ hình quan h (thưng gi là ngơn ng vn tin, query language) đưc chia làm hai nhĩm căn bn: Các ngơn ng da trên đi s quan h (relational algebra) và các ngơn ng da trên phép tính quan h (relational calculus). Khác bit gia chúng là cách thc ngưi s dng đưa ra câu vn tin. ði s quan h thu c lo i th tc (procedural), trong đĩ ng ưi dùng cn phi đc t, nh mt s tốn t, bng cách nào đt đưc kt qu . Ngưc li phép tính quan h thu c loi phi th tc (nonprocedural), ng ưi dùng ch cn đc t các mi liên h cn ph i đm bo trong kt qu. C hai ngơn ng đưc Codd đưa ra năm 1970 và ơng đã chng minh rng chúng tương đương v kh năng din t. 4.1. ði s quan h ði s quan h cĩ mt tp các phép tốn trên các quan h. Chúng cĩ ngu n gc t lý thuyt tp hp (mi quan h thc cht là mt tp hp). Mi tốn t nh n mt hoc hai quan h làm tốn hng và cho ra mt quan h mi (quan h kt qu), đn lưt nĩ quan h kt qu cĩ th dùng làm tốn hng cho mt tốn t khác. Nhng phép tốn này cho phép vn tin và cp nht cơ s d li u quan h. Cĩ năm phép tốn đi s cơ bn và năm phép tốn khác cĩ th đnh nghĩa theo các phép tốn cơ bn. Các phép tốn cơ bn là: phép chn, phép chiu, phép hp, phép hiu và tích Descartes. Hai phép tốn đu thuc loi mt ngơi, và ba phép tốn sau thu c loi hai ngơi. Các phép tốn b sung cĩ th đnh nghĩa bi các phép tốn cơ bn là: phép giao, phép ni, phép ni t nhiên, phép bán ni, và phép thương . Trong thc hành đi s quan h đưc m rng đ cĩ th nhĩm hoc sp xp kt qu và cĩ th thc hin các phép gp ph n (aggregation) hoc các phép tính s hc. Mt s phép tốn khác nh ư ni ngồi (outer join) cũng đưc h tr. Các tốn hng ca mt s phép tốn hai ngơi phi ng hp (union compartible), tc là chúng cùng bc (cùng s thu c tính) và các thu c tính tương ng cĩ cùng mi n giá tr. a. Phép chiu Cho quan h r vi lưc đ quan h R=(A1, , An). Cho S là lưc đ con ca R, S⊂R, S cĩ m thu c tính (m < n). Chiu ca r lên lưc đ S, ký hiu πS(r) , đưc đnh nghĩa là quan h vi lưc đ S gm các m-b u sao cho tn ti n-b v ∈r tho mãn v(S) = u tc là πS(r) = {m-b u : ∃ v∈r, v(S) = u } Chương 1. Tng quan v h qun tr cơ s d li u quan h 14
14. ◊ Ví d Cho quan h r vi các thuc tính A,B,C. Sau đây là ví d c th v chiu ca r lên hai thu c tính A và C. r πA,C(r) A B C ⇒ A C a b c a c d a f d f c b d c d c f d ◊ Ví d: Xét quan h PROJ PROJ PNO PNAME BUDGET P1 Instrumentation 150000 P2 Database Development 135000 P3 CAD/CAM 250000 P4 Maintenance 310000 Chiu ca PROJ lên các thuc tính PNO và BUDGET cĩ kt qu như sau πPNO,BUDGET(PROJ) PNO BUDGET P1 150000 P2 135000 P3 250000 P4 310000 b. Phép chn Cho quan h r vi lưc đ quan h R=(A1, , An) và F là biu thc lơgic bao gm (i) Các tốn hng là hng ho c (s hiu) thành ph n, (ii) Các phép tốn so sánh : , ≠ , ≤, ≥ (iii) Các phép tốn logic : &, ∧ (và), ∨ (ho c) , ¬ (ph đnh). Phép chn ca r theo biu thc F, ký hiu σF(r), là quan h vi lưc đ R gm tt c các b t trong r sao cho khi thay các thành phn ca t vào biu thc F thì ta cĩ giá tr đúng. Tc là σF(r) = { t∈r : F(t) = true } ◊ Ví d: Cho quan h r vi các thu c tính A,B,C. Sau đây là ví d c th v chn ca r theo biu thc B=b r σB=b (r) A B C ⇒ A B C a b c a b c Chương 1. Tng quan v h qun tr cơ s d li u quan h 15
15. d a f c b d c b d c f d ◊ Ví d: Xét quan h EMP EMP ENO ENAME TITLE SAL PNO RESP DUR E1 J.Doe Elect.Eng. 40000 P1 Manager 12 E2 M.Smith Syst.Anal. 34000 P1 Analyst 24 E2 M.Smith Syst.Anal. 34000 P2 Analyst 6 E3 A.Lee Mech.Eng. 27000 P3 Consultant 10 E3 A.Lee Mech.Eng. 27000 P4 Engineer 48 E4 J.Miller Programmer 24000 P2 Programmer 18 E5 B.Casey Syst.Anal. 34000 P2 Manager 24 E6 L.Chu Elect.Eng. 40000 P4 Manager 48 E7 R.David Mech.Eng. 27000 P3 Engineer 36 E8 J.Jones Syst.Anal. 34000 P3 Manager 40 Các b ca các k sư đin (electrical engineer) đưc biu din bng phép chn nh ư sau σTITLE = 'Elect. Eng.'(EMP) ENO ENAME TITLE SAL PNO RESP DUR E1 J.Doe Elect.Eng. 40000 P1 Manager 12 E6 L.Chu Elect.Eng. 40000 P4 Manager 48 c. Phép hp Cho quan h r, s vi lưc đ quan h R=(A1, , An). Hp ca r và s, ký hiu r ∪ s , là quan h vi lưc đ R gm tt c các b thu c r ho c thuc s. ◊ Ví d Cho quan h r và s vi các thu c tính A,B,C . Sau đây là ví d c th v hp ca r và s. r s r ∪ s A B C A B C ⇒ A B C a b c b g a a b c d a f d a f d a f c b d c b d b g a d. Phép hiu Cho quan h r, s vi lưc đ quan h R=(A1, , An). Hiu ca r và s, ký hiu r − s, là quan h vi lưc đ R gm tt c các b thu c r nh ưng khơng thu c s. Chương 1. Tng quan v h qun tr cơ s d li u quan h 16
16. ◊ Ví d Cho quan h r và s vi các thu c tính A,B,C . Sau đây là ví d c th v hiu ca r và s. r s r − s A B C A B C ⇒ A B C a b c b g a a b c d a f d a f c b d c b d e. Tích ð-các Cho quan h r vi lưc đ quan h R=(A1, , An) và quan h s vi lưc đ quan h S=(B 1, , Bm). Tích ð các ca r và s, ký hiu r × s, là quan h vi lưc đ =(A1, , An, B1, , Bm) gm tt c các (n+m)-b, trong đĩ n thành phn đu là b thuc r và m thành ph n sau là b thuc s. ◊ Ví d Cho quan h r vi các thu c tính A,B,C và s vi các thuc tính D,E,F. Sau đây là ví d c th v tích ð-các ca r và s. r s r × s A B C D E F ⇒ A B C D E F a b c b g a a b c b g a d a f d a f a b c d a f c b d d a f b g a d a f d a f c b d b g a c b d d a f f. Phép giao Cho quan h r, s vi lưc đ quan h R=(A1, , An). Giao ca r và s, ký hiu r ∩ s, là quan h vi lưc đ R gm tt c các b thu c r và thuc s. ♦ Cơng thc. Phép giao suy ra t phép hiu r ∩ s = r − (r − s) = s − (s − r) ◊ Ví d Cho quan h r và s vi các thu c tính A,B,C . Sau đây là ví d c th v giao ca r và s. r s r ∩ s A B C A B C ⇒ A B C a b c b g a d a f d a f d a f c b d g. Phép ni Chương 1. Tng quan v h qun tr cơ s d li u quan h 17
17. Cho quan h r vi lưc đ quan h R=(A1, , An) và quan h s vi lưc đ quan h S=(B 1, , Bm). Cho biu thc lơgic F. Phép ni ca quan h r và quan h s theo điu kin ni F, ký hiu r > < s C=D A B C D E ⇒ A B C D E 1 2 3 3 1 1 2 3 3 1 4 5 6 6 2 4 5 6 6 2 7 8 9 ◊ Ví d. Xét các quan h EMP( ENO, ENAME, TITLE) PAY(TITLE, SAL) ENO ENAME TITLE TITLE SAL E1 J.Doe Elect.Eng. Elect.Eng. 40000 E2 M.Smith Syst.Anal. Syst.Anal. 34000 E3 A.Lee Mech.Eng. Mech.Eng. 27000 E4 J.Miller Programmer Programmer 24000 E5 B.Casey Syst.Anal. Operator 15000 E6 L.Chu Elect.Eng. E7 R.David Mech.Eng. E8 J.Jones Syst.Anal. Chương 1. Tng quan v h qun tr cơ s d li u quan h 18
18. vi ràng bu c tồn vn tham chiu EMP.TITLE→PAY.TITLE. Phép ni EMP vi PAY theo EMP.TITLE=PAY.TITLE cĩ kt qu sau EMP > < s A B C B C D ⇒ A B C D a b c b c d a b c d d b c b c e a b c e b b f a d b d b c d Chương 1. Tng quan v h qun tr cơ s d li u quan h 19
19. c a d d b c e c a d b ◊ Ví d. Các quan h EMP(ENO, ENAME, TITLE) PAY(TITLE, SAL) cho ví d trưc, cĩ thu c tính chung là TITLE. Ni t nhiên ca hai quan h cho bng sau EMP > , ≠ , ≤, ≥). Cho F là biu thc lơgic gm các tốn hng dng Aθ B, trong đĩ A là thuc tính ca r và B là thuc tính s. Phép bán ni ca quan h r và quan h s theo điu kin ni F, ký hiu r > < s B<D A B C D E ⇒ A B C 1 2 3 3 1 1 2 3 Chương 1. Tng quan v h qun tr cơ s d li u quan h 20
20. 4 5 6 6 2 4 5 6 7 8 9 r s r > < EMP EMP.TITLE=PAY.TITLE TITLE SAL Elect.Eng. 40000 Syst.Anal. 34000 Mech.Eng. 27000 Programmer 24000 j. Phép chia (thương) Cho quan h r vi lưc đ quan h R=(A1, , An) và quan h s vi lưc đ quan h S=(A1, , Am), trong đĩ m < n. Ta đnh ngh ĩa phép chia r ÷ s là quan h vi lưc đ (A m+1, , An) gm tt c (n-m)-b v sao cho vi mi m-b u thuc s, b (u,v ) thu c r. ð lp cơng thc cho phép chia ta ký hiu t = π (r ) Am+1 , , An Khi đĩ (s × t) − r là tp hp các n-b khơng thu c r, to ra bng cách ly các phn t ca s kt hp vi n-m thành phn ca các ph n t thu c r. ðt Chương 1. Tng quan v h qun tr cơ s d li u quan h 21
21. ((s × t ) − r ) q = π Am +1 , , An Như vy q là tp tt c các (n−m)-b v gm n−m thành phn cui ca các ph n t ca r và tn ti ph n t u ∈ s sao cho b (u,v ) khơng thu c r. Suy ra ♦ Cơng thc r ÷ s = t − π ((s × t ) − r ) Am +1 , , An ◊ Ví d Cho quan h r vi các thu c tính A,B,C,D và s vi các thu c tính C,D. Sau đây là ví d c th v phép chia ca r cho s. r s r ÷ s A B C D C D ⇒ A B a b c d c d a b a b e f e f e d b c e f e d c d e d e f a b d e ◊ Ví d. Xét các quan h sau: Chương 1. Tng quan v h qun tr cơ s d li u quan h 22
22. ASG' ENO PNO PNAME BUDGET E1 P1 Instrumentation 150000 E2 P1 Instrumentation 150000 E2 P2 Database Deve. 135000 E3 P3 CAD/CAM 250000 E3 P4 Maintenance 310000 E4 P2 Database Deve. 135000 E5 P2 Database Deve. 135000 E6 P4 Maintenance 310000 E7 P3 CAD/CAM 250000 E8 P3 CAD/CAM 250000 PROJ' PNO PNAME BUDGET P3 CAD/CAM 250000 P4 Maintenance 310000 ð tìm mã s nhân viên ca nhng nhân viên đưc phân vào tt c d án trong PROJ’, ta ph i thc hin phép chia ASG’ cho PROJ’ và đưc kt qu là ASG' ÷ PROJ' ENO E3 • Các chương trình đi s quan h Vì tt c các phép tốn đi s đu nhn quan h làm đi bin và sinh ra các quan h kt qu , chúng ta cĩ th lng ghép các phép tốn này bng các du ngo c đơ n và sinh ra các chương trình đi s quan h. Dưi đây là mt s ví d minh ho s dng các quan h EMP(ENO, ENAME, TITLE) PAY(TITLE, SAL) PROJ(PNO, PNAME, BUDGET) ASG(ENO, PNO , RESP, DUR) ◊ Ví d. Sau đây là chương trình tìm tên tt c nhân viên đang làm vic cho d án CAD/CAM πENAME(((σPNAME=’CAD/CAM’(PROJ)) > < (σPNAME=’CAD/CAM’(PROJ)))) Chương 1. Tng quan v h qun tr cơ s d li u quan h 23
23. ◊ Ví d. Sau đây là chương trình tăng lương tt c các lp trình viên (programmer) lên 25000 USD. (PAY − (σTITLE=’Programmer’(PAY)) ∪ ( ) 4.2. ði s quan h Trong các ngơn ng da trên phép tính quan h, thay vì xác đnh xem ph i làm th nào đ thu đưc kt qu, chúng ta s xác đnh xem kt qu là gì bng cách đưa ra mi liên h đưc gi s là đúng đi vi kt qu. Ngơn ng phép tính quan h đưc phân làm 2 nhĩm: phép tính quan h b (tuple relational calculus) và phép tính quan h mi n (domain relational calculus). S khác bit gia chúng là các bin nguyên thu đưc dùng khi xác đnh các câu vn tin. Ngơn ng phép tính quan h cĩ cơ s lý thuy t vng chc bi vì chúng xây dng trên logic v t bc nh t. Ng ngh ĩa đưc gán cho các cơng thc bng cách din gii chúng nh ư các phán đốn trên cơ s d li u. Mt cơ s d li u quan h cĩ th xem nh ư tp các b ho c tp các min. Phép tính quan h b din gii các bin trong cơng thc nh ư mt b ca quan h, cịn phép tính quan h min din gii bin như giá tr ca min. a) Phép tính quan h b (Codd 1970) Bin nguyên thu dùng trong phép tính quan h b là bin b (tuple variable), biu th mt b ca quan h. Nĩi cách khác bin này bin thiên trên các b ca quan h. Trong phép tính quan h b, câu vn tin đưc đc t là {t | F(t) } trong đĩ t là bin b và F là cơng thc chnh dng. Cơng thc nguyên t cĩ hai dng: (1) Biu thc kiu ph n t bin b. Nu t là mt bin b bin thiên trên các b ca mt quan h R, biu thc “b t thu c quan h R” là cơng thc nguyên t, và đưc vit là R. t ho c R(t). (2) ðiu kin. Loi cơng thc nguyên t này cĩ th đnh ngh ĩa nh ư sau: (i) s[A] θ t[B] , trong đĩ s và t là các bin b và A và B là các thành phn tương ng ca s và t , θ là mt trong các tốn t so sánh , = , ≤ , ≥ và ≠ . (ii) s[A] θ c , trong đĩ s , A và θ đnh ngh ĩa ging nh ư trên và c là hng. Hin cĩ nhiu ngơn ng da trên phép tính quan h b, và ngơn ng thơng dng nh t là SQL và QUEL. SQL hin là chu n qu c t (duy nht) vi các phiên bn chu n hố đã đưc đưa ra năm 1986 (SQL1), năm 1992 (SQL2) và năm 1998 (SQL3). Chương 1. Tng quan v h qun tr cơ s d li u quan h 24
24. • Ngơn ng truy vn SQL SQL thuc loi ngơn ng th h th tư (4GL) đưc nghiên cu nhiu năm và tr thành tiêu chu n qu c t v kim sốt d li u. SQL k tha tính phi th tc ca 4GL: X lý đng thi hàng lot câu lnh. Ngưi dùng ch cn nêu ra yêu cu v d liu mà khơng cn bit máy tính x lý bên trong nh ư th nào. Ngưi dùng cĩ th truy xut nhanh chĩng vi nh ng CSDL ln, yêu cu nh ng x lý phc tp tinh vi mà khơng cn lp trình. SQL là ngơn ng cĩ cu trúc. Trong câu lnh ca SQL cĩ mt s mnh đ tuân theo nh ng cú pháp riêng ca nĩ. Cĩ 4 loi lnh trong SQL : - Các lnh truy vn d li u. - Các lnh đnh nghĩa d li u (DDL). - Các lnh x lý cp nh t d liu (DML). - Các lnh kim sốt d li u. ♦ Các lnh truy vn d liu, gi là câu vn tin cĩ cú pháp tng quát nh ư sau SELECT [DISTINCT] AS ] [, ] | * FROM [ ] [, ] [INTO ] [WHERE [AND | OR ]] [GROUP BY [, ] [HAVING ]] [ORDER BY [ASC | DESC] [, ]] [UNION | INTERSECT | MINUS ] Dưi đây là mt s ví d minh ha s dng các quan h EMP(ENO, ENAME, TITLE) PAY(TITLE, SAL) PROJ(PNO, PNAME, BUDGET) ASG(ENO, PNO , RESP, DUR) ◊ Ví d. Tìm tên tt c nhân viên đang làm vic cho d án CAD/CAM Select EMP.ENAME From EMP, ASG, PROJ Where (EMP.ENO = ASG.ENO) AND (ASG.PNO = PROJ.PNO) AND (PROJ.PNAME = “CAD/CAM”) ◊ Ví d. Tìm tên tt c nhân viên đang qun lý d án (Manager) SELECT ENAME FROM EMP, ASG WHERE (EMP.ENO = ASG.ENO) AND (RESP = “Manager”) ◊ Ví d. Tìm tên tt c nhân viên đang làm vic trong d án P3 và P4. (bài tp) Chương 1. Tng quan v h qun tr cơ s d li u quan h 25
25. ♦ Các lnh cp nht d li u gm cĩ lnh UPDATE (hiu chnh), INSERT (thêm) và DELETE (xố). ◊ Ví d. Tăng lương các lp trình viên (programmer) lên 25000 USD. UPDATE PAY SET SAL = 25000 WHERE PAY.TITLE = “Programmer” ◊ Ví d. Thêm nhân viên mi vào EMP INSERT INTO EMP VALUE (‘E10’, ‘John Smith’, ‘Programmer’) ◊ Ví d. Xố d án ‘P1’ DELETE FROM PROJ WHERE PNO = ‘P1’ b) Phép tính quan h min (Lacroix, Pirotte 1977) Bin nguyên thu dùng trong phép tính quan h mi n là bin min (domain variable ), xác đnh mt thành phn ca b bin thiên trong tp giá tr ca min. Nĩi cách khác, min xác đnh ca bin min bao gm các min trên đĩ quan h đưc đnh ngh ĩa. Câu vn tin cĩ dng sau: x1, , xn | F(x1, , x n ) trong đĩ F là cơng thc chnh dng cịn x1, , xn là các bin t do. Thành cơng ca ngơn ng phép tính quan h mi n ch yu do QBE (Zloof, 1977) đem li. ðây là ng dng kiu trc quan ca phép tính min. QBE (Query by example) đưc thit k dành cho kiu làm vic tương tác t thit b đu cui trc quan và thân thin. Khái nim cơ bn là example: ng ưi s dng đưa ra các câu vn tin bng cách cung cp mt example cĩ th cĩ ca câu tr li. Hành đng gõ tên quan h s kích ho t vic hin th các lưc đ ca chúng lên màn hình. Sau đĩ bng cách cung cp các t khố trong các ct (min), ng ưi dùng đc t câu vn tin. Ch ng hn các thuc tính ca quan h chiu đưc cho bng t P (Project). Theo mc đnh tt c các câu vn tin đu là kiu truy xut. Câu vn tin cp nh t địi hi ph i cĩ đc t U dưi tên quan h cn cp nh t. ◊ Ví d. Tìm tên tt c nhân viên đang làm vic cho d án CAD/CAM EMP ENO ENAME TITLE E2 P ASG ENO PNO RESP DUR E2 P3 PROJ PNO PNAME BUDGET Chương 1. Tng quan v h qun tr cơ s d li u quan h 26
26. P3 CAD/CAM ◊ Ví d. Tăng lương các lp trình viên (programmer) lên 25000 USD. PAY TITLE SAL Programmer U.25000 5. Thit k cơ s d li u quan h 5.1. Dư tha d li u Khi thit k cơ s d li u quan h ta thưng đng trưc vn đ la chn gia các lưc đ quan h: lưc đ nào tt hơn ? Ti sao ? Mc này s nghiên cu mt s tiêu chu n đánh giá lưc đ quan h và các thu t tốn giúp chúng ta xây dng đưc lưc đ cơ s d li u quan h cĩ cu trúc tt. Cĩ th nĩi tng quát mt lưc đ quan h cĩ cu trúc tt là lưc đ khơng cha đng s dư tha d li u, tc là là s trùng lp thơng tin trong cơ s d liu. 5.1.1. S dư tha d liu Dư tha d liu là s trùng lp thơng tin trong cơ s d li u. ◊ Ví d Xét quan h EMP(ENO, ENAME, TITLE, SAL, PNO, RESP, DUR). Nu mt nhân viên tham gia trong nhiu d án, thì các d liu như ENAME, TITLE, SAL ph i lp li nhiu ln và kéo theo dư tha d li u. Ngồi vic gây lãng phí dung lưng lưu tr, s dư tha d li u cĩ th gây ra nh ng hu qu nghiêm tr ng đi vi d li u khi ng ưi dùng cp nh t d liu làm cho d li u khơng tương thích, bt đnh ho c mt mát. Các s c nh ư vy gi là nh ng d thưng . 5.1.2. Các d thưng cp nht d li u Ta s minh ho các d thưng bng các lưc đ EMP(ENO, ENAME, TITLE, SAL, PNO , RESP, DUR) PROJ(PNO, PNAME, BUDGET) a. D thưng do d liu lp: Mt s thơng tin cĩ th đưc lp li mt cách vơ ích. ◊ Ví d: Trong quan h EMP tên (ENAME), chc v (TITLE), và lương (SAL) ca nhân viên đưc lp li trong mi d án mà h tham gia. ðiu này rõ ràng là làm lãng phí ch lưu tr và đi ngh ch vi các nguyên lý ca cơ s d liu. b. D thưng chèn b: Khơng th chèn b mi vào quan h, nu khơng cĩ đy đ d liu. Chương 1. Tng quan v h qun tr cơ s d li u quan h 27
27. ◊ Ví d: Xét quan h EMP. Gi s mt nhân viên mi đưc nhn vào cơng ty và chưa đưc phân cơng vào d án nào c. Khi đĩ chúng ta khơng th nhp các thơng tin v tên, chc v, lương ca nhân viên này vào quan h, vì khố ca EMP là (ENO, PNO). c. D thưng xố b: Trưng hp này ng ưc vi d thưng chèn b. Vic xố b cĩ th kéo theo mt thơng tin. ◊ Ví d: Xét quan h EMP. Gi s mt nhân viên làm vic trong mt d án duy nh t. Khi d án chm dt, chúng ta khơng th xố thơng tin v d án đĩ trong EMP đưc, vì nu làm th ta s mt luơn thơng tin v nhân viên đĩ. d. D thưng sa b: Vi c sa đi d liu dư tha cĩ th dn đn s khơng tương thích d liu. ◊ Ví d: Xét quan h EMP. Gi s mt nhân viên làm vic trong nhiu d án. Khi cĩ s thay đi v lương, rt nhiu b phi cp nh t s thay đi này. ðiu đĩ gây lãng phí thi gian cơng sc và là nguy cơ gây ra s khơng thng nh t d liu. Trong các ví d trên ta thy tác hi ca s dư tha d liu và s cn thit ph i loi b chúng khi các lưc đ quan h. Quá trình tng bưc thay th mt lưc đ quan h bng các tp lưc đ quan h đơn gin và chu n tc hơn gi là chun hố. Mc đích ca chun hố là loi b các d thưng (ho c các khía cnh khơng mong mun khác) đ cĩ nh ng quan h tt hơn. Cơ s lý thuy t ca vic thit k lưc đ cơ s d liu quan h tt là khái nim ph thuc d liu. Ph thu c d liu biu din các quan h nhân qu gia các thu c tính trong quan h. Ví d trong bng EMP, thuc tính SAL ph thuc vào thu c tính ENO, vì mi nhân viên ch cĩ mt lương duy nh t. Cũng da trên khái nim ph thuc d li u ngưi ta đnh ngh ĩa các dng chu n ca lưc đ d liu quan h. Mi dng chun đáp ng mt yêu cu nh t đnh đi vi lưc đ quan h. Quá trình bin đi mt lưc đ thành lưc đ tương đương (bo tồn thơng tin và ph thu c d li u) tho mãn dng chu n gi là quá trình chun hố lưc đ quan h. Khái nim ph thu c d liu s đưc nghiên cu chi tit ph n sau. 5.2. Cu trúc ph thu c d li u Cĩ ba dng ph thu c d li u, ph thuc hàm (functional dependancy - FD) , ph thu c đa tr (multivalued dependancy - MVD) và ph thu c chiu ni (projection-join dependancy - PJD) a. Ph thuc hàm Cho lưc đ quan h R=(A1, A2, , An) và X, Y là các tp con ca {A1, A2, , An}. Ta nĩi rng X xác đnh hàm Y hay Y ph thu c hàm X, ký hiu X→Y, nu mi quan h bt kỳ r ca lưc đ R tho mãn: ∀u, v ∈r : u(X) = v(X) ⇒ u(Y) = v(Y) Chương 1. Tng quan v h qun tr cơ s d li u quan h 28
28. Cn nh n mnh rng tính cht ph thuc hàm ph i tho vi mi quan h r ca lưc đ R. Ta khơng th ch xét mt quan h đc bit (quan h rng chng hn) ri quy np cho tồn lưc đ. Nhưng ta cĩ th ph nhn ph thuc hàm qua mt quan h c th nào đĩ. Ph thu c hàm X→Y gi là ph thu c hàm tm thưng nu Y⊂X (hin nhiên là nu Y⊂X thì theo đnh ngh ĩa ta cĩ X→Y). Ph thu c hàm X→Y gi là ph thu c hàm nguyên t nu khơng cĩ tp con thc s Z⊂X tho Z→Y. Tp thu c tính K ⊂ R gi là khố nu nĩ xác đnh hàm tt c các thu c tính và K→R là ph thu c hàm nguyên t. ◊ Ví d: Xét quan h PROJ. Ta cĩ th chp nh n rng mi d án cĩ tên và kinh phí xác đnh. Vy cĩ th khng đnh PNO→(PNAME, BUDGET) Trong quan h EMP ta cĩ (ENO, PNO)→(ENAME, TITLE, SAL, RESP, DUR) ENO→(ENAME, TITLE, SAL) Hồn tồn hp lý khi chúng ta kh ng đnh rng lương ca mi chc v là c đnh, do đĩ s tn ti ph thuc hàm TITLE→SAL b. Ph thuc đa tr Cho lưc đ quan h R=(A1, A2, , An) và X, Y là các tp con ca {A1, A2, , An}. Ta nĩi rng X xác đnh đa tr Y hay Y ph thuc đa tr vào X, ký hiu X→→ Y, nu mi quan h bt kỳ r ca lưc đ R tho mãn: ng vi mi giá tr ca mi n giá tr các thu c tính trong X, cĩ mt tp giá tr các thu c tính trong Y liên quan và tp này đc lp vi các thuc tính trong Z=R\(X∪Y), tc là: ∀x∈D(X) ∀y, y’∈D(Y) ∀z, z’∈D(Z):(x,y,z), (x,y’,z’) ∈r ⇒ (x,y, z’), (x,y’, z)∈r vi D(X), D(Y) và D(Z) là min giá tr ca X, Y và Z. • Chú ý rng ph thu c hàm là trưng hp riêng ca ph thuc đa tr, tc là X→Y ⇒ X→→Y Tht vy, nu (x,y,z), (x, y’, z’) ∈r và X→Y thì y=y’, và kéo theo Chương 1. Tng quan v h qun tr cơ s d li u quan h 29
29. (x, y, z’), (x, y’, z)∈r ◊ Ví d Tr li ví d đang xét. Gi s ta mun duy trì thơng tin v tp nhân viên và v tp d án cĩ liên quan đn cơng ty cũng như v chi nhánh (PLACE) thc hin d án. Yêu cu này cĩ th đưc thc hin bng cách đnh ngh ĩa quan h SKILL (ENO, PNO, PLACE) Ta gi s (cĩ th khơng thc t cho lm) (1) mi nhân viên đu cĩ th làm vic cho mi d án, (2) mi nhân viên đu cĩ th làm vic ti mi chi nhánh và (3) mi d án đu cĩ th đưc thc hin ti bt kỳ chi nhánh nào. Mt quan h mu tho các điu kin này cho bng sau: SKILL ENO PNO PLACE E1 P1 Toronto E1 P1 New York E1 P1 London E1 P2 Toronto E1 P2 New York E1 P2 London E2 P1 Toronto E2 P1 New York E2 P1 London E2 P2 Toronto E2 P2 New York E2 P2 London Chú ý rng khơng cĩ ph thuc hàm khơng tm thưng nào trong quan h SKILL; tt c thuc tính là thu c tính khố. Quan h SKILL cĩ hai ph thu c đa tr ENO→→ PNO ENO→→ PLACE c. Ph thuc chiu-ni Cho lưc đ quan h R=(A1, A2, , An) và R1, R2, , Rk là các tp con ca {A1, A2, , An}. Ta nĩi rng {R 1, R2, , Rk } xác đnh mt ph thuc chiu-ni ca R, nu mi quan h r ca R là ni t nhiên ca các chiu ca nĩ lên R1, R2, , Rk, tc là r = πR1(r) > < πRk(r) • Chú ý rng ph thu c đa tr là trưng hp riêng ca ph thuc chiu-ni, tc là X→→Y ⇒ {X∪Y, X∪Z} xác đnh mt ph thuc chiu-ni, trong đĩ Z=R\(X∪Y). Chương 1. Tng quan v h qun tr cơ s d li u quan h 30
30. Tht vy, cho quan h r trên lưc đ R tha ph thu c đa tr X→→Y. Hin nhiên πXY (r) > < πENO,PLACE(SKILL) 5.3. Ph thuc đa tr Trong ph n này chúng ta s nghiên cu sâu hơn v ph thuc đa tr, mi quan h gia ph thu c đa tr và ph thu c hàm. 5.3.1. ðnh nghĩa Ta nh c li đnh nghĩa ph thu c đa tr. Cho lưc đ quan h R(A1, A2, , An) và X, Y là các tp con ca {A1, A2, , An}. Ta nĩi rng X xác đnh đa tr Y hay Y ph thuc đa tr vào X, ký hiu X→→ Y, nu mi quan h bt kỳ r ca lưc đ R tho mãn: ng vi mi giá tr ca mi n giá tr các thu c tính trong X, cĩ mt tp giá tr các thu c tính trong Y liên quan và tp này đc lp vi các thuc tính trong Z=R\(X∪Y), tc là: ∀x∈D(X)∀y,y’∈D(Y) ∀z, z’∈D(Z):(x,y,z), (x,y’, z’) ∈r ⇒ (x, y, z’), (x, y’,z)∈r ◊ Ví d Chương 1. Tng quan v h qun tr cơ s d li u quan h 31
31. Xét lưc đ CTHRSG=(C,T,H,R,S,G), trong đĩ C (Course) là mơn hc, T (Teacher) là giáo viên, H (Hour) là ti t hc, R (Room) là phịng hc, S (Student) là sinh viên và G (Grade) là đim s. Mt quan h mu cho bng sau C T H R S G CS101 Trn M9 222 Hùng 9 CS101 Trn W9 333 Hùng 9 CS101 Trn F9 222 Hùng 9 CS101 Trn M9 222 Dũng 7 CS101 Trn W9 333 Dũng 7 CS101 Trn F9 222 Dũng 7 Trong ví d đơn gin này ta thy mơn hc cĩ nhiu gi hc, trong các phịng hc khác nhau, trong tun. Mi sinh viên cĩ mt bn ghi cho mi gi hc và đim ca sinh viên cũng đưc lp li tương ng. Như vy ta suy ra ph thu c đa tr C→→ H,R, tc là s cĩ tp gi-phịng ng vi mi mơn hc, đc lp vi các thu c tính khác. Ví d, cho hai bn ghi t = (CS101, Tr n, M9, 222, Hùng, 9) s = (CS101, Trn, W9, 333, Dũng, 7) chúng ta ch đi rng cĩ th hốn chuyn (M9, 222) ca t vi (W9, 333) ca s đ nh n đưc các b sau u = (CS101, Tr n, M9, 222, Dũng, 7) v = (CS101, Trn, W9, 333, Hùng, 9) Và ta thy u, v cũng cĩ m t trong quan h trên. Cn nh n mnh rng, C→→ H,R đúng bi vì vi mi mơn hc c, nu tn ti các b (c, h1, r1, t1, s1, g1) và (c, h2, r2, t2, s2, g2) thì cũng s tn ti (c, h1, r1, t2, s2, g2) và (c, h2, r2, t1, s1, g1). Lưu ý rng C→→H và C→→R khơng đúng, bi vì, nu ng ưc li, t t và s suy ra bn ghi (CS101, Trn, M9, 333, Dũng, 7) ph i cĩ trong quan h trên. Tn ti nhiu ph thu c đa tr khác nh ư C→→ S,G và H,R→→ S,G (bài tp). 5.3.2. Các tiên đ ph thuc đa tr và ph thuc hàm Ta s trình bày tp hp đy đ các tiên đ ph thu c hàm và ph thu c đa tr trên tp thuc tính U. Các tiên đ Armstrong đưc nhc li vì tính h thng. (A1) Quy tc phn x ph thu c hàm: Chương 1. Tng quan v h qun tr cơ s d li u quan h 32
32. Y ⊂ X ⊂ U ⇒ X→Y (A2) Quy tc tăng trưng ph thu c hàm: X→Y & Z⊂U ⇒ X∪Z→Y∪Z (A3) Quy tc bc cu ph thuc hàm: X→Y & Y→Z ⇒ X→Z (M1) Quy tc bù ph thuc đa tr: X→→ Y ⇒ X→→(U \ (X∪Y)) (M2) Quy tc tăng trưng ph thu c đa tr: X→→ Y & V ⊂W ⇒ X∪W→→Y∪V (M3) Quy tc bc cu ph thu c đa tr: X→→Y & Y→→ Z ⇒ X→→ (Z \ Y) (M4) Quy tc ph thuc hàm-đa tr: X→Y ⇒ X→→Y (M5) Quy tc ph thuc đa tr-hàm: X→→ Y & Z⊂Y & W→Z & W∩Y=∅ ⇒ X→Z • ðnh lý: Các tiên đ A1-A3 và M1-M5 là đúng và đ cho ph thuc hàm và ph thu c đa tr. Tc là, nu D là tp hp các ph thu c hàm và ph thu c đa tr trên tp thuc tính U, và D+ là tp hp các ph thuc hàm và ph thu c đa tr suy din lơgic t D (theo nghĩa mi quan h tho D thì cũng tho D +), thì D+ chính là tp hp các ph thuc hàm và ph thu c đa tr suy ra t D bng các tiên đ trên. Ch ng minh . (cơng nhn) 5.4. Chun hố lưc đ quan h Chúng ta đã ch ra rng s dư tha d liu là nguyên nhân ca các d thưng khi cp nht d liu dn đn s khơng tương thích d li u và các hu qu nghiêm trng khác. Mt lưc đ cơ s d li u đưc cho là tt là ph i loi b đưc s dư tha d liu. Tuy nhiên ta cn đưa ra đnh ngh ĩa chính xác th nào là lưc đ cơ s d li u tt cùng vi quá trình thit k chúng. Quá trình bin đi mt lưc đ cơ s d li u thành lưc đ tương đương , tc ph i bo tồn thơng tin và bo tồn ph thuc d li u, tho mãn nhng tiêu chu n nh t đnh gi là quá trình chu n hố lưc đ quan h. Chương 1. Tng quan v h qun tr cơ s d li u quan h 33
33. Chu n hố lưc đ quan h thưng đưc thc hin qua các giai đon tương ng vi các dng chun (xem sơ đ dưi). Dng chu n là trng thái quan h đưc xác đnh bng cách áp dng các quy tc đi vi ph thu c hàm ca quan h. Bng cĩ giá tr kép Loi giá tr kép Dng chu n 1 Loi ph thu c hàm b phn Dng chu n 2 Loi ph thu c hàm bc cu Dng chu n 3 Loi các d thưng cịn li do ph Dng chu n thu c hàm Boyce-Codd Loi các ph thu c đa tr Dng chu n 4 Loi các d thưng khác Dng chu n 5 5.4.1. Dng chun th nht (1NF) Quan h gi là dng chun th nht hay quan h chun hố nu mi n giá tr ca mi thuc tính ch cha nhng giá tr nguyên t, tc là khơng phân chia đưc na. Như vy mi giá tr trong quan h cũng là nguyên t. Dng chun 1 ch cĩ ý ngh ĩa mc th hin ca lưc đ quan h, vì ch liên quan đn giá tr các thu c tính ca các b trong mt quan h đưc đnh nghĩa trên lưc đ quan h đĩ. 5.4.2. Dng chun th 2 (2NF) Thu c tính A gi là ph thuc đy đ vào tp thuc tính X, nu X→A là ph thu c hàm nguyên t. Gi s K là khố ca lưc đ R. Khi đĩ mi thu c tính khơng khố A ca R đu ph thu c hàm vào khố K: K →A. Nu A khơng ph thu c đy đ vào K thì tn ti tp con thc s H ca K xác đnh hàm A, tc H→A. Khi đĩ ph thuc hàm H→A gi là ph thu c hàm b phn. Chương 1. Tng quan v h qun tr cơ s d li u quan h 34
34. Mt lưc đ quan h gi là dng chu n th 2 nu nĩ dng chun th 1 và khơng cĩ ph thu c hàm b phn, tc là mi thu c tính khơng khố đu ph thu c đy đ vào các khố ca lưc đ. ◊ Ví d - Xét các quan h sau: EMP(ENO, ENAME, TITLE, SAL, PNO , RESP, DUR) PROJ(PNO, PNAME, BUDGET) Lưc đ ca EMP cĩ khố là (ENO, PNO). Ph thu c hàm ENO→(ENAME, TITLE) là ph thu c hàm b phn vì v ph i là tp con thc s ca khố. Vy EMP khơng dng chu n th 2. Lưc đ ca PROJ khơng cĩ ph thu c hàm b ph n, vy nĩ dng chu n 2. - Xét quan h KHO_HANG(Kho, Hang, QuayHang, NhanVien). Lưc đ ca quan h này cĩ hai ph thu c hàm sau: Kho,Hang →QuayHang : Mi mt hàng mi kho ch đưc bán 1 quy hàng; Kho,QuayHang→NhanVien: Mi quy hàng ca mi kho ch cĩ 1 nhân viên ph trách. Khố ca lưc đ này là (Kho, Hang ). Vy lưc đ này dng chu n th 2 vì khơng cĩ ph thuc hàm b ph n. 5.4.3. Dng chun th 3 (3NF) Ph thu c hàm X→A gi là ph thu c hàm bc cu, nu nĩ là ph thu c hàm nguyên t, A là thu c tính khơng khố, A∉X, và X cha thu c tính khơng khố. Khi đĩ vi mi khố K ta cĩ các ph thuc hàm khơng tm thưng K→X & X→A. Mt khác khơng th cĩ X→K, vì X cha các thu c tính khơng khố và khơng cha khố (vì X→A là nguyên t). Nĩi mt cách khác ph thu c hàm bc cu là s ph thuc khơng tm thưng gia các thu c tính khơng khố. Mt lưc đ quan h gi là dng chu n th 3 nu nĩ dng chun th 2 và khơng cĩ ph thu c hàm bc cu. ◊ Ví d - Lưc đ ca quan h EMP(ENO, ENAME, TITLE, SAL, PNO, RESP, DUR) cĩ khố là (ENO, PNO). Ph thuc hàm TITLE→SAL là ph thu c hàm bc cu. Vy EMP khơng dng chu n th 3. - Lưc đ ca quan h Chương 1. Tng quan v h qun tr cơ s d li u quan h 35
35. PROJ(PNO, PNAME, BUDGET) khơng cĩ ph thu c hàm bc cu, vy nĩ dng chu n 3. - Xét quan h KHO_HANG(Kho , Hang, QuayHang, NhanVien). Ta cĩ hai ph thu c hàm sau: Kho,Hang →QuayHang : Mi mt hàng mi kho ch đưc bàn 1 quy hàng; Kho,QuayHang→NhanVien: Mi quy hàng ca mi kho ch cĩ 1 nhân viên ph trách. Khố ca lưc đ này là (Kho, Hang ). Ph thu c hàm th hai là ph thuc hàm bc cu, vì th lưc đ khơng dng chu n th 3, mc dù nĩ dng chun th 2. 5.4.4. Dng chun Boyce-Codd (BCNF) Mt lưc đ quan h gi là dng chun Boyce-Codd nu mi ph thu c hàm khơng tm thưng đu cĩ v trái là siêu khố ◊ Ví d: - Lưc đ ca quan h PROJ(PNO, PNAME, BUDGET) ch cĩ ph thu c hàm duy nht PNO→(PNAME, BUDGET), vy nĩ dng chu n Boyce-Codd. - Xét lưc đ LOPHOC(Lop,MonHoc,GiaoVien) vi 2 ph thu c hàm sau: GiaoVien→MonHoc và (Lop,MonHoc)→GiaoVien Lưc đ cĩ 2 khố K1 = (Lop, MonHoc) và K2 = (Lop, GiaoVien), nên tt c thuc tính đu là thu c tính khố. Như vy l ưc đ dng chu n th 3. Tuy nhiên lưc đ khơng dng chu n Boyce-Codd vì ph thu c hàm GiaoVien→MonHoc khơng tho yêu cu v trái phi là siêu khố. S d thưng khi thêm b hay sa b th hin ch nu mt giáo viên dy nhiu lp (cùng mt mơn hc) thì thơng tin v giáo viên đĩ lp li nhiu ln gây dư tha d liu. S d thưng khi xố b th hin ch nu giáo viên T ch dy lp C nào đĩ, thì thơng tin v giáo viên T (mơn hc mà giáo viên đĩ dy) s b mt nu ta xố bn ghi tương ng (chng hn vì giáo viên T thơi khơng dy lp C na). Chương 1. Tng quan v h qun tr cơ s d li u quan h 36
36. 5.4.5. Dng chun th 4 (4NF) Mt quan h R đưc gi là dng chu n th 4, nu vi mi ph thu c đa tr X→→ Y trong R, X cũng xác đnh hàm tt c thu c tính ca R. Như vy, nu quan h dng chun BCNF và các ph thuc đa tr cũng là ph thu c hàm thì quan h này dng chu n 4. ◊ Ví d: Xét quan h SKILL (ENO, PNO, PLACE) ENO PNO PLACE E1 P1 Toronto E1 P1 New York E1 P1 London E1 P2 Toronto E1 P2 New York E1 P2 London E2 P1 Toronto E2 P1 New York E2 P1 London E2 P2 Toronto E2 P2 New York E2 P2 London Chú ý rng khơng cĩ ph thu c hàm nào trong quan h SKILL; tt c thuc tính là thuc tính khố. Quan h SKILL cĩ hai ph thu c đa tr ENO→→ PNO ENO→→ PLACE Vì quan h khơng cĩ ph thu c hàm nên nĩ dng BCNF. Tuy nhiên nĩ khơng dng chu n 4, vì ENO khơng ph i là khố. ð đt dng chu n 4, cn phân rã SKILL thành hai quan h EP(ENO, PNO) và EL( ENO, PLACE) 5.4.6. Dng chun th 5 (5NF) Mt quan h R đưc gi là dng chun th 5, cịn gi là dng chun chiu- ni PJNF, nu mi ph thuc chiu ni đưc xác đnh bi các khố ca R. ◊ Ví d Vi quan h PROJ(PNO , PNAME, BUDGET) ta cĩ ph thu c chiu-ni {(PNO, PNAME), (PNO, BUDGET)} và mi thành phn đu cĩ khố chính PNO. Vì vy PROJ dng chun 5. Chương 3. Cơ s d liu phân tán 106
37. CHƯƠNG 2 CƠ S D LIU PHÂN TÁN 1. H qun tr cơ s d li u phân tán 1.1. Khái nim h qun tr cơ s d liu phân tán Cơng ngh các h qun tr c ơ s d liu phân tán (distributed database management system - distributed DBMS) là s hp nht ca hai hưng ti p cn đi vi quá trình x lý d li u: Cơng ngh cơ s d li u và cơng ngh mng máy tính. X lý d li u chuyn t h thng x lý file c đin sang dng cơ s d liu, qu n lý tp trung. ðiu này dn đn tính đc lp d li u, ngh ĩa là các ng dng đưc “min nhim” đi vi nh ng thay đi v t chc lơgic hoc vt lý ca d liu và ngưc li. Mt trong nhng đng lc ch yu thúc đy s dng cơ s d liu là nhu cu tích hp các d liu ho t tác ca mt xí nghip và cho phép truy xut tp trung. Cơng ngh mng máy tính đc trưng ch phi tp trung hố thit b. Tuy nhiên đim mu cht ca ý tưng cơ s d liu phân tán là tích hp (integration), ch khơng phi tp trung hố (centralization). Cn hiu rng cĩ th tích hp mà khơng cn tp trung. Và đây chính là mc tiêu ca cơng ngh cơ s d li u phân tán. Ti sao chúng ta phi thc hin phân tán ? Câu tr li kinh đin cho câu hi này là vic x lý phân tán nh m thích ng tt hơn vi vic phân b ngày càng rng rãi các cơng ty, xí nghip. Nhiu ng dng hin ti ca cơng nghip máy tính đưc phân tán. Thương mi đin t, các ng dng đa phương ti n, giáo dc t xa, cha bnh t xa, điu khin sn xut t xa, là các ví d minh ho . Tuy nhiên t gĩc đ tng quát hơn, x lý phân tán là mt bin th ca qui tc “chia đ tr” nhm gii quy t tt hơn các bài tốn ln và ph c tp. T quan đim kinh t, cách tip cn này cĩ ưu đim cơ bn là vic tính tốn phân tán tn dng sc mnh ca nhiu b ph n x lý mt cách ti ưu. • H cơ s d li u phân tán là gì ? Chúng ta cĩ th đnh nghĩa mt cơ s d liu phân tán là tp hp nhiu cơ s d liu cĩ liên quan lơgic và đưc phân b trên mt mng máy tính. H qu n tr cơ s d liu phân tán (distributed database management system - distributed DBMS) là h thng phn mm cho phép qu n lý các h cơ s d li u phân tán và làm cho vic phân tán tr nên vơ hình đi vi ng ưi s dng. Lưu ý rng mt h cơ s d li u phân tán khơng ph i là tp hp các tp tin lưu tr riêng r ti các nút ca mng máy tính. ð to ra mt h cơ s d liu phân tán, các tp tin khơng ch liên đi lơgic mà cịn phi cĩ cu trúc chung và đưc truy xu t qua mt giao din chung. Cũng cn phân bit mt h cơ s d li u phân tán vi các d liu bán cu trúc (semi-structrured data) đưc lưu trên Internet (chng hn như các trang Web). ðnh ngh ĩa trên cũng loi b các h thng đa b x lý dùng chung b nh trong (shared memory) ho c dùng chung b nh th cp (shared disk). Ngồi ra mt h cơ s d liu phân tán khơng phi là h thng mà trong đĩ, mc dù cĩ s hin din ca mng máy tính, cơ s d liu ch nm ti mt nút ca mng. Mơi trưng ca mt h CSDL phân tán cĩ th biu din bng sơ đ sau Chương 3. Cơ s d liu phân tán 107
38. Trạm 1 Trạm 5 Trạm 2 Mng truy n d li u Trạm 4 Trạm 3 • Các đc trưng ca cơ s d liu phân tán ðc tính vơ hình là s tách bit v ng ngh ĩa mc đ cao ca h th ng vi các vn đ cài đt cp đ thp. Ưu đim ca h cơ s d li u vơ hình là khơng cho ngưi dùng “nhìn thy” các chi tit cài đt, h tr phát trin các ng dng ph c tp. ðc lp d li u là dng vơ hình cơ bn cn cĩ trong mt h cơ s d liu. S đc lp d li u liên quan đn kh năng “mi n nhim” ca các ng dng đi vi nh ng thay đi trong đnh nghĩa và t chc d liu, và ng ưc li. Vơ hình kt mng. Trong mơi trưng phân tán, h thng mng là mt loi tài nguyên quan trng cn qun lý. Thơng thưng, ng ưi dùng cn đưc tách kh i mi chi ti t hot đng ca mng, thm chí ngưi ta mong mun che du s tn ti ca mng, nu đưc. Khi đĩ đi vi ng ưi dùng s khơng cĩ s khác bit gia các ng dng chy trên cơ s d li u tp trung và các ng dng chy trên cơ s d li u phân tán. Kiu vơ hình này gi là vơ hình kt mng (network transparency ) ho c vơ hình phân b (distribution transparency). Vơ hình nhân bn. Vì nh ng lý do v hiu năng (performance), đ tin cy (reliability) và tính sn sàng (availability), ng ưi ta mong mun cĩ th nhân d liu thành nhiu bn (nhân bn) trên các máy mng. Vic nhân bn giúp tăng hiu năng vì nhng yêu cu s dng cĩ xung đt và nm ri rác cĩ th đáp ng kp thi. Thí d, d liu thưng đưc mt ngưi truy xu t cĩ th đưc đt ti máy ca ng ưi đĩ và trên máy ca nhng ng ưi khác cĩ cùng nhu cu truy xu t, nh ư th s làm tăng khu vc truy xu t. Ngồi ra nu mt máy ph i ng ưng ho t đng, mt bn sao khác ca d li u vn cĩ sn trên máy khác ca mng. Tuy nhiên vic nhân bn s gây khĩ kh ăn khi cp nht cơ s d liu. Vì vy vic nhân bn và qui mơ nhân bn do các ng dng quyt đnh. Vơ hình phân mnh. Phân hoch d li u cho các v trí khác nhau là yêu cu tt yu ca h phân tán. Quá trình này gi là quá trình phân mnh (fragmentation ). Cĩ hai kiu phân mnh. Phân mnh ngang (horizontal fragmentation), trong đĩ mi quan h đưc phân hoch thành tp các quan h con, mi quan h con này cha mt tp con các b ca quan h ban đu. Phân mnh dc (vertical fragmentation), trong đĩ mi quan h đưc phân ho ch thành tp các quan h Chương 3. Cơ s d liu phân tán 108
39. con, mi quan h con này đưc đnh ngh ĩa trên mt tp con các thu c tính ca quan h ban đu). Khi các đi tưng cơ s d li u b phân mnh, chin lưc x lý vn tin là da trên các mnh ch khơng ph i quan h. Như vy câu vn tin tồn cc (global query) ph i đưc dch thành câu vn tin theo mnh (fragment query). 1.2. Mơ hình kin trúc h qun tr cơ s d liu phân tán Kin trúc ca mt h thng xác đnh cu trúc ca nĩ. Tc là các thành phn ca h thng đưc xác đnh, chc năng mi thành ph n đưc mơ t, các mi tương liên (interrelationship) và tương tác (interaction) gia các thành ph n đưc đnh ngh ĩa. Chúng ta hãy xem xét mt s cách kt hp nhiu cơ s d li u li đ dùng chung cho nhiu h qun tr cơ s d liu. Ta phân loi h thng theo các đc đim (1) tính t tr (autonomy) ca các h thng cc b, (2) tính phân tán (distribution ) ca chúng, (3) tính đa chng (heterogeneity) ca chúng. 1.2.1. Tính t tr Tính t tr (autonomy) mun nĩi đn s phân b quyn điu khin, ch khơng ph i phân b d liu. Tính t tr ch ra mc đ ho t tác đc lp ca tng h qun tr cơ s d li u. Tính t tr biu hin qua mt s yu t sau: - Các h thng thành viên cĩ trao đi thơng tin vi nhau khơng. - Các h thng thc hin các giao dch mt cách đc lp hay khơng. - Các h thng cĩ đưc sa đi hay khơng. T đĩ ngưi ta xây dng các yêu cu đi vi mt h thng t tr. Chng hn h thng t tr phi tho mãn: (1) Các ho t đng cc b ca tng h qun tr cơ s d liu khơng b nh hưng bi s tham gia ca chúng vào trong phc h cơ s d li u (multidatabase system). (2) Ph ương thc x lý và ti ưu hố vn tin trong tng h qu n tr cơ s d liu khơng b nh hưng bi vic thc hin các câu truy vn tồn cc truy xu t nhiu cơ s d liu. (3) Tính nht quán và ho t đng ca h thng khơng b nh hưng khi tng h qu n tr cơ s d li u riêng r tham gia hoc tách ra kh i liên minh cơ s d li u. bình din khác, tính t tr th hin các khía cnh sau: (1) T tr thit k (design autonomy ): Mi h qu n tr cơ s d liu t do s dng các mơ hình d liu và các k thu t qun lý giao dch thích hp. (2) T tr truyn thơng (communication autonomy): Mi h qun tr cơ s d liu t do quy t đnh loi thơng tin cung cp cho h qu n tr cơ s d liu khác ho c cho các ph n mm điu khin hot đng tồn cc. (3) T tr thc thi (execution autonomy): Mi h qu n tr cơ s d liu cĩ th thc hin các giao dch theo phương thc ca mình. Tính t tr cĩ th chia làm ba cp đ sau: (0) Tích hp mt thit (tight integration): Ch tn ti mt hình nh duy nh t v tồn b h thng cơ s d li u cho ngưi dùng mun dùng chung thơng tin trong Chương 3. Cơ s d liu phân tán 109
40. nhiu cơ s d li u. Mt trong các b qu n lý d liu (data manager) nm quyn kim sốt vic x lý yêu cu ca ng ưi dùng, ngay c khi yêu cu đĩ ph i đưc nhiu b qun lý d liu tham gia x lý. (1) H thng bán t tr (semiautonomous system): Bao gm các h qu n tr cơ s d li u cĩ th hot tác đc lp, nh ưng quyt đnh tham gia vào liên minh nh m chia s d liu cc b ca chúng. Mi h qu n tr cơ s d li u phi xác đnh nh ng ph n cơ s d liu nào ca riêng chúng mà các h qu n tr cơ s d li u khác đưc truy xut. Chúng khơng ph i là h thng t tr hồn tồn mà cn sa đi li đ cĩ th trao đi thơng tin vi nh ng h thng khác. (2) H thng cơ lp: Các h qun tr cơ s d liu ho t đng cơ lp, khơng cĩ giao ti p chia s d li u vi nhau. 1.2.2. Tính phân tán Tính phân tán (distribution) ch kh năng phân b d li u nhng v trí khác nhau. Cĩ hai loi kin trúc phân tán: (1) Phân tán khách/ch (client/server): ðây là hình thc phân tán chc năng. Thành phn ch (server) chu trách nhim qu n tr d liu; thành ph n khách (client) chu trách nhim cung cp mơi trưng ng dng, k c giao din ngưi dùng. Nhim v truyn thơng đưc chia s gia ch và khách. (2) Phân tán ngang hàng (peer-to-peer): Cịn gi là phân tán hồn tồn . Khơng cĩ s phân bit gia máy ch và khách, mi máy đu cĩ đy đ chc năng ca mt h qu n tr cơ s d liu và cĩ th trao đi thơng tin vi máy khác đ thc hin vn tin và giao dch. 1.2.3. Tính đa chng Tính đa chng (heterogeneous) th hin dưi nhiu hình thái khác nhau trong các h phân tán, t khác bit v ph n cng, các giao thc kt ni mng đn s khác bit ca các b qu n lý d li u. Tính đa chng liên quan đn s khác bit các mơ hình d li u (data model), ngơn ng vn tin (query language) và nghi thc qu n lý giao dch (transaction management protocol). 1.2.4. Các kiu kin trúc Ta t hp các mc đ t tr, phân tán và đa chng đ nghiên cu các mơ hình kin trúc khác nhau. Ký hiu A0 h thng t tr tích hp A1 h thng bán t tr A2 h thng cơ lp D0 h thng khơng phân tán (tp trung) D1 h thng phân tán khách/ch D2 h thng phân tán ngang hàng H0 h thng đng chng Chương 3. Cơ s d liu phân tán 110
41. H1 h thng đa chng • Mơ hình (A0,D0,H0): H thng tích hp, khơng phân tán, đng chng. ðưc gi là h thng ph c hp (composite system), bao gm nhiu h qu n tr cơ s d liu đưc tích hp v mt lơgic. Kin trúc này phù hp vi nh ng h thng đa b x lý và mi tài nguyên dùng chung. • Mơ hình (A0,D0,H1): H thng tích hp, khơng phân tán, đa chng. Nĩ cĩ nhiu h qun tr cơ s d li u đa chng, nhưng cung cp mt hình nh tích hp cho ngưi dùng. Ch ng hn trên cơ s d li u mng cùng hin din c cơ s d liu phân cp và c ơ s d liu quan h. • Mơ hình (A0,D1,H0): H thng tích hp, phân tán khách/ch, đng chng. H thng cung cp mt hình nh tích hp cho ng ưi dùng. • Mơ hình (A0,D2,H0): H thng tích hp, phân tán hồn tồn, đng chng. H thng khơng phân bit khách ch. Mi v trí đu trang b đy đ chc năng. • Mơ hình (A1,D0,H0): H thng bán t tr, khơng phân tán, đng chng , đưc gi dưi cái tên h qu n tr cơ s d liu liên bang (federated DBMS). Các h thng thành viên đu cĩ quy n t tr nht đnh trong các ho t đng ca chúng. Chúng t do hip đng vi nh ng h thng khác khi thc hin các yêu cu ca ng ưi dùng truy xu t đn nhiu cơ s d li u. ◊ Ví d. Nhiu bn cài đt mt h qun tr cơ s d liu “m” trên cùng mt máy. “M” đây cĩ nghĩa là h qu n tr cơ s d liu cĩ kh năng tham gia vào liên bang. • Mơ hình (A1,D0,H1): H thng bán t tr, khơng phân tán, đa chng , đưc gi dưi cái tên h qun tr cơ s d liu liên bang đa chng (heterogeneous federated DBMS). ◊ Ví d. Mt h qun tr cơ s d li u quan h lo qu n lý d li u cĩ cu trúc, mt h qu n tr cơ s d li u đ ho lo qu n lý hình nh tĩnh, và mt máy ch cung cp các hình video. Nu chúng ta mun cung cp mt hình nh tích hp cho ng ưi dùng thì cn ph i “che du” tính t tr và đa chng ca các h thng thành viên và thit lp giao din chung. • Mơ hình (A1,D1,H1): H thng bán t tr, phân tán khách/ch, đa chng, đưc gi dưi cái tên h qu n tr cơ s d liu liên bang đa chng phân tán (heterogeneous federated distributed DBMS). D li u đưc phân tán trên các máy khác nhau. • Kin trúc (A2,D0,H0): H thng cơ lp, khơng phân tán, đng chng , đưc gi dưi cái tên h qu n tr cơ s d liu ph c h (multidatabase system-MDBS). Các thành viên khơng cĩ khái nim hip đng. ðây th c cht là tp các cơ s d liu t tr và đưc kt ni li. Chương 3. Cơ s d liu phân tán 110
42. • Mơ hình (A2,D0,H1): H thng cơ lp, khơng phân tán, đa chng. H thng này đưc dùng đ xây dng các ng dng truy xu t d liu t nhiu h thng lưu tr khác nhau vi các đc tính khác nhau. Mt s h thng cĩ th khơng phi là h qun tr cơ s d liu. • Mơ hình (A2,D1,H1) và (A2,D2,H1): Ta xét chung hai trưng hp này do tính tương t ca nh ng vn đ do chúng sinh ra. C hai đu biu din cho trưng hp các cơ s d li u thành viên to ra ph c h phân tán trên mt s v trí − chúng đưc gi là các ph c h cơ s d liu phân tán (distributed MDBS). Khác bit chính gia hai kin trúc này là phân tán khách/ch, ph n ln các cơng vic tương tác đưc trao cho h thng trung gian (middleware system), to ra ki n trúc ba tng (three layer architecture). 1.3. Kin trúc h qun tr cơ s d liu phân tán Chúng ta s xem xét chi tit ba kin trúc h thng trong s các kin trúc gii thiu ph n trưc. ðĩ là các h thng khách/ch (Ax,D1,Hy), các h phân tán (A0,D2,H0) và các phc h (A2,Dx,Hy). 1.3.1. Các h khách/ch Các h qun tr cơ s d li u khách/ch xut hin đu nh ng năm 90 và cĩ nh hưng ln đn cơng ngh DBMS và ph ương thc x lý tính tốn. ý tưng tng quát ht sc đơ n gin và rõ ràng: phân bit các chc năng cn đưc cung cp và chia nhng chc năng này thành hai lp: chc năng ch (server function) và chc năng khách (client function). Nĩ cung cp mt ki n trúc hai tng (two-level architecture), to điu kin d dàng cho vic qu n lý mc đ phc tp ca các h qu n tr cơ s d li u hin đi và đ ph c tp ca vic phân tán d liu. Máy ch thc hin ph n ln cơng vic qu n lý d liu: x lý ti ưu hố vn tin, qu n lý giao dch, qun lý thit b lưu tr. Máy khách qu n lý các ng dng, giao din, h qu n tr cơ s d liu ca khách, chu trách nhim qu n lý d liu đưc gi cho khách và cĩ th c qu n lý các khố cht giao dch. Kin trúc này đưc mơ t trong hình sau. Chương 3. Cơ s d liu phân tán 111
43. C User interface Appl. Program L I Client DBMS E N Communication Software T SQL Result query relation S Communication Software E R Semantic Data Controller V Query Optimizer E R Transaction Manager Recovery Manager Runtime Support Processor OPERATING SYSTEM kin trúc tham chiu khách/ch Kin trúc này thơng dng trong các h cơ s d liu quan h, đĩ vic giao tip gia khách và ch nm mc câu lnh SQL. Khách hàng chuy n câu vn tin cho máy ch mà khơng cn bit nĩ thc hin và ti ưu hố như th nào. Máy ch thc hin hu ht cơng vic và gi quan h kt qu v cho khách. Cĩ mt s kin trúc khách/ch khác nhau: • Kin trúc nhiu khách, mt ch. T gĩc đ qun lý, loi này khơng khác nhiu so vi cơ s d liu tp trung, vì CSDL đưc lưu trên mt máy ch duy nh t và cũng cĩ phn mm qu n lý. Cĩ mt s khác bit quan trng cách thc hin các giao dch và qun lý b nh cache. • Kin trúc nhiu khách, nhiu ch: Cĩ hai chin lưc qun lý: - Mi máy khách t qu n lý kt ni ca nĩ vi các máy ch khác nhau. Li tip cn này làm đơn gin chương trình máy ch nhưng đt gánh nng lên máy khách cùng vi các trách nhim khác. - Mi máy khách ch quan h vi máy ch đi din ca mình và giao tip vi các máy ch khác thơng qua đi din khi cn. Chương 3. Cơ s d liu phân tán 112
44. 1.3.2. Các h phân tán ngang hàng Trong kin trúc này t chc d liu vt lý trên mi máy cĩ th rt khác nhau. ðiu này dn đn vic đnh nghĩa cu trúc d li u riêng cho mi v trí, gi là lưc đ ni ti cc b LIS (local internal schema). Cu trúc lơgic ca d li u mi v trí đưc mơ t bng lưc đ khái nim tồn cc GCS (global conceptual schema). ð mơ t t chc lơgic ca d li u ti mi v trí cn ph i cĩ tng th ba trong kin trúc gi là lưc đ khái nim cc b LCS (local conceptual schema). Lưc đ khái nim tồn cc lúc này là hp ca các lưc đ khái nim cc b. Các ng dng và vic truy xu t cơ s d liu đưc h tr qua các lưc đ ngo i gii ES (external schema), đưc đnh ngh ĩa là mt tng nm trên tng lưc đ khái nim tồn cc. Kin trúc này đưc mơ t trong hình sau. ES1 ES2 ESn GCS LCS1 LCS2 LCSm LIS 1 LIS 2 LIS m kin trúc tham chiu CSDL phân tán ngang hàng Các chc năng ca h phân tán ngang hàng đưc biu din bng sơ đ sau: Chương 3. Cơ s d liu phân tán 113
45. Enter prise Administrator Gl obal Global conce ptual Applicat ion database database schema System Administrator process or Administrator Ext er nal database schema GD/D process or Local Data Management Local Data Management Local Conceptual Local Conceptual Database Database Database Database Administrator Schema Administrator Schema Processor Processor Internal Internal Database LD/D Database LD/D Schema Schema Processor Processor Int.storage/ Internal Int.storage/ Internal Int.database Database Int.database Database Transform Conceptual Transform Conceptual Transformation Transformation sơ đ chc năng ca h qu n tr CSDL phân tán ngang hàng Trong h thng này các t đin/thư mc d li u, vit tt là D/D, cĩ vai trị trung tâm, va x lý lưc đ d li u va cung cp các ánh x gia chúng các cp đ tồn cc và cc b. • Th ư mc/t đin tồn cc GD/D (global directory/dictionary) cha các đnh ngh ĩa lưc đ tồn cc và thc hin các ánh x tồn cc. Chương 3. Cơ s d liu phân tán 114
46. • Th ư mc/t đin cc b LD/D (local directory/dictionary) cha các đnh ngh ĩa lưc đ cc b và thc hin các ánh x cc b. Nĩ cũng cĩ th cha các s li u thng kê v các ng dng, các thơng tin kim sốt truy xu t, Các thành ph n qu n lý cơ s d li u cc b đưc tích hp nh các chc năng ca h qu n tr cơ s d li u tồn cc. Trong sơ đ này, lưc đ khái nim cc b là ánh x ca lưc đ khái nim tồn cc vào mi v trí. Hơn na, nhng cơ s d liu loi này thưng đưc thit k theo kiu t trên xu ng, vì th tt c đnh ngh ĩa khung nhìn đu cĩ phm vi tồn cc. Mi v trí cũng cĩ mt qun tr viên cơ s d liu th hin mong mun cĩ đưc kh năng điu khin cc b đi vi ho t đng qun tr cơ s d liu. Các thành ph n ca h qu n tr cơ s d liu phân tán đưc trình bày trong hình sau: USER System responses User requests USER PROCESSOR User Interface External Handler Schema Sematic Data Controller Global Conceptual Schema Global Quer y Optimizer Decomposer GD/D Global Execution Monito r DATA PROCESSOR Local Query Local Processor Conceptual Schema Local Recovery System Manager Log Local Runtime Support Internal Processor Schema • Chương 3. Cơ s d liu phân tán 115
47. H thng cĩ hai thành phn chính: Mt thành ph n lo x lý mi tương tác vi ng ưi dùng gi là b ph n ph c v ng ưi dùng (user processor), cịn thành phn th hai lo vic lưu tr d liu, gi là b ph n x lý d li u (data processor). • B ph n ph c v ng ưi dùng (user processor): bao gm bn ph n: (1) B ph n giao tip (user interface handler) chu trách nhim din dch các yêu cu ca ngưi dùng (user requests) và đnh dng d li u kt qu đ chuyn cho ng ưi dùng. (2) B ph n ki m sốt d liu ng nghĩa (sematic data controller): s dng các ràng bu c tồn vn (integrity constraints) và thơng tin quy n hn (authorization), đưc đnh nghĩa như thành ph n ca lưc đ khái nim tồn cc, đ kim tra xem các câu vn tin cĩ th x lý đưc hay khơng. (3) B ph n phân rã và ti ưu hố vn tin (global query optimizer and decomposer) xác đnh chin lưc ho t đng nhm gim thiu chi phí, phiên dch các câu vn tin tồn cc thành các câu vn tin cc b bng cách s dng các lưc đ khái nim tồn cc, lưc đ khái nim cc b và các thư mc tồn cc. B ph n ti ưu vn tin tồn cc, ngồi nhng nhim v khác, cịn chu trách nhim to ra chin lưc thc thi tt nh t cho các phép ni phân tán. (4) B phn theo dõi hot đng phân tán (distributed execution monitor) điu ph i vic thc hin phân tán các yêu cu ngưi dùng và cũng đưc gi là b qu n lý giao dch phân tán (distributed transaction manager). Khi thc hin các vn tin phân tán, các b ph n ti các v trí cĩ th giao ti p vi nhau. • B ph n x lý d li u (data processor): bao gm ba phn. (1) B ph n x lý câu vn tin cc b (local query processor): ho t đng như b chn đưng truy xut (access path selector), chu trách nhim chn ra mt đưng truy xu t thích hp nh t đ truy xut các mc d liu. (2) B ph n khơi phc cc b (local recovery manager): bo đm cho các cơ s d li u cc b vn duy trì đưc tính nh t quán ngay c khi cĩ s c xy ra. (3) B ph n h tr thc thi (run-time support processor): truy xut cơ s d liu tuỳ vào các lnh trong lch biu (schedule) do b phn ti ưu vn tin sinh ra. Nĩ chính là giao din vi h điu hành và cha b qu n lý vùng đm cơ s d li u (database buffer manager), chu trách nhim qun lý vùng đm và vic truy xu t d li u. Lưu ý rng vic s dng thu t ng B phn ph c v ng ưi dùng và B ph n x lý d li u khơng phi là s phân chia chc năng ging như các h khách/ch. S phân chia này ch th hin khía cnh t chc và khơng bt buc phi đt trên các máy khác nhau. Trong các h thng ngang hàng, ngưi ta mong mun cĩ c mơdun ph c v ng ưi dùng và mơđun x lý d liu trên cùng mt máy. 1.3.3. Các phc h cơ s d liu H qu n tr phc h cơ s d li u phân tán khác bit vi h qu n tr cơ s d liu phân tán v Chương 3. Cơ s d liu phân tán 116
48. - mc đ t tr: ph n ánh trong các mơ hình kin trúc - đnh nghĩa lưc đ khái nim tồn cc: trong h phc hp lưc đ khái nim tồn cc ch là mt tp con bao gm mt s cơ s d liu cc b mà mi h qun tr CSDL mun dùng chung, cịn trong h phân tán cơ s d liu tồn cc là hp các cơ s d liu cc b. a) Các mơ hình s dng lưc đ khái nim tồn cc Trong ph c h cơ s d li u, lưc đ khái nim tồn cc GCS đưc đnh ngh ĩa bng cách tích hp các lưc đ ngồi ca các cơ s d liu t tr hoc các thành phn ca lưc đ khái nim cc b ca chúng, xem hình sau GES1 GES2 GESn LES11 LES12 LES1 GCS LESm1 LESm2 LESm3 LCS1 LCSm LIS 1 LIS m kin trúc ph c h CSDL vi mt lưc đ khái nim tồn cc Ngưi dùng ca h qu n tr cơ s d li u cc b s đnh ngh ĩa khung nhìn riêng (LES) ca h trên cơ s d li u cc b và khơng cn thay đi các ng dng hin cĩ nu h khơng truy xut d li u ca cơ s d liu khác. ðây chính là khía cnh t tr ca kin trúc này. Thit k lưc đ khái nim tồn cc trong phc h cơ s d liu bao gm vic tích hp các lưc đ khái nim cc b (ánh x đi t dưi lên, t lưc đ khái nim cc b lên lưc đ khái nim tồn cc, ng ưc li vi h phân tán) hoc tích hp các lưc đ ngồi cc b (ánh x đi theo chiu t trên xu ng). Mt khi đã thit k xong GCS, các khung nhìn trên lưc đ cĩ th đnh ngh ĩa cho ng ưi dùng cn truy xu t ph m vi tồn cc. Các lưc đ ngo i gii tồn cc GES và lưc đ khái nim tồn cc GCS khơng nht thit s dng cùng mt mơ hình và cùng ngơn ng , chúng khơng cn xác đnh xem h thng đng chng hay đa chng . Trong trưng hp đa chng, ta cĩ hai la chn cài đt: đơn ngơn (unilingal) ho c đa ngơn (multilingal). Chương 3. Cơ s d liu phân tán 117
49. Trong ph c h cơ s d li u đơ n ngơn, khi truy xu t tồn cc ngưi dùng s dng chung mt lưc đ ngoi gii tồn cc và mt ngơn ng x lý tồn cc. Trong ph c h cơ s d li u đa ngơn, khi truy xu t tồn cc mi ngưi dùng s dng lưc đ ngoi gii tồn cc đưc đnh ngh ĩa bng ngơn ng ca h qun tr cơ s d liu cc b ca mình và các câu vn tin tồn cc cũng đưc to bng ngơn ng ca h qun tr cơ s d liu cc b. b) Các mơ hình khơng cĩ lưc đ khái nim tồn cc Kin trúc ca phc h cơ s d li u khơng cĩ lưc đ khái nim tồn cc đưc trình bày trong hình sau ES1 ES2 ESn Multidatabase layer Local system layer LCS1 LCS2 LCSm LIS 1 LIS 2 LIS m kin trúc ph c h CSDL khơng cĩ lưc đ khái nim tồn cc Kin trúc này cĩ hai tng: tng h thng cc b và tng phc h CSDL phía trên. Tng h thng cc b bao gm mt s h qu n tr cơ s d liu, vi chc năng là gii thiu cho tng phc h cơ s d li u các thành phn ca cơ s d liu cc b cĩ th dùng chung vi nhng cơ s d liu khác. D liu dùng chung này đưc trình bày qua lưc đ khái nim cc b thc s hoc qua lưc đ ngo i gii cc b. Nu cĩ vn đ đa chng, mi lưc đ LCS i cĩ th s dng mơ hình d liu khác nhau. Tng ph c h cơ s d liu gm các lưc đ ngo i gii, trong đĩ mi khung nhìn đưc đnh nghĩa trên mt hay nhiu lưc đ khái nim cc b. Vì vy trách nhim cung cp quyn truy xu t đn nhiu cơ s d liu (cĩ th đa chng) đưc trao cho ánh x gia lưc đ ngoi gii và lưc đ khái nim cc b. ðây là đim khác bit cơ bn so vi kin trúc s dng lưc đ khái nim tồn cc, trong đĩ quan h gia lưc đ ngo i gii và lưc đ khái nim cc b đưc thc hin bi các ánh x thơng qua lưc đ khái nim tồn cc. Kin trúc cơ s d liu liên bang cũng khơng s dng lưc đ khái nim tồn cc. Trong h thng này mi h qu n tr cơ s d liu cc b đnh ngh ĩa mt Chương 3. Cơ s d liu phân tán 118
50. lưc đ xut (export schema), trong đĩ đnh ngh ĩa d li u mun chia s vi các DBMS khác, mi ng dng truy xu t đn cơ s d li u tồn cc qua đnh nghĩa ca lưc đ nh p (import schema), thc cht là hình nh ngo i gii tồn cc. Các thành ph n ca h qun tr phc hp khác bit nhiu so vi h qun tr cơ s d li u phân tán. đây cĩ mt tng ph n mm chy bên trên nhng h qu n tr cơ s d liu riêng bit và cung cp cho ngưi dùng nhng tin ích đ truy xu t nhiu cơ s d li u khác nhau. Tuỳ thuc vào s tn ti hay khơng lưc đ khái nim tồn cc và vn đ đa chng mà ni dung ph n mm s thay đi cho phù hp. USER System responses User requests Multi-DBMS lay er DBMS DBMS Quer y Query Processor Processor Transaction Transaction Manager Manager Scheduler Scheduler Recovery Recovery Manager Manager Runtime Runtime Support Support Processor Processor • • các thành ph n ca ph c h CSDL 1.4. T chc thư m c tồn cc Chương 3. Cơ s d liu phân tán 119
51. Các vn đ t chc thư mc tồn cc ch đưc đ cp đn trong các h phân tán và ph c h cĩ s dng lưc đ khái nim tồn cc. Thư mc tồn cc cũng là cơ s d li u cha d li u v các d liu thc s l ưu tr trong cơ s d liu (cịn gi là meta d liu hay siêu d liu). Vì th nh ng k thu t thit k cơ s d liu phân tán cũng áp dng cho vic qun lý thư mc. Như vy thư mc cĩ th tồn cc đi vi tồn b cơ s d liu hoc cc b đi vi tng v trí. Nghĩa là cĩ th cĩ mt thư mc duy nht cha các thơng tin v tt c d li u trong cơ s d li u, ho c cĩ mt s thư mc, mi thư mc cha thơng tin đưc lưu các v trí khác nhau. Trong trưng hp sau chúng ta cĩ th xây dng h phân cp thư mc đ d dàng khi tìm kim hoc cài đt mt chin lưc tìm kim phân tán cho phép trao đi gia các v trí lưu tr thư mc. Vn đ th hai liên quan đn v trí cha thư mc. Thư mc cĩ th đưc duy trì tp trung ti mt v trí ho c phân tán đn mt s v trí. Gi thư mc ti mt v trí làm cho vic qu n lý đưc d dàng, nh ưng cĩ th làm tăng ti trng ti đĩ, gây ùn tc lưu lưng thơng báo v trí đĩ. Ngưc li, phân tán thư mc trên nhiu v trí làm gim ti trng ti mt đim nh ưng s làm cho vn đ qu n lý thư mc thêm ph c tp. Trong các phc h cơ s d liu, s la chn s ph thuc vào vn đ h thng cĩ phân tán hay khơng. Nu cĩ, thư mc s đưc phân tán, ng ưc li nĩ đưc qu n lý tp trung. Vn đ th ba là nhân bn thư mc. Cĩ th cĩ mt bn thư mc duy nht ho c nhiu bn. Cĩ nhiu bn thư mc s làm tăng đ tin cy ca h thng do kh năng truy xu t đưc mt bn thư mc s cao hơn. Hơn na thi gian tr khi truy xu t thư mc s gim đi do ít xy ra tranh chp và kho ng cách đn các bn sao s ng n hơn. Tuy nhiên, vic duy trì cp nh t các bn sao cũng ph c tp và tn kém. Vì vy s la chn s ph thuc vào mơi trưng h thng và ph i cân bng các yu t như thi gian đáp ng, kích thưc thư mc, kh năng ca máy mi v trí, yêu cu kh tín, mc đ thay đi ca thư mc. Chương 3. Cơ s d liu phân tán 120
52. 2. Thit k cơ s d li u phân tán Thit k mt h thng máy tính phân tán cn ph i chn v trí đt d li u và chương trình trên mt mng máy tính, rt cĩ th ph i k luơn c vic thit k mng. ði vi h qun tr cơ s d li u phân tán cn ph i thc hin hai điu: phân tán cơ s d li u và phân tán các chương trình ng dng chy trên h đĩ. đây chúng ta ch tp trung vào vic phân tán d liu. Vic t chc các h phân tán cĩ th đưc nghiên cu da theo ba trc khơng gian • Mc đ chia s d liu (level of sharing) • Kiu mu truy xut (behavior of access pattern) • Mc đ hiu bit v kiu mu truy xut (1) Theo mc đ chia s cĩ ba kh năng xy ra: - Khơng chia s d liu: mi ng dng và d liu ca nĩ thc thi ti mt v trí, khơng cĩ trao đi ho c giao tip vi nhng chương trình khác hoc truy xu t d liu nhng v trí khác. Hình thc này đc trưng cho các kt ni mng thi kỳ sơ khai. - Chia s d li u: tt c chương trình đu đưc nhân bn cho mi v trí, nh ưng khơng nhân bn d li u. Theo đy các yêu cu ca ngưi dùng đưc x lý ti mi v trí và d liu cn thit đưc chuyn đi trên mng. - Chia s d li u − chương trình : c chương trình và d liu đưc dùng chung. Ngh ĩa là chương trình nm ti mt v trí cĩ th yêu cu dch v t mt chương trình nm v trí th hai, và đn lưt nĩ, chương trình này cĩ th truy xu t d li u nm ti v trí th ba. đây cn phân bit gia Chia s d liu và Chia s d liu - chương trình , đc bit đi vi h phân tán đa chng. Trong mơi trưng đa chng rt khĩ kh ăn, cĩ khi khơng th đưc, cho thc thi mt chương trình trên mt phn cng khác và trong h điu hành khác. (2) Theo kiu mu truy xu t cĩ hai kiu la chn: - Loi tĩnh, khơng thay đi theo thi gian - Loi đng , thay đi theo thi gian. 2.1. Các chin lưc thit k Hai chin lưc chính trong vic thit k cơ s d liu phân tán là tip cn t trên xung và ti p cn t dưi lên . Trong thc t rt him các ng dng đơ n gin đ ch s dng mt cách tip cn, vì vy trong ph n ln thit k c hai cách tip cn đu đưc áp dng b sung nhau. 2.1.1. Quá trình thit k t trên xung Sơ đ quá trình thit k t trên xu ng biu din trong hình sau: Chương 3. Cơ s d liu phân tán 121
53. Phân tích yêu cu Yêu cu h thng Nguyên liu t ngưi dùng Thit k khái nim Thit k khung nh ìn Tích hp khung nhìn Lưc đ khái nim tồn cc Thơng tin truy xut ðnh nghĩa lưc đ ngồi Thit k phân tán Nguyên liu t ngưi dùng Lưc đ khái nim cc b Thit k vt lý Lưc đ vt lý Theo dõi bo trì Vic phân tích yêu cu nh m đnh nghĩa mơi trưng h thng và thu nhp các nhu cu x lý ca tt c ng ưi dùng, đng thi cũng xác đnh yêu cu h thng. H sơ ghi chép các yêu cu là nguyên liu cho hai ho t đng song song: Thit k khung nhìn (view design) và Thit k khái nim (conceptual design). Thit k khung nhìn đnh ngh ĩa các giao din cho ng ưi dùng đu cui (end- user). Thit k khái nim là quá trình xem xét tng th đi tưng − xí nghip, nh m xác đnh các loi thc th và mi liên h gia chúng vi nhau. Ta cĩ th chia quá trình này thành 2 nhĩm bao gm các ho t đng liên quan ti nhau: Phân tích thc Chương 3. Cơ s d liu phân tán 122
54. th (entity analysis) và Phân tích chc năng (functional analysis). Phân tích thc th cĩ liên quan đn vic xác đnh các thc th, các thu c tính và các mi liên h gia chúng. Phân tích chc năng đ cp đn vic xác đnh các chc năng cơ bn cĩ liên quan đn xí nghip cn đưc mơ hình hố. Kt qu ca hai quá trình này cn đưc đi chiu qua li, giúp chúng ta bit đưc chc năng nào s ho t tác trên nhng thc th nào. Cĩ s liên h kh ăng khít gia thit k khái nim và thit k khung nhìn. Theo ngh ĩa nào đĩ thit k khái nim đưc coi nh ư là s tích hp các khung nhìn. Tuy nhiên mơ hình khái nim cn ph i h tr khơng ch nhng ng dng hin cĩ mà cịn c nh ng ng dng trong tương lai. Tích hp khung nhìn nh m đm bo các yêu cu v thc th và các mi liên h gia các khung nhìn đu phi đưc bao quát trong lưc đ khái nim. Trong các hot đng thit k khái nim và thit k khung nhìn, ng ưi thit k cn phi đc t các thc th d liu và phi xác đnh các ng dng chy trên cơ s d li u cũng như các thơng tin thng kê v nhng ng dng này. Thơng tin thng kê bao gm đc t v tn s ng dng, kh i lưng thơng tin khác nhau, Lưc đ khái nim tồn cc GCS và thơng tin v kiu mu truy xut thu đưc trong thit k khung nhìn s là nguyên liu (input) cho bưc thit k phân tán . Mc tiêu ca giai đon này là thit k các lưc đ khái nim cc b LCS bng cách phân tán các thc th cho các v trí ca h thng phân tán. Ta chia quan h thành nhiu quan h nh hơn gi là các mnh (fragment) và phân tán các mnh này. Hot đng thit k phân tán gm hai bưc: Phân mnh (fragmentation) và cp phát (allocation). Ta s tho lun v vn đ này trong các ph n sau. Thit k vt lý là ánh x lưc đ khái nim cc b sang các thit b lưu tr vt lý cĩ sn ti các v trí tương ng. Nguyên liu cho quá trình này là lưc đ khái nim cc b và thơng tin v kiu mu truy xut các mnh. Hot đng phát trin và thit k luơn là quá trình liên tc, địi hi theo dõi hiu chnh thưng xuyên. Vì th chúng ta đưa vn đ quan sát và theo dõi như mt ho t đng chính trong quá trình này. Cn chú ý rng chúng ta khơng ch theo dõi vn đ cài đt cơ s d li u, mà cịn quan sát theo dõi tính thích hp ca các khung nhìn ca ngưi dùng. Kt qu này cĩ tác dng ph n hi, to cơ s cho vic tái thit k v sau. 2.1.2. Quá trình thit k t dưi lên Thit k t trên xu ng thích hp cho nhng cơ s d liu đưc thit k t đu. Tuy nhiên trong thc t cũng cĩ khi đã cĩ sn mt s cơ s d liu, và chúng ta ph i tích hp chúng thành mt cơ s d liu chung. Ti p cn t dưi lên s thích hp cho tình hung này. Khi đim ca thit k t dưi lên là các lưc đ khái nim cc b, s ph i đưc tích hp thành lưc đ khái nim tồn cc. 2.2. Các vn đ thit k phân tán Chương 3. Cơ s d liu phân tán 123
55. Trong mc này chúng ta s tr li các câu hi sau: • Ti sao cn phân mnh • Làm th nào đ thc hin phân mnh • Phân mnh nên thc hin đn mc đ nào • Cách thc kim tra tính đúng đn ca phân mnh • Cách thc cp phát d liu • Nhng thơng tin nào cn thit cho phân mnh và cp phát 2.2.1. Các lý do phân mnh Trưc tiên, khung nhìn ca các ng dng thưng ch là tp con ca quan h. Vì th đơ n v truy xut khơng ph i tồn b quan h mà ch là tp con ca quan h. Kt qu là xem tp con ca quan h là đơ n v phân tán là thích hp. Th hai là, nu các ng dng cĩ các khung nhìn đưc đnh nghĩa trên mt quan h cho trưc li nm ti nh ng v trí khác nhau thì ch cĩ hai cách chn la vi đơ n v phân tán là tồn b quan h, khi khơng cĩ phân mnh: Hoc quan h khơng đưc nhân bn mà đưc lưu mt v trí, ho c quan h đưc nhân bn cho tt c ho c mt s v trí cĩ chy ng dng. Chn la đu gây ra mt s lưng ln truy xu t khơng cn thit đn d li u xa. Cịn chn la sau cĩ th dn đn nhân bn khơng cn thit, gây khĩ khăn khi cp nht và lãng phí khơng gian lưu tr. Cu i cùng vic phân rã quan h thành nhiu mnh, mi mnh x lý nh ư mt đơ n v, s cho phép thc hin nhiu giao dch đng thi. Vic phân mnh quan h cho phép thc hin song song câu vn tin, bng cách chia nĩ thành mt tp câu vn tin con ho t tác trên các mnh. Vì th vic phân mnh s làm tăng mc đ ho t đng đng thi và kéo theo tăng lưu lưng ho t đng ca h thng. Kiu ho t đng này gi là đng thi ni vn tin (intraquery concurency) , s đưc phân tích trong các ph n sau. 2.2.2. Các kiu phân mnh Cĩ hai kiu phân mnh: phân mnh theo chiu dc và phân mnh theo chiu ngang. ◊ Ví d Chúng ta s dng lưc đ cơ s d liu đã phát trin trong chương trưc. Ta thêm vào lưc đ PROJ thu c tính LOC (v trí) đ ch nơi thc hin d án. Sau đây là mt th hin cơ s d li u s đưc dùng: EMP ASG ENO ENAME TITLE ENO PNO RESP DUR E1 J.Doe Elect.Eng. E1 P1 Manager 12 E2 M.Smith Syst.Anal. E2 P1 Analyst 24 E3 A.Lee Mech.Eng. E2 P2 Analyst 6 E4 J.Miller Programmer E3 P3 Consultant 10 E5 B.Casey Syst.Anal. E3 P4 Engineer 48 E6 L.Chu Elect.Eng. E4 P2 Programmer 18 E7 R.David Mech.Eng. E5 P2 Manager 24 E8 J.Jones Syst.Anal. E6 P4 Manager 48 E7 P3 Engineer 36 E8 P3 Manager 40 Chương 3. Cơ s d liu phân tán 124
56. PROJ PAY PNO PNAME BUDGET LOC TITLE SAL P1 Instrumentation 150000 Montreal Elect.Eng. 40000 P2 Database Develop. 135000 New York Syst.Anal. 34000 P3 CAD/CAM 250000 New York Mech.Eng. 27000 P4 Maintenance 310000 Paris Programmer 24000 Trong hình sau trình bày quan h PROJ đưc tách ngang thành 2 quan h PROJ1 cha các thơng tin v d án cĩ kinh phí dưi 200000 USD, và PROJ2 cha các thơng tin v d án cĩ kinh phí ln hơn 200000 USD. PROJ1 PNO PNAME BUDGET LOC P1 Instrumentation 150000 Montreal P2 Database Develop. 135000 New York PROJ2 PNO PNAME BUDGET LOC P3 CAD/CAM 250000 New York P4 Maintenance 310000 Paris Cịn trong hình sau trình bày quan h PROJ đưc tách dc thành 2 quan h PROJ1 cha các thơng tin v kinh phí d án, và PROJ2 cha các thơng tin v tên và v trí d án. PROJ 1 PROJ2 PNO BUDGET PNO PNAME LOC P1 150000 P1 Instrumentation Montreal P2 135000 P2 Database Develop. New York P3 250000 P3 CAD/CAm New York P4 310000 P4 Maintenamce Paris Vic phân mnh cĩ th lng ghép, va phân mnh ngang va phân mnh dc, thành phân mnh tng hp (hybrid fragmentation). 2.2.3. Các qui tc phân mnh đúng đn Cĩ ba qui tc trong khi phân mnh đm bo cơ s d li u s khơng thay đi ng nghĩa khi phân mnh. 1) Tính đy đ (completeness): Cho quan h r bt kỳ. Gi s r đưc phân rã thành các mnh. Khi đĩ tính đy đ yêu cu mi mc d liu trong r cũng ph i đưc lưu tr trong mt hoc vài mnh nào đĩ. 2) Tính tái thit (reconstruction ): Cho quan h r bt kỳ. Gi s r đưc phân rã thành các mnh r1, , rn. Khi đĩ tính tái thit yêu cu “hp” các phân mnh ca quan h r tr li đy đ d li u ban đu ca quan h r. Khái nim “hp” đây là tốn t quan h ∆ sao cho n r r = ∆ i i =1 Chương 3. Cơ s d liu phân tán 125