Luận văn Phụ thuộc hàm theo thời gian

MỞ ĐẦU Ngày nay, chúng ta đang sống và làm việc trong thời đại phát triển của công nghệ thông tin. Nhu cầu sử dụng thông tin ngày càng được mọi người quan tâm hơn, thông tin không những phải được truy cập nhanh mà còn phải chính xác. Với một lượng lớn dữ liệu từ các lĩnh vực khác nhau đang ngày một tăng nhanh, các kho dữ liệu sớm được hình thành. Do đó, để sử dụng và khai thác dữ liệu một cách có hiệu quả, các nhà khoa học đã tập trung nghiên cứu về cơ sở dữ liệu (CSDL). Một khía cạnh quan trọng khi nghiên cứu cơ sở dữ liệu đó chính là yếu tố thời gian. Yếu tố thời gian làm cho CSDL rõ ràng hơn, hữu ích hơn nhưng đồng thời cũng làm cho nó trở nên phức tạp hơn. Do đó người ta thường bỏ qua yếu tố thời gian, không quan tâm đến nó khi thiết kế CSDL. Song, hầu hết các ứng dụng CSDL hiện nay đều có liên quan đến yếu tố thời gian. Vì vậy, vấn đề đặt ra cho các nhà khoa học là: làm thế nào để có thể xây dựng được các ứng dụng CSDL có yếu tố thời gian một cách thích hợp và có hiệu quả. Các nghiên cứu về CSDL trong những năm gần đây đa số tập trung vào việc giải quyết vấn đề này. Yếu tố thời gian có ở khắp nơi trong các hệ thống thông tin và làm cho các hệ thống đó trở nên phức tạp. Tại các hệ thống thông tin, dữ liệu luôn tăng nhanh và không ngừng thay đổi theo thời gian, do đó việc lưu trữ không chỉ được thực hiện tại một thời điểm nhất định ở một ngày cụ thể nào đó mà phải thường xuyên được lưu trữ theo thời gian nhằm đảm bảo việc cung cấp thông tin cho người sử dụng là hoàn toàn chính xác ở mọi thời điểm, cả trong qúa khứ, hiện tại và tương lai. Yếu tố thời gian trong CSDL bước đầu được nghiên cứu trong ngữ cảnh của mô hình quan hệ [12] do mô hình này được xây dựng trên một cơ sở toán học chặt chẽ với các phép toán đại số và logic, điều này rất phù hợp với việc mô tả các khái niệm về thời khoảng cũng như một số các thao tác đối với dữ liệu có yếu tố thời gian. Song, trong những năm gần đây, mô hình hướng đối tượng cũng đã và đang phát triển theo xu thế của việc đưa khái niệm hướng đối tượng vào trong một số lĩnh vực của khoa học máy tính. Việc áp dụng cách tiếp cận hướng đối tượng vào lĩnh vực CSDL đã tạo khả năng linh hoạt cho mô hình dữ liệu này trong việc mô hình hóa thế giới thực vốn ngày càng phức tạp. Một trong những vấn đề đặt ra đối với CSDL có yếu tố thời gian đó là phụ thuộc hàm theo thời gian (TFD). Phụ thuộc hàm theo thời gian có vai trò quan trọng đối với việc phân tích và thiết kế CSDL có yếu tố thời gian. Phụ thuộc hàm theo thời gian được nghiên cứu lần đầu tiên bởi Wang [12], kết quả nghiên cứu của ông liên quan đến việc thiết kế CSDL có yếu tố thời gian. Sau này đã được các nhà khoa học khác như Jensen, Vianu, Navathe … tiếp tục nghiên cứu và phát triển, đặc biệt đã được Wijsen [15] nghiên cứu trong mô hình hướng đối tượng. Trong luận văn này, mục đích chính của chúng tôi là nhằm 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. Liên quan đến lý thuyết phụ thuộc hàm theo thời gian của Wang, chúng tôi cũng đã đưa ra một số hệ quả và tính chất về mối liên hệ giữa phụ thuộc hàm theo thời gian (TFD) và phụ thuộc hàm (FD) truyền thống. Bên cạnh đó, khi tìm hiểu cách tiếp cận của Wijsen chúng tôi đã so sánh hai quan điểm về lý thuyết phụ thuộc hàm theo thời gian của Wang và Wijsen thông qua việc so sánh hệ 4 tiên đề cho các TFD của Wang và hệ 7 tiên đề cho các TFD của Wijsen. Tổ chức của luận văn Luận văn bao gồm phần mở đầu, ba chương nội dung, phần kết luận, tài liệu tham khảo và phần phụ lục. Các khái niệm cơ sở của luận văn được trình bày trong chương 1. Chương này nhằm giới thiệu khái quát về CSDL có yếu tố thời gian bao gồm: ngữ nghĩa dữ liệu theo thời gian, cách biểu diễn yếu tố thời gian trong CSDL, các phép toán trên thời khoảng, cách biểu diễn các bộ dữ liệu theo thời gian, các phép toán giữa các bộ theo thời gian và các phép toán đại số trong CSDL có yếu tố thời gian. Chương 2 trình bày về lý thuyết chuẩn hoá cơ sở dữ liệu quan hệ theo thời gian theo cách tiếp cận của Wang [12] bao gồm: khái niệm kiểu thời gian và môđun thời gian, cơ sở lý thuyết của phụ thuộc hàm theo thời gian với khái niệm về TFD, hệ tiên đề cho các TFD, bao đóng của tập TFD, khoá của lược đồ môđun thời gian, bao đóng của tập thuộc tính, phủ tối thiểu TFD, lý thuyết chuẩn hóa CSDL quan hệ theo thời gian. Trên cơ sở đó, chúng tôi đưa ra một số tính chất và hệ qủa phản ánh mối quan hệ giữa TFD và FD truyền thống. Chương 3 trình bày về việc mở rộng lý thuyết phụ thuộc hàm theo thời gian trên các đối tượng phức theo cách tiếp cận của Wijsen [15] bao gồm: việc định danh đối tượng, vai trò của việc định danh đối tượng, các mô hình dữ liệu ngữ nghĩa, mô hình thời gian, mô hình dữ liệu hướng đối tượng và sự thể hiện theo thời gian, lý thuyết phụ thuộc hàm theo thời gian trên các đối tượng phức với khái niệm hình thức về TFD và hệ tiên đề cho các TFD. Từ đó, chúng tôi so sánh cách tiếp cận của Wang và Wijsen để thấy rằng: khái niệm kiểu thời gian theo cách tiếp cận của Wijsen là một mở rộng so với cách tiếp cận của Wang. Phần phụ lục trình bày một số chứng minh của các định lý, bổ đề và mệnh đề đã được trình bày trong chương 2 và chương 3. Do thời gian còn hạn chế nên bài luận văn này không thể tránh khỏi những nhầm lẫn và thiếu sót. Rất mong nhận được những ý kiến đóng góp chân thành của qúy thầy cô giáo, bạn bè và những người quan tâm. CHƯƠNG 1 GIỚI THIỆU KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU CÓ YẾU TỐ THỜI GIAN 1.1. Giới thiệu Cơ sở dữ liệu và khai thác dữ liệu là hai vấn đề có thể được xem là quan trọng trong ngành công nghệ thông tin. Với sự ra đời của mô hình dữ liệu quan hệ vào năm 1970 do E. Codd đề xuất, mô hình này sớm được chọn để cài đặt các CSDL. Sở dĩ như vậy là do nó có hỗ trợ các ngôn ngữ khai báo, khá đơn giản nhưng lại có hiệu quả, cùng với các phép toán trên dữ liệu. Với một lượng lớn dữ liệu được lưu trữ ngày càng nhiều nên yếu tố thời gian trong vấn đề lưu trữ dữ liệu luôn là vấn đề được quan tâm đến, dữ liệu cung cấp cho người sử dụng phải có giá trị ở mọi thời điểm khác nhau, cả trong quá khứ, hiện tại và tương lai. Cơ sở dữ liệu có yếu tố thời gian sẽ lưu lại các thông tin liên quan khi các sự kiện thực sự xảy ra hoặc khi các sự kiện được xem là đúng. Trong CSDL có yếu tố thời gian, các sự kiện thường được gắn liền với một thời điểm hoặc với một khoảng thời gian cụ thể nào đó. Trong quá trình lưu trữ dữ liệu, giá trị của một số thuộc tính như Họ tên, Ngày sinh, Phái ... luôn ổn định, thông thường không thay đổi theo thời gian. Trong khi đó, giá trị của một số thuộc tính như Phòng ban, Chức vụ, Bậc lương ... thay đổi theo thời gian. Những thuộc tính có giá trị không thay đổi theo thời gian được gọi là thuộc tính phi thời gian, ngược lại được gọi là những thuộc tính có yếu tố thời gian. Trong chương 1 trình bày một cách khái quát về CSDL có yếu tố thời gian, bao gồm các mục như: mục 1.1 là phần giới thiệu, mục 1.2 trình bày các ngữ nghĩa dữ liệu theo thời gian, vấn đề về cách biểu diễn yếu tố thời gian trong mô hình dữ liệu quan hệ được trình bày trong mục 1.3, mục 1.4 trình bày các phép toán trên thời khoảng, từ những mối quan hệ khác nhau giữa hai thời khoảng trong cùng một quan hệ, chúng có thể dẫn đến các phép toán như phép hợp, phép giao và phép hiệu giữa hai thời khoảng. Mục 1.5 trình bày cách biểu diễn các bộ dữ liệu theo thời gian, mục 1.6 trình bày các phép toán trên các bộ dữ liệu theo thời gian như phép tương đương, phép hợp nhất theo thời gian, phép bao theo thời gian. Các phép toán đại số trong CSDL có yếu tố thời gian được trình bày trong mục 1.7 và cuối cùng là kết luận chương, phần này được trình bày trong mục 1.8. 1.2. Ngữ nghĩa dữ liệu theo thời gian Trong nhiều ứng dụng, yếu tố thời gian được xem là quan trọng đối với CSDL. Chẳng hạn như hệ thống theo dõi sức khỏe bệnh nhân ở bệnh viện, hệ thống đặt vé máy bay tại các phòng bán vé… Cơ sở dữ liệu có yếu tố thời gian sẽ lưu lại các thông tin liên quan khi các sự kiện thực sự xảy ra hoặc khi các sự kiện được xem là đúng. Trong CSDL có yếu tố thời gian, các sự kiện thường được gắn liền với một thời điểm hoặc với một khoảng thời gian cụ thể nào đó, chẳng hạn giáo viên “Lê Hoàng” dạy cho khóa “TINA28” kể từ ngày 06/03/05. Xét về mặt ngữ nghĩa, ta có thể phân yếu tố thời gian trong CSDL thành các dạng thời gian khác nhau tùy từng cách hiểu. Thời gian có thể được gọi là thời gian hợp lệ nếu nó được hiểu như là thời gian mà sự kiện xảy ra hoặc là quãng thời gian mà sự kiện đúng trong thực tế. Thời gian cũng có thể được gọi là thời gian giao dịch nếu nó được hiểu như là thời gian mà khi thông tin thực sự được lưu giữ trong CSDL, thời gian ở đây chính là giá trị của đồng hồ hệ thống khi thông tin được lưu giữ. Chẳng hạn, giả sử CSDL của một hệ thống đặt vé máy bay lưu trữ các thông tin về Họ tên khách hàng, Số CMND, Chuyến bay, Hướng bay, Thời gian xuất phát. Giả sử rằng, tại thời điểm 07:30:00 ngày 01/03/2006, một khách hàng đã cập nhật hệ thống để đặt mua vé máy bay với các thông tin như Họ tên khách hàng: Nguyễn Nam, Số CMND:123456789, Chuyến bay: HS2, Hướng bay: Huế đi TP. Hồ Chí Minh, Thời gian xuất phát: 14:00:00 ngày 05/03/2006. Với CSDL như thế này, xét về mặt ngữ nghĩa thì thời gian hợp lệ chính là thời gian xuất phát của máy bay, tức là vào lúc 14:00:00 ngày 05/03/2006, còn thời gian giao dịch chính là thời gian được tính kể từ lúc khách hàng cập nhật vào hệ thống để đặt mua vé, tức là vào lúc 07:30:00 ngày 01/03/2006. Thời gian hợp lệ và thời gian giao dịch là hai dạng thời gian thông dụng nhất trong CSDL có yếu tố thời gian. Tùy từng ứng dụng cụ thể, ta có thể chỉ cần đến một dạng thời gian nào đó. Song, có một vài ứng dụng lại đòi hỏi phải sử dụng đến cả hai dạng thời gian kể trên. Bên cạnh thời gian hợp lệ và thời gian giao dịch còn có nhiều dạng thời gian khác cũng được xét đến như: thời gian dự kiến, thời gian quyết định… Một dạng thời gian khác thúc đẩy sự nghiên cứu của các nhà khoa học trong nhiều thế kỷ qua và thật khó để có thể mô tả một cách cụ thể và rõ ràng đó chính là thời gian hiện tại (ta ký hiệu là “nay” trong CSDL). Thời gian hiện tại là dạng thời gian không ngừng tăng, toàn bộ các hoạt động thường được đặt ở thời gian hiện tại, thời gian hiện tại tách rời quá khứ và tương lai. Thời gian hiện tại đã mở ra một thách thức mới cho những ai quan tâm đến việc quản lý dữ liệu, mà đặc biệt là với các CSDL có yếu tố thời gian. 1.3. Biểu diễn yếu tố thời gian trong CSDL Ta gọi không gian các thời điểm C là không gian một chiều, liên tục và không âm [0, +¥), trên đó có xác định quan hệ thứ tự “£”. Ta quy ước các ký hiệu như sau: t Î C cho biết t là một thời điểm. a = Í C cho biết là một khoảng thời gian hay còn được gọi là một thời khoảng, với t £ t’. Thời khoảng này có thể được phân loại dựa trên các khoảng đóng hay mở bên trái hoặc bên phải, bao gồm (t, t’); [t, t’]; (t, t’]; [t, t’). Với mô hình quan hệ n ngôi, yếu tố thời gian trong CSDL được biểu diễn bởi một bảng gồm n cột, các cột có tên cột được gọi là thuộc tính của quan hệ. Các chữ cái in hoa ở đầu dãy Alphabeta như A, B, C, ... được dùng để ký hiệu cho tên các thuộc tính. Các chữ cái in hoa ở cuối dãy Alphabeta như U, V, Z, ... được dùng để ký hiệu cho tập các thuộc tính. R được sử dụng để ký hiệu cho lược đồ quan hệ có yếu tố thời gian. r được sử dụng để ký hiệu cho quan hệ hiện hành của lược đồ quan hệ R. Phép ghép được sử dụng thay cho phép hợp. Như vậy, A1A2...An được sử dụng để biểu diễn tập {A1, A2, ...,An}, và với phép hợp của X và Y, thay vì ta viết X È Y thì ta có thể viết XY. Ví dụ 1.1. Xét quan hệ GIÁOVIÊN như sau: Bảng 1.1. Quan hệ GIÁOVIÊN có yếu tố thời gian. GIÁOVIÊN: Mã GV Họ tên Khoá dạy HS lương Thời gian 001 Lê Hoàng KTV36 1.82 [01/03/05, 01/05/05) 002 Nguyễn Huy TINA27 1.82 [02/10/05, 15/10/05] 002 Nguyễn Huy KTV36 1.82 [01/11/05, 30/11/05] 005 Phạm Khoa KTV63 2.30 [05/09/06, nay] Như vậy, từ ví dụ trên, nếu GIÁOVIÊN là một quan hệ có yếu tố thời gian gồm các thuộc tính như: Mã GV, Họ tên, Khoá dạy, Môn dạy, HS lương và Thời gian thì GIÁOVIÊN = (Mã GV, Họ tên, Khoá dạy, Môn dạy, HS lương, Thời gian) được gọi là một lược đồ quan hệ có yếu tố thời gian. 1.4. Các phép toán trên thời khoảng Với a1 và a2 là hai thời khoảng trên C (a1, a2 Î C). Mối quan hệ giữa hai thời khoảng đó có thể đưa về một trong các trường hợp sau: a1 và a2 rời nhau, ký hiệu a1 ¹ a2 a1 và a2 giao nhau, ký hiệu a1 Ç a2 a1 chứa a2, ký hiệu a1 É a2 a1 chứa trong a2, ký hiệu a1 Ì a2 Từ đó, ta có các phép toán trên thời khoảng như sau: Phép giao: a1 Ç a2 = {t Î C | t Î a1 Ù t Î a2} Phép hợp: a1 È a2 = {t Î C | t Î a1 Ú t Î a2} Phép hiệu: a1 \ a2 = {t Î C | t Î a1 Ù t Ï a2} Hai thời khoảng a1 và a2 được gọi là kề nhau, ký hiệu a1 Ñ a2 nếu: a1 = hoặc a1 = 1.5. Biểu diễn các bộ dữ liệu theo thời gian R = (A1, A2, …, An) là một lược đồ quan hệ có yếu tố thời gian, trong đó {A1, A2, …An} là tập các thuộc tính của quan hệ và An là một thuộc tính chỉ thời gian, ta ký hiệu là thuộc tính T. Với mỗi thuộc tính Ai (i = ) tương ứng với miền giá trị của thuộc tính Ai, ký hiệu là dom(Ai). Đặt D = dom(A1) È … È dom(An). Khi đó: Một bộ dữ liệu trên R, ký hiệu t, là một ánh xạ được xác định như sau: t: R D, sao cho t[Ai] Î dom(Ai), i = . Như vậy, ta có thể xem các bộ như là các ánh xạ từ tên các thuộc tính đến các giá trị trong miền thuộc tính. Nếu t là một bộ và X là một tập các thuộc tính, chúng ta có thể dùng t[X] để thay cho các thành phần của t trong tập các thuộc tính của X. Trong ví dụ 1.1, nếu t là một bộ thì t[{Mã GV, Họ tên, Khoá dạy, Môn dạy, HS lương, Thời gian}] là bộ (001, Lê Hoàng, KTV36, Excel, 1.82, [01/03/05, 01/05/05]). 1.6. Các phép toán giữa các bộ theo thời gian Định nghĩa 1.1. (Phép tương đương giữa hai bộ theo thời gian) Cho lược đồ quan hệ R với t1 và t2 là hai bộ trên R. Khi đó, t1 và t2 được gọi là tương đương nhau, ký hiệu t1 » t2, nếu với "X Î (R \ {T}) thì (t1[X] = t2[X]) trong đó T là thuộc tính chỉ thời gian. Nhận xét: + Hai bộ dữ liệu được gọi là tương đương nhau nếu giá trị các thuộc tính của chúng bằng nhau, ngoại trừ thuộc tính chỉ thời gian. + Ngược lại, hai bộ dữ liệu t1 và t2 là không tương đương, ký hiệu t1≉ t2. Ví dụ 1.2. Xét quan hệ GIÁOVIÊN như sau: Bảng 1.2. Phép tương đương giữa hai bộ theo thời gian. GIÁOVIÊN: Mã GV Họ tên Khoá dạy HS lương Thời gian 001 Lê Hoàng KTV36 1.82 [01/03/05, 01/05/05) 002 Nguyễn Huy KTV36 1.82 [01/11/05, 30/11/05] 002 Nguyễn Huy TINA27 1.82 [02/10/05, 15/10/05] 005 Phạm Khoa KTV63 2.30 [05/09/06, nay] 005 Phạm Khoa KTV63 2.30 [01/09/06, 10/09/06] Trong ví dụ 1.2, nếu t1[{Mã GV, Họ tên, Khoá dạy, HS lương, Thời gian}] = (005, Phạm Khoa, KTV63, 2.30, [01/09/06, nay]) và t2[{Mã GV, Họ tên, Khoá dạy, HS lương, Thời gian}] = (005, Phạm Khoa, KTV63, 2.30, [01/09/06, 10/09/06]) ta nói rằng t1 » t2. Như vậy, với các bộ dữ liệu tương đương nhau, nếu ta không xét đến yếu tố thời gian thì chúng hoàn toàn trùng nhau trong một mô hình dữ liệu quan hệ thông thường. Vì quan hệ thực chất là tập các bộ, mà theo lý thuyết tập hợp thì không thể tồn tại hai bộ trùng nhau trong cùng một tập, do đó sự trùng nhau của hai bộ trong cùng một quan hệ sẽ dẫn đến điều không hợp lệ. Chính vì vậy, việc tìm ra một phép toán nhằm đưa toàn bộ các bộ dữ liệu tương đương trong cùng một quan hệ về dạng hợp lệ được xem là vấn đề cần thiết, và phép toán thực hiện được điều này được gọi là phép hợp nhất. Khi đó, một quan hệ không chứa các bộ dữ liệu tương đương nhau được gọi là quan hệ chính tắc. Nói cách khác, một quan hệ có yếu tố thời gian r trên lược đồ R được gọi là chính tắc nếu nó không tồn tại hai bộ phân biệt của r tương đương nhau. Điều này có nghĩa là, r là chính tắc nếu với "t1, t2 Î r mà t1 ≉ t2. Như ta đã biết, nguyên nhân dẫn đến sự trùng lặp dữ liệu giữa các bộ trong cùng một quan hệ đó chính là yếu tố thời gian. Vì vậy, để đưa một quan hệ có yếu tố thời gian về dạng chính tắc ta cần phải thực hiện một phép toán gọi là phép hợp nhất theo chiều thời gian. Định nghĩa 1.2. (Phép hợp nhất theo thời gian) Cho lược đồ quan hệ R với t1 và t2 là hai bộ tương đương nhau trên R. Khi đó, phép hợp nhất của t1 và t2, ký hiệu t1 Å t2 là một bộ m được xác định như sau: m = t1 Å t2 Û (m » t1) Ù (m » t2) Ù (m[T] = t1[T] È t2[T]) Ví dụ 1.3. Xét quan hệ GIÁOVIÊN được cho trong bảng 1.2. Áp dụng phép hợp nhất, ta có thể đưa quan hệ ở bảng 1.2 về dạng chính tắc như sau: Bảng 1.3. Phép hợp nhất theo thời gian. GIÁOVIÊN: Mã GV Họ tên Khoá dạy HS lương Thời gian 001 Lê Hoàng KTV36 1.82 [01/03/05, 01/05/05) 002 Nguyễn Huy TINA27 1.82 [02/10/05, 15/10/05] 002 Nguyễn Huy KTV36 1.82 [01/11/05, 30/11/05] 005 Phạm Khoa KTV63 2.30 [01/09/06, nay] Định nghĩa 1.3. (Quan hệ bao theo thời gian) Cho lược đồ quan hệ R với t1 và t2 là hai bộ tương đương nhau trên R. Khi đó, t1 được gọi là bao theo thời gian t2 trên R, ký hiệu t1 ®T t2, nếu t1 và t2 là hai bộ tương đương nhau trong đó thời khoảng của t1 chứa thời khoảng của t2, hay ta nói cách khác t1[T] Ê t2[T]. Nhận xét: t1 ®T t2 Û t1 = t1 Å t2 Ví dụ 1.4. Xét quan hệ GIÁOVIÊN được cho trong bảng sau: Bảng 1.4. Quan hệ bao theo thời gian. GIÁOVIÊN: Mã GV Họ tên Khoá dạy HS lương Thời gian 001 Lê Hoàng KTV36 1.82 [01/03/05, 01/05/05) 002 Nguyễn Huy TINA27 1.82 [02/10/05, 15/10/05] 002 Nguyễn Huy KTV36 1.82 [01/11/05, 30/11/05] 005 Phạm Khoa KTV63 2.30 [01/09/06, nay] 005 Phạm Khoa KTV63 2.30 [05/09/06, 10/09/06] Trong bảng 1.4, với t1[{Mã GV, Họ tên, Khoá dạy, HS lương, Thời gian}] = (005, Phạm Khoa, KTV63, 2.30, [01/09/06, nay]) và t2[{Mã GV, Họ tên, Khoá dạy, HS lương, Thời gian}] = (005, Phạm Khoa, KTV63, 2.30, [05/09/06, 10/09/06]). Ta có thể nói rằng t1 bao t2 theo thời gian hay t1 ®T t2. Định nghĩa 1.4. (Phần tử theo thời gian) Cho lược đồ quan hệ R với t là một bộ trên R. Khi đó, t là một phần tử theo thời gian của quan hệ r trên R, ký hiệu t ÎT r, nếu $t’Î r sao cho t’ ®T t. Như vậy, một quan hệ có yếu tố thời gian có thể chứa vô số các phần tử, song quan hệ này luôn được biểu diễn bởi một quan hệ chính tắc chứa một số hữu hạn các bộ. 1.7. Các phép toán đại số trong CSDL có yếu tố thời gian Định nghĩa 1.5. (Phép hợp nhất trên một quan hệ) Cho r là một quan hệ trên R. Khi đó, phép hợp nhất theo thời gian của một quan hệ, ký hiệu År, chính là phép hợp nhất giữa các bộ trong cùng một quan hệ, được xác định như sau: År = {t | $t1, t2 ÎT r: t1 » t2, t = t1 Å t2} Nhận xét: Quan hệ År có được bằng cách hợp nhất các bộ trên r tương đương với nhau. Định nghĩa 1.6. (Phép hợp theo thời gian) Cho r1 và r2 là hai quan hệ chính tắc trên R. Khi đó, phép hợp theo thời gian của hai quan hệ r1 và r2 trên R, ký hiệu r1 ÈT r2 là tập các bộ được xác định như sau: r1 ÈT r2 = {t | (t ÎT r1 Ù t ÏT r2) Ú (t ÏT r1 Ù t ÎT r2) Ú ($t1 ÎT r1, $t2 ÎT r2: t1 » t2, t = t1 Å t2)} Định nghĩa 1.7. (Phép hiệu theo thời gian) Cho r1 và r2 là hai quan hệ chính tắc trên R. Khi đó, phép hiệu theo thời gian của hai quan hệ r1 và r2 trên R, ký hiệu r1 \T r2, là tập các bộ được xác định như sau: r1 \T r2 = {t | (t ÎT r1 Ù t ÏT r2) Ú ($t1 ÎT r1, $t2 ÎT r2: t1 » t2, t[T] = t1[T] \ t2[T] )} Ví dụ 1.5. Xét hai quan hệ GV1 và GV2 như sau: Bảng 1.5. Hai quan hệ GV1 và GV2 có yếu tố thời gian. GV1: Mã GV Họ tên Khoá dạy HS lương Thời gian 001 Lê Hoàng KTV36 1.82 [01/03/05, 01/05/05) 002 Nguyễn Huy TINA27 1.82 [02/10/05, 15/10/05] 002 Nguyễn Huy KTV36 1.82 [01/11/05, 15/11/05) 005 Phạm Khoa KTV63 2.30 [01/09/06, 10/09/06] GV2: Mã GV Họ tên Khoá dạy HS lương Thời gian 002 Nguyễn Huy TINA 27 1.82 [05/10/05, 10/10/05] 002 Nguyễn Huy KTV36 1.82 [15/11/05, 30/11/05] 005 Phạm Khoa KTV63 2.30 [06/09/06, nay] Thực hiện phép hợp theo thời gian cho hai quan hệ GV1 và GV2, ta có: Bảng 1.6. Phép hợp theo thời gian của hai quan hệ. GV1 ÈT GV2: Mã GV Họ tên Khoá dạy HS lương Thời gian 001 Lê Hoàng KTV36 1.82 [01/03/05, 01/05/05) 002 Nguyễn Huy TINA27 1.82 [02/10/05, 15/10/05] 002 Nguyễn Huy KTV36 1.82 [01/11/05, 30/11/05] 005 Phạm Khoa KTV63 2.30 [01/09/06, nay] Thực hiện phép hiệu theo thời gian cho hai quan hệ GV1 và GV2, ta có: Bảng 1.7. Phép hiệu theo thời gian của hai quan hệ. GV1 \T GV2: Mã GV Họ tên Khoá dạy HS lương Thời gian 001 Lê Hoàng KTV36 1.82 [01/03/05, 01/05/05) 002 Nguyễn Huy TINA27 1.82 [02/10/05, 05/10/05) È (10/10/05, 15/10/05] 002 Nguyễn Huy KTV36 1.82 [01/11/05, 15/11/05) 005 Phạm Khoa KTV63 2.30 [01/09/06, 06/09/06) Định nghĩa 1.8. (Phép kết nối tự nhiên theo thời gian) Cho r và s là hai quan hệ lần lượt trên R và S. Khi đó, phép kết nối tự nhiên theo thời gian của hai quan hệ r và s, ký hiệu r ⋈T s, và được xác định như sau: r ⋈T s = {t | ($t1 ÎT r : t1 = t[R]) Ù ($t2 ÎT s : t2 = t[S])} Ví dụ 1.6. Xét các quan hệ GV, KD và LUONG như sau: Bảng 1.8. Các quan hệ GV, KD, LUONG có yếu tố thời gian. GV: Mã GV Họ tên Thời gian 001 Lê Hoàng [0, +¥) 002 Nguyễn Huy [0, +¥) 005 Phạm Khoa [0, +¥)  KD: Mã GV Khoá dạy Thời gian 001 KTV36 [01/03/05, 01/05/05) 002 TINA27 [02/10/05, 15/10/05] 002 KTV36 [01/11/05, 30/11/05] 005 KTV63 [01/09/06, nay] LUONG: Mã GV HS lương Thời gian 001 1.82 [01/03/05, 01/04/05) 001 2.06 [01/04/05, 01/05/05) 002 1.82 [02/10/05, 15/10/05] 002 2.06 [01/11/05, 30/11/05] 005 2.30 [01/09/06, nay] Thực hiện phép kết nối tự nhiên cho hai quan hệ GV và KD, ta có: Bảng 1.9. Phép kết nối tự nhiên theo thời gian hai quan hệ GV và KD. GV ⋈T KD: Mã GV Họ tên Khoá dạy Thời gian 001 Lê Hoàng KTV36 [01/03/05, 01/05/05) 002 Nguyễn Huy TINA27 [02/10/05, 15/10/05] 002 Nguyễn Huy KTV36 [01/11/05, 30/11/05] 005 Phạm Khoa KTV63 [01/09/06, nay] Thực hiện phép kết nối tự nhiên các quan hệ GV, KD và LUONG, ta có: Bảng 1.10. Phép kết nối tự nhiên theo thời gian các quan hệ GV, KD, LUONG. GV ⋈T KD ⋈T LUONG: Mã GV Họ tên Khoá dạy HS lương Thời gian 001 Lê Hoàng KTV36 1.82 [01/03/05, 01/04/05) 001 Lê Hoàng KTV36 2.06 [01/04/05, 01/05/05) 002 Nguyễn Huy TINA27 1.82 [02/10/05, 15/10/05] 002 Nguyễn Huy KTV36 2.06 [01/11/05, 30/11/05] 005 Phạm Khoa KTV63 2.30 [01/09/06, nay] Định nghĩa 1.9. (Phép chiếu theo thời gian) Cho r là một quan hệ chính tắc trên R và S Í R. Khi đó, phép chiếu theo thời gian của r trên S, ký hiệu p(r) và được xác định như sau: p(r) = Å{t[S] | t ÎT r} Ví dụ 1.7. Xét quan hệ R = (Mã GV, Họ tên, Khoá dạy, HS lương, Thời gian) và S = (Mã GV, Họ tên, Khoá dạy), với r là một quan hệ chính tắc trên R được cho trong bảng sau: Bảng 1.11. Quan hệ r có yếu tố thời gian. r: Mã GV Họ tên Khoá dạy HS lương Thời gian 001 Lê Hoàng KTV36 1.82 [01/03/05, 01/04/05) 001 Lê Hoàng KTV36 2.06 [01/04/05, 01/05/05) 002 Nguyễn Huy TINA27 1.82 [02/10/05, 15/10/05] 002 Nguyễn Huy KTV36 2.06 [01/11/05, 30/11/05] 005 Phạm Khoa KTV63 2.30 [01/09/06, nay] Thực hiện phép chiếu theo thời gian cho quan hệ r trên S, ta có: Bảng 1.12. Phép chiếu theo thời gian. p(r): Mã GV Họ tên Khoá dạy Thời gian 001 Lê Hoàng KTV36 [01/03/05, 01/05/05) 002 Nguyễn Huy TINA27 [02/10/05, 15/10/05] 002 Nguyễn Huy KTV36 [01/11/05, 30/11/05] 005 Phạm Khoa KTV63 [01/09/06, nay] Định nghĩa 1.10. (Phép chọn theo thời gian) Cho r là một quan hệ chính tắc trên R và P là biểu thức logic mà mỗi bộ của quan hệ r có thể thoả hoặc không. Khi đó, phép chọn theo thời gian của r đối với P là tập các bộ t trên r thoả điều kiện P, ký hiệu s(r), được xác định như sau: s(r) = {t ÎT r | t thoả điều kiện P} Ví dụ 1.8. Xét quan hệ r được cho trong bảng 1.11, với P: “Mã GV = 002”, ta có kết quả như sau: Bảng 1.13. Phép chọn theo thời gian. s(r): Mã GV Họ tên Khoá dạy HS lương Thời gian 002 Nguyễn Huy TINA27 1.82 [02/10/05, 15/10/05] 002 Nguyễn Huy KTV36 2.06 [01/11/05, 30/11/05] 1.8. Kết luận Như vậy, chương 1 của luận văn đã giới thiệu một cách khái quát về CSDL có yếu tố thời gian. Nguyên nhân chính dẫn đến sự trùng lặp, dư thừa dữ liệu giữa các bộ trong cùng một quan hệ chính là yếu tố thời gian. Vì vậy, để đưa một quan hệ về dạng chính tắc ta cần phải thực hiện một phép toán gọi là phép hợp nhất theo thời gian. Trong chương này, chúng tôi đã giới thiệu các phép toán giữa các bộ theo thời gian bao gồm các phép như: phép tương đương, phép bao theo thời gian và phép hợp nhất. Từ các quan hệ chính tắc, chúng tôi đã giới thiệu các phép toán đại số trong CSDL có yếu tố thời gian, bao gồm phép hợp theo thời gian, phép hiệu theo thời gian, phép kết nối tự nhiên theo thời gian, phép chiếu theo thời gian và phép chọn theo thời gian. Như vậy, từ một CSDL với tập các ràng buộc theo thời gian cho trước. Các ràng buộc ở đây là tập các phụ thuộc hàm theo thời gian (TFD) mà chính nó đã gây nên các dư thừa dữ liệu và những dị thường trong khi cập nhật và xóa dữ liệu. Vì vậy, một vấn đề được đặt ra là: làm thế nào để ta có thể xây dựng được các lược đồ mong muốn, khắc phục được những hạn chế kể trên. Vấn đề này sẽ được chúng tôi trình bày trong chương tiếp theo. CHƯƠNG 2 CHUẨN HÓA CƠ SỞ DỮ LIỆU QUAN HỆ THEO THỜI GIAN 2.1. Giới thiệu Việc thiết kế CSDL luôn là vấn đề được nhiều người quan tâm nghiên cứu. Vấn đề này được đặt ra như sau: từ một CSDL cho trước với tập các ràng buộc trên đó, làm thế nào để đưa ra được một cấu trúc phù hợp với những dữ liệu đó. Cũng như CSDL truyền thống, việc thiết kế CSDL có yếu tố thời gian cũng được thực hiện từ một CSDL có yếu tố thời gian với tập các ràng buộc cho trước. Xét quan hệ KHOÁHỌC = (Mã KH, Số ĐVHT, Họ tên GVGD, HS Lương, Số HV, Ngày) được cho ở bảng sau: Bảng 2.1. Quan hệ KHOÁHỌC. KHOÁHỌC: Mã KH Số ĐVHT Họ tên GVGD HS Lương Số HV Ngày TINA27 3 Lê Hoàng 1.82 50 3/3/05 TINA27 3 Lê Hoàng 1.82 45 8/3/05 TINA27 3 Lê Hoàng 2.06 50 5/4/05 TINA27 3 Nguyễn Huy 1.82 50 3/10/05 TINA27 3 Nguyễn Huy 1.82 50 7/10/05 TINA27 3 Nguyễn Huy 1.82 45 17/10/05 Trong đó: Mã KH là mã của mỗi khóa học, Số ĐVHT là số đơn vị học trình của mỗi khóa học, Họ tên GVGD là họ và tên của giáo viên tham gia giảng dạy vào thời điểm đó, HS Lương là hệ số lương của giáo viên tại thời điểm đó, Số HV là số học viên tham gia học trong ngày đó. Quan hệ này nhằm lưu trữ thông tin về mỗi khóa học tại các Ngày khác nhau. Giả sử quan hệ KHOÁHỌC có các ràng buộc sau: Các thuộc tính Mã KH và Ngày tạo thành khóa. Phụ thuộc hàm (FD) Mã KH ® Số ĐVHT phải được thoả mãn. HS Lương của giáo viên giảng dạy không được thay đổi trong một tháng. Giáo viên giảng dạy cho một khóa học không được thay đổi trong một tuần. Rõ ràng, các ràng buộc (3) và (4) không thể được biểu diễn như các phụ thuộc hàm truyền thống. Vậy, một số câu hỏi có thể được đặt ra cho CSDL có yếu tố thời gian như sau: Thế nào là một kiểu thời gian? Thế nào là một môđun thời gian? Làm thế nào để có thể biểu diễn được các ràng buộc theo thời gian bằng các phụ thuộc hàm theo thời gian (TFD)? Từ tập các TFD cho trước, làm thế nào để có thể nhận biết được các TFD hệ quả? Với CSDL có yếu tố thời gian, có nhiều TFD được suy ra từ tập hữu hạn các TFD cho trước. Để giải quyết vấn đề này, chúng ta phải tìm hiểu khái niệm bao đóng hữu hạn cho các TFD, từ đó phát triển hệ tiên đề đúng đắn và đầy đủ để tính bao đóng. Trong CSDL có yếu tố thời gian, thông tin luôn được cập nhật theo thời gian nên dễ dẫn đến việc xuất hiện các dữ liệu dư thừa và dị thường. Chẳng hạn, trong quan hệ KHOÁHỌC, giá trị của thuộc tính Họ tên GVGD được lặp lại nhiều lần trong một tháng, chính sự dư thừa dữ liệu này đã dẫn đến các mâu thuẫn trong cập nhật và những dị thường trong việc chèn và xóa. Trong quá trình cập nhật dữ liệu, nếu ta chỉ cập nhật hệ số lương cho giáo viên giảng dạy trong một bộ mà không cập nhật cho các bộ khác trong cùng một tháng thì sẽ gây nên mâu thuẫn. Trong quá trình chèn và xóa bộ, nếu chưa có buổi học nào được diễn ra thì ta không thể ghi nhận giáo viên giảng dạy cho một khóa học, và nếu ta xóa tất cả các bộ của một khóa học nào đó thì thông tin về họ tên và lương của giáo viên tham gia giảng dạy khóa học đó sẽ bị mất. Việc thiết kế CSDL có yếu tố thời gian phải hướng đến mục đích là tránh được dư thừa dữ liệu và những dị thường của việc chèn và xóa. Vì vậy, để thu được các lược đồ mong muốn nhằm khắc phục được những hạn chế kể trên, trong lý thuyết chuẩn hóa theo thời gian do Wang [12] đề xuất đã giải quyết được vấn đề này. Ngoài việc sử dụng lý thuyết chuẩn hóa, lý thuyết phân tách cũng giúp người thiết kế tạo ra các lược đồ mong muốn. Chẳng hạn, xét quan hệ KHOÁHỌC với các ràng buộc: Số ĐVHT của mỗi khóa học mãi mãi không thay đổi. Số HV trong một khóa học không thay đổi trong 1 ngày. Họ tên GVGD cho mỗi khóa học không được thay đổi trong 1 tuần. HS Lương của GVGD không được thay đổi trong 1 tháng. Từ các ràng buộc đó, để tránh dư thừa dữ liệu ta có thể tách quan hệ KHOÁHỌC thành các quan hệ KH1, KH2, KH3, KH4 như sau: Bảng 2.2. Một phân tách tự nhiên của quan hệ KHOÁHỌC.  KH1: KH2: Họ tên GVGD HS Lương Tháng Lê Hoàng 1.82 3/05 Mã KH Số ĐVHT Lê Hoàng 2.06 4/05 TINA27 3 Nguyễn Huy 1.82 10/05 KH4: KH3: Mã KH Số HV Ngày Mã KH Họ tên GVGD Tuần TINA27 50 3/3/05 TINA27 Lê Hoàng Tuần từ 28/2/05 TINA27 45 8/3/05 TINA27 Lê Hoàng Tuần từ 7/3/05 TINA27 50 5/4/05 TINA27 Lê Hoàng Tuần từ 4/4/05 TINA27 50 3/10/05 TINA27 Nguyễn Huy Tuần từ 2/10/05 TINA27 50 7/10/05 TINA27 Nguyễn Huy Tuần từ 16/10/05 TINA27 45 17/10/05 Trong đó: KH1: lưu thông tin về số đơn vị học trình của mỗi khóa học. KH2:lưu diễn biến về lương của các giáo viên giảng dạy theo từng tháng. KH3:lưu việc phân công giảng dạy của các giáo viên cho mỗi khóa học theo từng tuần. KH4: lưu số học viên trong một buổi học. Với mục đích kể trên, trong chương này trình bày lý thuyết chuẩn hóa CSDL quan hệ theo thời gian thông qua các mục như sau: mục 2.1 là phần giới thiệu, mục 2.2 trình bày về kiểu thời gian và môđun thời gian, một cơ sở lý thuyết của TFD được trình bày trong mục 3.3 với các khái niệm như TFD, hệ tiên đề cho các TFD, bao đóng của tập TFD, bao đóng của tập thuộc tính và vấn đề về phủ tối thiểu TFD; mục 2.4 trình bày lý thuyết chuẩn hóa CSDL quan hệ theo thời gian, mục 2.5 trình bày một số kết quả được đưa ra phản ánh mối quan hệ giữa TFD và FD truyền thống, sau cùng là những kết luận của chương, phần này được trình bày trong mục 2.6. 2.2. Kiểu thời gian và môđun thời gian 2.2.1. Kiểu thời gian Định nghĩa 2.1. (Kiểu thời gian) Với là tập các số thực (tập thời gian tuyệt đối) và * là tập các số nguyên dương (các thời điểm). Khi đó, một kiểu thời gian được ký hiệu bởi t là một ánh xạ được xác định như sau: t: * ® Ã() sao cho với "i, j Î * và i < j, các điều kiện sau phải được thoả mãn: t(i) ¹ Æ và t(j) ¹ Æ suy ra mỗi số thực trong t(i) phải bé hơn mọi số thực trong t(j). Nếu t(i) = Æ suy ra t(j) = Æ. Tức là, nếu giá trị của ánh xạ tại một thời điểm là một tập rỗng thì giá trị của thời điểm tiếp theo cũng là một tập rỗng. Ví dụ 2.1. Chẳng hạn, nếu ta xem mốc thời gian bắt đầu từ ngày 1/1/2005 thì: t = “Ngày”: là một ánh xạ từ * ® sao cho: t(1) = t(1/1/2005) = [0, 1) t(2) = t(2/1/2005) = [1, 2) ... t(7) = t(7/1/2005) = [6, 7) ... t(32) = t(1/2/2005) = [31, 32) t’ = “Tháng”: là một ánh xạ từ * ® sao cho: t’(1) = t’(Tháng 1/2005) = [0, 31) t’(2) = t’(Tháng 2/2005) = [31, 59) Định nghĩa 2.2. (Kiểu con của một kiểu thời gian) Cho hai kiểu thời gian t và t’. Ta nói rằng t’ là một kiểu con của kiểu thời gian t nếu với "i Î*, $j Î * sao cho t’(i) = t(j). Ví dụ 2.2. Cho hai kiểu thời gian Thứ hai và Ngày. Khi đó, Thứ hai là một kiểu con của kiểu Ngày. Định nghĩa 2.3. (Một phân hoạch của kiểu thời gian) Ta nói rằng một tập các kiểu {t1, ..., tn} là một phân hoạch của kiểu t nếu: Mỗi ti, (1 £ i £ n) là một kiểu con của kiểu t, và Với "l Î*, $j Î * sao cho t(l) = tk(j), với k nào đó và 1 £ k £ n Với "j, r Î * và i ¹ k: tk(j) ¹ ti(r) Ví dụ 2.3. Tập các kiểu {Thứ hai, ..., Chủ nhật} là một phân hoạch của kiểu Ngày. Định nghĩa 2.4. (Hợp của hai kiểu thời gian con) Cho t1 và t2 là hai kiểu thời gian con của kiểu thời gian t. Khi đó, hợp của chúng t1 È t2 là một kiểu sao cho: + "i, (t1 È t2)(i) = t1(j1) hoặc (t1 È t2)(i) = t2(j2), với j1, j2 là hai thời điểm nào đó của t1 và t2. + "j1, j2: t1(j1) = (t1 È t2)(i1), và t2(j2) = (t1 È t2)(i2) với i1, i2 là hai thời điểm nào đó của (t1 È t2). Ví dụ 2.4. Cho hai kiểu thời gian Thứ bảy và Chủ nhật. Khi đó Thứ bảy È Chủ nhật là một kiểu Ngày nghỉ và là một kiểu con của kiểu Ngày. 2.2.2. Mối quan hệ trên các kiểu thời gian Định nghĩa 2.5. (Quan hệ bé hơn) Cho t1, t2 là các kiểu thời gian. Khi đó, t1 được gọi là bé hơn t2, ký hiệu t1 ≼ t2 nếu với "iÎ*, $jÎ* sao cho t1(i) Í t2(j), tức là thời điểm j của t2 chứa thời điểm i của t1. Ví dụ 2.5. Với Ngày và Tuần là hai kiểu thời gian thì Ngày ≼ Tuần. Định nghĩa 2.6. (Quan hệ bé hơn thực sự) Cho t1, t2 là các kiểu thời gian. Khi đó, t1 được gọi là bé hơn t2 thực sự, ký hiệu t1 ≺ t2 nếu: t1 ≼ t2 và t1 ¹ t2. Ví dụ 2.6. Cho hai kiểu thời gian Ngày và Tháng. Khi đó, Ngày ≺ Tháng. Nhận xét: + Nếu t1 ≼ t2 và t2 ≼ t1 thì t1 = t2. + Luôn tồn tại một cận trên bé nhất, ký hiệu tTop và cận dưới lớn nhất, ký hiệu tBottom cho tập tất cả các kiểu thời gian. Trong đó: tTop(1) = , tTop(i) = Æ, "i>1 và tBottom(i) = Æ, với i Î*. + Mỗi cặp t1, t2 luôn tồn tại một cận trên bé nhất lub(t1, t2) và một cận dưới lớn nhất glb(t1, t2) đối với quan hệ ≼. Ví dụ 2.7. lub(Tháng, Tuần) = tTop, glb(Tháng, Tuần) = Ngày lub(Tuần, Ngày) = Tuần, glb(Tuần, Ngày) = Ngày Định nghĩa 2.7. (Quan hệ bé hơn toàn bộ) Kiểu thời gian t’được gọi là bé hơn toàn bộ tập các kiểu thời gian {t1,t2,... tn}, ký hiệu t’ ≼ C{t1, t2, ..., tn}, nếu: với "i Î * , $k: 1 £ k £ n và j sao cho t’(i) Í tk(j) Nhận xét: t ≼ t1 suy ra t ≼C{t1, t2} với t2 tùy ý. Ví dụ 2.8. Cho Y1 là kiểu thời gian tương ứng với những năm trước năm 2006, Y2 là kiểu thời gian tương ứng với những năm sau năm 2006, Year là kiểu thời gian tương ứng với hợp của Y1 và Y2. Khi đó, Year ≼C{Y1, Y2}. 2.2.3. Môđun thời gian Định nghĩa 2.8. (Lược đồ môđun thời gian) Một lược đồ môđun thời gian là một cặp (R, t) với R là một lược đồ quan hệ và t là một kiểu thời gian. Định nghĩa 2.9. (Môđun thời gian) Một môđun thời gian là một bộ ba (R, t, f) trong đó (R, t) là một lược đồ môđun thời gian và f là một hàm được gọi là hàm cửa sổ thời gian từ N* (các số nguyên dương biểu diễn các thời điểm) đến 2Tup(R) (biểu diễn tập tất cả các tập con của tập các bộ dữ liệu trên R) sao cho với mỗi i³ 1, thì f(i) = Æ nếu t(i) = Æ. Điều này có nghĩa là: hàm f trong môđun thời gian (R, t, f) là tập các bộ được lưu giữ tại thời điểm i nào đó trong kiểu thời gian t. Ví dụ 2.9. Xét quan hệ KHOÁHỌC được cho trong bảng 2.1, ta có: + Lược đồ môđun thời gian (KHOÁHỌC, Ngày), trong đó: KHOÁHỌC = (Mã KH, Số ĐVHT, Họ tên GVGD, HS Lương, Số HV) + Môđun thời gian là (KHOÁHỌC, Ngày, f ), với: f(3/3/05) = {(TINA27, 3, Lê Hoàng, 1.82, 50)} f(8/3/05) = {(TINA27, 3, Lê Hoàng, 1.82, 45)} f(5/4/05) = {(TINA27, 3, Lê Hoàng, 2.06, 50)} f(3/10/05) = {(TINA27, 3, Nguyễn Huy, 1.82, 50)} f(7/10/05) = {(TINA27, 3, Nguyễn Huy, 1.82, 50)} f(17/10/05) = {(TINA27, 3, Nguyễn Huy, 1.82, 45)} Quy ước: + Các môđun thời gian cũng có thể được ký hiệu bằng M. + Với mỗi môđun thời gian, ta có thể ký hiệu fM là tập tất cả các bộ trên môđun thời gian M, nghĩa là: fM = {T | $i Î *: T Îf(i) } 2.2.4. Các phép toán trên môđun thời gian Định nghĩa 2.10. (Phép nối tự nhiên hai môđun thời gian) Cho M1 = (R1, t, f1) và M2 = (R2, t, f2) là hai môđun cùng kiểu thời gian t. Khi đó, phép nối tự nhiên hai môđun M1 và M2, ký hiệu M1 ⋈T M2 là một môđun thời gian M được xác định như sau: M = (R1 È R2, t, f) Trong đó: với i ³ 1, f(i) = f1(i) ⋈ f2(i), và ⋈ là một phép nối tự nhiên truyền thống. Ví dụ 2.10. Cho M1 = (KH1, Ngày, f1), với: + KH1 = (Mã KH, Số ĐVHT, Số HV) + f1(3/3/05) = {(TINA27, 3, 50)} f1(8/3/05) = {(TINA27, 3, 45)} f1(5/4/05) = {(TINA27, 3, 50)} Cho M2 = (KH2, Ngày, f2), với: + KH2 = (Mã KH, Họ tên GVGD, HS Lương) + f2(3/3/05) = {(TINA27, Lê Hoàng, 1.82)} f2(8/3/05) = {(TINA27, Lê Hoàng, 1.82)} f2(5/4/05) = {(TINA27, Lê Hoàng, 2.06)} Khi đó: M1 ⋈T M2 = (KH, Ngày, f), với: KH = (Mã KH, Số ĐVHT, Số HV, Họ tên GVGD, HS Lương) f(3/3/05) = {(TINA27, 3, 50, Lê Hoàng, 1.82)} f(8/3/05) = {(TINA27, 3, 45, Lê Hoàng, 1.82)} f(5/4/05) = {(TINA27, 3, 50, Lê Hoàng, 2.06)} Định nghĩa 2.11. (Phép chiếu M lên một lược đồ môđun thời gian) Cho M = (R, t, f) và R1 Í R. Khi đó, phép chiếu của M trên R1, ký hiệu là p(M) là một môđun thời gian M’ được xác định như sau: M’ = (R1, t, f1) Trong đó: với mỗi i ³ 0, f1(i) = pR(f(i)), và p là phép chiếu truyền thống. Ví dụ 2.11. Cho M = (KHOÁHỌC, Ngày, f), với: + KHOÁHỌC = (Mã KH, Số ĐVHT, Họ tên GVGD, HS Lương, Số HV) + f(3/3/05) = {(TINA27, 3, Lê Hoàng, 1.82, 50)} f(8/3/05) = {(TINA27, 3, Lê Hoàng, 1.82, 45)} f(5/4/05) = {(TINA27, 3, Lê Hoàng, 2.06, 50)} f(3/10/05) = {(TINA 27, 3, Nguyễn Huy, 1.82, 50)} f(7/10/05) = {(TINA27, 3, Nguyễn Huy, 1.82, 50)} f(17/10/05) = {(TINA27, 3, Nguyễn Huy, 1.82, 45)} Cho KH Í KHOÁHỌC, với KH = (Mã KH, Họ tên GVGD, HS Lương) Khi đó: p(M) = (KH, Ngày, f1), với: + KH = (Mã KH, Họ tên GVGD, Lương) + f(3/3/05) = {(TINA27, Lê Hoàng, 1.82)} f(8/3/05) = {(TINA27, Lê Hoàng, 1.82)} f(5/4/05) = {(TINA27, Lê Hoàng, 2.06)} f(3/10/05) = {(TINA27, Nguyễn Huy, 1.82)} f(7/10/05) = {(TINA27, Nguyễn Huy, 1.82)} f(17/10/05) = {(TINA27, Nguyễn Huy, 1.82)} Định nghĩa 2.12. (Phép hợp các môđun thời gian) Cho Mj = (R, t, fj) với j = là các môđun thời gian trên lược đồ môđun thời gian (R, t). Khi đó, hợp của các môđun thời gian M1 ÈT M2 ÈT , ..., ÈT Mn là một môđun M được xác định bởi: M = (R, t, f) Trong đó, với i ³ 1: f(i) = Ví dụ 2.12. Cho M1 = (KHOÁHỌC, Ngày, f1), với: + KHOÁHỌC = (Mã KH, Số ĐVHT, Họ tên GVGD, HS Lương, Số HV) + f1(3/3/05) = {(TINA27, 3, Lê Hoàng, 1.82, 50)} f1(8/3/05) = {(TINA27, 3, Lê Hoàng, 1.82, 45)} Cho M2 = (KHOÁHỌC, Ngày, f2), với: + f2(5/4/05) = {(TINA27, 3, Lê Hoàng, 2.06, 50)} Khi dó: M1 ÈT M2 = (KHOÁHỌC, Ngày, f) Với f(3/3/05) = {(TINA27, 3, Lê Hoàng, 1.82, 50)} f(8/3/05) = {(TINA27, 3, Lê Hoàng, 1.82, 45)} f(5/4/05) = {(TINA27, 3, Lê Hoàng, 2.06, 50)} Định nghĩa 2.13. (Phép ánh xạ một kiểu thời gian đến một kiểu thời gian bé hơn trên một môđun thời gian) Cho M = (R, t, f) và một kiểu thời gian t’. Khi đó, phép ánh xạ một kiểu thời gian t đến một kiểu thời gian bé hơn t’ trên M sao cho mỗi bộ hợp lệ tại thời điểm i của t cũng hợp lệ tại thời điểm j của t’ thoả t’(j) Í t(i), ký hiệu là Down(M, t’) và được xác định bởi: Down(M, t’) = (R, t’, f’) Trong đó, với i ³ 1: Æ nếu t’(i) = Æ f’(i) = Æ nếu j sao cho t’(i) Í t(j) f(j) nếu ngược lại: t’(i) Í t(j) Ví dụ 2.13. Cho M = (KH, Tháng, f) Với KH = (Mã KH, Họ tên GVGD, HS Lương) f(3/05) = {(TINA27, Lê Hoàng, 1.82)} f(4/05) = {(TINA27, Lê Hoàng, 2.06)} f(10/05) = {(TINA27, Nguyễn Huy, 1.82)} Khi đó, Down(KH, Ngày) = (KH, Ngày, f’) f’(8/3/05) = {(TINA27, Lê Hoàng, 1.82)} f’(5/4/05) = {(TINA27, Lê Hoàng, 2.06)} f’(3/10/05) = {(TINA27, Nguyễn Huy, 1.82)} f’(17/10/05) = {(TINA27, Nguyễn Huy, 1.82)} f’(2/2/05) = Æ Định nghĩa 2.14. (Phép ánh xạ một kiểu thời gian đến một kiểu thời gian lớn hơn trên một môđun thời gian) Cho M = (R, t, f) và một kiểu thời gian t’. Khi đó, phép ánh xạ một kiểu thời gian t đến một kiểu thời gian lớn hơn t’ trên M sao cho mỗi bộ hợp lệ tại thời điểm i của t cũng hợp lệ tại thời điểm j của t’ thoả t(i) Í t’(j), ký hiệu là Up(M, t’) và được xác định bởi: Up(M, t’) = (R, t’, f’) f’(i) = Trong đó, với i ³ 1: nếu $j sao cho t(j) Í t’(i) Æ nếu j sao cho t(j) Í t’(i) Ví dụ 2.14. Cho M = (KH, Ngày, f) Với KH = (Mã KH, Họ tên GVGD, HS Lương) f(8/3/05) = {(TINA27, Lê Hoàng, 1.82)} f(8/3/05) = {(VB36, Trần Lê, 2.06)} f(5/4/05) = {(TINA27, Lê Hoàng, 2.06)} f(3/10/05) = {(TINA27, Nguyễn Huy, 1.82)} f(17/10/05) = {(TINA27, Nguyễn Huy, 1.82)} f(2/2/05) = Æ Khi đó, Up(KH, Tháng) = (KH, Tháng, f’) f’(3/05) = {(TINA27, Lê Hoàng, 1.82)} f’(3/05) = {(VB36, Trần Lê, 2.06)} f’(4/05) = {(TINA27, Lê Hoàng, 2.06)} f’(10/05) = {(TINA27, Nguyễn Huy, 1.82)} f’(2/05) = Æ 2.3. Cơ sở lý thuyết của phụ thuộc hàm theo thời gian 2.3.1. Phụ thuộc hàm theo thời gian (TFD) Thông thường, CSDL truyền thống sử dụng các thông tin “tĩnh”, thông tin được cất giữ trong CSDL chỉ mang tính chất “hiện thời”. Cho lược đồ quan hệ R = (A1,…., An), và X, Y là các tập con của {A1,…., An}. Cho r là một quan hệ trên R. Theo lý thuyết phụ thuộc hàm truyền thống, r được gọi là thoả X xác định Y, ký hiệu X ® Y, nếu với " t1, t2 Î r : t1[X] = t2[X] Þ t1[Y] = t2[Y]. Trong CSDL có yếu tố thời gian, các thông tin được cất giữ mang tính chất “động”, được thay đổi theo thời gian. Vì vậy, ta cần có định nghĩa về TFD như sau: Định nghĩa 2.15. (Phụ thuộc hàm theo thời gian) Cho môđun thời gian M = (R, t, f) và t’ là một kiểu thời gian. Cho X, Y Í R. Khi đó, môđun thời gian M được gọi là thoả TFD X ®t’Y nếu với "t1, t2 ÎfM và i1, i2 Î * sao cho: t1 Î f(i1), và t2 Î f(i2) $j: t(i1) È t(i2) Í t’(j) t1[X] = t2[X] thì t1[Y] = t2[Y]. Nhận xét: + Ta có thể sử dụng t(i1,…, ik) để ký hiệu cho (ij). + Môđun thời gian M = (R, t, f) luôn thoả TFD X ®t’ Y nếu t không có hai thời điểm khác nhau nào chứa trong một thời điểm của t’. Vì nếu t có hai thời điểm khác nhau chứa trong một thời điểm của t’ thì t1 và t2 cùng chỉ một bộ, do đó hiển nhiên t1[Y] = t2[Y]. Ví dụ 2.15. Xét môđun thời gian M = (KHOÁHỌC, ngày, f ), với: KHOÁHỌC = (Mã KH, Số ĐVHT, Họ tên GVGD, HS Lương, Số HV) f(3/3/05) = {(TINA27, 3, Lê Hoàng, 1.82, 50)} f(8/3/05) = {(TINA27, 3, Lê Hoàng, 1.82, 45)} f(5/4/05) = {(TINA27, 3, Lê Hoàng, 2.06, 50)} f(3/10/05) = {(TINA27, 3, Nguyễn Huy, 1.82, 50)} f(7/10/05) = {(TINA27, 3, Nguyễn Huy, 1.82, 50)} f(17/10/05) = {(TINA27, 3, Nguyễn Huy, 1.82, 45)} Rõ ràng, M thoả TFD: Mã KH ®Ngày Số HV Tuy nhiên, M cũng có thể thoả TFD được xác định dưới một kiểu thời gian khác. Chẳng hạn, M cho trong ví dụ 2.15 cũng thoả TFD: Mã KH ®Tuần Họ tên GVGD Và M cho trong ví dụ 2.15 không thoả TFD: Mã KH ®Tháng Số HV Vậy, với M và tập các TFD cho trước, làm thế nào để ta có thể nhận biết được các TFD hệ quả được suy ra từ tập các TFD cho trước đó mà M cũng thoả các TFD hệ quả. Vấn đề này có thể được giải quyết trong mục sau. 2.3.2. Hệ tiên đề cho các TFD Trong ví dụ 2.15, rõ ràng M thoả TFD: Mã KH ®Tuần Họ tên GVGD Xét về mặt ngữ nghĩa, điều này có nghĩa là trong một tuần không thể có hai Họ tên GVGD khác nhau cho một khóa học. Do đó, trong một ngày không thể có hai Họ tên GVGD khác nhau cho một khóa học, điều này có nghĩa là: Mã KH ®Ngày Họ tên GVGD Vậy, M được cho trong ví dụ 2.15 cũng thoả TFD: Mã KH ®Ngày Họ tên GVGD Điều này có được bằng luật suy dẫn sau: Nếu X ®tY và t’ ≼ t thì X ®t’Y 2.3.2.1. Hệ bốn tiên đề cho các TFD Cho mô đun thời gian M = (R, t, f), tập các phụ thuộc hàm theo thời gian F và X, Y, Z Í R. Khi đó, hệ 4 tiên đề cho các TFD được phát biểu như sau: T1 (Luật phản xạ): Nếu Y Í X thì X ®t Y, với "t. T2 (Luật tăng trưởng): Nếu X ®t Y thì XZ ®tYZ. T3 (Luật bắc cầu): Nếu X ®t Y và Y ®t Z thì X ®t Z. T4 (Luật thừa kế): Nếu X ®tY, ..., X ®tY với n ³1, thì X ®t Y với "t ≼C{t1, ..., tn}. Như vậy, nếu M thoả X ®t Y và với "t’ ≼ t thì M thoả X ®t’Y (theo T4) Định nghĩa 2.16. (TFD suy dẫn từ F) Cho M = (R, t, f) là một môđun thời gian, F là tập các TFD và X, Y Í R. Khi đó, một TFD X ®t Y được gọi là suy dẫn từ F, ký hiệu F⊦ X ®t Y, nếu tồn tại dãy hữu hạn các chứng minh f1, ..., fk sao cho: fk là X ®t Y. Mỗi fi là một TFD thuộc F hoặc là một TFD thu được bằng cách sử dụng hệ 4 tiên đề trên đối với các TFD f1, ..., fi-1. Định nghĩa 2.17. (TFD suy dẫn logic từ F) Cho M = (R, t, f) là một môđun thời gian, F là tập các TFD và X, Y Í R. Khi đó, một TFD X ®t Y được gọi là suy dẫn logic từ F, ký hiệu F╞ X ®tY, nếu mọi M thoả mỗi TFD trong F thì M cũng thoả X ®t Y. Bổ đề 2.1. (Tính đúng đắn của hệ tiên đề cho các TFD) Hệ 4 tiên đề cho các TFD là đúng đắn. 2.3.2.2. Các luật được suy ra từ hệ tiên đề cho các TFD T5 (Luật bắc cầu mở rộng): Nếu X ®tY và Y ® t Z thì X ®glb(t, t) Z T6 (Luật hợp): Nếu X ®tY và X ® t Z thì X ®glb(t, t)YZ. Chứng minh. + Vì glb(t1, t2) ≼ t1 và glb(t1, t2) ≼ t2 nên ta có X ®glb(t, t)Y và Y ®glb(t, t)Z Theo luật T3, ta có X ®glb(t, t)Z. Vậy T5 được chứng minh. + Với X ®tY, áp dụng T2 ta có X ®tXY. với X ® t Z, áp dụng T2 ta có XY ® t ZY. Theo luật T5, ta có: X ®®glb(t, t) YZ. Vậy T6 được chứng minh. □ Nhận xét: Với một TFD cho trước, ta có thể tạo ra vô số các TFD khác bằng cách sử dụng T4, vì khi cho trước một kiểu (hay tập các kiểu) thời gian thì sẽ có vô số các kiểu thời gian mà bé hơn toàn bộ kiểu (hay tập các kiểu) thời gian cho trước đó, do đó sẽ có vô số TFD được tạo ra dưới dạng các kiểu thời gian bé hơn này. Ví dụ 2.16. Xét TFD: Mã KH ®Tuần Họ tên GVGD Với Tuầni là kiểu thời gian chỉ chứa tuần thứ i. Rõ ràng, Tuầni ≼ Tuần, do đó Tuầni ≼C{Tuần}, "i ³ 1. Do đó, với T4 ta có: Mã KH ®TuầnHọ tên GVGD, "i ³ 1 Rõ ràng, ta có thể tạo ra vô số các TFD hệ quả từ một TFD cho trước, vấn đề được đặt ra như sau: Có thể có tập các phụ thuộc hàm theo thời gian F’ mà mọi TFD được suy dẫn logic từ F có thể được suy dẫn từ F’ chỉ bằng cách áp dụng T4 mà thôi hay không? Có thể tìm tập F’ một cách hiệu quả hay không? Vấn đề này sẽ được giải quyết bởi hệ ba tiên đề hệ quả hữu hạn được trình bày dưới đây. 2.3.2.3. Hệ ba tiên đề hệ quả hữu hạn cho các TFD Cho mô đun thời gian M = (R, t, f), tập các phụ thuộc hàm theo thời gian F và X, Y, Z Í R. Khi đó, hệ ba tiên đề cho các TFD được phát biểu như sau: T7 (Luật phản xạ giới hạn): Nếu Y Í X thì X ®tY. T8 (Luật tăng trưởng): Nếu X ®tY thì XZ ®t YZ . T9 (Luật bắc cầu mở rộng): Nếu X ®tY và Y ®tZ thì X ®glb(t, t)Z Nhận xét: - Nếu X ®tY được suy dẫn từ F bằng cách sử dụng hệ ba tiên đề hệ quả hữu hạn trên thì ta nói rằng F suy dẫn hữu hạn X ®tY, ký hiệu F├ f X ®tY. - Nếu F├ f X ®tY thì t là cận dưới lớn nhất (glb) của một số các kiểu thời gian nào đó trong F. 2.3.3. Bao đóng của tập phụ thuộc hàm theo thời gian Định nghĩa 2.18. (Bao đóng hữu hạn của tập các TFD) Cho F là tập các TFD. Khi đó, bao đóng hữu hạn của F, ký hiệu F+, là tập tất cả các TFD có thể suy dẫn được từ F bằng cách sử dụng hệ ba tiên đề hệ quả hữu hạn. Nghĩa là: F+ = {X ®tY | F├ f X ®tY } Ví dụ 2.17. Cho F = {A ®tB, A ®t’B} Với A ®tB. Áp dụng T8, ta có A ®tAB Î F+ Với A ®t’B. Áp dụng T8, ta có AB ®t’B Î F+ Áp dụng T9, ta có: A ®glb(t, t’) B Î F+ Định lý 2.1. (Tính chất của hệ ba tiên đề hệ quả hữu hạn cho các TFD) Hệ ba tiên đề hệ quả hữu hạn cho các TFD là đúng đắn và đầy đủ. Nhận xét: + Các tiên đề hệ quả hữu hạn là đúng đắn, vì T7, T8, T9 lần lượt được suy ra từ T1, T2, T3. Mà theo bổ đề 2.1 thì các tiên đề T1, T2, T3 là đúng đắn. + Tính đầy đủ của các tiên đề hệ quả hữu hạn có thể được chứng minh dựa vào tiên đề T4, nghĩa là: nếu F╞ X ®tY thì tồn tại X ®tY, ..., X ®tY Î F+ sao cho t ≼C{t1, ..., tm}. Để chứng minh tính đầy đủ của hệ ba tiên đề hệ quả hữu hạn, ta tìm hiểu phép toán hỗ trợ và hai bổ đề sau: Định nghĩa 2.19. (Phép chiếu tập TFD trên R) Với F là tập các TFD và R là tập các số thực (R Í ). Khi đó, tập phụ thuộc hàm truyền thống có liên quan đến yếu tố thời gian trong tập R, ký hiệu: pR(F) và được xác định như sau: pR(F) = {X ®Y | $X ®tY Î F và $j(R Í t(j))} Ví dụ 2.18. Cho F = {A ®NgàyB, B ®ThángC, A ®NămC}. Khi đó pTháng(F) = {B ®C, A ®C} Như vậy, pÆ (F) là tập tất cả các FD truyền thống tương ứng của tập tất cả các TFD trong F. Bổ đề 2.2. (Mối quan hệ giữa FD và TFD) Cho tập phụ thuộc hàm theo thời gian F và X ®tY là một TFD sao cho F╞ X ®tY. Khi đó, với "i sao cho t(i) ¹ Æ ta có pt(i)(F)╞ X ® Y. Nhận xét: + Gọi G là tập các TFD. Khi đó, G được gọi là một hỗ trợ cho X ® Y nếu pÆ (G)╞ X ®Y. Hỗ trợ đó là cực tiểu nếu không có tập con nào của G là một hỗ trợ cho X ®Y. + Với tập các phụ thuộc hàm theo thời gian G, glb(G) được định nghĩa là kiểu thời gian glb({t | V ®tW Î G}) + glb(G) = tTop nếu G = Æ. Ví dụ 2.19. Cho M = (R, t, f) với G = {A ®tB, B ®t’C}. Khi đó: pÆ(G) = {A ® B, B ® C} là một hỗ trợ cho A ®C Bổ đề 2.3. (Mối quan hệ giữa các kiểu thời gian của một tập TFD với các hỗ trợ cực tiểu của nó ) Cho tập phụ thuộc hàm theo thời gian F. Nếu F1 Í F là một hỗ trợ cực tiểu cho FD X ®Y, thì F├f X ®glb(F)Y. Nếu Fi là tất cả các hỗ trợ cực tiểu cho X ®Y, Fi Í F, (i = ), và F╞ X ®tY thì: t ≼C{t1, ..., tm}, với ti = glb(Fi), (i = ) Lúc này, ta có thể chứng minh tính đầy đủ của các tiên đề hệ quả hữu hạn như sau: Chứng minh. Giả sử F╞ X ®tY. Theo định nghĩa TFD, $i sao cho t(i) ¹ Æ. Theo bổ đề 2.2, ta có: pt(i) (F)╞ X ®Y. Vì pt(i) (F) Î pÆ (F) nên ta có pÆ (F)╞ X ®Y. Vì pÆ (F)╞ X ®Y nên tồn tại ít nhất một hỗ trợ cực tiểu cho X ®Y. Cho F1, ..., Fn là tất cả các hỗ trợ cực tiểu cho X ®Y. Với mỗi i, 1 £ i £ n, cho ti = glb(Fi). Theo bổ đề 2.3, ta có: F├f X ®tY. Vậy, X ®tY Î F+ với 1 £ i £ n.. Cũng theo bổ đề 2.3, ta có thể thấy được rằng t ≼C{t1, ..., tn}. Như vậy, nếu F╞ X ®tY thì tồn tại tập {X ®tY, ..., X ®tY} Í F+ sao cho t ≼C{t1, ..., tm}. Vậy, các tiên đề hệ quả hữu hạn là đầy đủ. □ Định lý 2.2. (Tính chất của hệ bốn tiên đề cho các TFD) Hệ bốn tiên đề cho các TFD là đúng đắn và đầy đủ. Chứng minh. + Tính đúng đắn: được chứng minh ở bổ đề 2.1. + Tính đầy đủ: Cho F là tập các TFD, F╞ X ®tY. Theo định lý 2.1, tồn tại các TFD X ®tY, ..., X ®tY Î F+ sao cho t ≼C{t1, ..., tk}. Theo định nghĩa 2.18, với mỗi 1 £ i £ k ta có F├f X ®tY, do đó F├ X ®tY. Áp dụng T4, ta có: F├ X ®tY. Định lý được chứng minh. □ 2.3.4. Khóa của lược đồ môđun thời gian Định nghĩa 2.20. (Siêu khóa của lược đồ môđun thời gian) 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 (chỉ gồm các thuộc tính trong R). Khi đó, K Í R được gọi là siêu khóa của (R, t) nếu K ®t R được suy dẫn logic từ các TFD trong F. Định nghĩa 2.21. (Khóa của lược đồ môđun thời gian) Cho lược đồ môđun thời gian (R, t); K Í R. Khi đó, K được gọi là khóa của lược đồ môđun thời gian nếu: K là siêu khóa của lược đồ môđun thời gian (R, t). K’ Ì K: K’ là siêu khóa của lược đồ môđun thời gian (R, t) 2.3.5. Bao đóng của tập thuộc tính Cho F là tập các TFD. Để tìm tất cả các TFD được suy ra từ F ta phải tiến hành tìm F+. Với việc làm này thường phải mất rất nhiều thời gian vì thực tế cho thấy rằng tập F+ lớn hơn rất nhiều so với F. Trên thực tế, chúng ta cũng không cần thiết phải tính tất cả các TFD được suy ra từ F mà chỉ cần biết một TFD X ®tY nào đó có được suy ra từ F hay không? Định nghĩa 2.22. (Bao đóng của các thuộc tính) Cho F là tập hữu hạn các TFD và X là tập hữu hạn các thuộc tính. Khi đó, bao đóng của X đối với F, ký hiệu là X+, được xác định như sau: X+ = {(B, t) | X ®tB Î F+ và X ®t’B Î F+: t ≺ t’} Nhận xét: Do F là hữu hạn nên X+ là hữu hạn. Mệnh đề 2.1. Cho F là tập hữu hạn các TFD, X là tập hữu hạn các thuộc tính. Khi đó, F╞ X ®tB nếu và chỉ nếu: ${(B, t1), ..., (B, tm)} Í X+ sao cho t ≼C{t1, ..., tm} Theo mệnh đề 2.1, ta có thể kiểm tra được TFD X ®tB có được suy ra từ F hay không. Điều này có thể thực hiện dễ dàng bằng cách kiểm tra xem (B, t) có thuộc X hay không, mà việc tính X lại không phức tạp lắm, có thể được thực hiện bởi thuật toán sau: Thuật toán 2.1. (Tính bao đóng của các thuộc tính) Vào: + Tập hữu hạn các thuộc tính U. + Tập phụ thuộc hàm theo thời gian F. + X Í U. Ra: X Phương pháp: + Bước 1. X(0) = {(A, tTop) | A Î X} + Bước 2. Lần lượt tính X(i+1) dựa vào X(i) như sau: Với mỗi TFD A1 ... Ak ®t B1 ... Bm Î F sao cho {(A1, t1), ..., (Ak, tk)} Í X(i) ta tính tập {(Bj, t’) | j = ; t’ = glb(t1, ..., tk, t )}. Cho f1, ..., fr là tất cả các TFD trong F thoả điều kiện trên và các tập Y1, ..., Yr là các tập ta tính được tương ứng, khi đó: X(i+1) = X(i) È Y1 È ... È Yr Bước 2 được lặp lại cho đến khi X(i+1) = X(i) Kết quả: X = X(i) \ {(B, t’) Î X(i) | $t’’ (B, t’’) Î X(i) với t’ ≺ t’’} Nhận xét: Vì X = X(0) Í X(1) Í ... Í U và do U là hữu hạn nên thuật toán 2.1 sẽ được dừng lại sau hữu hạn bước thực hiện. Ví dụ 2.20. Cho M = (R, Ngày, f) với R = (A, B, C) F = {A ®Ngày B, B ®Ngày C, B ®ThángC, B ®Tháng A} 1. Với X = AB. Tính X ? Áp dụng thuật toán 2.1, với X = AB ta có: X(0) = {(A, tTop), (B, tTop)} X(1) = X(0) È (B, Ngày) È (C, Ngày) È (C, Tháng) È (A, Tháng) = {(A, tTop); (B, tTop); (B, Ngày); (C, Ngày); (C, Tháng); (A, Tháng)} X(2) = X(1) È (A, Ngày) = {(A, tTop); (B, tTop); (B, Ngày); (C, Ngày); (C, Tháng); (A, Tháng); (A, Ngày)} X(3) = X(2) Vậy, X = {(A, tTop); (B, tTop); (C, Tháng)} 2.3.6. Phủ tối thiểu phụ thuộc hàm theo thời gian Định nghĩa 2.23. (Phủ tối thiểu theo thời gian) Cho F là tập các TFD, và là phủ tối thiểu truyền thống của pÆ(F). Khi đó, G được gọi là một phủ tối thiểu theo thời gian của F nếu: G = {X ®tA | (A, t) Î X+ và X ®A Î } Với định nghĩa 2.23, ta có thể đưa ra thuật toán cho phép tìm phủ tối thiểu của tập TFD. Thuật toán 2.2. (Tìm phủ tối thiểu tập TFD) Vào: + Tập hữu hạn các thuộc tính U. + Tập phụ thuộc hàm theo thời gian F. Ra: G (là một phủ tối thiểu theo thời gian của F) Phương pháp: Bước 1. Tìm phủ tối thiểu truyền thống của pÆ(F) Bước 2. G:= Æ For mỗi X ®A Î Do For mỗi (A, t) Î X Do G:= G È {X ®tA} Ví dụ 2.21. Cho U = (A, B, C) Với F = {A®NgàyB, B ®NgàyC, B®ThángC, A®NgàyC} Tìm G là một phủ tối thiểu của F? Bước 1. Ta có: pÆ(F) = {A ®B, B®C, A®C} = {A®B, B®C} Bước 2. Kiểm tra: Với A ® B Î ta xét: A = {(A, tTop); (B, Ngày); (C, Ngày)}. Vì (B, Ngày) Î A nên G = {A ®NgàyB} Với B ® C Î ta xét: B = {(B, tTop); (C, Tháng)}. Vì (C, Tháng) Î B nên G = {A ®NgàyB; B ®ThángC} Vậy, phủ tối thiểu của F là: G = {A ®NgàyB, B ®ThángC} 2.4. Chuẩn hóa lược đồ quan hệ theo thời gian Tương tự như CSDL truyền thống, hầu hết các lược đồ quan hệ trong CSDL có yếu tố thời gian bước đầu thường được xây dựng dựa trên kinh nghiệm của người thiết kế và không có một quy tắc hình thức nào, do đó sẽ có một số lược đồ được tạo ra không thích hợp với bài toán, có thể xuất hiện các dư thừa dữ liệu và những dị thường khi cập nhật dữ liệu. Lý thuyết chuẩn hóa cho phép người thiết kế thu được những lược đồ mong muốn, khắc phục được những hạn chế kể trên. Định nghĩa 2.24. (Phép chiếu tập TFD lên tập thuộc tính) Cho M = (R, t,f) với F là tập các TFD, và Z Í R . Khi đó, phép chiếu tập phụ thuộc hàm theo thời gian F lên tập thuộc tính Z, ký hiệu pZ(F) là tập các TFD được xác định như sau: pZ(F) = {X ®t Y | F ╞ X ®tY , XY Í Z} Nhận xét: + pZ(F) có thể là vô hạn do có vô số các TFD được suy dẫn logic từ tập F cho trước, hay có nhiều X ®t Y Î F+. + Vì ta biết cách tính bao đóng của tập thuộc tính nên ta có thể tính một “phủ hữu hạn” của phép chiếu F lên Z như sau: Z(F) = {X ®tA1 ... Am | XA1...Am Í Z và (Ai, t) Î X+ với 1 £ i £ m} Rõ ràng Z(F) hữu hạn do X là hữu hạn. Với tính đầy đủ của ba tiên đề hệ quả hữu hạn và định nghĩa F+, rõ ràng Z(F) là một “phủ hữu hạn” của pZ(F). Mệnh đề 2.2. pZ(F) = {X ®t’A1 ... Am | X ®tAi Î Z(F) với 1 ≤ i ≤ m và t’ ≼C{t1, ..., tm}} Nhận xét: pZ(F) bao gồm các TFD tầm thường và các TFD không tầm thường (là TFD mà vế phải không là con của vế trái). Vì vậy, việc xác định Fi (i = ) có thể dựa vào việc xác định phủ tối thiểu của pZ(F), theo thuật toán sau: Thuật toán 2.3. (Chiếu tập TFD lên tập thuộc tính) Vào: + Lược đồ môđun thời gian (R, t) và + Tập các phụ thuộc hàm theo thời gian F Ra: Z(F) Phương pháp: + Bước1. Lần lượt tính các bao đóng của các tậ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át ta giả sử t1 ≼ t2 và F là tập các TFD. Khi đó, nếu X ®tY và Y ®tZ thì X ®tZ Chứng minh. Theo T9, nếu X ®tY và Y ®tZ thì X ®glb(t, t) Z. Mặt khác, vì t1 ≼ t2 nên glb(t1, t2) = t1. Vậy X ®tZ. □ Hệ quả 2.3. (Một trường hợp đặc biệt của thuật toán phân tách T3NF sử dụng phương pháp phân tách thành 3NF truyền thống) Gọi T là tập các kiểu thời gian có trong các TFD của 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. Khi đó, ta có thể xây dựng thuật toán sau: Vào: + Lược đồ môđun thời gian (R, t) và + Tập các phụ thuộc hàm theo thời gian F, sao cho t là cận dưới lớn nhất của các kiểu thời gian có trong F mà thuộc T. Ra: r = {(R1, t1), ..., (Rn, tn)} bảo toàn thông tin và bảo toàn phụ thuộc hàm, sao cho (Ri, ti) Î T3NF, i = Phương pháp: Giả sử T = {t1, t2, …, tn} sao cho t1< t2 < …< tn. Bước 1. Khởi tạo tập F’ F’ = Æ For mỗi ti < tj Do F’ = F’ È {ti ® tj} Bước 2. Khởi tạo lược đồ R’ R’ = R For mỗi ti Î T Do R’ = R’ È {ti} Bước 3. Tạo lược đồ quan hệ R’ và tập phụ thuộc hàm theo thời gian F’ For mỗi X ®t’Y Î F Do Begin R’ = R’ È {t’} F’ = F’ È {t’X ® Y} End Bước 4. Phân tách R’ thành 3NF: Với tập các phụ thuộc hàm F’ mà loại trừ các FD có giá trị các thuộc tính ở vế trái và vế phải là những thuộc tính chỉ thời gian, ta thực hiện việc tách R’ thành 3NF: r’ = {R’1, ..., R’k) với R’i Î 3NF (i = ), r’ bảo toàn thông tin và bảo toàn phụ thuộc hàm. Bước 5. Xây dựng r từ r’: Với mỗi lược đồ con thuộc r’, sử dụng tính chất 2.1 ta có thể xây dựng r từ r’. Khi đó: r = {(R1, t1), ..., (Rk, tk)}với (Ri, ti) Î T3NF (i = ), r bảo toàn thông tin và bảo toàn phụ thuộc hàm. Ví dụ 2.33. Xét lược đồ môđun thời gian (R, Ngày) với: R = (Mã KH, Họ tên GVGD, HS lương, Số HV) F = { Mã KH ®NgàySố HV; Mã KH ®Tháng Họ tên GVGD Họ tên GVGD ®NămHS lương} Áp dụng hệ quả 2.3, ta có: B1. Khởi tạo F’: F’ = {Ngày ® Tháng, Ngày ® Năm, Tháng ® Năm} B2. Khởi tạo R’: R’ = (Mã KH, Họ tên GVGD, HS lương, Số HV, Ngày, Tháng, Năm) B3. Khởi tạo (R’, F’): R’ = (Mã KH, Họ tên GVGD, HS lương, Số HV, Ngày, Tháng, Năm) F’ = {Ngày, Mã KH ® Số HV; Tháng, Mã KH ® Họ tên GVGD; Năm, Họ tên GVGD ® HS lương Ngày ® Tháng, Ngày ® Năm, Tháng ® Năm} B4. Tách R’ thành 3NF bảo toàn thông tin và bảo toàn phụ thuộc hàm: Với (R’, F’) được cho như ở B3. Ta có: + Phủ tối thiểu của F’ là: F’ = {Ngày, Mã KH ® Số HV; Tháng, Mã KH ® Họ tên GVGD; Năm, Họ tên GVGD ® HS lương Ngày ® Tháng, Ngày ® Năm, Tháng ® Năm} + Khoá của R’ là: K = {Mã KH, Ngày} R’0 = (U’0, F’0) với U’0 = (Mã KH, Ngày) và F0 = Æ. R’1 = (; {Ngày, Mã KH ® Số HV}) R’2 = (; {Tháng, Mã KH ® Họ tên GVGD}) R’3 = (; {Năm, Họ tên GVGD ® HS lương}) Vì U’0 Í U1 nên loại R0 ra khỏi phép tách. Vậy, r’ = ({Ngày, Mã KH, Số HV}; {Tháng, Mã KH, Họ tên GVGD}; {Năm, Họ tên GVGD, HS lương}) B5. Xây dựng r từ r’: r’ = {(; Ngày); (; Tháng); (; Năm)} Ví dụ 2.34. Xét (R, Ngày) với: R = (Mã KH, Họ tên GVGD, HS lương, Số HV) F = { Mã KH ®NgàySố HV; Mã KH ®Tuần Họ tên GVGD Họ tên GVGD ®ThángHS lương} Vì quan hệ ≼ giữa các kiểu thời gian Ngày, Tuần, Tháng không phải là quan hệ thứ tự toàn phần. Do đó, với ví dụ 2.34 thì hệ quả 2.3 không thể áp dụng được. Như vậy, nếu gọi T là tập các kiểu thời gian có trong các TFD của F mà quan hệ ≼ giữa các kiểu thời gian trên T không là quan hệ thứ tự toàn phần (như trong trường hợp ở ví dụ 2.34) thì hệ quả 2.3 sẽ như thế nào. Đây được xem như là một hướng mở, có thể tiếp tục nghiên cứu sau này. 2.6. Kết luận Chương này đã trình bày lý thuyết chuẩn hoá CSDL quan hệ theo thời gian bao gồm: khái niệm kiểu thời gian, mô đun thời gian; các phép toán trên các kiểu thời gian và môđun thời gian; khái niệm TFD, hệ tiên đề cho các TFD; các khái niệm về bao đóng và phủ tối thiểu nhằm hỗ trợ cho lý thuyết chuẩn hoá. Kết quả thu được từ nghiên cứu này là: Xây dựng thuật toán tìm phủ tối thiểu tập phụ thuộc hàm theo thời gian dựa trên định nghĩa 2.23 của Wang [12] Xây dựng thuật toán tìm chiếu tập TFD lên tập thuộc tính cho trước dựa trên định nghĩa 2.24 và mệnh đề 2.2 của Wang [12]. Xây dựng một số các tính chất và hệ quả phản ánh mối liên hệ giữa TFD và FD truyền thống. Lý thuyết phụ thuộc hàm theo thời gian được trình bày trong chương này hoàn toàn được xây dựng trên lược đồ quan hệ. Một vấn đề được đặt ra là: cách biểu diễn các phụ thuộc hàm theo thời gian bởi kiểu thời gian mà Wang đã định nghĩa trong chương 2 đã phản ánh một cách đầy đủ các ngữ nghĩa của thế giới thực hay chưa? Trên thực tế, giả sử một thư viện yêu cầu rằng các cuốn sách cho đọc giả mượn phải được trả trong vòng 1 tuần. Ở đây, “một tuần” có nghĩa là một khoảng thời gian bảy ngày và có thể bắt đầu từ bất kỳ ngày nào trong tuần. Rõ ràng, với kiểu thời gian theo cách tiếp cận của Wang [12] là hoàn toàn không thể biểu diễn được. Vì vậy, trong chương tiếp theo, chúng tôi tiếp tục tìm hiểu một cách tiếp cận khác của Wijsen, cho phép mở rộng kiểu thời gian ở chương 2 để biểu diễn các TFD trên mô hình dữ liệu hướng đối tượng. CHƯƠNG 3 PHỤ THUỘC HÀM THEO THỜI GIAN TRÊN CÁC ĐỐI TƯỢNG PHỨC 3.1. Giới thiệu Mặc dù ngay từ khi mới ra đời, nhờ đặc tính đơn giản và hiệu quả, cùng với các phép toán đại số quan hệ, rất thuận lợi cho việc mô tả các phép toán trên thời khoảng nên mô hình quan hệ đã sớm được chọn để cài đặt cơ sở dữ liệu có yếu tố thời gian. Tuy vậy, trong những năm gần đây, mô hình hướng đối tượng cũng đã và đang phát triển theo xu thế ngày càng mở rộng việc ứng dụng các khái niệm hướng đối tượng vào một số lĩnh vực của tin học nói chung và khoa học máy tính nói riêng. Chính điều này đã góp phần giúp mô hình dữ liệu này tạo ra những khả năng linh hoạt trong việc mô hình hóa thế giới thực, vốn ngày càng phức tạp. Như ta đã biết, thực chất CSDL có yếu tố thời gian là một mở rộng của CSDL truyền thống, cho phép lưu trữ và cập nhật thông tin một cách đầy đủ và chính xác theo thời gian. Với mô hình dữ liệu hướng đối tượng, đặc điểm chung của chúng là có hỗ trợ: Đặc tính định danh đối tượng (Object Identity - OID): là khả năng hệ thống phân biệt được hai đối tượng trông có vẻ giống nhau theo nghĩa tất cả các cấu thành của các kiểu cơ bản dều như nhau. Các đối tượng phức (Complex Objects): là khả năng định nghĩa các kiểu dữ liệu mới có cấu trúc lồng nhau bằng phương pháp tạo lập mẫu tin hay tạo lập tập hợp. Phân cấp theo kiểu: là khả năng cho phép các kiểu có thể có những kiểu con và có thuộc tính riêng. Chính vì những đặc điểm đó nên mô hình dữ liệu hướng đối tượng có vai trò quan trọng đối với các CSDL có yếu tố thời gian. Chương này trình bày về việc mở rộng lý thuyết phụ thuộc hàm theo thời gian trên các đối tượng phức. Việc tìm hiểu TFD trong chương này có một vài điểm khác so với các TFD trong chương hai, đặc biệt chương này có giới thiệu một mô hình thời gian tổng quát hơn và có bổ sung các đối tượng phức vào trong mô hình dữ liệu. Mô hình dữ liệu ở đây bao gồm các lớp và các đối tượng, nó tổng quát hơn so với mô hình quan hệ theo nghĩa: giá trị của một thuộc tính không chỉ là một kiểu nguyên tố mà còn tham chiếu đến một đối tượng của lớp khác và các đối tượng mà có các tham chiếu đến các đối tượng khác được gọi là các đối tượng phức, nó cho phép tạo ra các lược đồ có chu trình. Chương này trình bày các mục như: mục 3.1 là phần giới thiệu, mục 3.2 trình bày vấn đề định danh đối tượng, mục 3.3 trình bày mô hình dữ liệu hướng đối tượng theo thời gian, vấn đề về phụ thuộc hàm theo thời gian trên các đối tượng phức được trình bày ở mục 3.4; mục 3.5 trình bày các tính chất của phụ thuộc hàm theo thời gian trên đối tượng phức và sau cùng là phần kết luận chương, được trình bày trong mục 3.6. 3.2. Định danh đối tượng Trong phần này, chúng ta sẽ tiến hành tìm hiểu tại sao việc định danh đối tượng lại có vai trò quan trọng đối với các CSDL có yếu tố thời gian nói chung và đối với các ràng buộc trên các CSDL có yếu tố thời gian nói riêng, mà chúng ta thường gọi là các ràng buộc theo thời gian, và các ràng buộc theo thời gian được nhắc đến trong chương này lại chính là các TFD. Từ đó, chúng ta có thể rút ra kết luận về khả năng ứng dụng của việc kết hợp giữa việc định danh đối tượng với các TFD. Trước hết, ta sẽ tìm hiểu vai trò của việc định danh đối tượng. 3.2.1. Vai trò của việc định danh đối tượng Với CSDL có yếu tố thời gian, việc định danh đối tượng là hết sức quan trọng. Sở dĩ như vậy là do việc định danh đối tượng cho phép chúng ta nhận biết ra các đối tượng mà bất chấp cả thời gian. Chính điều này đã tạo điều kiện thuận lợi cho việc biểu diễn các ràng buộc có liên quan đến diễn biến dữ liệu của đối tượng, đồng thời cũng thuận lợi cho việc xây dựng cấu trúc trên các đối tượng phức. Ví dụ 3.1. Trên quan hệ GV, xét lược đồ quan hệ GV = (Họ tên, Khoá dạy, HS lương, TG) cho phép lưu trữ thông tin về giáo viên tham gia giảng dạy cho mỗi khoá học tại các thời điểm khác nhau, trong đó Họ tên, Khoá dạy, HS lương là các thuộc tính do người dùng định nghĩa, và TG là một thuộc tính chỉ thời gian với TG = , t1 £ t2. Khi đó, một bộ dữ liệu t với {Họ tên: X, Khoá dạy: Y, HS lương: Z, TG: [t1, t2]} có nghĩa là trong khoảng thời gian từ t1 đến t2, giáo viên X đã dạy cho khoá Y với hệ số lương là Z. Trên quan hệ GV, xét các ràng buộc: C1. Tại bất kỳ một thời điểm nào, các giáo viên được xác định duy nhất bởi họ tên của giáo viên, dạy cho một khoá học và nhận được một khoản tiền lương. Nghĩa là, Họ tên được xem như là khoá chính của quan hệ tại các thời điểm. C2. Một giáo viên không thể thay đổi khoá dạy trong cùng một tuần. C3. Một giáo viên không thể có hai hệ số lương khác nhau trong cùng một tháng. Với lý thuyết phụ thuộc hàm theo thời gian được giới thiệu trong chương hai, các ràng buộc C2, C3 có thể được biểu diễn bởi các TFD sau: TFD1. Họ tên ®TuầnKhoá dạy TFD2. Họ tên ®ThángHS lương Xét về mặt ngữ nghĩa, ta có thể nhận thấy rằng: trong khoảng thời gian TG = là 1 tuần hoặc 1 tháng, nếu bộ dữ liệu {Họ tên: X, Khoá dạy: Y, HS lương: Z} là giá trị của quan hệ GV tại thời điểm t1 và một bộ khác {Họ tên: X, Khoá dạy: Y’, HS lương: Z’} là giá trị của quan hệ GV tại thời điểm t2 thì khi đó, theo TFD1: Y = Y’ và theo TFD2: Z = Z’. Trong quan hệ GV, nếu ta giả thiết rằng thuộc tính Họ tên có thể được sử dụng để nhận biết các giáo viên tại các thời điểm khác nhau. Điều này có nghĩa là, các bộ dữ liệu của quan hệ GV mà có cùng Họ tên thì mô tả thông tin của cùng một giáo viên tại các thời điểm khác nhau, các bộ dữ liệu mà không cùng Họ tên thì mô tả các giáo viên khác nhau. Ngược lại, nếu giả thiết này không được chấp nhận vì một lý do nào đó thì không có cách nào để có thể nhận biết được các giáo viên một cách nhất quán, và khi đó các ràng buộc C2, C3 không thể được sử dụng cho quan hệ GV. Thực tế cho ta thấy rằng, trong quan hệ GV, mặc dù giá trị của thuộc tính Họ tên thường không thay đổi theo thời gian. Song, khả năng một giáo viên nào đó có cùng họ tên vào dạy cho một khoá học nào đó là điều hoàn toàn có thể xảy ra. Do đó, việc sử dụng thuộc tính Họ tên như là khoá bất biến theo thời gian để xác định đối tượng là không phù hợp trong nhiều ứng dụng. Chẳng hạn, ta xét một bảng mô tả quan hệ GV được nhóm theo thời gian như sau: Bảng 3.1. Quan hệ GV được nhóm theo thời gian. GV: Họ tên Khoá dạy HS lương Lê Hoàng [01/03/05, 03/03/05] Lê Hoàng A [04/03/05, 01/05/05) KTV36 [01/03/05, 01/05/05) 1.82 [01/03/05, 01/04/05) 2.06 [01/04/05, 01/05/05) Nguyễn Huy [02/10/05, 15/10/05] TINA27 [02/10/05, 15/10/05] 1.82 [02/10/05, 15/10/05] Lê Hoàng [04/03/05, 31/03/05] KTV37 [04/03/05, 05/03/05] TINA28 [06/03/05, 31/03/05] 2.30 [04/03/05, 31/03/05] Như vậy, toàn bộ thông tin của mỗi giáo viên được nhóm thành một bộ dữ liệu không theo 1NF. Quan hệ GV trong bảng 3.1. lưu trữ thông tin của ba giáo viên. Một giáo viên có họ tên là “Lê Hoàng”, họ tên của giáo viên đó được đổi thành “Lê Hoàng A” vào ngày 04/03/05 khi một giáo viên mới có cùng tên chuyển đến trung tâm để tham gia giảng dạy cho khoá học KTV37. Do thuộc tính Họ tên được xem như là khoá bất biến theo thời gian nên tại bất kỳ thời điểm nào cũng không thể có hai giáo viên có họ tên trùng nhau. Vậy, các ràng buộc C2, C3 có được thoả mãn không? Giả thiết rằng tuần đầu tiên của tháng 3 rơi đúng vào ngày 01/03/05. Khi đó, nếu với bộ dữ liệu t1 là {Họ tên: Lê Hoàng, Khoá dạy: KTV36, HS lương: 1.82} lưu trữ thông tin của giáo viên tại thời điểm 03/03/05, và bộ dữ liệu t2 là {Họ tên: Lê Hoàng, Khoá dạy: KTV37, HS lương: 2.30} lưu trữ thông tin của giáo viên tại thời điểm 04/03/05 thì khi đó, xét về mặt ngữ nghĩa cả TFD1 và TFD2 đều bị vi phạm. Trong bảng 3.1, rõ ràng C3 được thoả mãn do không có giáo viên nào có đến hai hệ số lương khác nhau trong 1 tháng. Với ràng buộc C2, do giáo viên “Lê Hoàng” dạy cho khoá “KTV37” ở thời điểm 05/03/05 và đã chuyển sang dạy cho khoá “TINA28” vào thời điểm 06/03/05, như vậy là trong 1 tuần, giáo viên này đã thay đổi khoá dạy, điều này có nghĩa là ràng buộc C2 không thoả mãn. Tuy nhiên, C2 cũng có thể được thoả mãn khi ta xem “KTV37” và “TINA28” là hai khoá dạy riêng biệt. Vì vậy, C2 được thoả mãn hay không còn tùy thuộc vào quan hệ KD hay KD’. Bảng 3.2. Hai quan hệ “Khoá dạy”. KD: KD’: Tên khoá dạy Tên khoá dạy KTV36 [01/03/05, 01/05/05] KTV36 [01/03/05, 01/05/05] TINA27 [02/10/05, 15/10/05] TINA27 [02/10/05, 15/10/05] KTV37 [04/03/05, 05/03/05] KTV37 [04/03/05, 05/03/05] TINA28 [06/03/05, 31/03/05] TINA28 [06/03/05, 31/03/05] Như vậy, việc kiểm tra C2 có thể kéo theo việc kiểm tra các quan hệ “Khoá dạy” khác nhau. Chẳng hạn, để trả lời câu hỏi “Với mỗi giáo viên, hãy cho biết danh sách các khoá dạy mà anh/ chị đã từng tham gia giảng dạy?”, rõ ràng sẽ không đầy đủ nếu ta chỉ sử dụng quan hệ GV. Trong trường hợp này có thể dẫn đến sự nhầm lẫn và rắc rối. Sở dĩ như vậy là vì mặc dù các mô hình dữ liệu đã được nhóm theo thời gian nhưng các tham chiếu đến bộ dữ liệu đó vẫn phải dựa vào giá trị khoá, mà ở đây khoá lại không duy nhất theo thời gian. Điều này đã mở ra một thách thức mới, thúc đẩy các nhà nghiên cứu CSDL phải tìm ra một phương pháp mới có thể khắc phục được hạn chế kể trên. Một trong những phương pháp mới có thể khắc phục được những khó khăn liên quan đến các tham chiếu dựa vào giá trị của các quan hệ theo thời gian, đó là phương pháp định danh nhóm hoặc định danh đối tượng theo thời gian. Bảng 3.3 Các quan hệ được nhóm theo thời gian với các OID. GV_O: l Họ tên Khoá dạy HS lương Oid1 [01/03/05, 01/05/05) Lê Hoàng [01/03/05, 03/03/05] Lê Hoàng A [04/03/05, 01/05/05) Oid4 [01/03/05, 01/05/05] 1.82 [01/03/05, 01/04/05) 2.06 [01/04/05, 01/05/05) Oid2 [02/10/05, 15/10/05] Nguyễn Huy [02/10/05, 15/10/05] Oid5 [02/10/05, 15/10/05] 1.82 [02/10/05, 15/10/05] Oid3 [04/03/05, 31/03/05] Lê Hoàng [04/03/05, 31/03/05] Oid6 [04/03/05, 31/03/05] 2.30 [04/03/05, 31/03/05] KD_O: l Tên khoá dạy Oid4 [01/03/05, 01/05/05] KTV36 [01/03/05, 01/05/05] Oid5 [02/10/05, 15/10/05] TINA27 [02/10/05, 15/10/05] Oid6 [04/03/05, 31/03/05] KTV37 [04/03/05, 05/03/05] TINA28 [06/03/05, 31/03/05] Bảng 3.3 mô tả các quan hệ được nhóm theo thời gian sử dụng phương pháp định danh đối tượng để xác định các bộ dữ liệu. Trong toàn bộ chương này, ký hiệu l được sử dụng như một thuộc tính đặc biệt biểu thị cho việc định danh đối tượng. Như vậy, việc định danh đối tượng có một vài điểm thuận lợi sau: Thuộc tính l có thể được sử dụng để định danh một cách chính xác các đối tượng mà bất chấp cả thời gian. Ví dụ 3.2. Thuộc tính l cho phép biểu diễn các ràng buộc C2 và C3 như sau: TFD3. l ®TuầnKhoá dạy TFD4. l ®ThángHS lương Việc định danh đối tượng cho phép một đối tượng có thể tham chiếu đến các đối tượng khác qua các OID. Những đối tượng tham chiếu đến các đối tượng khác được gọi là các đối tượng phức. Ví dụ 3.3. Quan hệ GV_O tham chiếu đến các khoá dạy bởi OID. Do đó, để kiểm tra ràng buộc C2 thì ta không cần phải kiểm tra quan hệ KD_O. Từ quan hệ GV_O, rõ ràng “Lê Hoàng” chỉ tham gia một khoá dạy. Việc định danh đối tượng cho phép chuyển đổi giữa các quan hệ được nhóm theo thời gian với các quan hệ không được nhóm theo thời gian mà không mất thông tin. Ví dụ 3.4. Từ các quan hệ được nhóm theo thời gian cho trong bảng 3.3, ta có thể chuyển thành các quan hệ không được nhóm theo thời gian như bảng sau: Bảng 3.4. Các quan hệ không được nhóm theo thời gian với các OID. GV_O: l Họ tên Khoá dạy HS lương Thời gian Oid1 Oid1 Oid1 Oid2 Oid3 Lê Hoàng Lê Hoàng A Lê Hoàng A Nguyễn Huy Lê Hoàng Oid4 Oid4 Oid4 Oid5 Oid6 1.82 1.82 2.06 1.82 2.30 [01/03/05, 03/03/05] [04/03/05, 01/04/05) [01/04/05, 01/05/05) [02/10/05, 15/10/05] [04/03/05, 31/03/05] KD_O: l Khoá dạy Thời gian Oid4 Oid5 Oid6 Oid6 KTV36 TINA27 KTV37 TINA28 [01/03/05, 01/05/05] [02/10/05, 15/10/05] [04/03/05, 05/03/05] [06/03/05, 31/03/05] Ta có thể nhận thấy rằng, quan hệ GV_O trong bảng 3.3 sau khi được tách thành một quan hệ không được nhóm theo thời gian như trong bảng 3.4 sẽ xuất hiện một số dữ liệu dư thừa, chúng được tạo ra vào thời điểm 04/03/05 khi một giáo viên mới Oid3 tham gia giảng dạy có họ tên trùng với họ tên của giáo viên Oid1 buộc Oid1 phải thay đổi họ tên. Ta cũng lại nhận thấy rằng, quan hệ GV_O ở bảng 3.4, với GV[l]=Oid1 thì hai bộ dữ liệu đầu tiên của bảng có giá trị các thuộc tính Khoá dạy và HS lương như nhau, do đó nếu ta áp dụng lý thuyết chuẩn hóa theo thời gian của Wang [12] thì có thể khắc phục được hiện tượng dư thừa dữ liệu nói trên. Như vậy, sự chuẩn hóa theo thời gian dường như phụ thuộc vào việc các dữ liệu theo thời gian được tổ chức như thế nào[15]. 3.2.2. Việc định danh đối tượng Việc định danh đối tượng được sử dụng nhằm định danh và tham chiếu đến các đối tượng mà không phụ thuộc vào yếu tố thời gian. Tuy nhiên, các OID đó chỉ được tạo ra bởi các hệ quản trị CSDL và không được quan tâm bởi những người dùng cuối. Nhìn chung, những người dùng cuối chỉ quan tâm đến các đối tượng thông qua những thuộc tính do người dùng định nghĩa ra mà ta gọi là “khoá”. Một trong những đặc điểm thuận lợi của việc định danh đối tượng là nó cho phép chuyển đổi giữa các quan hệ được nhóm theo thời gian và các quan hệ không được nhóm theo thời gian mà không làm mất thông tin. Ví dụ 3.5. Giả sử ta có một quan hệ không được nhóm theo thời gian với các OID như quan hệ GV_O được cho ở bảng 3.4. Hãy tìm một khoá K (do người dùng định nghĩa và không phải là l) sao cho K thoả hai tính chất sau: - Các bộ dữ liệu không cùng giá trị khoá thì biểu diễn các đối tượng riêng biệt. Tính chất này được gọi là tính bất biến theo thời gian. - Các bộ dữ liệu có cùng giá trị khoá thì biểu diễn chính đối tượng đó tại các thời điểm khác nhau. Tính chất này được gọi là tính nhất quán theo thời gian. Cả hai tính chất này có thể được biểu diễn bởi các phụ thuộc hàm theo thời gian. Chẳng hạn, tính bất biến theo thời gian của thuộc tính Họ tên có thể được biểu diễn bởi phụ thuộc hàm theo thời gian như sau: l ®a Họ tên Trong đó, a là các kiểu thời gian như Ngày, Tuần, Tháng, Năm... Nếu giá trị a càng rộng thì mức độ bất biến theo thời gian càng cao. Chẳng hạn, TFD l ®TuầnHọ tên có mức độ bất biến theo thời gian cao hơn TFD l