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

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 ®NgàyHọ tên, vì nếu Họ tên của một giáo viên không thể thay đổi trong một tuần thì nó cũng không thể thay đổi trong một ngày. Trong quan hệ GV_O, tính bất biến theo thời gian tuyệt đối được biểu diễn bởi TFD: l ®ForeverHọ tên. TFD này không được thoả mãn trên CSDL ở bảng 3.4, khi “Lê Hoàng” thay đổi tên thành “Lê Hoàng A” vào ngày 04/03/05. Trong quan hệ GV_O, tính nhất quán theo thời gian của thuộc tính Họ tên có thể được biểu diễn bởi các TFD có dạng sau: Họ tên ®b l Cũng như tính bất biến theo thời gian, nếu b càng rộng thì mức độ nhất quán theo thời gian càng cao. Trong quan hệ GV_O, TFD Họ tên ®Foreverl mô tả rằng các giáo viên khác nhau thì có họ tên khác nhau bất kể ở thời gian nào. TFD này cũng không được thoả mãn với CSDL ở bảng 3.4 khi “Lê Hoàng” là họ tên của hai giáo viên khác nhau. Như vậy, một khoá có thể được biểu diễn bởi hai tham số a và b trong đó a mô tả mức độ bất biến theo thời gian và b mô tả mức độ nhất quán theo thời gian. Một khoá được xem là lý tưởng nếu a = b = Forever. Ví dụ 3.6. Xét quan hệ GV_O trong bảng 3.4, giả sử ta thêm thuộc tính Mã GV vào quan hệ. Mỗi giáo viên được gán duy nhất bởi một Mã GV gồm 3 ký tự chẳng hạn, và chỉ được thay đổi khi giáo viên đó chuyển sang dạy cho một khoá khác. Vì một giáo viên không thể thay đổi khoá dạy trong 1 tuần, cho nên họ không thể có hai Mã GV khác nhau trong 1 tuần. Khi đó, tính bất biến theo thời gian trên quan hệ GV_O có thể được biểu diễn bởi TFD: l ®TuầnMã GV Mặt khác, do số lượng Mã GV bị hạn chế nên nó có thể được sử dụng để gán lại cho một giáo viên mới sau khi giáo viên cũ đã chuyển đi. Tuy nhiên, để hạn chế các cuộc truy cập nhầm, một yêu cầu được đặt ra là phải ít nhất sau 5 ngày tính từ này giáo viên chuyển đi, Mã GV cũ của giáo viên đó mới được sử dụng để gán lại cho một giáo viên khác. Trong khoảng thời gian 5 ngày này, nếu một ai đó truy cập đến Mã GV cũ của giáo viên đã chuyển đi sẽ được hệ thống trả lời các thông tin về giáo viên đó ở vị trí mới. Khi đó, trên quan hệ GV_O xuất hiện TFD có dạng: Mã GV ®5 ngàyl Như vậy, tại tất cả các thời điểm t1 và t2 nằm trong khoảng thời gian là 5 ngày, nếu t1 là một bộ dữ liệu trên quan hệ GV_O ở thời điểm t1 và t2 là một bộ dữ liệu trên quan hệ GV_O ở thời điểm t2 thì t1(Mã GV) = t2(Mã GV), nghĩa là t1(l) = t2(l). Khi đó trong quan hệ GV_O, Mã GV có mức độ bất biến theo thời gian là 1 tuần và mức độ nhất quán theo thời gian là 5 ngày. Điều này có nghĩa là: trong khoảng thời gian 5 ngày, các giáo viên có thể được nhận biết một cách rõ ràng qua Mã GV của họ. Nói cách khác, trong khoảng thời gian 5 ngày kể từ ngày giáo viên chuyển đi, Mã GV có thể được xem như là khoá của quan hệ để nhận biết đối tượng. Chú ý rằng, nếu ta không thể sử dụng một thuộc tính nào đó để làm khoá cho quan hệ thì ta có thể tạo khoá cho quan hệ từ hơn một thuộc tính. 3.2.3. Các mô hình dữ liệu ngữ nghĩa Mặc dù mục tiêu chính của lý thuyết chuẩn hóa là nhằm thiết kế ra các lược đồ CSDL tốt, có thể tuân theo một dạng chuẩn nào đó nhằm giảm thiểu dữ liệu dư thừa và tránh được những dị thường khi cập nhật dữ liệu. Tuy vậy, lý thuyết chuẩn hóa không là một phương pháp thiết thực trong việc thiết kế lược đồ CSDL. Hiện nay, người ta thường sử dụng các mô hình ngữ nghĩa của dữ liệu để xây dựng nên một lược đồ ngữ nghĩa, như lược đồ thực thể quan hệ chẳng hạn và sau đó chuyển thành một lược đồ quan hệ. Wang là người đầu tiên đã đề xuất lý thuyết chuẩn hóa trên CSDL có yếu tố thời gian, mục đích chính của ông là nhằm thiết kế được một lược đồ tốt cho các CSDL quan hệ theo thời gian. Do CSDL theo thời gian thực chất là một mở rộng của CSDL truyền thống nên có một vấn đề được đặt ra ở đây là: phải chăng việc mở rộng theo thời gian đối với các mô hình dữ liệu ngữ nghĩa có thể giúp việc thiết kế các CSDL có yếu tố thời gian một cách thiết thực hơn so với việc sử dụng lý thuyết chuẩn hóa theo thời gian mà Wang đã đề xuất. Ví dụ 3.7. Giả sử các môn học trong một khoá được dạy bởi các giáo viên của trung tâm. Do đó ta bổ sung vào quan hệ GV thuộc tính Môn dạy sao cho trong cùng một khoá thì thuộc tính này phải thoả các ràng buộc như sau: Một môn không thể được dạy bởi hai giáo viên khác nhau trong một ngày. Một giáo viên không thể dạy hai môn khác nhau trong một tháng. Điều này được biểu diễn bởi lược đồ thực thể quan hệ sau:  MD Giáo viên Môn dạy HS lương Mã MD Tên MD Hä tªn 1 1 Hình 3.1. Lược đồ thực thể quan hệ MD. Trong lược đồ ở hình 3.1, ta có thể nhận thấy rằng: mối quan hệ MD giữa Giáo viên và Môn dạy là mối quan hệ 1:1. Điều này có nghĩa là tại một thời điểm bất kỳ, không có môn nào được phân chung cho hai giáo viên khác nhau dạy và không có giáo viên nào được phép dạy hơn một môn. Lược đồ ở hình 3.1 không thể hiện được các ràng buộc trên. Một mở rộng theo thời gian của lược đồ thực thể quan hệ GV với CSDL tương ứng có thể được mô tả trong hình sau: MD Giáo viên Môn dạy HS lương Mã MD Tên MD Hä tªn Ngày:1 Tháng:1 MD: Giáo viên Môn dạy Thời gian Oid2 Oid2 Oid7 Oid8 Oid9 Oid8 [02/10/2005, 15/10/2005] [01/11/2005, 30/11/2005] [16/10/2005, 31/10/2005] GIÁOVIÊN: l Họ tên HS lương Thời gian Oid2 Nguyễn Huy 1.82 [01/10/2005, 30/11/2005] Oid7 Trần Linh 2.30 [01/10/2005, 30/11/2005] MÔNDẠY: l Mã MD Tên MD Thời gian Oid8 EX27 Excel 27 [01/10/2005, 30/11/2005) Oid9 VB36 Visual Basic 36 [01/10/2005, 30/11/2005] Hình 3.2. Lược đồ thực thể quan hệ theo thời gian và CSDL tương ứng. Trong lược đồ thực thể quan hệ theo thời gian ở hình 3.2, ràng buộc “tháng:1” cho biết rằng một giáo viên không thể dạy hai môn khác nhau trong 1 tháng, điều này được biểu diễn bởi TFD sau: Giáo viên ®Tháng Môn dạy Tương tự, ràng buộc “ngày:1” cho biết rằng một môn nào đó không thể phân cho hai giáo viên khác nhau dạy trong một ngày, điều này được biểu diễn bởi TFD sau: Môn dạy ®Ngày Giáo viên Như vậy với các TFD, nó không chỉ hữu ích đối với vấn đề định danh đối tượng mà còn có vai trò quan trọng trong việc biểu diễn ngữ nghĩa của các mô hình dữ liệu, đặc biệt là các mô hình dữ liệu có yếu tố thời gian. 3.3. Mô hình thời gian Mô hình thời gian được giới thiệu trong phần này tập trung xung quanh vấn đề về quan hệ thời gian, mà quan hệ thời gian ở đây thực chất là một quan hệ hai ngôi trên tập các thời điểm. 3.3.1. Quan hệ thời gian Thông thường ta sử dụng tập các số tự nhiên ( = {1, 2, 3, …}) để biểu diễn thời gian. Các phần tử của còn được gọi là các thời điểm. Trên thực tế, ta có thể xem các số tự nhiên này như là các giây, phút, giờ, ngày hay một đơn vị thời gian nào đó. Định nghĩa 3.1. (Quan hệ thời gian) Cho I, J, Í . Khi đó, I Ä J = {(i, j) | i Î I, j Î J, i £ j}, và Forever = Ä được gọi là các quan hệ thời gian. Nhận xét: + Một tập con của Forever gọi là một quan hệ thời gian. + Current và Twin là hai quan hệ thời gian đặc biệt: Current = {(i, i) | i Î } và Twin = {(1,1); (1,2); (2,2)} + f cũng là một quan hệ thời gian. + Một quan hệ thời gian là một tập các ràng buộc trên Forever. Ví dụ 3.8. Tháng = {(i, j) | i, j Î Tháng} là một quan hệ thời gian. Giả sử rằng số 1 tương ứng với ngày 1/1/2006, số 2 tương ứng với ngày 2/1/2006… Khi đó, Tháng có thể được định nghĩa như sau: Tháng(1/2006) = {(1,1); (1,2); …; (1,31); (2,2); (2,3); …; (2,31); …; (30, 30); (30, 31); (31,31)} Tháng(2/2006) = {(32, 32); …; (32, 59); (33, 33); …; (33, 59); …; (58, 58); (58, 59); (59, 59)} … Tháng(1/2007) = {(366, 366); (366, 367); …; (396, 396); (396, 397); (397, 397)} 3.3.2. Lớp hạn chế của các quan hệ thời gian Trong phần này trình bày một lớp hạn chế của các quan hệ thời gian mà ta gọi là các chronology, nó có thể được sử dụng để biểu diễn các kiểu thời gian. Định nghĩa 3.2. (Cơ sở của một quan hệ thời gian) Cho B Í Ã() với Ã() là tập các tập con của . ÄB = È {I ÄI | I Î B} Cho a là một quan hệ thời gian. Khi đó, một cơ sở của a là tập B gồm các tập con khác f của sao cho a = ÄB. Nhận xét: + Äf = f. + Các phần tử của một cơ sở có thể là vô hạn. + {} là một cơ sở của Forever + {i | i Î } là một cơ sở của Current. + f là một cơ sở của f. + Không phải mọi quan hệ thời gian đều có cơ sở. Chẳng hạn a = {1, 2}. Ví dụ 3.9. Với Ä{{1, 2}; {4, 6}} = ({1, 2} Ä {1, 2}) È ({4, 6} Ä {4, 6}) = = {(1, 1); (1, 2); (2, 2); (4, 4); (4, 6); (6, 6)} Vậy, B = {{1, 2}; {4, 6}} là một cơ sở của a = {(1, 1); (1, 2); (2, 2); (4, 4); (4, 6); (6, 6)} Bổ đề 3.1. Một quan hệ thời gian có tối đa một cơ sở. Định nghĩa 3.4. (Quan hệ sớm hơn thực sự trên Ã()) Cho I, J, Í . Khi đó, I được gọi là sớm hơn J thực sự, ký hiệu I ≺ J, khi và chỉ khi với "i Î I và "j Î J thì i ≺ j. Ví dụ 3.10. Cho I = {1, 2} và J = {4, 6}. Ta nói I ≺ J. Định nghĩa 3.5. (Quan hệ sớm hơn trên Ã()) Cho I, J, Í . Khi đó, I được gọi là sớm hơn J, ký hiệu I ≼ J, khi và chỉ khi I ≺ J hoặc I = J. Ví dụ 3.11. Cho I = {1, 2} và J = {2, 6}. Ta nói I ≼ J. Định nghĩa 3.6. (Định nghĩa chronology) Cho a là một quan hệ thời gian và B là một cơ sở của a. Khi đó, a được gọi là một chronology khi và chỉ khi: a có một cơ sở thoả bổ đề 3.1, và ≼ là một quan hệ thứ tự trên B. Ví dụ 3.12. Cho a = {(1, 1); (1, 2); (2, 2); (4, 4); (4, 6); (6, 6)}. + Từ ví dụ trên ta thấy rằng B = {{1, 2}; {4, 6}} là một cơ sở của a. + Mặt khác, do {1, 2} ≼ {4, 6}. Vậy a là một chronology. Ví dụ 3.13. Cho a = {(1, 1); (1, 4); (4, 4); (2, 2); (2, 6); (6, 6)}. + Vì Ä{{1, 4}; {2, 6}} = a nên {{1, 4}; {2, 6}} là một cơ sở của a. + Do {1, 4} {2, 6}. Vậy a đã cho không phải là một chronology. Như vậy, một quan hệ thời gian a chỉ có thể là một chronology nếu a có một cơ sở B và trên B có xác định quan hệ ≼. Bên cạnh đó, cũng có những quan hệ thời gian khác mặc dù không phải là một chronology nhưng rất quan trọng. Chẳng hạn, một thư viện yêu cầu rằng các cuốn sách cho mượn phải được trả trong vòng một 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. Một tuần = {(i, j) | j – i £ 7} Ngoài ra, còn có một số các quan hệ thời gian khác như: năm ngày, năm mươi ngày hay Next. Trong đó: Next = {(i, j) | j – i £ 1} Rõ ràng các quan hệ như: một tuần, năm ngày, Next… không phải là các chronology. Song, nó có thể được biểu diễn như là hợp của hai chronology. Chẳng hạn, Next = Next 1 È Next 2, trong đó: Next 1 = Ä{{1, 2}; {3, 4}; {5, 6}; …} và Next 2 = Ä{{2, 3}; {4, 5}; {6, 7}; …}. 3.3.3. So sánh chronology với các kiểu thời gian Trong phần này trình bày mối quan hệ 1:1 tương ứng giữa các chronology với các kiểu thời gian. Định nghĩa 3.7. (Mối quan hệ giữa chronology với các kiểu thời gian) Cho a là một chronology với cơ sở B = {I1, I2, I3, …}, n là số các phần tử của B (n có thể vô hạn). Do B là một dãy có thứ tự, giả sử I1 ≺ I2 ≺ I3 ≺ … với "Ii ¹ Æ, i = . Khi đó, từ a ta định nghĩa một kiểu thời gian được ký hiệu bởi là một ánh xạ được xác định như sau: : ® Ã() sao cho với "i Î ta có: (i) = Ii nếu i £ n Æ nếu ngược lại Nhận xét: + Với a và b là hai chronology bất kỳ. Nếu = thì a = b. + Với t là một kiểu thời gian. Do t Î Ã() trong khi đó (i) Î Ã() với "i nên có một số kiểu thời gian không thể là kết quả của việc chuyển đổi từ một chronology. Ví dụ 3.14. Cho a = Tháng là một chronology. Khi đó: (1) = {1, …, 31}; (2) = {32, …, 59}; … (12) = {334, …, 365}; Như vậy, rõ ràng cũng là một kiểu thời gian. Mệnh đề 3.1. (Quan hệ bé hơn trên các chronology) Cho a1 và a2 là các chronology. Khi đó, 1 được gọi là bé hơn 2 khi và chỉ khi a1 Í a2. Tóm lại, một lớp hạn chế của các quan hệ thời gian gọi tắt là các chronology tương đương với các kiểu thời gian. Từ mối quan hệ bé hơn trên các kiểu thời gian ta có thể chuyển nó thành quan hệ bé hơn trên các chronology. Có một số quan hệ thời gian không phải là chronology như một tuần, Next…song, lại rất quan trọng trong CSDL có yếu tố thời gian. 3.4. Mô hình dữ liệu hướng đối tượng theo thời gian Phần này trình bày định nghĩa một mô hình dữ liệu với các đối tượng phức (mô hình dữ liệu hướng đối tượng). Trước hết là trình bày khái niệm về lược đồ hướng đối tượng (gọi tắt là lược đồ) và sự thể hiện theo thời gian của lược đồ. Sau đó là trình bày một đồ thị biểu diễn lược đồ nhằm giới thiệu khái niệm chu trình trong một lược đồ hướng đối tượng. 3.4.1. Lược đồ hướng đối tượng và thể hiện theo thời gian ● Giả sử một số các kiểu nguyên tố và miền giá trị tương ứng của chúng là đôi một rời nhau, bao gồm: Integer, String, Boolean và Float. Tập dom của các giá trị nguyên tố là hợp của các miền này, các phần tử của dom được gọi là các hằng. ● Giả sử att là tập các tên thuộc tính, att ⊉ l với l là một thuộc tính định danh đối tượng. ● Giả sử obj là tập vô hạn các OID và class là tập các tên lớp. Định nghĩa 3.8. (Lược đồ hướng đối tượng) Cho C là tập hữu hạn các tên lớp (C Í class). Một tập {A1: w1, A2: w2 …, An: wn} là một kiểu trên C, trong đó A1… An Î att và mỗi wi (i Î [1..n]) là một kiểu nguyên tố hoặc một tên lớp của C. Khi đó, một lược đồ M là một cặp (C, g) với C là một tập hữu hạn các tên lớp và g là các hàm trên C ánh xạ mỗi tên lớp của C đến một kiểu trên C. Ví dụ 3.15. M = (C, g) với: C = {GV, KD} g(GV) = { Mã GV: String, Họ tên: String, HS lương: Integer, Môn dạy: String, Khoá dạy: KD, Thủ trưởng: GV } g(KD) = { Tên khoá dạy: String, Chủ nhiệm khoá dạy: GV } Định nghĩa 3.9. (Thể hiện của một lược đồ) Cho C là một tập các tên lớp. Một sự chỉ định OID đến C là một hàm p từ C đếnÃ(obj) sao cho với mỗi c, d Î C, c ¹ d thì p(c) Ç p(d) = Æ. Điều này có nghĩa là một sự chỉ định OID đến C là một ánh xạ từ mỗi tên lớp của C đến một tập các OID. Cho {A1: w1, A2:wn, … An: wn}là một kiểu trên C. Một bộ dữ liệu của nó là một tập {A1: u1, A2: u2, …, An: un}sao cho với mỗi i Î [1..n], nếu wi Î C thì ui Î p(C), và nếu wi là kiểu nguyên tố thì ui thuộc về miền thông thường của kiểu nguyên tố đó. Khi đó, một thể hiện của lược đồ (C, g) là một cặp I = (p, n) trong đó: p là một sự chỉ định OID đến C (và cho O = È {p(c) | c Î C}); n là một hàm trên O ánh xạ mỗi OID của O đến một bộ dữ liệu của một kiểu xác định trên C, ví dụ với mỗi c Î C, o Î p(c) thì n(o) là một bộ dữ liệu của kiểu g(c). Nhận xét: Cho I = (p, n) là một thể hiện của lược đồ (C, g). Khi đó: + I = Æ nếu p(c) = Æ với "c Î C. + Nếu c Î C và o Î p(c) với n(o) = {A1: u1, A2: u2, …, An: un} thì {l: o, A1: u1, A2: u2, …, An: un} được gọi là một đối tượng của c. + Từ I ta định nghĩa là một hàm trên C ánh xạ mỗi tên lớp của C đến một tập nhỏ nhất chứa tất cả các đối tượng của c. Các đối tượng, các bộ dữ liệu, và các kiểu là toàn bộ các hàm trên tập con nào đó của att È {l}. Miền giá trị của một hàm t được ký hiệu là [[t]]. Chúng ta biểu diễn [[t]] È {l} bởi [[t]]l. Nếu t là một hàm và X Í [[t]] thì t[X] biểu diễn toàn bộ hàm t’ trên X mà t’(x) = t(x) với "x Î X. Ví dụ 3.16. Xét lược đồ được cho ở ví dụ 3.15. Khi đó, một thể hiện của lược đồ đã cho là I = (p, n) trong đó: p(GV) = {oid2, oid3}, p(KD) = {oid5}, và: u(oid2) = {Mã GV: 002, Họ tên: Nguyễn Huy, HS lương: 1.82, Môn dạy: Excel 27, Khoá dạy: oid5, Thủ trưởng: oid2} u(oid3) = {Mã GV: 003, Họ tên: Lê Hoàng, HS lương: 2.30, Môn dạy: Winword 27, Khoá dạy: oid5, Thủ trưởng: oid2} u(oid5) = {Tên khoá dạy: TinA27, Chủ nhiệm khoá dạy: oid2} Khi đó, (KD) = {{l: oid5, Tên khoá dạy: TinA27, Chủ nhiệm khoá dạy: oid2}} Định nghĩa 3.10. (Thể hiện theo thời gian của một lược đồ) Một thể hiện theo thời gian T của lược đồ (C, g) là một dãy vô hạn các thể hiện của (C, g). Thể hiện thứ i của T được biểu diễn Ti = (pi, ni). Cho c Î C, một phần tử của i(c) được gọi là một đối tượng của c tại thời điểm i. Trên thực tế, ta có thể xem Ti như là giá trị dữ liệu tại thời điểm i. 3.3.2. Đồ thị biểu diễn lược đồ Đồ thị biểu diễn lược đồ (SDG) của (C, g) là một đồ thị có hướng với các nút được gán nhãn và các cạnh không được gán nhãn. Mỗi nút trên SDG của (C, g) được gán nhãn c với mỗi tên lớp c Î C. Khi A: d Î g(c) với d Î C, chúng ta vẽ một cạnh có hướng từ nút có nhãn c đến nút có nhãn d. Nếu SDG không có chu trình thì ta gọi SDG đó là lược đồ không có chu trình. Ngược lại, nếu SDG có ít nhất một chu trình thì ta gọi SDG đó là lược đồ có chu trình. Ví dụ 3.17. SDG của lược đồ (C, g) được cho trong ví dụ 3.15. GV KD Hình 3.3. SDG của lược đồ (C, g). 3.5. Phụ thuộc hàm theo thời gian 3.5.1. Định nghĩa hình thức về TFD Định nghĩa 3.11. (TFD trên đối tượng phức) Cho lược đồ M = (C, g), c Î C, a là một quan hệ thời gian, và X, Y Í [[g(c)]]l với X ¹ Æ. Khi đó, một TFD trên (C, g) có dạng: c: X ®aY Cho T là một thể hiện theo thời gian của (C, g). Khi đó, T được gọi là thoả TFD c: X ®aY khi và chỉ khi với "(i, j) Î a, t1 Îi(c) và t2 Î j(c), nếu t1[X] = t2[X] thì t1[Y] = t2[Y]. Nhận xét: + T được gọi là thoả tập F các TFD nếu nó thoả mỗi TFD của F. + Một lược đồ (C, g) mở rộng là cặp ((C, g), F) với F là tập các TFD trên (C,g). Ví dụ 3.18. Xét lược đồ M = (C, g) được cho trong ví dụ 3.15 với tập các ràng buộc sau: 1) Tại bất kỳ thời điểm nào, không có hai giáo viên nào trùng tên nhau. 2) Mối giáo viên không thể có hai hệ số lương khác nhau trong 1 tháng. 3) Mỗi giáo viên không thể thay đổi khoá dạy trong 1 tuần. 4) Một môn không thể phân cho hai giáo viên khác nhau dạy trong 1 ngày. 5) Mã giáo viên chỉ thay đổi khi họ thay đổi khoá dạy, các mã giáo viên không sử dụng nữa có thể được sử dụng để gán lại cho các giáo viên khác, nhưng chỉ sau một khoảng thời gian là 5 ngày. 6) Tại bất kỳ thời điểm nào, không có hai khoá dạy nào có cùng tên. 7) Tại bất kỳ thời điểm nào, không có hai khoá dạy nào có cùng chủ nhiệm. Với các ràng buộc trên, ta có thể biểu diễn chúng dưới dạng các TFD sau: i) GV: Họ tên ®Current l ii) GV: l ®Tháng HS lương iii) GV: l ®Tuần Khoá dạy iv) GV: Môn dạy ®Ngày l v) GV: l, Khoá dạy ®Next Mã GV v’) GV: Mã GV ®5 ngày l vi) KD: Tên khoá dạy ®Current l vii) KD: Chủ nhiệm khoá dạy ®Current l 3.5.2. Hệ tiên đề cho các TFD Cho lược đồ M = (C, g), quan hệ thời gian a. Với mỗi c Î C và X, Y, Z Í [[g(c)]]l. Khi đó, hệ tiên đề cho các TFD trên M được phát biểu như sau: TD1. (Luật phản xạ): Nếu Y Í X thì c: X ®ForeverY TD2. (Luật tăng trưởng): Nếu c: X ®aY thì c: XZ ®aYZ TD3. (Luật bắc cầu): Nếu c: X ®aY và c: Y ®b Z thì c: X ®a Ç b Z TD4. Nếu c: X ®aY và c: X ®bY thì c: X ®a È bY TD5. c: X ®ÆY TD6. c: {l} ®CurrentX TD7. Nếu a Í b và c: X ®bY thì c: X ®aY Nhận xét: + Ba tiên đề TD1, TD2 và TD3 tương tự với các tiên đề của Armstrong. + Tiên đề TD4 và TD7 được thành lập theo cách tiếp cận của Wang. + TD5 là một TFD tầm thường. + TD6 được hiểu đơn giản là các giá trị thuộc tính của một đối tượng là đơn trị tại mọi thời diểm. Nếu bỏ qua việc định danh đối tượng thì TD6 có thể được xem như một TFD thông thường. Định nghĩa 3.12. (TFD suy dẫn logic từ F) Cho một lược đồ mở rộng ((C, g), F) và f là một TFD trên (C, g). Khi đó, f được gọi là suy dẫn logic từ F, ký hiệu F╞ f , khi và chỉ khi mỗi thể hiện theo thời gian của (C, g) mà thoả F thì cũng thoả f. Định nghĩa 3.13. (TFD suy dẫn từ F) Cho một lược đồ mở rộng ((C, g), F) và f là một TFD trên (C, g). Khi đó, f được gọi là suy dẫn từ F, ký hiệu F├ f nếu f thu được bằng cách sử dụng hệ 7 tiên đề {TD1, TD2, …, TD7} Từ các nhận xét ở mục 3.5.2. Định lý sau khẳng định rằng, hệ 7 tiên đề trên là đúng đắn. Định lý 3.1. (Tính đúng đắn của hệ 7 tiên đề) Cho một lược đồ mở rộng ((C, g), F) và f là một TFD trên (C, g). Nếu F├ f thì F╞ f. Chứng minh. Xét TD3 như là một ví dụ. Giả sử c: X ®a Ç bY nhận được từ c: X ®aY và c: Y ®b Z. Cho T là một thể hiện theo thời gian thoả F. Cho (i, j) Î a Ç b. Cho t1 Î i(c) và t2 Î j(c) với t1[X] = t2[X] thế thì t1[Z] = t2[Z]. Theo giả thiết F╞ c: X ®aY và F╞ c: Y ®b Z. Vì (i, j) Î a nên ta có t1[Y] = t2[Y]. Vì (i, j) Î b nên ta có t1[Z] = t2[Z] Vậy, định lý được chứng minh. □ 3.5.3. So sánh hệ 4 tiên đề của Wang và hệ 7 tiên đề của Wijsen Như ta đã biết, thực chất các chronology là lớp hạn chế có ý nghĩa của các quan hệ thời gian, nó có thể biểu diễn các kiểu thời gian như: năm, tháng, tuần, ngày… Trong phần này sẽ so sánh hệ 4 tiên đề của Wang được trình bày trong mục 2.3.2 của chương 2 với hệ 7 tiên đề của Wijsen được trình bày trong mục 3.5.2 của chương 3 để thấy được sự khác nhau về mặt ngữ nghĩa giữa các hệ tiên đề này. Định nghĩa 3.13. (Định nghĩa TFD-C) Cho lược đồ M = (C, g), quan hệ thời gian a. Với mỗi c Î C và X, Y Í [[g(c)]]l. Khi đó, một TFD có dạng c: X ®aY được gọi là một TFD-C nếu a là một chronology. Ví dụ 3.19. Trở lại ví dụ 3.18. Theo định nghĩa 3.13 thì rõ ràng: GV: Họ tên ®Current l là một TFD-C. Song, GV: Mã GV ®5 ngày l không phải là một TFD-C. Mệnh đề 3.2. (Quan hệ bé hơn toàn bộ) Cho a, a1, a2, …, an là các chronology. Nếu bé hơn toàn bộ {1, …, n} thì a Í a1 È … È an. Chứng minh. Giả sử bé hơn toàn bộ {1, …, n}. Cho (l, m) Î a. Ta sẽ chứng minh rằng (l, m) Î ak với "k Î [1..n]. Do (l, m) Î a nên l, m Î (i) với "i Î . Vì bé hơn toàn bộ {1, …, n} nên ta có (i) Í k(j) với "k Î [1..n] và j Î . Vì vậy l, m Î k(j) do đó (l, m) Î ak . □ Nhận xét: Mệnh đề 3.2 sẽ không đúng trong trường hợp ngược lại. Ví dụ 3.20. Cho các chronology a1, a2, a3 với: a1 = {(1, 1); (1, 2); (2, 2)} a2 = {(1, 1); (1, 3); (3, 3)} a3 = {(2, 2); (2, 3); (3, 3)} Cho a4 = a1 È a2 È a3. Rõ ràng a4 = Ä{{1, 2, 3}} cũng là một chronology. Ta có: 1(1) = {1, 1}; 2(1) = {1, 3}; 3(1) = {2, 3} và 4(1) = {1, 2, 3}. Mặt khác, với "i Î [1..4] ta có: i(j) = Æ nếu j > 1. Vậy, a4 Í a1 È a2 È a3. Song, 4 không bé hơn toàn bộ {1, 2, 3}. Với 4 tiên đề được trình bày trong chương 2: 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}. Rõ ràng các tiên đề T1, T2 và T3 của Wang lần lượt tương đương với các tiên đề TD1, TD2, TD3 của Wijsen. Do Wang không chấp nhận một kiểu thời gian rỗng xuất hiện trong TFD nên hệ tiên đề của ông không có tiên đề như TD5 của Wijsen. Mặt khác, do Wang không có khái niệm định danh đối tượng nên ông cũng không có tiên đề như TD6. Đối với T4, nó có thể được hiểu như sau: TDx. Nếu c: X ®aY, …, c: X ®aY là các TFD-C với a là một chronology, và bé hơn toàn bộ {1, …, n} thì c: X ®aY. (Luật thừa kế) Rõ ràng TDx là đúng, giả sử c: X ®aY, …, c: X ®aY và bé hơn toàn bộ {1, …, n}. Từ mệnh đề 2, a Í a1 È … È an. Áp dụng TD4, ta có c: X ®aÈ … È aY. Từ TD7, ta có c: X ®aY. Như vậy, mọi TFD-C nhận được từ TDx thì cũng có thể nhận được từ việc sử dụng TD4 và TD7. Song, trường hợp ngược lại thì không đúng. Ví dụ 3.21. Cho các chronology a1, a2, a3 với: a1 = {(1, 1); (1, 2); (2, 2)} a2 = {(1, 1); (1, 3); (3, 3)} a3 = {(2, 2); (2, 3); (3, 3)} Cho a4 = a1 È a2 È a3. Cho F = {c: X ®aY, c: X ®aY, c: X ®aY}. Áp dụng TD4, từ F ta có c: X ®aY. Mặt khác, vì 4 không bé hơn toàn bộ {1, 2, 3} do đó tiên đề thừa kế không thể áp dụng được. Như vậy, lý do chính để tìm hiểu lý thuyết phụ thuộc hàm theo thời gian (như các TFD ở trong chương 2 và chương 3) là chúng cho phép mô tả đầy đủ các ngữ nghĩa của thế giới thực trong một lược đồ CSDL. Các TFD-C trong chương 3 và các TFD trong chương 2 về bản chất có cùng ý nghĩa. Song, ví dụ 3.21 đã chỉ ra sự khác nhau trong việc lập luận xung quanh hai cấu trúc này. 3.6. Kết luận Trong chương này đã trình bày được vai trò của việc định danh đối tượng trong các mô hình dữ liệu được nhóm theo thời gian, tính khả dụng của nó trong việc biểu diễn các ràng buộc theo thời gian mà các ràng buộc ở đây lại là các TFD. Một mô hình thời gian khác tổng quát hơn so với mô hình được trình bày trong chương 2 cũng đã được trình bày trong chương này. Với mô hình thời gian trong chương này, ngoài các kiểu thời gian “cố định” như Ngày, Tuần, Tháng, Năm … nó còn cho phép biểu diễn các khoảng thời gian “động” như 5 ngày, 1 tuần … chẳng hạn. Cũng trong chương này, một mở rộng của lý thuyết phụ thuộc hàm theo thời gian trên các đối tượng phức đã được trình bày. Từ đó so sánh được các TFD ở trong chương 2 với các TFD-C ở chương 3. Một hạn chế của cách tiếp cận này là Wijsen đã chưa đưa ra được một lý thuyết chuẩn hoá trên các lược đồ hướng đối tượng theo thời gian. Tuy nhiên, hạn chế này cũng khó tránh khỏi khi mà mô hình hướng đối tượng trên thực tế chưa có một chuẩn thống nhất. KẾT LUẬN 1. Kết luận Thông thường, việc quản lý CSDL trong hầu hết các ứng dụng CSDL đều có liên quan đến yếu tố thời gian. Song, do sự phức tạp mà yếu tố thời gian mang lại trong các ứng dụng đó nên người ta thường bỏ qua nó trong CSDL. Do đó đã làm cho CSDL mất đi tính đầy đủ, rõ ràng, dẫn đến ứng dụng mất đi tính thực tiễn. Chính vì thế mà các nhà khoa học đã không ngừng nghiên cứu nhằm tìm ra những giải pháp hợp lý nhất để giải quyết vấn đề phức tạp của yếu tố thời gian trong CSDL, góp phần giúp các nhà thiết kế CSDL hiểu rõ vấn đề CSDL có yếu tố thời gian. Trên cơ sở tìm hiểu lý thuyết phụ thuộc hàm theo thời gian theo cách tiếp cận của Wang và Wijsen, những kết quả đạt được và đóng góp của luận văn này là: + Tìm hiểu một cách khái quát về CSDL có yếu tố thời gian. + Tìm hiểu lý thuyết chuẩn hoá CSDL quan hệ theo thời gian theo cách tiếp cận của Wang, với những khái niệm như: 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 bao đóng và phủ tối thiểu. + Xây dựng được thuật toán tìm phủ tối thiểu tập TFD dựa trên quan điểm của Wang. + Xây dựng được 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 quan điểm của Wang. + Xây dựng một số tính chất và hệ quả phản ánh mối quan hệ giữa TFD và FD truyền thống. Từ những tính chất và hệ quả được đưa ra trong chương 2, chúng ta có thể chứng minh được 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. + Tìm hiểu lý thuyết phụ thuộc hàm theo thời gian trong mô hình dữ liệu hướng đối tượng theo cách tiếp cận của Wijsen. Với Wijsen, ông đã đưa ra một kiểu thời gian mới tổng quát hơn so với kiểu thời gian mà Wang đã đưa ra trong chương 2 của luận văn, đó là bao gồm những kiểu thời gian “cố định” như Ngày, Tuần, Tháng, Năm... và cả những khoảng thời gian “động” như 5 Ngày hay 1 Tuần.... + Từ những quan điểm của Wang và Wijsen, so sánh được hệ tiên đề cho các TFD của Wang và Wijsen. Trong khuôn khổ của bài luận văn này, chúng tôi đã bước đầu nghiên cứu được lý thuyết phụ thuộc hàm theo thời gian trong CSDL, với một vài kết quả được đưa ra. Song, đó chỉ là một trong số những vấn đề cần nghiên cứu đối với CSDL có yếu tố thời gian, thực tế còn nhiều vấn đề đáng quan tâm khác trong CSDL có yếu tố thời gian vẫn đang là hướng mở, có thể phát triển và chưa được đề cập đến trong bài luận văn này. 2. Hướng phát triển Ngày nay, khi các ứng dụng CSDL có yếu tố thời gian được phát triển ngày càng cao thì phạm vi nghiên cứu CSDL có yếu tố thời gian ngày càng rộng. Chẳng hạn như: + Những vấn đề về việc thiết kế CSDL có yếu tố thời gian ở mức khái niệm và mức vật lý. + Xây dựng thuật toán tìm một khoá và nhiều khoá cho các lược đồ môđun thời gian theo cách tiếp cận của Wang. + Xây dựng một cơ sở TFD hoàn chỉnh với những khái niệm như bao đóng, phủ tối thiểu trong mô hình dữ liệu hướng đối tượng theo cách tiếp cận của Wijsen. + Xây dựng lý thuyết chuẩn hóa, lý thuyết phân tách cho các lược đồ hướng đối tượng theo thời gian theo cách tiếp cận của Wijsen. TÀI LIỆU THAM KHẢO Tiếng Việt Hoàng Quang (2005), Giáo trình cơ sở dữ liệu, Huế. Nguyễn Đình Thuân (2004), Khai thác các luật kết hợp trong cơ sở dữ liệu có yếu tố thời gian, Luận án Tiến sĩ Toán học, Trường Đại học Thủy sản Nha Trang, Nha Trang. Tiếng Anh Jan Chornicki, David Toman (2004), Time in Database System, Department of Computer Science, University at Buffalo, USA and University of Waterloo, Canada. Carlo Combi, Massimo Franceschet, Adriano Peron (2004), Representing and Reasoning about Temporal Granularities, Italy. Virginie Detienne, Jean Luc-Hainaut (2001), CASE Tool Support for Tempotal Database Design, University of Namurrue Grandgagnage. D. Dey, T. M. Baron (1996), Complete Temporal Relational Algebra, The VLDB Journal. Ramez Elmasri, Shamkant B. Navathe (2000), Fundamentals of Database System, International Edition. Christian S. Jensen. Richard T. Snodgrass (1994), Extending existing depedency theory to temporal database, Senior Member, IEEE. Christian S. Jensen. Richard T. Snodgrass (1996), Semantics of Time Varying Information, Senior Member, IEEE. Christian S. Jensen. Richard T. Snodgrass (2001), Temporal Data Management, Senior Member, IEEE. Christian S. Jensen (2001), Introduction to Temporal Database Research, Senior Member, IEEE. X. Sean Wang, Alexander Brodsky, Sushil Jajodia and Claudio Bettini (1997), Logical Design for Temporal Databases with Multiple Granularities, George Mason University, Fairfax, VA and University of Milan, Milan, Italy. J. Wijsen, J. Vandenbulcke, H. Olive (1993), Functional Dependencies Generalised for Temporal Databases that Include Object – Identity, Proc. Int’l Conf. Entity – Rlationship Approach. Jef Wijsen (1995), Design of temporal relation databases based on dynamic and temporal funtion dependencies, In proceedings of the Internatial Workshop on Temporal Databases. Jef Wijsen (1999), Temporal FDs on Complex Objects, Vrije University Brussel. PHỤ LỤC Chứng minh bổ đề 2.1. Vì T1, T2, T3 được xây dựng dựa trên ba tiên đề của Armstrong, mà ba tiên đề của Armstrong là đúng đắn nên T1, T2 và T3 là đúng đắn. Với T4 (Luật kế thừa): nếu X ®tY,…, X ®tY thì X ®t Y với mọi t ≼C  {t 1,…, t n}. Cho M = (R, t’, f) là một môđun tùy ý thỏa F. Giả sử X ®tY,…, X ®tY được suy dẫn logic từ F, nên chúng cũng được thỏa bởi M. Giả sử X ®t Y bị vi phạm bởi M; tức là tồn tại một thời điểm của t như t(i) chứa một hoặc nhiều thời điểm của t’, và hàm f tại những thời điểm này có hai bộ có cùng giá trị của X nhưng khác giá trị của Y. Bởi vì t ≼C  {t 1,…, t n}, nên những thời điểm này cũng được chứa trong một thời điểm của tk, với 1 £ k £ n. Do đó, M không thỏa X ®tY, đây là một sự mâu thuẫn. □ Chứng minh bổ đề 2.2. Cho i Î *, với t(i) ¹ Æ, và r là một quan hệ (phi thời gian) thỏa pt(i)(F). Như thế cũng đã đủ để chỉ ra rằng r thỏa X ® Y. Cho môđun thời gian M = (R, t, f), với R là lược đồ quan hệ của r và f được cho như sau: f(i) = r và f(j) = Æ với "j ¹ i. Ta cần chứng minh rằng M thỏa F. Thật vậy, giả sử V®ν W thuộc F. Nếu ∄j sao cho t(i) Í n(j), thì M thoả V®ν W. Mặt khác, vì ∄j sao cho t(i) Í n(j), nên V® W thuộc pt(i)(F). Vì r thỏa pt(i)(F), theo đó M thoả V®ν W. Do đó, M thỏa F. Với giả thiết đó thì M thoả X ®tY. Vậy, r thỏa X ® Y vì f(i) = r. □ Chứng minh bổ đề 2.3. a) Cho F1 Í F là một hỗ trợ cực tiểu cho X ® Y. Thì tồn tại một dãy hữu hạn các chứng minh cho X ® Y từ pÆ(F1) bằng cách sử dụng các tiên đề Armstrong (vì các tiên đề Armstrong là đầy đủ). Bằng cách thay thế mỗi FD thuộc pÆ(F1) trong dãy các chứng minh bằng một TFD tương ứng thuộc F1, và thay thế mỗi tiên đề Armstrong bằng các tiên đề hệ quả hữu hạn tương ứng, thì ta thấy: F1├f X ®t ’Y với một số t ’ nào đó. Vì F1├f X ®t ’Y, nên dễ dàng thấy rằng glb(F1) ≼ t ’. Để chứng minh đầy đủ ta cần chỉ ra rằng t ’≼ glb(F1). Giả sử t ’≰ glb(F1). Khi đó tồn tại một thời điểm i của t ’ với i ¹ Æ sao cho t’ (i) ⊈ glb(F1)(j) với "j. Từ định nghĩa của glb(F1), ta thấy tồn tại V®νW Î F1 sao cho t ’(i) ⊈ n(j) với "j. Do đó, pt’(i)(F1) là một tập con của pÆ(F1). Với tính đúng đắn của bốn tiên đề, và kéo theo đó là tính đúng đắn của ba tiên đề hệ quả hữu hạn, ta thấy F1╞ X ®t’Y vì F1├f X ®t ’Y. Với bổ đề 2.2, ta thấy pt’(i)(F1)├ X ® Y. Do đó, có một dãy hữu hạn các chứng minh cho X ® Y từ pt’(i)(F1) bằng cách sử dụng các tiên đề Armstrong. Với mỗi tiên đề Armstrong, ta tìm một tiên đề tương tự thuộc các tiên đề hệ quả hữu hạn. Như thế, nếu Z1 ® Z2 thuộc pt’(i)(F1) được sử dụng trong dãy các chứng minh, thì ta sử dụng Z1 ®n ’ Z2 thuộc F1 với t ’(i) Í n ’(j) với một số j nào đó (Z1 ®n ’ Z2 Î F1 được đảm bảo bằng định nghĩa của pt’(i)(F1)). Như vậy V®ν W không được sử dụng trong quá trình này. Do đó, ta có (F1  {V®ν W})├f  X ®t ” Y với t ” nào đó. Tuy nhiên, điều này mâu thuẫn bởi tính cực tiểu của F1. Do đó, t ’≼ glb(F1). b) Giả sử t ≰C {m 1,…, m m}. Do đó với i, j, k, 1 £ k £ m, thì t (i) ⊈ tk(j). Tức là tồn tại một thời điểm i cụ thể nào đó của t sao cho không có thời điểm nào của tk, với 1 £ k £ m, chứa t(i). Rõ ràng, t(i) ¹ Æ. Xét các trường hợp sau: tk = tTop với một số k nào đó, và tk ¹ tTop với "k. Trường hợp (1) dẫn đến mâu thuẫn bởi vì tTop(1) = R nên nó sẽ chứa t(i). Với trường hợp (2), Fk ¹ Æ với mọi k vì tk = glb(Fk). Vì mỗi tk là cận dưới lớn nhất (glb) của các kiểu thời gian xuất hiện trong Fk, nên tồn tại ít nhất một TFD V®ν W Î Fk sao cho không có thời điểm nào của n chứa t(i) (vì không có thời điểm nào của tk chứa t(i)); tức là ∄j sao cho t (i) Ín(j). Khi đó, bằng định nghĩa ta suy ra V®W Ï pt(i)(F). Do đó, pÆ(Fk) ⊈ pt(i)(F), với mỗi k. Tiếp theo, vì F╞ X ®tY và t(i) ¹ Æ, nên với bổ đề 2.2 ta có pt(i)(F)╞ X ®Y. Do đó, pt(i)(F) là một hỗ trợ phi thời gian cho X ®Y. Bởi vì F1,…, Fm là tất cả các hỗ trợ cực tiểu phi thời gian cho X ®Y, nên phải tồn tại 1 £ k £ m sao cho pÆ(Fk) Í pt(i)(F), điều này mâu thuẫn. Vậy, t ≼C {t 1,…, t m}. □ Chứng minh mệnh đề 2.1. Để chứng minh phần “chỉ nếu”, ta cho U = {n | (B, n) Î X+}. Ta cần chỉ ra t≼CU. Vì F╞ X ®t B, nên với định lý 2.1 tồn tại tập {X ®tB,…, X ®tB} Í F+ sao cho t ≼C  {t 1,…, t m}. Cho V = {n | X ®n B Î F+}. Rõ ràng, {t 1,…, t m} Í V và t ≼C V. Dựa vào định nghĩa, U Í V và với "n Î V, $n ’ Î U sao cho n ≼ n ’. Vì t ≼C V, nên t ≼C U (chú ý rằng với bất kỳ tập các kiểu thời gian U ’ nào, n1 và n2 nào đó với n1 ≼ n2, mà t ≼C U ’ ∪ {n1,n2} thì suy ra t ≼C U ’ ∪ {n2}). Để chứng minh phần “nếu”, ta cần chứng minh rằng nếu {(B, t1),…, (B, tm)} Í X+, thì dựa vào định nghĩa, ta có X ®tB Î F+ với 1 £ i £ m, và dựa vào định nghĩa của F+ ta có được F├f  X ®tB. Vì ba tiên đề hệ quả hữu hạn được suy ra từ bốn tiên đề hệ quả cho các TFD, nên ta có F├ X ®tB. Mặt khác, dựa vào tiên đề thừa kế ta có F├ X ®t B. Như thế, dựa vào tính đầy đủ của bốn tiên đề hệ quả cho các TFD ta có F╞ X ®t B. □ Chứng minh định lý 2.3: Cho M = (R1 ∪ R2, t, f) là một môđun thời gian thỏa tất cả các TFD trong F. Cho (R1, t, f1) = p(M), (R2, t’, f2) = Up(p(M), t’) và k ³ 1. Ta chỉ cần chỉ ra rằng f(k) = f1(k) ⋈ f2(k’), với t(k) Í t’(k’), bởi vì điều này suy ra rằng phân tách là bảo toàn thông tin. Nếu t(k) = Æ, thì ta có f(k) = Æ và f1(k) = Æ. Vì thế f(k) = f1(k) ⋈ f2(k’). Bây giờ ta giả sử rằng t(k) ¹ Æ. Vì t ≼ t’ , nên tồn tại một số nguyên dương k’ sao cho t(k) Í t’(k’). Dựa vào định nghĩa dễ dàng thấy rằng f(k) Í f1(k) ⋈ f2(k’). Giờ ta giả sử rằng bộ t thuộc f1(k) ⋈ f2(k’). Tiếp theo ta chỉ cần chỉ ra rằng t cũng thuộc f(k). Vì t Î f1(k) ⋈ f2(k’), nên tồn tại t1 Î f1(k) và t2 Î f2(k’) sao cho t[R1] = t1 và t[R2] = t2. Theo định nghĩa, tồn tại t’1 Î f(k) sao cho t’1[R1] = t1 và tồn tại k’’ và t’2 Î f(k’’) sao cho t(k, k’’) Í t’(k’) và t’2[R2] = t2. Vì t(k, k’’) Í t’(k’), nên theo giả thiết ta biết rằng R1 Ç R2 ®R2 là thuộc pt(k, k’’)(F). Vì R1 Ç R2 Í R1 và R1 Ç R2 Í R2, nên ta có t’1[R1 Ç R2] = t1[R1 Ç R2] =  t[R1 Ç R2] = t2[R1 Ç R2] = t’2[R1 Ç R2]. Theo: t Î f(k) và t’2 Î f(k’’) và R1 Ç R2 ®R2 Î pt(k, k’’)(F) thì t’1[R2] = t’2[R2]. Kết hợp điều này với t[R1] = t1 = t’1[R1], ta có t[R1 ∪ R2] = t’1[R1 ∪ R2]; tức là t = t’1. Do đó t Î f(k). □ Chứng minh bổ đề 3.1. Cho a là một quan hệ thời gian với các cơ sở B1 và B2. Ta cần chứng minh rằng B1 = B2 bằng cách chỉ ra B1 Í B2 và B2 Í B1. Sau đây sẽ trình bày phần chứng minh B1 Í B2 còn B2 Í B1 được chứng minh tương tự. Theo định nghĩa ta có I Î B1 và I ¹ Æ. Cho a Î I ta có (a, a) Î a. Khi đó, $Ja Î B2 sao cho a Î Ja. Với "b Î I, nếu b > a thì (a, b) Î a, ngược lại thì (b, a) Î a. Do đó, b Î Ja. Vậy, $JI Î B2 sao cho I Í JI. Tương tự, $K Î B1 sao cho JI Í K. Ta có: I Í JI Í K. Vì I = K nên I = JI. Vậy B1 Í B2. □ Chứng minh mệnh đề 3.1. Với mỗi chronology a, ta có: (l, m) Î a khi và chỉ khi l, m Î (i) với i Î . Þ. Giả sử 1 bé hơn 2 và (l, m) Î a1. Ta cần chứng minh (l, m) Î a2: Ta có l, m Î 1(i) với i Î . Theo giả thiết, 1 bé hơn 2 nên 1(i) Í 2(j) với j Î . Vậy l, m Î 2(i) hay (l, m) Î a2. Ü. Giả sử a1 Í a2. Cho i Î , ta cần chứng minh rằng 1(i) Í 2(j) với j Î . Cho l, m Î 1(i) với l £ m. Khi đó, (l, l); (l, m); (m, m) Î a1. Theo giả thiết a1 Í a2 nên (l, l); (l, m); (m, m) Î a2. Vì vậy, cơ sở của a2 chứa {…, l, …, m, …}. Vậy l, m Î 2(j) với j Î . Như vậy, với i, l, m tùy ý ta có thể kết luận rằng 1 bé hơn 2. □