Tài liệu Cơ sở dữ liệu thời gian

- 1- MỤC LỤC HT TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU DANH MỤC CÁC BẢNG VÀ HÌNH VẼ .............................................................. 3 TH MỞ ĐẦU ................................................................................................................... 4 UT CHƯƠNG 1: TỔNG QUAN VỀ CSDL VÀ CSDL THỜI GIAN ....................... 6 UT 1.1- GIỚI THIỆU ....................................................................................................... 6 UT 1.2 NHẮC LẠI MỘT SỐ KHÁI NIỆM TRONG CSDL QUAN HỆ: ..................... 7 UT 1.3- CƠ SỞ DỮ LIỆU CÓ YẾU TỐ THỜI GIAN ................................................... 9 UT 1.3.1- Dữ liệu thời gian và một số khái niệm cơ bản: ................................................ 9 UT 1.3.2- Khái niệm về Thời gian hợp thức và Thời gian giao dịch: ............................ 11 UT 1.3.3- Các vấn đề về thời gian hoá: .......................................................................... 14 UT 1.3.3.1 - Bán thời gian hoá: ...................................................................................... 15 UT 1.3.3.1.1 - Các ràng buộc: ........................................................................................ 17 UT 1.3.3.1.2 - Truy vấn .................................................................................................. 17 UT 1.3.3.2 -Thời gian hóa toàn phần: ............................................................................ 18 UT 1.3.3.2.1 – Ràng buộc .............................................................................................. 21 UT 1.3.3.2.2 – Truy vấn: ............................................................................................... 23 UT 1.4- BIỂU DIỄN YẾU TỐ THỜI GIAN TRONG CSDL THỜI GIAN. ................ 24 UT 1.4.1- Khoảng thời gian ............................................................................................ 24 UT 1.4.2- Các kiểu khoảng: ............................................................................................ 26 UT 1.4.2- Toán tử vô hƣớng trên khoảng: ...................................................................... 29 UT 1.4.3- Các toán tử gộp nhập trên khoảng ................................................................. 31 UT 1.4.5- Ràng buộc trên các khoảng ............................................................................ 41 UT 1.4.6- Toán tử Update trên khoảng: ......................................................................... 46 UT CHƯƠNG 2: THIẾT KẾ CƠ SỞ DỮ LIỆU THỜI GIAN ................................. 48 UT 2.1- QUÁ TRÌNH THIẾT KẾ .................................................................................. 49 UT 2.1.1- Dƣ thừa dữ liệu và các dị thƣờng cập nhật .................................................... 51 UT 2.1.2- Chiều thời gian của thiết kế logic .................................................................. 52 UT 2.2. KIỂU VÀ MODUL THỜI GIAN: .................................................................... 54 Cơ sở dữ liệu thời gian UT - 2- TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU TU 2.2.1- Kiểu thời gian: ................................................................................................ 54 UT 2.2.2 - Module thời gian: .......................................................................................... 57 UT 2.3. PHỤ THUỘC HÀM THỜI GIAN: ................................................................... 59 UT 2.3.1 - Các tiên đề suy diễn cho TFDs: .................................................................... 61 UT 2.3.2 - Bao đóng của một tập các thuộc tính: ........................................................... 68 UT 2.4. CHUẨN HOÁ THỜI GIAN: ............................................................................ 70 UT 2.5. DẠNG CHUẨN BOYCE-CODD CÓ YẾU TỐ THỜI GIAN. ........................ 79 UT 2.5.1 Tách các lƣợc đồ module thời gian về dạng TBCNF: ..................................... 80 UT 2.6. BẢO TOÀN PHỤ THUỘC: ............................................................................. 86 UT 2.7. DẠNG CHUẨN BA CÓ YẾU TỐ THỜI GIAN .............................................. 88 UT 2.7.1 Tách lƣợc đồ module thời gian về dạng T3NF: .............................................. 89 UT CHƯƠNG 3: UT TU NGÔN NGỮ TRUY VẤN TSQL2 ........................................... 96 UT 3.1- GIỚI THIỆU ..................................................................................................... 96 UT 3.2- MỘT SỐ TÍNH NĂNG CẦN THIẾT CỦA NGÔN NGỮ TSQL2: ................ 97 UT 3.3- MỘT SỐ ĐẶC TẢ VỀ SỰ MỞ RỘNG CỦA TSQL2: .................................... 99 UT 3.4-VÍ DỤ MINH HOẠ. ........................................................................................ 102 UT 3.4.1 - Lƣợc đồ cho CSDL thử nghiệm. ................................................................. 102 UT 3.4.2 - Lƣợc đồ trong TSQL2 ................................................................................. 104 UT 3.4.3 - Cập nhật dữ liệu thử nghiệm. ...................................................................... 106 UT 3.4.4 - Một số truy vấn: .......................................................................................... 110 UT MỘT SỐ HƯỚNG NGHIÊN CỨU TIẾP THEO ............................................. 113 UT KẾT LUẬN ........................................................................................................... 117 UT TÀI LIỆU THAM KHẢO ................................................................................... 118 UT Cơ sở dữ liệu thời gian - 3- DANH MỤC CÁC BẢNG VÀ HÌNH VẼ TU TU CHƢƠNG 1: TỔNG QUAN VỀ CSDL VÀ CSDL THỜI GIAN ............................ 6 UT Bảng 1.1 CSDL Nhà cung cấp & Mặt hàng (Phiên bản dạng ảnh hiện tại) ..................................................................................... 9 UT TU Bảng 1.2 CSDL Nhà cung cấp & Mặt hàng (Phiên bản bán thời gian hoá với các giá trị đơn giản) ............................................. 15 UT TU Bảng 1.3 CSDL Nhà cung cấp & Mặt hàng (Phiên bản thời gian hoá toàn phần thứ nhất, Sử dụng các nhãn thời gian) ............. 19 UT TU Bảng 1.4 CSDL Nhà cung cấp & Mặt hàng (Phiên bản thời gian hoá toàn phần sau cùng , Sử dụng các khoảng) ...................... 25 UT TU TU TU TU TU TU TU TU TU TU TU TU CHƢƠNG 2: THIẾT KẾ CƠ SỞ DỮ LIỆU THỜI GIAN ...................................... 48 UT Hình 2.1 Quá trình thiết kế một CSDL ................................................................... 50 UT Hình 2.2: Ví dụ về quan hệ các khóa học. ................................................................ 52 UT Hình 2.3. Phép tách tự nhiên. ................................................................................... 53 UT Hình 2.4: Thuật toán tìm X + U PU UT TPU . ................................................................................. 69 UT Hình 2.5: Thuật toán tách về dạng chuẩn TBCNF. .................................................. 82 UT Hình 2.6. Hàm Raise ................................................................................................ 87 UT Hình 2.7 Thuật toán tách về dạng chuẩn T3NF. ..................................................... 93 UT CHƢƠNG 3: UT TU NGÔN NGỮ TRUY VẤN TSQL2 ............................................. 96 UT Bảng 3.1 - Nhanvien_Tbl ....................................................................................... 109 UT Bảng 3.2 - Kynang_Tbl .......................................................................................... 109 UT Bảng 3.3 - Phong_ban_Tbl ..................................................................................... 110 UT Cơ sở dữ liệu thời gian - 4- MỞ ĐẦU Hầu hết các ứng dụng kỹ thuật về cơ sở dữ liệu (CSDL) trong tự nhiên đều mang yếu tố thời gian. Ví dụ: các ứng dụng về tài chính nhƣ: quản lý đầu tƣ, kế toán, ngân hàng; các ứng dụng lƣu trữ hồ sơ nhƣ: quản lý nhân sự, hồ sơ bệnh án, quản lý kiểm kê, kiểm toán; các ứng dụng về lập lịch trong ngành đƣờng sắt, hàng không, đặt chỗ khách sạn; các ứng dụng khoa học nhƣ: dự báo thời tiết, thảm hoạ tự nhiên…v.v. Tất cả những ứng dụng đó đều dựa trên những CSDL ghi lại dữ liệu tham chiếu tới thời gian và đƣợc gọi là “CSDL có yếu tố thời gian” hay “CSDL thời gian” (Temporal Database). Với những ứng dụng rộng rãi trong mọi lĩnh vực đời sống, quản trị CSDL thời gian đƣợc xem là một lĩnh vực nghiên cứu đầy sức lôi cuốn, đã có hàng trăm nhà nghiên cứu với trên 2000 bài viết về vấn đề này trong suốt 2 thập kỷ qua. Việc xây dựng và ứng dụng một CSDL có yếu tố thời gian thành công mang một ý nghĩa rất quan trọng trong thực tiễn. Một CSDL thời gian phải phản ánh hay biểu diễn đƣợc một cách chân thực nhất, chính xác nhất về dữ liệu tại mọi thời điểm. Một hệ quản trị CSDL có yếu tố thời gian sẽ quản lý những dữ liệu tham chiếu tới thời gian (Time-referenced data), do đó các yếu tố thời gian gắn liền với các thực thể trong CSDL. Nói một cách không chặt chẽ, cơ sở dữ liệu (CSDL) thời gian là một CSDL bao gồm dữ liệu mang tính lịch sử thay vì dữ liệu hiện tại. Một vài trong số những nghiên cứu này đã thừa nhận một quan điểm cực đoan là dữ liệu trong một CSDL đó chỉ đƣợc chèn (Insert), không bao giờ xoá (Delete) hoặc đƣợc cập nhật (Update), trong trƣờng hợp đó CSDL chỉ bao gồm dữ liệu mang tính lịch sử. Ở một thái cực khác là một CSDL dạng ảnh, chỉ bao gồm dữ liệu hiện tại và dữ liệu đã đƣợc xóa hoặc cập nhật khi các sự kiện biểu diễn bởi dữ liệu không còn đúng (hay nói cách khác, một CSDL dạng ảnh chỉ là một CSDL nhƣ cách hiểu thông thƣờng, chứ không phải là CSDL biểu thị thời gian). Cơ sở dữ liệu thời gian - 5- Trong quá trình lƣu trữ và thao tác trên CSDL thì giá trị của một số thuộc tính ổn định theo thời gian, nhƣng với một số thuộc tính khác thì giá trị của chúng lại thay đổi theo thời gian. Luận văn này nghiên cứu, hệ thống lại khái niệm về mô hình dữ liệu quan hệ có yếu tố thời gian kéo theo các phép toán đại số, mở rộng các phụ thuộc hàm và các dạng chuẩn có yếu tố thời gian. Trong thực tế, chúng ta sẽ gặp phải rất nhiều khó khăn khi quản trị CSDL thời gian bằng những mô hình dữ liệu và các ngôn ngữ truy vấn thông thƣờng (không mang yếu tố thời gian). Từ những khái niệm cơ sở về CSDL thời gian, luận văn tập trung vào nghiên cứu và trình bày cách giải quyết một số vấn đề liên quan nhƣ:  Biểu diễn yếu tố thời gian trong CSDL.  Xây dựng những mô hình CSDL thời gian, thêm yếu tố thời gian vào ngôn ngữ truy vấn và chuẩn hoá các lệnh truy vấn.  Thiết kế CSDL thời gian ở mức Logic và Khái niệm.  Xử lý các câu lệnh truy vấn, các toán tử đại số, các chỉ mục (index) trên CSDL thời gian. Bản luận văn đƣợc chia thành bốn phần. Phần thứ nhất nhắc lại một số khái niệm cơ bản về CSDL quan hệ, tiếp theo đó tập trung vào giới thiệu những nét tổng quan về CSDL thời gian, những thuật ngữ cũng nhƣ những cơ sở để tiếp cận với CSDL thời gian. Trong phần thứ hai, luận văn đi sâu vào việc nghiên cứu cách xây dựng, thiết kế những CSDL có yếu tố thời gian, những vấn đề liên quan đến phụ thuộc hàm thời gian, các dạng chuẩn thời gian và những thuật toán tách lƣợc đồ module thời gian về các dạng chuẩn. Để có những minh hoạ rõ nét và cụ thể hơn về CSDL thời gian, phần ba sẽ giới thiệu ngắn ngọn về ngôn ngữ truy vấn thời gian (TSQL2) thông qua một ví dụ cụ thể. Phần cuối của luận văn là phần nhận xét, kết luận và một số hƣớng nghiên cứu tiếp theo. Cơ sở dữ liệu thời gian - 6- U CHƢƠNG 1 : TỔNG QUAN VỀ CSDL VÀ CSDL THỜI GIAN U 1.1- GIỚI THIỆU Một CSDL là một tập hợp các dữ liệu có liên quan với nhau chứa thông tin về một tổ chức nào đó (nhƣ một trƣờng đại học, một ngân hàng, một công ty, hay một nhà máy…), đƣợc lƣu trữ trên các thiết bị nhớ thứ cấp (nhƣ đĩa từ, đĩa quang học…) để đáp ứng nhu cầu khai thác thông tin của nhiều ngƣời sử dụng với nhiều mục đích khác nhau. Do đó, trƣớc hết CSDL phản ánh đƣợc thông tin về hoạt động của một tổ chức nhất định, nghĩa là biểu thị một “góc” của thế giới thực (tạm gọi là một thế giới nhỏ). Nhƣ vậy CSDL cũng phải phản ánh đƣợc một cách trung thực sự thay đổi của thế giới nhỏ đó, nó phải tập hợp thông tin mang tính hệ thống chứ không thể là một tập hợp dữ liệu tuỳ tiện chứa những thông tin rời rạc không có mối quan hệ với nhau. Thông tin lƣu trữ trong CSDL đƣợc chia sẻ cho nhiều ngƣời sử dụng hay cho nhiều ứng dụng khác nhau. Từ đó cho thấy việc thiết kế, xây dựng một CSDL phản ánh thế giới nhỏ đó một cách khách quan, chân thực và chính xác đã trở thành một nhu cầu tất yếu. Từ những năm 80 của thế kỷ hai mƣơi, các hệ CSDL dựa trên mô hình quan hệ đƣợc sử dụng một cách rộng rãi bởi tính đơn giản và các cơ sở toán học của nó. Tuy nhiên cũng giống nhƣ những các hệ CSDL thông thƣờng, CSDL quan hệ cũng chỉ biểu thị đƣợc những dữ liệu ở dạng tĩnh (dạng ảnh) với mỗi sự kiện của thực thể tƣơng ứng. Trong một CSDL dạng ảnh, yếu tố thời gian của bức ảnh thông thƣờng đƣợc xem là thời điểm hiện tại (nghĩa là thời gian khi mà CSDL thực sự đƣợc xem xét. Ngay cả khi yếu tố thời gian của CSDL dạng ảnh đôi khi diễn ra khác với “hiện tại”, điều đó không tạo ra sự khác biệt nào đáng kể đến cách quản lý và sử dụng dữ liệu. Tuy nhiên, nhƣ chúng ta sẽ thấy dữ liệu trong một CSDL thời gian đƣợc quản lý và sử dụng rất khác trong hàng loạt phƣơng diện quan trọng so với cách nó đƣợc quản lý và sử dụng trong một CSDL dạng ảnh; điều này đƣợc xem là phần quan trọng nhất và sẽ đƣợc trình bày cụ thể sau phần nhắc lại một số những khái niệm cơ bản về CSDL quan hệ. Cơ sở dữ liệu thời gian - 7- 1.2 NHẮC LẠI MỘT SỐ KHÁI NIỆM TRONG CSDL QUAN HỆ: Mô hình quan hệ biểu thị dữ liệu trong một CSDL nhƣ là một bảng giá trị gồm các hàng và các cột. Mỗi hàng trong bảng là một tập các giá trị có liên quan đến nhau, các giá trị này biểu thị một sự kiện tƣơng ứng với một thực thể hay một mối quan hệ trong thế giới thực [1].  Miền (Domain): Một miền D là một tập hợp các giá trị nguyên tố, hiểu theo nghĩa mỗi giá trị trong miền không thể phân chia trong phạm vi mô hình quan hệ.  Quan hệ (Relation): Một quan hệ trên một tập các thuộc tính là một tập con của tích Đềcác của một hay nhiều miền: Cho một quan hệ r xác định trên tập thuộc tính Ω = {A 1 , A 2 ,…,A n }. Khi đó B B B B B B r ⊆ Dom(A 1 ) × Dom(A 2 ) × …. × Dom(A n ), trong đó Dom(A i ) là miền của B B B B B B B B thuộc tính A i , là tập các giá trị có thể của nó. B B  Lược đồ quan hệ (Relation schema): Một lƣợc đồ quan hệ R là một cặp có thứ tự R = <Ω, F>, trong đó Ω là tập hữu hạn các thuộc tính của quan hệ, F là tập các điều kiện giữa các thuộc tính (F còn gọi là tập các ràng buộc toàn vẹn).  Siêu khoá của một lƣợc đồ quan hệ R là một tập hợp gồm một hay nhiều thuộc tính của lƣợc đồ R có tính chất xác định duy nhất một bộ trong mỗi thể hiện của R.  Khoá của một lƣợc đồ quan hệ là một siêu khoá của lƣợc đồ này sao cho mọi tập con thực sự của nó không là một siêu khoá.  Khoá ngoài của một lƣợc đồ quan hệ là tập hợp gồm một hay nhiều thuộc tính là khoá của một lƣợc đồ quan hệ khác.  Phụ thuộc hàm: Cho U là một tập thuộc tính và R(U) là một lƣợc đồ quan hệ trên U. Giả sử X, Y ⊆U. Khi đó, Y đƣợc gọi là phụ thuộc hàm vào X trên lƣợc đồ R(U), ký hiệu là X Y, nếu với mọi quan hệ r trên lƣợc đồ R(U), với hai bộ bất kỳ t 1 , t 2 ∈ r, mà t 1 [X] = t 2 [X] thì t 1 [Y] = t 2 [Y]. B B B B Cơ sở dữ liệu thời gian B B B B B B B B - 8-  Bao đóng: Ta gọi bao đóng của tập hợp phụ thuộc hàm F là tập các phụ thuộc hàm đƣợc suy diễn logic từ F và ký thiệu nó là F*. Hay nói một cách hình thức: F*= { X  Y | F ⊨ (X  Y) }.  Khoá: Giả sử U là một tập thuộc tính, R là một lƣợc đồ quan hệ trên U thỏa một tập phụ thuộc hàm F, K là một tập con của U. Ta nói K là một khoá của R nếu: o (K  U) ∈ F*, nghĩa là với mọi quan hệ r của lƣợc đồ R, hai bộ bất kỳ của r bằng nhau trên K thì bằng nhau. (r ∈ R) (t 1 , t 2 ∈ r) B B B B t 1 [K] = t 2 [K]  t 1 = t 2 . B B B B B B B B o Nếu K‟ là tập con thực sự của K thì (K‟ U) ∉ F*  Hệ tiên đề suy diễn Armstrong: o Phản xạ: Nếu Y ⊆ X thì X  Y o Gia tăng: Nếu X  Y thì với mọi Z ⊆ U : XZ  YZ o Bắc cầu: Nếu X  Y và Y  Z thì X  Z  Phép tách với kết nối không mất thông tin: Phép tách R thành {R 1 , B B R 2 ,...,R 3 } đƣợc gọi là tách không mất thông tin đối với tập phụ thuộc hàm F, B B B B nếu với mỗi quan hệ r trên R thoả mãn F, ta đều có r = r 1 * r 2 *....* r k , trong B B B B B B đó r i = U i (r) (r i là kết quả của phép chiếu r trên U i ). B B B B B B B B  Dạng chuẩn 3NF: Lƣợc đồ quan hệ R đƣợc gọi là thuộc dạng chuẩn ba (3NF) nếu nó thuộc dạng chuẩn thứ nhất và với mọi X  A đúng trên R thì hoặc X phải là siêu khoá hoặc A phải là thuộc tính khoá  Dạng chuẩn BCNF: Lƣợc đồ quan hệ R chuẩn hóa với tập phụ thuộc hàm F đƣợc gọi là thuộc dạng chuẩn BCNF nếu có X  A đúng trên lƣợc đồ R và A ∉ X thì X chứa một khoá của R (nói cách khác, X là siêu khoá). Cơ sở dữ liệu thời gian - 9- 1.3- CƠ SỞ DỮ LIỆU CÓ YẾU TỐ THỜI GIAN 1.3.1- Dữ liệu thời gian và một số khái niệm cơ bản: Trƣớc khi bắt đầu xem xét tới các mô hình dữ liệu thời gian và những ngôn ngữ truy vấn, chúng ta sẽ nghiên cứu những khái niệm độc lập với mô hình dữ liệu, sự gắn kết của yếu tố thời gian với các sự kiện, đó là vấn đề cốt lõi của quản lý dữ liệu thời gian. Trong chƣơng này chúng ta sẽ sử dụng một CSDL đơn giản về “Nhà cung cấp & Mặt hàng” để giải thích và minh hoạ những vấn đề liên quan đến CSDL thời gian. Bảng 1.1 CSDL Nhà cung cấp & Mặt hàng (Phiên bản dạng ảnh hiện tại) (Các thuộc tính là khoá chính trong các ví dụ đƣợc in đậm và gạch chân ) U S: TENCONGTY TRANGTHAI VinhTrinh 20 CMC 10 HaiAn 30 VinaComm 20 Hanel 30 S# S1 S2 S3 S4 S5 SP: S# S1 S1 S1 S1 S1 S1 S2 S2 S3 S4 S4 S4 U U P# P1 P2 P3 P4 P5 P6 P1 P2 P2 P2 P4 P5 U U Cơ sở dữ liệu thời gian DIACHI HaNoi SaiGon SaiGon HaNoi DaNang U - 10 - U Chú ý: mỗi bộ trong bảng S thể nhiện: “Nhà cung cấp có số hiệu S#, có tên U là TENCONGTY, có tình trạng là TRANGTHAI và có trụ sở tại địa chỉ là DIACHI”; mỗi bộ trong bảng SP minh hoạ nhà cung cấp S# hiện tại có khả năng cung ứng mặt hàng P#. Tất nhiên CSDL này là một CSDL dạng ảnh, và nó chỉ ra rằng trong số các nhà cung cấp thì giá trị trạng thái hiện tại của S1 là 20. Một cách tƣơng phản, phiên bản mang yếu tố thời gian của CSDL đó có thể chỉ ra không chỉ giá trị trạng thái hiện tại là 20, mà nó còn chỉ ra rằng giá trị này đƣợc thiết lập từ ngày 1 tháng 7 và có thể giá trị đó là 15 từ ngày 5-04 đến 30-06 ...v.v. Hiển nhiên, đặc điểm nổi bật của CSDL thời gian là chính yếu tố thời gian. Do đó trong số các nghiên cứu về CSDL thời gian có nhiều khảo cứu về chính bản chất của thời gian và một vài vấn đề sau đã đƣợc nghiên cứu thấu đáo:  Liệu thời gian có điểm đầu cũng như điểm kết thúc?  Thời gian là liên tục hay xuất hiện theo những lượng rời rạc?  Việc mô tả khái niệm quan trọng: “hiện tại” (now) tốt đến mức nào? Những vấn đề này tuy rất thú vị nhƣng không đơn thuần thuộc về khía cạnh CSDL, và do vậy chúng ta sẽ không đi sâu vào xem xét trong chƣơng này. Thay vào đó, ta đƣa ra các giả định hợp lý tại những chỗ thích hợp. Cách tiếp cận này cho phép ta tiếp cận mục đích ban đầu một cách trực tiếp hơn. Tuy nhiên ta cũng chú ý rằng, các nghiên cứu về thời gian dẫn tới một số kết luận thú vị, nêu lên ý tƣởng phát triển dữ liệu thời gian cũng có thể có các ứng dụng trong nhiều lĩnh vực khác. Xuyên suốt chƣơng này, ta vẫn sử dụng khóa thời gian, toán tử thời gian, quan hệ thời gian, mặc dù các khái niệm này không giới hạn chỉ trong dữ liệu thời gian. Sau đây ta chỉ tập trung vào những vấn đề chúng ta quan tâm và quan trọng nhất của rất nhiều ý tƣởng nghiên cứu (nói cách khác, trong chƣơng này chúng ta sẽ chắt lọc những phần hay (chất lƣợng) của các nghiên cứu thông qua các vấn đề về các thuật ngữ và những vấn đề nhỏ khác).  Dữ liệu thời gian [2]: (Temporal data) Nếu dữ liệu là một cách biểu diễn mã hóa của các sự kiện, thì dữ liệu thời gian là biểu diễn mã hoá của các sự kiện Cơ sở dữ liệu thời gian - 11 - có nhãn thời gian (timestamps). Trong một CSDL thời gian, theo cách giải thích cực đoan của thuật ngữ này, tất cả dữ liệu đều mang tính thời gian, nghĩa là mọi bản ghi thực tế là các nhãn thời gian.  Quan hệ thời gian: (Temporal relation) Một quan hệ thời gian là một quan hệ mà trong mỗi bộ dữ liệu bao gồm ít nhất một nhãn thời gian (nghĩa là phần mô tả bao gồm tối thiểu một thuộc tính có kiểu nhãn thời gian).  Biến quan hệ thời gian: (Temporal relvar 1 ) là một quan hệ mà phần mô tả P P của nó là mô tả một quan hệ mang tính thời gian.  CSDL thời gian: là một CSDL mà trong đó mọi biến quan hệ đều là thời gian. CSDL thời gian quản lý những dữ liệu tham chiếu tới thời gian, do đó các yếu tố thời gian gắn liền với những thực thể trong CSDL. 1.3.2- Khái niệm về Thời gian hợp thức và Thời gian giao dịch: Những nghiên cứu trong thập kỷ trƣớc về CSDL thời gian chỉ ra một vấn đề hóc búa. Dữ liệu thay đổi theo thời gian (Time-varying data) đƣợc xem là rất đơn giản: nó có thể có nhiều hơn một giá trị, mỗi giá trị ứng với mỗi khoảng thời gian, nhƣng việc thiết kế một mô hình dữ liệu thời gian đúng là vô cùng phức tạp. Đã có rất nhiều mô hình dữ liệu thời gian, tính tới nay đã có khoảng trên 40 mô hình đƣợc trình bày trong những tài liệu, và chắc chắn sẽ còn nhiều hơn thế. Do vậy chúng ta sẽ làm thế nào để nắm đƣợc bản chất của dữ liệu thời gian. Các học giả đã từ lâu công nhận sự lƣỡng phân (dichotomy) và tính đối ngẫu (duality) giữa những sự kiện (events) và trạng thái (states). Một trạng thái là cái gì đó mà nó đúng (true) về một đối tƣợng trong một khoảng thời gian, nhƣng không đúng trong các khoảng thời gian trƣớc đó và sau đó. Một sự kiện đƣợc xem là một điều gì đó “xảy ra” (happen). Các sự kiện phân định các trạng thái. Với ví dụ Bảng 1.1 ở trên, ta sẽ xem xét một số cách diễn đạt tự nhiên liên quan đến nhãn thời gian nhƣ sau: 1 TP PT Relvar là viết tắt của Relation Variable Cơ sở dữ liệu thời gian - 12 - 1. Nhà cung cấp S1 được chọn (nghĩa là được ký kết hợp đồng) vào ngày 01-07-1999. 2. Nhà cung cấp S1 trở thành nhà cung cấp được ký kết hợp đồng từ ngày 01-07-1999. 3. Nhà cung cấp S1 là một nhà cung cấp được ký kết hợp đồng trong khoảng thời gian từ 01-07-1999 đến nay. Mỗi phát biểu đó là một sự lý giải có thể của một bộ hai giá trị bao gồm nhà cung cấp số hiệu S1 và nhãn thời gian 01-07-1999, và mỗi phát biểu trong số đó có thể là thích hợp cho một bộ nếu nó xuất hiện trong CSDL dạng ảnh biểu diễn một trạng thái hiện tại về hoạt động của một doanh nghiệp nào đó. Bây giờ mặc dù chúng ta mới nói tới 3 cách lý giải có thể, nhƣng vẫn có những tranh cãi cho rằng phát biểu 1, 2 và 3 là thực sự nói về cùng một điều bằng các cách nói với những khác biệt nhỏ. Thực tế, ta có thể xem phát biểu 2 và 3 là tƣơng đƣơng, tuy nhiên phát biểu 1 và 2 (hoặc 1 và 3) là không, cân nhắc một số vấn đề sau:  Phát biểu 1 khẳng định rõ ràng rằng S1 không trở thành nhà cung cấp trƣớc ngày 01/07/1999, tức là ngày 30/06/1999 chẳng hạn, trong khi phát biểu 2 không nói gì về sự kiện đó cũng nhƣ không suy ra sự kiện đó.  Giả sử rằng hôm nay là 25/09/2000, phát biểu 2 nói rằng S1 là nhà cung cấp trong mọi ngày từ 01/07/1999 tới 25/09/2000, trong khi phát biểu 1 không nói gì về sự kiện đó cũng nhƣ không suy ra sự kiện đó. Do đó, phát biểu 1 và 2 là không tƣơng đƣơng nhau, và không phát biểu nào suy ra đƣợc phát biểu kia. Điều đó nghĩa là, các bộ dữ liệu trong các CSDL dạng ảnh thƣờng bao gồm những yếu tố nhƣ ngày tháng của một thời điểm, và các phát biển nhƣ phát biểu 2 hoặc 3 thƣờng là dành cho việc giải thích. Nếu là trƣờng hợp này thì phát biểu 1 ở dạng hiện tại của nó là không lý giải chính xác, đầy đủ về bộ dữ liệu đang xét. Chúng ta có thể làm chính xác hơn bằng cách phát biểu lại nó nhƣ sau: Nhà cung cấp S1 đã hầu nhƣ đƣợc chọn ký hợp đồng vào 01-07-1999. Điều gì thêm vào đó, nếu phiên bản này của phát biểu 1 thực sự là điều giả thiết của chúng ta về bộ Cơ sở dữ liệu thời gian - 13 - hai giá trị đƣợc giả sử mang ý nghĩa. Do đó phát biểu 2 ở dạng hiện tại của nó cũng không đƣợc hiểu một cách hoàn toàn chính xác – nó cần phải đƣợc phát biểu lại nhƣ sau: “Nhà cung cấp S1 không phải là nhà cung cấp chính thức vào ngày 30-06-1999, mà chỉ bắt đầu từ ngày 01-07-1999.” Nhận thấy rằng phát biểu 1 diễn tả một thời điểm mà một sự kiện nào đó xảy ra trong khi phát biểu 2 và 3 diễn tả trong một khoảng thời gian trong đó một trạng thái xác định tiếp tục tồn tại. Chúng ta đã cân nhắc thận trọng lựa chọn một ví dụ, trong đó một trạng thái xác định có thể đƣợc suy diễn ra từ thông tin về một sự kiện nhất định: Kể từ khi S1 đƣợc lựa chọn chính thức lần gần nhất vào 01-07-1999, nhà cung cấp đó đã có trạng thái là đang ký hợp đồng kể từ ngày đó đến ngày hiện tại. Thực tế cho thấy những kỹ thuật CSDL cũ quản lý các thời điểm xảy ra sự kiện khá tốt, tuy nhiên chúng không quản lý tốt các khoảng thời gian. Điều tiếp theo nhận thấy rằng, mặc dù phát biểu 2 và 3 là tƣơng đƣơng về mặt lôgic, nhƣng dạng thức của chúng lại khác nhau đáng kể. Cụ thể là dạng của phát biểu 2 không thể sử dụng để ghi lại sự kiện của quá khứ (bởi vì “từ” hàm ý đến hiện tại), trong khi dạng của phát biểu 3 lại có thể- với điều kiện là chúng ta thay thế cụm từ “ngày hiện tại” trong câu đó bởi một ngày chính xác nào đó nhƣ 25-092000. (Tất nhiên, câu đó sẽ tƣơng ứng với một bộ ba chứ không phải bộ hai). Ta kết luận rằng: khái niệm “trong khoảng” là rất quan trọng với những bản ghi mang tính lịch sử, ít nhất là với dữ liệu trạng thái nếu không phải là với dữ liệu sự kiện. Có hai loại thời gian trong CSDL thời gian và việc hiểu chính xác đƣợc khái niệm của hai loại thời gian này là vấn đề rất quan trọng. Thuật ngữ [2]:  Thời gian hợp thức (Valid time): Những thời điểm mà tại đó một sự kiện nào đó xảy ra hoặc các khoảng thời gian trong đó tồn tại một trạng thái xác định đƣợc gọi là thời gian hợp thức. Chính xác hơn là thời gian hợp thức của một mệnh đề p là tập các thời điểm tại đó p đƣợc tin là true. Cơ sở dữ liệu thời gian - 14 -  Thời gian giao dịch (Transaction time): là một tập các thời điểm mà tại đó p đã đƣợc thực sự biểu diễn là true trong CSDL. - Thời gian hợp thức có thể đƣợc cập nhật để phản ánh những niềm tin thay đổi, nhƣng thời gian giao dịch thì không thể; đó là do thời gian giao dịch đƣợc quản lý hoàn toàn bởi hệ thống, và không có ngƣời dùng nào đƣợc phép thay đổi chúng bằng bất kỳ cách nào (điển hình là đƣơng nhiên chúng đƣợc ghi lại, ẩn hoặc tƣờng minh, trong nhật ký giao dịch (transaction log)). - Mặc dù mọi sự kiện đều có một thời gian hợp thức nhƣng thời gian hợp thức của một sự kiện có thể không nhất thiết dƣợc ghi lại trong CSDL (có thể do không nhận ra hoặc không liên quan đến ứng dụng). - Thời gian giao dịch có thể đƣợc gắn với bất kỳ thực thể nào trong CSDL chứ không phải chỉ gắn với các sự kiện. Cho dù mọi thực thể đều có thể đƣợc gán cho một thời gian giao dịch nhƣng ngƣời thiết kế CSDL có thể thiết kế chỉ cho một số các thực thể cần thiết. Khía cạnh thời gian giao dịch của một thực thể CSDL có khoảng thời gian tồn tại từ phép chèn (insertion) cho đến phép xoá (detetion), và do ngữ nghĩa của thời gian giao dịch phép xoá là xoá về lôgic chứ không phải là xoá vật lý, mà chỉ thôi không còn là một phần trạng thái hiện tại của CSDL. 1.3.3- Các vấn đề về thời gian hoá: Bây giờ ta tiếp tục thảo luận về một số ràng buộc đơn giản và truy vấn cho CSDL về Nhà cung cấp & Mặt hàng trong Bảng 1.1, tiếp theo ta sẽ xem xét điều gì sẽ xảy ra với những ràng buộc và truy vấn khi CSDL đƣợc mở rộng để bao gồm những yếu tố đặc trƣng thời gian khác nhau.  Ràng buộc (CSDL dạng ảnh hiện tại): Các ràng buộc mà chúng ta xem xét ở đây là các ràng buộc về khóa (key constraints). Thuộc tính in đậm và gạch chân trong Bảng 1.1 đƣợc sử dụng để biểu diễn rằng {S#} và {S#,P#} theo thứ tự là khóa chính của S và SP. {S#} là một khóa ngoài trong SP tham chiếu tới khóa chính của S. {P#} trong SP có thể là một khoá ngoài tham chiếu tới khoá Cơ sở dữ liệu thời gian - 15 - chính của một biến quan hệ “mặt hàng”, P, nhƣng chúng ta không muốn dùng biến quan hệ đó trong ví dụ đơn giản này.  Truy vấn (ảnh hiện tại): Ta chỉ xem xét 2 truy vấn mà cả 2 đều đƣợc thể hiện rất đơn giản:  Truy vấn 1.1: Lọc ra số hiệu của các nhà cung cấp đang cung ứng một loại hàng nào đó. SP{S#}  Truy vấn 1.2: Lọc ra số hiệu của các nhà cung cấp hiện đang không có khả năng cung ứng một loại hàng nào: S{S#} MINUS SP{S#} Xét thấy rằng truy vấn 1.1 gồm một phép chiếu đơn giản và truy vấn 1.2 là hiệu của hai phép chiếu đơn giản đó. Phần tiếp theo ta sẽ xem xét tính tƣơng tự thời gian (temporal analogs) của hai truy vấn này và sẽ thấy rằng chúng có liên hệ với hai toán tử đó. 1.3.3.1 – Bán thời gian hoá: Để tiến hành một cách thận trọng, bƣớc tiếp theo của chúng ta là thực hiện bán thời gian hoá các biến quan hệ S và SP bằng cách thêm vào một thuộc tính nhãn thời gian, SINCE, với mỗi biến quan hệ S và SP và đổi tên chúng một cách phù hợp nhƣ trong Bảng 1.2 dƣới đây : Bảng 1.2 CSDL Nhà cung cấp & Mặt hàng (Phiên bản bán thời gian hoá với các giá trị đơn giản) S: S# TENCONGTY TRANGTHAI DIACHI SINCE S1 VinhTrinh 20 HaNoi d04 S2 CMC 10 SaiGon d07 S3 HaiAn 30 SaiGon d03 S4 VinaComm 20 HaNoi d04 S5 Hanel 30 DaNang d02 U U Cơ sở dữ liệu thời gian - 16 - SP: U S# U U P# U SINCE S1 P1 d04 S1 P2 d05 S1 P3 d09 S1 P4 d05 S1 P5 d04 S1 P6 d06 S2 P1 d08 S2 P2 d09 S3 P2 d08 S4 P2 d06 S4 P4 d04 S4 P5 d05 Để cho đơn giản, chúng ta sẽ không thể hiện các nhãn thời gian thực trong Bảng 1.2; thay vào đó ta dùng ký hiệu dƣới dạng d01, d02…., trong đó d có thể theo quy ƣớc đọc là “ngày”, một quy ƣớc đƣợc sử dụng trong suốt chƣơng này. (Các ví dụ của chúng ta do đó tất cả đều sử dụng các điểm thời gian đặc biệt đó là ngày). Ta giả sử rằng “ngay 01” là ngày ngay trƣớc “ngay 02”, “ngay 02” là ngày ngay trƣớc “ngay 03” và tuần tự nhƣ vậy. Tân từ đối với S_SINCE là kể từ ngày SINCE thì nhà cung cấp S# đƣợc đặt tên là TENCONGTY, có một trạng thái là TRANGTHAI, và có trụ sở tại thành phố DIACHI đã đƣợc ký kết hợp đồng chính thức. Tân từ đối với SP_SINCE là kể từ ngày SINCE thì nhà cung cấp S# có khả năng cung cấp mặt hàng P#. Cơ sở dữ liệu thời gian - 17 - 1.3.3.1.1 Các ràng buộc: Khoá chính và khoá ngoài của cơ sơ dữ liệu bán thời gian hoá này vẫn nguyên nhƣ trƣớc. Tuy nhiên, chúng ta cần thêm một ràng buộc nữa – có thể đƣợc xem nhƣ là sự bổ sung cho ràng buộc khoá ngoài từ SP_SINCE tới S_SINCE để biểu thị sự kiện là không có nhà cung cấp nào có thể cung cấp bất kỳ mặt hàng nào trƣớc khi nhà cung cấp đó đƣợc ký kết chính thức. Hay nói cách khác, nếu bộ sp trong SP_SINCE tham chiếu tới bộ giá trị s trong S_SINCE, thì giá trị SINCE trong sp không đƣợc nhỏ hơn trong s: CONSTRAINT AUG_SP_TO_S_FK IS_EMPTY (((S_SINCE RENAME SINCE AS SS) JOIN (SP_SINCE RENAME SINCE AS SPS)) WHERE SPS < SS); Với ví dụ này chúng ta bắt đầu nhận thấy vấn đề. Cho trƣớc một CSDL bán thời gian nhƣ Bảng 1.2, chúng ta sẽ có thể phải phát biểu nhiều ràng buộc “khoá ngoài đƣợc bổ sung” nhƣ vậy, và điều ta mong muốn là có đƣợc một phƣơng pháp nhanh chóng thuận tiện cho mục tiêu của chúng ta. 1.3.3.1.2 Truy vấn Bây giờ chúng ta sẽ xem xét phiên bản “bán thời gian” của truy vấn 1.1 và 1.2:  Truy vấn 2.1: Lọc ra số hiệu của các nhà cung cấp mà đang cung ứng loại hàng nào đó, chỉ ra trong mỗi trƣờng hợp ngày nào nhà cung cấp đó có thể cung ứng. Nếu nhà cung cấp Sx hiện tại có thể cung cấp vài mặt hàng, thì Sx có khả năng cung cấp sớm nhất kể từ ngày SINCE chỉ thị cho Sx trong SP_SINCE (ví dụ, nếu Sx là S1, ngày sớm nhất SINCE là d04). Do đó: SUMMARIZE SP PER SP{S#} ADD MIN (SINCE) AS SINCE sẽ cho kết quả là: Cơ sở dữ liệu thời gian - 18 - S# SINCE S1 d04 S2 d08 S3 d08 S4 d04 U U  Truy vấn 2.2: Lọc ra số hiệu của các nhà cung cấp mà hiện không thể cung ứng bất kỳ loại hàng nào, chỉ ra trong mỗi trƣờng hợp ngày nào nhà cung cấp đó không thể cung ứng. Trong dữ liệu đơn giản của chúng ta chỉ có một nhà cung cấp hiện không cung cấp đƣợc mặt hàng nào đó là S5. Tuy nhiên ta không thể suy đƣợc ngày nào S5 đƣợc ký hợp đồng nhƣng không cung cấp đƣợc mặt hàng nào, bởi vì thông tin trong CSDL là không đầy đủ và vẫn chỉ là đƣợc bán thời gian hoá. Ví dụ giả sử ngày hiện tại là d10: thì S5 đã có thể cung cấp ít nhất một mặt hàng kể từ ngày d02, khi S5 đƣợc ký kết ít nhất cho tới ngày d09; hoặc cho tới một thái cực khác, có thể là S5 chƣa từng bao giờ cung ứng mặt hàng nào. Để trả lời cho truy vấn 2.2, ta phải hoàn thiện việc “thời gian hoá” CSDL của chúng ta, hoặc chí ít là phần SP của nó. Để cho chính xác hơn, ta phải lƣu những bản ghi có tính lịch sử trong CSDL để chỉ ra rằng nhà cung cấp nào là có thể cung ứng mặt hàng nào, khi nào nhƣ trong phần tiếp theo đây. 1.3.3.2 -Thời gian hóa toàn phần: Bảng 1.3 mô tả một phiên bản thời gian hoá hoàn toàn về CSDL các Nhà cung cấp & Mặt hàng mà chúng ta đang nghiên cứu. Nhận thấy rằng các thuộc tính SINCE đã trở thành thuộc tính FROM, và mỗi biến quan hệ thời gian có thêm một thuộc tính nhãn thời gian --gọi là TO. Thuộc tính FROM và TO cùng biểu diễn một khái niệm của một khoảng thời gian mà trong đó một điều gì đó là đúng; do vậy ta Cơ sở dữ liệu thời gian - 19 - thay tên biến quan hệ SINCE bằng FROM_TO. Vì hiện tại chúng ta đang lƣu trữ các bản ghi mang tính lịch sử, do đó có nhiều bộ dữ liệu trong cở sở dữ liệu hơn là các phiên bản trƣớc. Để xác định ta giả sử rằng ngày hiện tại là ngày d10, nên d10 xem nhƣ là giá trị TO cho mỗi bộ gắn liền với trạng thái hiện tại của mỗi sự vụ. Chú ý là: Bạn có thể băn khoăn bằng kỹ thuật nào để thay thế toàn bộ những giá trị d10 đó thành d11 vào đúng lúc nửa đêm. Chúng ta sẽ tạm đặt vấn đề này sang một bên và sẽ quay trở lại trong các phần sau. Bảng 1.3 CSDL Nhà cung cấp & Mặt hàng (Phiên bản thời gian hoá toàn phần thứ nhất, Sử dụng các nhãn thời gian) S_FROM_TO: U S# TENCONGTY TRANGTHAI DIACHI FROM TO U U U S1 VinhTrinh 20 HaNoi d04 d10 S2 CMC 10 SaiGon d07 d10 S2 CMC 10 SaiGon d02 d04 S3 HaiAn 30 SaiGon d03 d10 S4 VinaComm 20 HaNoi d04 d10 S5 Hanel 30 DaNang d02 d10 Cơ sở dữ liệu thời gian - 20 - SP_FROM_TO: U S# U U P# U U FROM TO U S1 P1 d04 d10 S1 P2 d05 d10 S1 P3 d09 d10 S1 P4 d05 d10 S1 P5 d04 d10 S1 P6 d06 d10 S2 P1 d02 d04 S2 P2 d03 d03 S2 P1 d08 d10 S2 P2 d09 d10 S3 P2 d08 d10 S4 P2 d06 d09 S4 P4 d04 d08 S4 P5 d05 d10 CSDL thời gian của Bảng 1.3 bao gồm toàn bộ mọi thông tin từ CSDL bán thời gian trong Bảng 1.2, cùng với những thông tin mang tính lịch sử liên quan đến thời kỳ trƣớc (từ ngày d02 đến d04) trong khoảng đó nhà cung cấp S2 đƣợc ký kết chính thức. Tân từ đối với S_FROM_TO là “Nhà cung cấp S# đƣợc đặt tên là TENCONGTY, có trạng thái là TRANGTHAI, đóng tại thành phố DIACHI,đã ký hợp đồng chính thức, từ ngày FROM (không phải ngay ngày trƣớc ngày FROM) tới ngày TO (không phải ngày ngay sau TO)”. Tân từ đối với SP_FROM_TO là tƣơng tự. Cơ sở dữ liệu thời gian