Luận văn Phụ thuộc hàm theo thời gian
1
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.
2
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.
3
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.
4
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.
5
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
6
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ế.
7
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
8
đã 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.
• = <t, t’> C cho biết <t, 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.
9
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
KTV36
TINA27
KTV36
KTV63
HS lương
1.82
Thời gian
001
002
002
005
Lê Hoàng
[01/03/05, 01/05/05)
[02/10/05, 15/10/05]
[01/11/05, 30/11/05]
[05/09/06, nay]
Nguyễn Huy
Nguyễn Huy
Phạm Khoa
1.82
1.82
2.30
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 1 và 2 là hai thời khoảng trên C (1, 2 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:
i. 1 và 2 rời nhau, ký hiệu 1 2
ii. 1 và 2 giao nhau, ký hiệu 1 2
iii. 1 chứa 2, ký hiệu 1 2
iv. 1 chứa trong 2, ký hiệu 1 2
Từ đó, ta có các phép toán trên thời khoảng như sau:
• Phép giao: 1 2 = {t C | t 1 t 2}
• Phép hợp: 1 2 = {t C | t 1 t 2}
• Phép hiệu: 1 \ 2 = {t C | t 1 t 2}
10
• Hai thời khoảng 1 và 2 được gọi là kề nhau, ký hiệu 1 2 nếu:
1 = <t, t’); 2 = [t’, t’’> hoặc 1 = <t, t’]; 2 = (t’, t’’>
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 = 1,n ) 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 , là một ánh xạ được xác định như sau:
: R D, sao cho [Ai] dom(Ai), i = 1,n
.
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 là một bộ và X là một tập các thuộc tính,
chúng ta có thể dùng [X] để thay cho các thành phần của trong tập các thuộc
tính của X.
Trong ví dụ 1.1, nếu là một bộ thì [{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 1 và 2 là hai bộ trên R. Khi đó, 1 và 2 được
gọi là tương đương nhau, ký hiệu 1 2, nếu với X (R \ {T}) thì
(1[X] = 2[X]) trong đó T là thuộc tính chỉ thời gian.
11
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 1 và 2 là không tương đương, ký hiệu 1≉ 2.
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
KTV36
KTV36
TINA27
KTV63
KTV63
HS lương
Thời gian
001
Lê Hoàng
1.82
[01/03/05, 01/05/05)
[01/11/05, 30/11/05]
[02/10/05, 15/10/05]
[05/09/06, nay]
002
Nguyễn Huy
Nguyễn Huy
Phạm Khoa
Phạm Khoa
1.82
002
1.82
005
2.30
005
2.30
[01/09/06, 10/09/06]
Trong ví dụ 1.2, nếu 1[{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à 2[{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 1 2.
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
12
đượ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 1, 2 r mà 1 ≉ 2.
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 1 và 2 là hai bộ tương đương nhau trên R.
Khi đó, phép hợp nhất của 1 và 2, ký hiệu 1 2 là một bộ được xác định
như sau:
= 1 2 ( 1) ( 2) ([T] = 1[T] 2[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
KTV36
TINA27
KTV36
KTV63
HS lương
1.82
Thời gian
001
Lê Hoàng
[01/03/05, 01/05/05)
[02/10/05, 15/10/05]
[01/11/05, 30/11/05]
[01/09/06, nay]
002
Nguyễn Huy
Nguyễn Huy
Phạm Khoa
1.82
002
1.82
005
2.30
13
Định nghĩa 1.3. (Quan hệ bao theo thời gian)
Cho lược đồ quan hệ R với 1 và 2 là hai bộ tương đương nhau trên R.
Khi đó, 1 được gọi là bao theo thời gian 2 trên R, ký hiệu 1 T 2, nếu 1 và 2
là hai bộ tương đương nhau trong đó thời khoảng của 1 chứa thời khoảng của 2,
hay ta nói cách khác 1[T] 2[T].
Nhận xét: 1 T 2 1 = 1 2
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
KTV36
TINA27
KTV36
KTV63
KTV63
HS lương
1.82
Thời gian
001
Lê Hoàng
[01/03/05, 01/05/05)
[02/10/05, 15/10/05]
[01/11/05, 30/11/05]
[01/09/06, nay]
002
Nguyễn Huy
Nguyễn Huy
Phạm Khoa
Phạm Khoa
1.82
002
1.82
005
2.30
005
2.30
[05/09/06, 10/09/06]
Trong bảng 1.4, với 1[{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à 2[{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 1 bao 2 theo thời gian hay 1 T 2.
Định nghĩa 1.4. (Phần tử theo thời gian)
Cho lược đồ quan hệ R với là một bộ trên R. Khi đó, là một phần tử
theo thời gian của quan hệ r trên R, ký hiệu T r, nếu ’ r sao cho ’ T .
14
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 = { | 1, 2 T r: 1 2, = 1 2}
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 r1 T r2) ( T r1 T r2)
(1 T r1, 2 T r2: 1 2, = 1 2)}
Đị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 r1 T r2)
(1 T r1, 2 T r2: 1 2, [T] = 1[T] \ 2[T] )}
15
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
Lê Hoàng
Khoá dạy
KTV36
TINA27
KTV36
KTV63
HS lương
1.82
Thời gian
001
002
002
005
[01/03/05, 01/05/05)
[02/10/05, 15/10/05]
[01/11/05, 15/11/05)
[01/09/06, 10/09/06]
Nguyễn Huy
Nguyễn Huy
Phạm Khoa
1.82
1.82
2.30
GV2:
Mã GV
Họ tên
Khoá dạy
TINA 27
KTV36
HS lương
1.82
Thời gian
002
002
005
Nguyễn Huy
Nguyễn Huy
Phạm Khoa
[05/10/05, 10/10/05]
[15/11/05, 30/11/05]
[06/09/06, nay]
1.82
KTV63
2.30
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
KTV36
TINA27
KTV36
KTV63
HS lương
1.82
Thời gian
001
Lê Hoàng
[01/03/05, 01/05/05)
[02/10/05, 15/10/05]
[01/11/05, 30/11/05]
[01/09/06, nay]
002
Nguyễn Huy
Nguyễn Huy
Phạm Khoa
1.82
002
1.82
005
2.30
Thực hiện phép hiệu theo thời gian cho hai quan hệ GV1 và GV2, ta có:
16
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
KTV36
HS lương
1.82
Thời gian
001
002
Lê Hoàng
[01/03/05, 01/05/05)
[02/10/05, 05/10/05)
(10/10/05, 15/10/05]
[01/11/05, 15/11/05)
[01/09/06, 06/09/06)
Nguyễn Huy
TINA27
1.82
002
005
Nguyễn Huy
Phạm Khoa
KTV36
KTV63
1.82
2.30
Đị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 = { | (1 T r : 1 = [R]) (2 T s : 2 = [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
[0, +)
[0, +)
[0, +)
001
Lê Hoàng
002
Nguyễn Huy
Phạm Khoa
005
17
KD:
Mã GV
Khoá dạy
KTV36
TINA27
KTV36
KTV63
Thời gian
001
002
002
005
[01/03/05, 01/05/05)
[02/10/05, 15/10/05]
[01/11/05, 30/11/05]
[01/09/06, nay]
LUONG:
Mã GV
HS lương
1.82
Thời gian
001
001
002
002
005
[01/03/05, 01/04/05)
[01/04/05, 01/05/05)
[02/10/05, 15/10/05]
[01/11/05, 30/11/05]
[01/09/06, nay]
2.06
1.82
2.06
2.30
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
KTV36
TINA27
KTV36
KTV63
Thời gian
001
Lê Hoàng
[01/03/05, 01/05/05)
[02/10/05, 15/10/05]
[01/11/05, 30/11/05]
[01/09/06, nay]
002
Nguyễn Huy
Nguyễn Huy
Phạm Khoa
002
005
Thực hiện phép kết nối tự nhiên các quan hệ GV, KD và LUONG, ta có:
18
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
KTV36
KTV36
TINA27
KTV36
KTV63
HS lương
Thời gian
001
001
002
002
005
Lê Hoàng
1.82
[01/03/05, 01/04/05)
[01/04/05, 01/05/05)
[02/10/05, 15/10/05]
[01/11/05, 30/11/05]
[01/09/06, nay]
Lê Hoàng
2.06
Nguyễn Huy
Nguyễn Huy
Phạm Khoa
1.82
2.06
2.30
Đị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
T
thời gian của r trên S, ký hiệu S (r) và được xác định như sau:
T
S (r) = {[S] | 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
KTV36
KTV36
TINA27
KTV36
KTV63
HS lương
1.82
Thời gian
001
001
002
002
005
Lê Hoàng
[01/03/05, 01/04/05)
[01/04/05, 01/05/05)
[02/10/05, 15/10/05]
[01/11/05, 30/11/05]
[01/09/06, nay]
Lê Hoàng
2.06
Nguyễn Huy
Nguyễn Huy
Phạm Khoa
1.82
2.06
2.30
19
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.
T
S (r):
Mã GV
Họ tên
Khoá dạy
KTV36
TINA27
KTV36
KTV63
Thời gian
001
Lê Hoàng
[01/03/05, 01/05/05)
[02/10/05, 15/10/05]
[01/11/05, 30/11/05]
[01/09/06, nay]
002
Nguyễn Huy
Nguyễn Huy
Phạm Khoa
002
005
Đị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
T
với P là tập các bộ trên r thoả điều kiện P, ký hiệu P (r), được xác định như
T
sau:
P (r) = { T r | 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.
T
P (r):
Mã GV
002
Họ tên
Nguyễn Huy
Nguyễn Huy
Khoá dạy
TINA27
KTV36
HS lương
1.82
Thời gian
[02/10/05, 15/10/05]
[01/11/05, 30/11/05]
002
2.06
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ề
20
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.
21
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
TINA27
TINA27
TINA27
TINA27
TINA27
TINA27
Số ĐVHT Họ tên GVGD HS Lương
Số HV
50
Ngày
3/3/05
3
3
3
3
3
3
Lê Hoàng
1.82
1.82
2.06
1.82
1.82
1.82
Lê Hoàng
45
8/3/05
Lê Hoàng
50
5/4/05
Nguyễn Huy
Nguyễn Huy
Nguyễn Huy
50
3/10/05
7/10/05
17/10/05
50
45
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à
22
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:
1. Các thuộc tính Mã KH và Ngày tạo thành khóa.
2. Phụ thuộc hàm (FD) Mã KH Số ĐVHT phải được thoả mãn.
3. HS Lương của giáo viên giảng dạy không được thay đổi trong một
tháng.
4. 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.
23
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:
1. Số ĐVHT của mỗi khóa học mãi mãi không thay đổi.
2. Số HV trong một khóa học không thay đổi trong 1 ngày.
3. Họ tên GVGD cho mỗi khóa học không được thay đổi trong 1 tuần.
4. 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:
24
Bảng 2.2. Một phân tách tự nhiên của quan hệ KHOÁHỌC.
KH2:
Họ tên GVGD
HS Lương
1.82
Tháng
3/05
Lê Hoàng
KH1:
Mã KH
Số ĐVHT
Lê Hoàng
2.06
4/05
TINA27
3
Nguyễn Huy
1.82
10/05
KH4:
KH3:
Mã KH
TINA27
TINA27
TINA27
TINA27
TINA27
TINA27
Số HV
50
Ngày
Họ tên GVGD
Mã KH
Tuần
3/3/05
8/3/05
Tuần từ 28/2/05
Tuần từ 7/3/05
Tuần từ 4/4/05
Tuần từ 2/10/05
Tuần từ 16/10/05
TINA27 Lê Hoàng
TINA27 Lê Hoàng
TINA27 Lê Hoàng
TINA27 Nguyễn Huy
TINA27 Nguyễn Huy
45
50
5/4/05
50
3/10/05
7/10/05
17/10/05
50
45
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
25
đề 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:
1. 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).
2. 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(2) =
...
t(1/1/2005) = [0, 1)
t(2/1/2005) = [1, 2)
t(7) =
...
t(7/1/2005) = [6, 7)
26
t(32) =
t(1/2/2005) = [31, 32)
t’ = “Tháng”: là một ánh xạ từ * sao cho:
t’(1) =
t’(2) =
t’(Tháng 1/2005) = [0, 31)
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:
1. Mỗi ti, (1 i n) là một kiểu con của kiểu t, và
*
2. Với l , j * sao cho t(l) = tk(j), với k nào đó và 1 k n
3. 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).
27
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
28
Đị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’ ≼ {t1, t2, ..., tn}, nếu:
C
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, ) trong đó (R, t) là một lược đồ
môđun thời gian và 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ì (i) = nếu t(i) = .
Điều này có nghĩa là: hàm trong môđun thời gian (R, t, ) 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)
29
+ Môđun thời gian là (KHOÁHỌC, Ngày, ), với:
(3/3/05)
(8/3/05)
(5/4/05)
=
=
=
{(TINA27, 3, Lê Hoàng, 1.82, 50)}
{(TINA27, 3, Lê Hoàng, 1.82, 45)}
{(TINA27, 3, Lê Hoàng, 2.06, 50)}
{(TINA27, 3, Nguyễn Huy, 1.82, 50)}
{(TINA27, 3, Nguyễn Huy, 1.82, 50)}
{(TINA27, 3, Nguyễn Huy, 1.82, 45)}
(3/10/05) =
(7/10/05) =
(17/10/05) =
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 M là tập tất cả các bộ trên
môđun thời gian M, nghĩa là:
*
M = {T | i : T (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, 1) và M2 = (R2, t, 2) 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, )
Trong đó: với i 1, (i) = 1(i) ⋈ 2(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, 1), với:
+ KH1 = (Mã KH, Số ĐVHT, Số HV)
+
1(3/3/05) =
{(TINA27, 3, 50)}
30
1(8/3/05) =
1(5/4/05) =
{(TINA27, 3, 45)}
{(TINA27, 3, 50)}
Cho M2 = (KH2, Ngày, 2), với:
+ KH2 = (Mã KH, Họ tên GVGD, HS Lương)
+
2(3/3/05) =
2(8/3/05) =
2(5/4/05) =
{(TINA27, Lê Hoàng, 1.82)}
{(TINA27, Lê Hoàng, 1.82)}
{(TINA27, Lê Hoàng, 2.06)}
Khi đó:
M1 ⋈T M2 = (KH, Ngày, ), với:
KH = (Mã KH, Số ĐVHT, Số HV, Họ tên GVGD, HS Lương)
(3/3/05)
(8/3/05)
(5/4/05)
=
=
=
{(TINA27, 3, 50, Lê Hoàng, 1.82)}
{(TINA27, 3, 45, Lê Hoàng, 1.82)}
{(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, ) và R1 R. Khi đó, phép chiếu của M trên R1, ký hiệu là
T
R (M) là một môđun thời gian M’ được xác định như sau:
1
M’ = (R1, t, 1)
Trong đó: với mỗi i 0, 1(i) = R ((i)),
1
và là phép chiếu truyền thống.
Ví dụ 2.11. Cho M = (KHOÁHỌC, Ngày, ), với:
+ KHOÁHỌC = (Mã KH, Số ĐVHT, Họ tên GVGD, HS Lương, Số HV)
+
(3/3/05)
(8/3/05)
=
=
{(TINA27, 3, Lê Hoàng, 1.82, 50)}
{(TINA27, 3, Lê Hoàng, 1.82, 45)}
Tải về để xem bản đầy đủ
114 trang
20/07/2025
780
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Phụ thuộc hàm theo thời gian", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_phu_thuoc_ham_theo_thoi_gian.doc
