Tiểu luận Nghiên cứu các phụ thuộc hàm theo thời gian thông qua hai quan điểm của Wang và Wijsen

p con thực sự của Z trên F. + Bước 2. Suy ra các phụ thuộc hàm không tầm thường, ký hiệu F’ mà vế phải chỉ có một thuộc tính thuộc Z. + Bước 3. Tìm G là phủ tối thiểu của F’ Kết luận: Z(F) = G Ví dụ 2.22. Cho M = (R, Ngày, f) với R = ABCD và F = { A ®NgàyD, D ®NgàyB, A ®ThángC} Cho Z = (ABC). Áp dụng thuật toán 2.3, ta có: Bước1. Tính các bao đóng: A = {(A, tTop); (D, Ngày); (B, Ngày); (C, Tháng)} B = {(B, tTop)} C = {(C, tTop)} AB = {(A, tTop); (B, tTop); (D, Ngày); (C, Tháng)} AC = {(A, tTop); (C, tTop); (D, Ngày); (B, Ngày)} BC = {(B, tTop); (C, tTop)} Bước 2. Xác định F’: F’ = {A ®NgàyB, A ®ThángC, AB ®ThángC, AC ®NgàyB} Bước 3. Tìm G là phủ tối thiểu của F’: Ta có: pÆ (F’) = {A ®B, A ®C, AB ®C, AC ®B} Phủ tối thiểu của pÆ (F’) là: Æ(F’) = {A ®B, A ®C} + Với A ® B Î Æ(F’): vì (B, Ngày) Î A nên ta có G = {A ®NgàyB} + Với A ® C Î Æ(F’): vì (C, Tháng) Î A nên ta có: G = {A ®NgàyB, A ®ThángC} Vậy Z(F) = {A ®NgàyB, A ®ThángC} Tương tự như CSDL truyền thống, với CSDL có yếu tố thời gian, sự dư thừa dữ liệu trong các lược đồ môđun thời gian thường được tạo ra từ tập các TFD cho trước. Chính vì thế, để tránh được điều này ta phải thực hiện việc chuẩn hóa lược đồ môđun thời gian nhằm đưa nó về một dạng chuẩn nào đó. TBCNF là một trong các dạng chuẩn cho phép loại bỏ những dư thừa dữ liệu do các TFD gây nên. 2.4.1. Dạng chuẩn Boyce Codd theo thời gian (TBCNF) Định nghĩa 2.25. (TBCNF) Cho lược đồ môđun thời gian (R, t) với tập các phụ thuộc hàm theo thời gian F. Khi đó, (R, t) được gọi là thoả TBCNF nếu: với mỗi X ®t’Y Î F+ mà XY Í R; Y Ï X và ít nhất một thời điểm của t được phủ bởi thời điểm của t’ thì: 1). X là siêu khóa của (R, t) và, 2). Nếu mọi thời điểm i1 ¹ i2 của t khác rỗng, thì X ® Y Ï pt(i,i) (F). Hay nói cách khác: không tồn tại hai thời điểm khác nhau của t chứa trong cùng một thời điểm của t’. Nhận xét: + Điều kiện (1) tương tự như điều kiện của BCNF truyền thống. + Điều kiện (2) không cho phép có dư thừa do các TFD gây nên. Nếu tồn tại một TFD với kiểu thời gian t’ sao cho hai thời điểm khác nhau của kiểu thời gian t (là kiểu thời gian của môđun) chứa trong cùng một thời điểm của t’ thì xuất hiện dư thừa dữ liệu vì trong trường hợp này, nếu có hai bộ riêng biệt trên hai thời điểm thì một trong hai bộ đó là dư thừa. Ví dụ 2.23. Xét lược đồ môđun thời gian (R, Giây), với R = (ABCD) và F = {A ®NgàyD}. Hỏi (R, Giây) thoả TBCNF không ? Vì A = {(A, tTop); (D, Ngày)}. Vậy A ↛Giây R, do đó A không là siêu khóa của R. Vậy (R, Giây) không thoả TBCNF. Trong ví dụ 2.23, rõ ràng (R, Giây) làm cho (R, Giây, f) dư thừa dữ liệu do tồn tại A ®NgàyD. Để tránh được điều này, ta có thể thực hiện việc phân tách (R, Giây) thành hai lược đồ môđun thời gian riêng biệt thoả TBCNF mà vẫn bảo toàn được thông tin. Định nghĩa 2.26. (Phân tách) Một phân tách của lược đồ mô đun thời gian (R, t) là tập các lược đồ môđun thời gian r = {(R1, t1), ..., (Rk, tk)} sao cho: Ri Í R, với i = R = Với mỗi ti không có thời điểm nào của t phủ lên một thời điểm của ti, tức là với "l, j: t(l) Ç ti(j) = Æ hoặc t(l) Í ti(j). Nhận xét: Điều kiện (i) và (ii) tương tự như các điều kiện của định nghĩa phân tách truyền thống. Với điều kiện (iii), mỗi thời điểm của nó giao nhau với một thời điểm của kiểu thời gian gốc, hay kiểu thời gian trong phân tách lớn hơn kiểu thời gian gốc. Điều kiện này được đưa ra nhằm giảm dư thừa dữ liệu, vì nếu một thời điểm nào đó của kiểu thời gian gốc chứa hai hay nhiều thời điểm của một kiểu thời gian trong phân tách thì một vài giá trị của các thuộc tính sẽ bị lặp lại trong cả hai thời điểm của kiểu thời gian mới. Định nghĩa 2.27. (Tách bảo toàn thông tin) Cho lược đồ môđun thời gian (R, t) và tập phụ thuộc hàm theo thời gian F. Khi đó, một phân tách r của (R, t) đối với F được gọi là bảo toàn thông tin nếu tồn tại các tập con r1, ..., rm của r sao cho với mỗi môđun thời gian M trên (R, t) thoả tất cả các TFD trong F thì ta có: M = Join(r1) ÈT ... ÈT Join(r2) Với: Join(ri) = Down(Up(pR(M), t), t) ⋈T ... ⋈TDown(Up(pR(M), t), t) với ri = {(R, t), ...,(R, t)} Ví dụ 2.24. Cho lược đồ môđun thời gian (R, Ngày). Giả sử ta phân tách lược đồ đó thành hai lược đồ (R, t1) và (R, t2), trong đó t1 là những ngày Thứ bảy và Chủ nhật, t2 là những ngày từ Thứ hai đến Thứ sáu. Cho M = (R, Ngày, f) + Với r1 = {(R, t1)} ta có: Join(r1) = Down(Up(pR(M), t1), Ngày) = (R, Ngày, f1); f1(i) = f(i), với i là các ngày Thứ bảy, Chủ nhật và f1(i) = Æ đối với các ngày còn lại. + Với r2 = {(R, t2)} ta có: Join(r2) = Down(Up(pR(M), t2), Ngày) = (R, Ngày, f2); f2(i) = f(i), với i là các ngày từ Thứ hai đến Thứ sáu và f2(i) = Æ đối với các ngày còn lại. Như vậy, M = M1 ÈT M2 = (R, Ngày, f), với f(i) = f1(i) È f2(i). Vậy phép tách bảo toàn thông tin. Trong định nghĩa 2.27, nếu khi m = 1 thì điều kiện cho một phân tách bảo toàn thông tin là M = Join(r). Phép toán Join gồm một phép nối giữa các môđun được phân tách theo r, nghĩa là các môđun được tạo ra từ Up(p(M), ti), với (Rj, tj) là lược đồ tương ứng trong r. Tuy nhiên, phép nối tự nhiên theo thời gian (⋈T) đòi hỏi các môđun phải có cùng kiểu và kết quả của phép nối sẽ là một môđun với kiểu t, vì ta phải kiểm tra xem có bằng với môđun gốc hay không. Việc chuyển mỗi môđun thời gian sang kiểu t trước khi thực hiện nối là điều cần thiết. Theo định nghĩa phân tách, rõ ràng phép Down là phép toán dự bị cho mục đích này, phép Down và Up có thể dẫn đến các giá trị không có trong môđun gốc. Ví dụ 2.25. Cho M = (KHOÁHỌC, Ngày,f ) Với r1 = {(KH1, tT)}, KH1 = (Mã KH, Số ĐVHT) r2 = {(KH2, Tháng)}, KH2 = (Họ tên GVGD, Lương ) r3 = {(KH3, Tuần)}, KH3 = (Mã KH, Họ tên GVGD) r4 = {(KH4, Ngày)}, KH4 = (Mã KH, Số HV) Khi đó: Join(r1) = Down(Up(pKH1(KHOÁHỌC), tT), Ngày) Join(r2) = Down(Up(pKH2(KHOÁHỌC), Tháng), Ngày) Join(r3) = Down(Up(pKH3(KHOÁHỌC), Tuần), Ngày) Join(r4) = Down(Up(pKH4(KHOÁHỌC), Ngày), Ngày) Ta có thể nhận thấy rằng phép Down trên mỗi phép biến đổi bằng với các môđun KH1, KH2, KH3 và KH4. Phép biến đổi cuối không làm thay đổi môđun KH4 vì Down và Up không hiệu quả đối với KHOÁHỌC khi các kiểu thời gian đều ở dưới dạng Ngày. Do đó, ta thực hiện nối Down(KH1, Ngày), Down(KH2, Ngày), Down(KH3, Ngày) với KH4 để được quan hệ KHOÁHỌC. Trước khi trình bày thuật toán phân tách lược đồ môđun thời gian thành các lược đồ con thoả TBCNF, chúng ta sẽ tìm hiểu hai phép toán sau: Phép che lấp (collapse): Cho một kiểu thời gian t và một số nguyên dương i. Khi đó, phép che lấp của t, ký hiệu tc được tạo ra bằng cách nối thời điểm i và i+1 lại thành một thời điểm và giữ lại tất cả các thời điểm khác của t. Với mọi j ³ 1, kiểu tc được xác định như sau: tc = t(j) với 1 ≤ j ≤ i - 1 t(i, i + 1) với j = i t(j + 1) với j > i Phép lược bỏ (Prune): Cho một kiểu thời gian t và một số nguyên dương i. Khi đó, phép lược bỏ của t, ký hiệu tp được tạo ra bằng cách bỏ đi thời điểm i của t và giữ lại tất cả các thời điểm khác của t. Với j ³ 1, kiểu tp được xác định như sau: tp = t(j) với 1 ≤ j ≤ i -1 t(j + 1) với j ³ i Ta có thể nhận thấy rằng, nếu lược đồ (Ri, ti) không thuộc dạng TBCNF đối với pR(F) thì tồn tại một TFD trong R(F) sao cho một trong hai điều kiện của định nghĩa TBCNF bị vi phạm. Vì thế thuật toán phân tách đòi hỏi bước 2 luôn được thực hiện. Sau đây là một thuật toán cho phép tách một lược đồ môđun thời gian thành các lược đồ con thoả TBCNF mà không mất thông tin. Thuật toán 2.4. (Thuật toán tách một lược đồ môđun thời gian thành các lược đồ con thoả TBCNF bảo toàn thông tin) Vào: + Lược đồ môđun thời gian (R, t). + Tập các phụ thuộc hàm theo thời gian F. Ra: r = {(R1, t1), ..., (Rk, tk)} bảo toàn thông tin và (Ri, ti) Î TBCNF, i= Phương pháp: + Bước 1. r(0) = {(R, t)} + Bước 2. Giả sử r(j) là tập cuối cùng ta tính được. Nếu có ít nhất một lược đồ con trong r(j ) không phải là TBCNF thì ta sẽ tính r(j + 1) như sau: Với (Ri, ti) Ï TBCNF và TFD X ®t’A Î R(F) của lược đồ này vi phạm các điều kiện của TBCNF thì: r(j + 1) = (r(j) \ {(Ri, ti)}) È {(Ri, t); (Ri - A, t); (XA, t)}, với t, t, t là các kiểu thời gian mới được xác định như sau: t có được từ ti bằng cách áp dụng phép toán lược bỏ theo cách đệ quy để bỏ bớt tất cả các thời điểm khác rỗng của ti chứa trong các thời điểm của t’. Nếu t dẫn đến một kiểu rỗng thì lược đồ tương ứng (Ri, t) sẽ không được thêm vào trong r(j + 1). t là phần bù của t, nghĩa là các thời điểm của nó là tất cả các thời điểm của ti chứa trong các thời điểm của t’. t có được từ t bằng cách áp dụng phép toán che lấp theo cách đệ quy để nối mỗi cặp thời điểm của t chứa trong các thời điểm của t’. Nghĩa là mỗi thời điểm khác rỗng của t là sự kết nối của một hay nhiều thời điểm của t. Ngoài ra, không có hai thời điểm nào của t được chứa trong một thời điểm của t’. Bước 2 được lặp lại cho đến khi mỗi lược đồ trong r(j) đều thuộc TBCNF. Thuật toán trả về phân tách r(j). Ví dụ 2.26. Cho (R, Giây) với R = (ABCD) và F = {A ®NgàyD} Theo ví dụ 2.23, rõ ràng (R, Giây) không thoả TBCNF nên áp dụng thuật toán 2.4, ta có: Với (R, Giây) Ï TBCNF và với TFD A ®NgàyD Î R(F): Vì TFD A ®NgàyD vi phạm điều kiện của TBCNF nên ta tách (R, Giây) thành hai lược đồ con là (R1, Giây) với R1 = ABC và (R2, Ngày) với R2 = AD. Vậy ta có phép tách r = {(R1, Giây); (R2, Ngày)} Định lý 2.3. (Điều kiện cần để 1 phân tách thành hai lược đồ con bảo toàn thông tin) Cho F là tập các TFD. Khi đó, phân tách (R1, t) và (R2, t’) của (R1 È R2, t) với t ≼ t’ là bảo toàn thông tin đối với F nếu với mọi i1, i2, t(i1, i2) Í t’(j) với j nào đó suy ra R1 Ç R2 ® R2 Î pt(i,i)(F) Ví dụ 2.27. Theo ví dụ 2.26, từ lược đồ môđun thời gian (R, Giây) với R = (ABCD) và F = {A ®NgàyD}, sau khi được tách thành hai lược đồ con là (R1, Giây) với R1 = (ABC) và (R2, Ngày) với R2 = (AD). Vì R1 Ç R2 ® R2 Î pGiây(F) hay ABC Ç AD ® AD Î {A ® D} nên theo định lý 2.3, phép tách trên là bảo toàn thông tin. Ví dụ 2.28. Cho lược đồ môđun thời gian (KHOÁHỌC, Ngày), với: KHOÁHỌC = (Mã KH, Số ĐVHT, Họ tên GVGD, Lương, Số HV) F = { Mã KH ®tSố ĐVHT Mã KH ®TuầnHọ tên GVGD Họ tên GVGD ®ThángLương Mã KH ®NgàySố HV } Để thuận lợi cho việc theo dõi, giả sử ta ký hiệu A: Mã KH, B: Số ĐVHT; C: Họ tên GVGD; D: Lương và E: Số HV. Khi đó ta có: + Lược đồ môđun thời gian (KHOÁHỌC, Ngày) với: KHOÁHỌC = ABCDE và F = {A ®tB; A ®TuầnC; C ®ThángD; A ®NgàyE} Áp dụng thuật toán 2.4 ta có: A = {(A, tTop); (B, tTop); (C, Tuần); (D, Ngày); (E, Ngày)}. Vậy A ®NgàyKHOÁHỌC, hay A là siêu khoá của (KHOÁHỌC, Ngày). pNgày(F) = {A ®B; A ®C; C ®D; A ®E} Bước 1. Ta có: r(0) = (ABCDE, Ngày) Bước 2. + Xét TFD A ®tB: vì A ® B Î pNgày(F) nên (ABCDE, Ngày) Ï TBCNF. Với (ABCDE, Ngày) Ï TBCNF và A ®tB Î ABCDE(F), ta có ti = Ngày, t’ = tTop. Vì Ngày ≼ tTop nên t = tBottom, t = Ngày, t = tTop. Khi đó: r(1) = (r(0) \ (ABCDE, Ngày)) È {(ACDE, Ngày); (AB, tTop)} + Xét TFD C ®ThángD: vì C ® D Î pNgày(F) nên (ACDE, Ngày) Ï TBCNF. Với (ACDE, Ngày) Ï TBCNF và C ®ThángD Î ACDE(F), ta có ti = Ngày, t’ = Tháng. Vì Ngày ≼ Tháng nên t = tBottom, t = Ngày, t = Tháng. Khi đó: r(2) = (r(1) \ (ACDE, Ngày)) È {(ACE, Ngày); (CD, Tháng)} = {(AB, tTop); (ACE, Ngày); (CD, Tháng)} + Xét TFD A ®TuầnC: vì A ® C Î pNgày(F) nên (ACE, Ngày) Ï TBCNF. Với (ACE, Ngày) Ï TBCNF và A ®TuầnC Î ACE(F), ta có ti = Ngày, t’ = Tuần. Vì Ngày ≼ Tuần nên t = tBottom, t = Ngày, t = Tuần. Khi đó: r(3) = (r(2) \ (ACE, Ngày)) È {(AE, Ngày); (AC, Tuần)} = {(AB, tTop); (CD, Tháng); (AE, Ngày); (AC, Tuần)} + Xét TFD A ®NgàyE. Rõ ràng (AE, Ngày) Î TBCNF. Vậy r = {(AB, tTop); (CD, Tháng); (AC, Tuần); (AE, Ngày)} Như vậy, để tránh tất cả các dư thừa dữ liệu do các phụ thuộc hàm gây nên thì đổi lại ta phải chịu tồn tại một số phụ thuộc hàm không bảo toàn. Vì BCNF là một trường hợp đặc biệt của TBCNF nên sẽ không ngạc nhiên nếu việc phân tách một lược đồ môđun thời gian thành các lược con thoả TBCNF mà không bảo toàn được các TFD. Với các lược đồ phi thời gian, nếu lược đồ đó chỉ chứa hai thuộc tính thì nó luôn thuộc BCNF và không có dư thừa nào cả. Trong khi đó thì với các lược đồ môđun thời gian, ngay cả khi nó chỉ có hai thuộc tính cũng không hoàn toàn tránh được dư thừa mà không làm mất các TFD. Chẳng hạn, xét lược đồ (AB, Ngày) với F = {A ®TuầnB, A ®ThángB}. Rõ ràng (AB, Ngày) không thoả TBCNF do tồn tại A ®B Î Ngày(F) , sử dụng thuật toán 2.4 ta tách (AB, Ngày) thành hai lược đồ con r = {(A, Ngày), (AB, Tháng)}. Rõ ràng r bảo toàn thông tin, song TFD A ®TuầnB không được ràng buộc trong hai lược đồ con. Việc tách một lược đồ môđun thời gian thành các lược đồ con thoả TBCNF mà vẫn bảo toàn được các TFD là hoàn toàn không thể thực hiện được. Vì vậy, chúng ta cần phải tách một lược đồ môđun thời gian thành các lược đồ con thoả một dạng chuẩn khác mà không phải là TBCNF, dạng chuẩn đó chính là T3NF được giới thiệu sau đây. 2.4.2. Dạng chuẩn 3 theo thời gian (T3NF) Định nghĩa 2.28. (T3NF) Cho lược đồ môđun thời gian (R, t) với tập các phụ thuộc hàm theo thời gian F. Khi đó, (R, t) được gọi là thoả T3NF nếu: với mỗi X ®t’A Î F+ mà XA Í R; A Ï X và ít nhất một thời điểm của t chứa trong một thời điểm của t’ thì: + Hoặc A là thuộc tính khóa của (R, t) + Hoặc X là siêu khóa của R và không tồn tại i1, i2 với i1 ¹ i2 sao cho X ® Y Î pt(i,i) (F) trừ khi tồn tại i3 với i3 ¹ i1 sao cho X ® Y Î pt(i,i) (F) nhưng X ® Y Ï pt(i,i,i) (F) Ví dụ 2.29. Xét lược đồ môđun thời gian (AB, Ngày), với: F = {A ®NgàyB, B ®ThángA}. (AB, Ngày) thoả T3NF không ? + A = {(A, tTop); (B, Ngày)} Þ A ®NgàyAB A là siêu khóa của (AB, Ngày). + B = {(B, tTop); (A, Tháng)} Þ B ®Ngày AB B là siêu khóa của (AB, Ngày). Vậy cả A và B đều là thuộc tính khóa của (AB, Ngày). Do đó (AB, Ngày) thoả T3NF. Song, lược đồ môđun thời gian với tập F được cho trong ví dụ 2.29 là không thoả TBCNF do tồn tại TFD B ®ThángA vi phạm điều kiện của TBCNF. Như đã giới thiệu ở trước, khác với chuẩn TBCNF, các điều kiện của chuẩn T3NF có phần nhẹ hơn, nó cho phép tồn tại dư thừa dữ liệu nhưng đổi lại có thể bảo toàn được các TFD. Để làm rõ vấn đề này, trước hết chúng ta sẽ tìm hiểu định nghĩa sau đây. Định nghĩa 2.29. (Tách bảo toàn TFD) Cho một lược đồ môđun (R, t) và tập các phụ thuộc hàm theo thời gian F. Khi đó, phép tách r = {(R1, t1), ..., (Rk, tk)} được gọi là bảo toàn phụ thuộc hàm trong F nếu: với mỗi môđun M trên (R, t) mà Up(pR(M), ti) thoả pR(F), i = thì suy ra M thoả F. Trước tiên, ta giải quyết trường hợp đơn giản đối với mỗi TFD có vế trái và vế phải giống nhau. Chẳng hạn, cho trước một kiểu thời gian t và tập các TFD F = {X ®tY, ..., X ®tY}, cho hàm Cop(t, F) trả về một kiểu thời gian mới là l bắt đầu với l = t và che lấp theo cách đệ quy mỗi cặp thời điểm kề nhau i1 và i2 sao cho cả hai điều kiện sau được thoả mãn: 1). X ® Y Î pl(i, i)(F) và 2). Với "i3, X ® Y Î pl(i, i)(F) È pl(i, i)(F) suy ra: X ® Y Î pl(i, i, i)(F) Hàm Cop cho ra một kiểu thời gian lớn nhất của tất cả các kiểu thời gian t’ sao cho mỗi thời điểm của t’ là một thời điểm của t hoặc là một phân tách của tập các thời điểm của t chứa trong cùng TFD thuộc ≼ và sao cho {(R, t’)} vẫn bảo toàn tất cả các TFD trong F. Ví dụ 2. 30. Cho kiểu thời gian Ngày và F = {A ®TuầnB, A ®ThángB}. Hình sau đưa ra kiểu thời gian Cop(Ngày, F). Tháng Ngày Tuần Cop Thời gian tuyệt đối Hình 2.1. Hàm Cop(Ngày, F) Việc bảo toàn các TFD là mâu thuẫn với việc tránh dư thừa. Trở lại với ví dụ trước, cho l = Cop(Ngày, F) với F = {A ®TuầnB, A ®ThángB}. Cho d1 là ngày 31/3/2006 và d2 là ngày 1/4/2006. Giả sử rằng bộ t = (a, b) thuộc cả f(d1) và f(d2). Điều này là dư thừa. Song, d1 và d2 thuộc cùng một tuần nhưng khác tháng. Do đó, ở hình 2.1, d1 và d2 không được nối với nhau trong việc tính l. Do vậy, hai bộ này vẫn còn nhưng bị tách rời trong môđun mới Up(M, l). Nếu d1 và d2 thuộc cùng một thời điểm của l thì phân tách {(A, Ngày), (AB, l)} của (AB, l) sẽ không bảo toàn TFD. Tiếp theo, chúng ta sẽ trình bày giải thuật cho phép tách một lược đồ môđun thời gian thành các lược đồ con thoả T3NF bảo toàn được các TFD. Thuật toán 2.5. (Thuật toán tách một lược đồ môđun thời gian thành các lược đồ con thoả T3NF bảo toàn thông tin và bảo toàn các TFD) Vào: + Lược đồ môđun thời gian (R, t). + Tập các phụ thuộc hàm theo thời gian F. Ra: r = {(R1, t1), ..., (Rk, tk)} bảo toàn thông tin và bảo toàn TFD, với (Ri, ti) Î T3NF, i= Phương pháp: Bước 1. Tìm là một phủ cực tiểu theo thời gian của F. Từ tập tất cả các kiểu {t,…, t} xuất hiện trong các TFD của , ta tính một phân chia P = {t1,…, tm} của t như sau: Bắt đầu với P(0) = {t}, với mỗi t trong các TFD bắt đầu từ i = 1 đến i = l, có P(i) bằng cách thay thế mỗi t k trong P(i–1) bằng t k1, t k2 với t k1 có được từ t k bằng cách bỏ đi tất cả các thời điểm khác rỗng chứa trong t, và t k2 là kiểu bổ sung; nghĩa là kiểu chỉ có những thời điểm chứa trong t. P = P(l)sẽ là một phân chia mong muốn. Với mỗi thời điểm j¹ Æ của t , chỉ một và một kiểu tk Î P(l) với một thời điểm s chứa nó. Ngoài ra, t(j) = t k(s). Với mỗi t k trong P ta định nghĩa tập: Ft= {X ®t’ A | X ®t’ A Î  và $j, i : t k(j) ¹ Æ Ù t k(j) Í t’(i)}. Bước 2. Cho r = Æ. Với mỗi X ® A Î pÆ(), được cho trước {t r,…, t s} = {t k ΠP | $t sao cho X ®tA Î Ft} và FX ® A = {X ®tA | $t k ΠP sao cho X ®tA Î Ft}, thì ta thêm (XA, Raise(t r ∪ … ∪ t s, FX ® A)) vào r. Bước 3. Với mỗi tk trong P thêm (Z, tk) vào r với Z là khóa thời gian của (R, tk), nếu không có (V, t r) Î r, với Z Í V và tk là một kiểu con của t r. Bước 4. Nếu (X, t’) và (Y, t’) với X Í Y đều thuộc r, thì bỏ (X, t’) từ r. Ngoài ra, nếu (X, t) và (X, t) đều thuộc r, và t và t là các kiểu con của một kiểu thời gian, thì bỏ (X, t) và (X, t) nhưng thêm (X, t È t) vào. Bước cuối cùng này được lặp lại cho đến khi nào không còn thay đổi nào nữa. Ví dụ 2. 31. Trở lại ví dụ 2.28, với: Lược đồ môđun thời gian (KHOÁHỌC, Ngày), trong đó: KHOÁHỌC = (Mã KH, Số ĐVHT, Họ tên GVGD, Lương, Số HV) và F = { Mã KH ®tSố ĐVHT Mã KH ®TuầnHọ tên GVGD Họ tên GVGD ®ThángLương Mã KH ®NgàySố HV } Để thuận lợi cho việc theo dõi, giả sử ta ký hiệu A: Mã KH, B: Số ĐVHT; C: Họ tên GVGD; D: Lương và E: Số HV. Khi đó ta có: + Lược đồ môđun thời gian (KHOÁHỌC, Ngày) với: KHOÁHỌC = ABCDE và F = {A ®tB; A ®TuầnC; C ®ThángD; A ®NgàyE} Với ví dụ này, kết quả phân tách thu được bằng việc áp dụng thuật toán 2.4 cũng bảo toàn TFD. Vì vậy, để phân biệt thuật toán 2.4 và thuật toán 2.5 ta sẽ bổ sung vào tập các ràng buộc trên một ràng buộc mới. Chẳng hạn, với ràng buộc: lương của giáo viên giảng dạy không được thay đổi trong một tháng, điều này có nghĩa là C ®ThángD. Song, người quản lý trung tâm lại quyết định trả lương cho giáo viên theo hàng tuần, do đó trong F có thêm TFD C ®TuầnD. Sự tồn tại TFD C ®TuầnD trong F sẽ không làm thay đổi kết quả phân tách thu được từ việc sử dụng thuật toán 2.4, vì với hai TFD C ®ThángD và C ®TuầnD, rõ ràng TFD C ®ThángD được chọn. Khi đó, tất cả các lược đồ được tách đều thuộc TBCNF. Song, nó lại không bảo toàn các TFD. Vì vậy, để bảo toàn các TFD, ta sử dụng thuật toán 2.5 để phân tách thành T3NF. Bước 1. Tính . Ta có: = {A ®tB; A ®TuầnC; C ®ThángD; C ®TuầnD; A ®NgàyE} Vì kiểu thời gian của môđun này là Ngày, là kiểu thời gian bé hơn bất kỳ kiểu nào có trong nên không có phân chia nào được thực hiện trong bước này. Khi đó, ta có P = {Ngày} và FNgày = {A ®tB; A ®TuầnC; C ®ThángD; C ®TuầnD; A ®NgàyE} Bước 2. Ta có: pÆ() = {A ®B; A ®C; C ®D; A ®E} + Với các FD {A ®B; A ®C; A ®E}Î pÆ(), vì hàm Cop(Ngày, F’) với F’ = {A ®tB; A ®TuầnC; A ®NgàyE} luôn trả về một kiểu thời gian lớn hơn nên ta có phân tách: r = {(AB, tTop); (AC, Tuần); (AE, Ngày)} + Với FD C ® D Î pÆ(), nó xác định thêm trong r một lược đồ với kiểu thời gian mới (CD, Cop(Ngày, F’’)) trong đó F’’ = {C ®ThángD; C ®TuầnD}, kiểu thời gian mới ở đây là kiểu lớn nhất của hai kiểu Tuần và Tháng. Điều này đã được chỉ ra trong hình 2.1. Vì bước 3 và bước 4 của thuật toán 2.5 không đưa ra bất kỳ một thay đổi nào, do đó kết quả của phép tách thành T3NF ở ví dụ này là: r = {(AB, tTop); (AC, Tuần); (AE, Ngày); (CD, Cop(Ngày, F’’))} với F’’ = {C ®ThángD; C ®TuầnD} Như vậy, với tập gồm 5 TFD được cho trong ví dụ 2.31, rõ ràng nếu ta áp dụng thuật toán 2.4 để tách (ABCDE, Ngày) thành các lược đồ môđun con thoả TBCNF thì chỉ bảo toàn thông tin. Song, nếu ta áp dụng thuật toán 2.5 để tách (ABCDE, Ngày) thành các lược đồ môđun con thoả T3NF thì kết quả thu được là những lược đồ con bảo toàn thông tin và bảo toàn phụ thuộc hàm. Nhận xét: Nếu kiểu thời gian của lược đồ môđun thời gian và các kiểu thời gian có trong các phụ thuộc hàm của lược đồ môđun là như nhau thì thuật toán 2.5 thực chất là thuật toán tách một lược đồ quan hệ thành 3NF truyền thống. 2.5. Mối quan hệ giữa FD và TFD Gọi T là tập các kiểu thời gian có trong các TFD của tập F mà quan hệ ≼ giữa các kiểu thời gian trên T là quan hệ thứ tự toàn phần. Cho môđun thời gian M = (R, t, f). Xét kiểu thời gian t’ sao cho t ≼ t’. Khi đó, ta có thể xem t’ như là thuộc tính trên M và hoàn toàn có thể xác định được giá trị của t’ tại các bộ thuộc môđun M. Chẳng hạn, xét quan hệ KHOÁHỌC được cho ở bảng 2.1 ta thấy: rõ ràng đó là một quan hệ theo thời gian có sử dụng kiểu thời gian t = Ngày, do đó ta có thể bổ sung thuộc tính (cột) t’ = Tháng và giá trị của t’ này tại mọi bộ là hoàn toàn xác định được. Từ nhận xét này, ta có thể xây dựng tính chất như sau: Tính chất 2.1. (Mối quan hệ giữa TFD và FD) Trên lược đồ môđun thời gian (R, t) cho một môđun thời gian M = (R, t, f). Gọi t’ là một kiểu thời gian sao cho t ≼ t’. Xét M’ = (R’, t ,f’) trong đó R’ = R È {t’} và f’ là tập các bộ của f đồng thời có bổ sung thuộc tính thời gian t’. Khi đó, ta nói rằng M thoả X ®t’Y khi và chỉ khi M’ thoả t’X ® Y. Chứng minh. Giả sử M thoả TFD: X ®t’Y. Xét về mặt ngữ nghĩa, TFD này có nghĩa là: trong khoảng thời gian t’, nếu có hai bộ giống nhau trên X thì cũng giống nhau trên Y. Điều này cũng có thể biểu diễn bởi một FD truyền thống bằng cách đưa thuộc tính t’ vào (R, t). Khi đó, (R’, t, f’) = M’ và TFD t’X ®tY hay FD: t’X ® Y FD này có nghĩa là: tại bất kỳ thời điểm nào, nếu có hai bộ giống nhau về t’ và X thì cũng giống nhau về Y. Vậy, M thoả X ®t’Y khi và chỉ khi M’ thoả t’X ®Y □ Ví dụ 2.32. Xét quan hệ KHOÁHỌC được cho trong bảng sau: Bảng 2.3. Quan hệ KHOÁHỌC. KHOÁHỌC: Mã KH Số ĐVHT Họ tên GVGD HS Lương Số HV Ngày EX27 3 Lê Hoàng 1.82 50 3/3/05 EX27 3 Lê Hoàng 1.82 45 8/3/05 EX27 3 Lê Hoàng 2.06 50 5/4/05 Trên lược đồ môđun thời gian (KHOÁHỌC, Ngày). Cho: + M = (KHOÁHỌC, Ngày, f), trong đó: KHOÁHỌC = (Mã KH, Số ĐVHT, Họ tên GVGD, HS lương, Số HV) f(3/3/05) = {} f(8/3/05) = {} f(5/4/05) = {} Với t’ = Tháng. Ta xét: + M’ = (KH, Ngày, f’), trong đó: KH = (Mã KH, Số ĐVHT, Họ tên GVGD, HS lương, Số HV, Tháng) f’(3/3/05) = {} f’(8/3/05) = {} f’(5/4/05) = {} Giả sử trên M có ràng buộc là HS lương của giáo viên giảng dạy không được thay đổi trong một tháng. Ta có thể biểu diễn ràng buộc này bởi TFD sau: Họ tên GVGD ®ThángHS lương (1) Xét về mặt ngữ nghĩa, TFD này có nghĩa là: tại bất kỳ thời điểm nào đó của Tháng, nếu giá trị của Họ tên GVGD giống nhau thì giá trị của HS lương cũng phải giống nhau. Ngoài ra, ta cũng có thể biểu diễn ràng buộc trên bởi một FD truyền thống bằng cách đưa thuộc tính Tháng vào quan hệ KHOÁHỌC. Khi đó, theo tính chất trên thì (1) tương đương với ràng buộc sau Tháng, Họ tên GVGD ® HS lương (2) Ta có thể thận thấy rằng FD (2) đúng trên quan hệ KHOÁHỌC. Điều này có nghĩa là: trong quan hệ KHOÁHỌC, tại bất kỳ thời điểm nào đó nếu có hai giáo viên nào đó trong cùng Tháng có giá trị Họ tên GVGD giống nhau thì giá trị của HS lương cũng giống nhau. Như vậy, tính chất 2.1 đã phản ánh được mối quan hệ giữa TFD và FD. Ngoài ra, tính chất 2.1 đã cho phép chúng ta có được một số hệ quả sau: Hệ quả 2.1. Cho môđun thời gian M = (R, t, f) và X, Y Í R. Khi đó, ta nói rằng M thoả X ®tY khi và chỉ khi M thoả tX ®Y. Chứng minh. Giả sử M thoả TFD: X ®tY. Xét về mặt ngữ nghĩa, TFD này có nghĩa là: trong khoảng thời gian t, nếu có hai bộ giống nhau trên X thì cũng giống nhau trên Y. Theo tính chất trên, điều này cũng có thể biểu diễn bởi một FD truyền thống bằng cách xem t như là một thuộc tính và đưa thuộc tính t vào (R, t). Khi đó, ta có FD: tX ® Y FD này có nghĩa là: tại bất kỳ thời điểm nào đó, nếu có hai bộ giống nhau về t và X thì cũng giống nhau về Y. Vậy, M thoả X ®tY khi và chỉ khi M thoả tX ®Y □ Nhận xét: Từ hệ qủa này, chúng ta có thể chứng minh một số tính chất của TFD bằng cách chuyển các TFD thành các FD tương ứng. Chẳng hạn, ta cũng có luật tách như sau: Cho môđun thời gian M = (R, t, f), X Í R, Ai Î R, i = và tập phụ thuộc hàm theo thời gian F. Khi đó, ta nói rằng: M thoả X ®tA1A2...An khi và chỉ khi M thoả X ®tAi với "i = . Hệ quả 2.2. Cho môđun thời gian M = (R, t, f) với X, Y, Z Í R. Gọi T là tập các kiểu thời gian mà quan hệ ≼ giữa các kiểu thời gian trong chúng là quan hệ thứ tự toàn phần. Cho t1, t2 Î T, không mất tính tổng quá