Lý do chọn đề tàiCơ sở dữ liệu là một lĩnh vực thu hút khá nhiều sự quan tâm tìm hiểu của cácnhà nghiên cứu cả về lý thuyết cũng như xây dựng các phần mềm ứng dụng.Trong đóquản lý CSDL c
Trang 1ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
TIỂU LUẬN
CƠ SỞ DỮ LIỆU NÂNG CAO
ĐỀ TÀI NGỮ NGHĨA CƠ SỞ DỮ LIỆU CÓ YẾU TỐ THỜI GIAN
GVHD: PGS.TS Nguyễn Hà Nam HVTH: Nguyễn Thị Duyên
Nguyễn Thị Việt
Tháng 3/2012
Trang 2MỤC LỤC
A Lý do chọn đề tài 3
B Nội dung 3
I Về mặt lưu trữ 3
1 Thiết kế ở mức khái niệm 3
1.1 Thời gian hợp lệ, thời gian giao tác 3
1.2 Lược đồ CSDL ở mức khái niệm 6
2 Thiết kế ở mức lôgíc 8
2.1 Bảng thời gian hợp lệ 10
2.2 Bảng thời gian giao tác 13
2.3 Bảng theo hai loại thời gian 14
2.4 Những lưu ý khi thiết kế cơ sở dữ liệu có yếu tố thời gian 18
3 Thiết kế ở mức vật lý 19
II Về mặt truy vấn 20
C Kết luận 21
I Kết quả đã đạt được 21
II Hạn chế còn tồn tại 21
III Hướng phát triển của đề tài 21
D Tài liệu tham khảo 22
Trang 3A Lý do chọn đề tài
Cơ sở dữ liệu là một lĩnh vực thu hút khá nhiều sự quan tâm tìm hiểu của cácnhà nghiên cứu cả về lý thuyết cũng như xây dựng các phần mềm ứng dụng.Trong đóquản lý CSDL có yếu thời gian đang là khía cạnh nghiên cứu sôi nổi với hàng trăm nhànghiên cứu tích cực nghiên cứu hơn hai thập kỷ qua nhằm đưa ra được các CSDL hữuích
Phần lớn các ứng dụng CSDL đều quản lý các dữ liệu thay đổi theo thời gian Ví
dụ, các ứng dụng về tài chính như quản lý hồ sơ, điều hành ngân hàng hay quản lýnhân sự; các ứng dụng liên quan đến việc lập thời gian biểu như quản lý việc đặt chỗtrước trong ngành hàng không, ga tàu và khách sạn; các ứng dụng khoa học như dự báothời tiết Các ứng dụng như thế đều dựa trên CSDL có yếu tố thời gian Nhưng trongthực tế, người sử dụng thường cố gắng để đơn giản hóa hay phớt lờ các lĩnh vực có yếu
tố thời gian do sự phức tạp của chúng mang lại trong các ứng dụng của họ
Có thể nói rằng thiết kế CSDL là một công việc rất quan trọng, nó ảnh hưởng rấtnhiều đến chất lượng của ứng dụng Đặc biệt quan trọng khi thiết kế đối với CSDL có yếu
tố thời gian Thiết kế CSDL có yếu tố thời gian là một việc rất khó vì sự phức tạp của yếu
tố thời gian đem lại
Công nghệ CSDL hiện có chỉ hỗ trợ một phần nhỏ cho việc quản lý các dữ liệunhư thế Vì vậy, các nghiên cứu về CSDL có yếu tố thời gian hiện nay chú trọng vàoviệc thay đổi tình trạng đó bằng cách miêu tả rõ đặc điểm ngữ nghĩa của dữ liệu có yếu
tố thời gian và đưa ra các cách thức hiệu quả để xây dựng các mô hình, lưu trữ và truyvấn dữ liệu có yếu tố thời gian
Với mong muốn được tìm hiểu CSDL thời gian, theo hướng miêu tả ngữ nghĩacủa CSDL thời gian, đưa ra cách thức xây dựng các mô hình lưu trữ, xây dựng phéptoán hỗ trợ truy vấn trên CSDL thời gian; cùng sự hướng dẫn của thầy giáo chúng tôi
chọn đề tài: Ngữ nghĩa cơ sở dữ liệu có yếu tố thời gian.
Trang 4B Nội dung
I Về mặt lưu trữ
1 Thiết kế ở mức khái niệm
1.1 Thời gian hợp lệ, thời gian giao tác
Trước khi chúng ta đi đến tìm hiểu mô hình dữ liệu có yếu tố thời gian, thìchúng ta cần nhìn lại đặc điểm mô hình dữ liệu thông thường Ta biết rằng trong mộtCSDL thông thường khi dữ liệu được cập nhật, chèn hay xóa thì nó được viết đè lêntrạng thái CSDL cũ và tạo nên một trạng thái mới trong CSDL Và khi đó trạng tháitrước khi có thay đổi xảy ra sẽ không còn nữa
Còn đối với một CSDL có yếu tố thời gian được tạo nên do nó lưu trữ các dữliệu liên quan đến thời gian Sự khác nhau giữa dữ liệu có yếu tố thời gian và dữ liệuphi thời gian đó là có một khoảng thời gian được thêm vào dữ liệu để biểu diễn cho khi
nào thì dữ liệu hợp lệ hay khi nào thì dữ liệu được lưu trữ trong CSDL Dữ liệu sẽ được
lưu trữ trong CSDL thông thường nếu nó được kiểm tra xem có hợp lệ tại thời điểmhiện thời không Như vậy, bằng cách kết hợp dữ liệu với thời gian thì ta có thể lưu lạicác trạng thái khác nhau đó trong CSDL
Một mô hình dữ liệu và các bản ghi thông tin về một phần của thực tế được gọi
là mô hình thực tế Mô hình thực tế được biểu diễn trong CSDL bằng nhiều cấu trúc
khác nhau mà chúng ta gọi đơn giản là các thực thể CSDL Ví dụ: Tập thực thể nhânviên, tập thực thể lớp học, tập thực thể môn học, …Chúng ta thường chủ yếu quan tâmđến các sự kiện được ghi lại bởi các thực thể CSDL
Có 2 loại thời gian khác nhau có thể được kết hợp với các sự kiện được ghi lạibởi các thực thể CSDL:
Thứ nhất đó là thời gian hợp lệ: Thời gian hợp lệ của một sự kiện là một tập
thời gian – có thể là quá khứ, hiện tại và tương lai – khi sự kiện là thực ở trong mô hình thực tế Như vậy, thời gian hợp lệ sẽ lưu lại các trạng thái thay đổi theo thời gian trong mô hình thực tế Theo định nghĩa như vậy thì tất cả các sự kiện đều có một thời
gian hợp lệ
Ví dụ: Cho tập thực thể NHÂN VIÊN với các thuộc tính: Tên, mã nhân viên,lương, mã phòng ban mà nhân viên làm việc Trong mô hình thực tế luôn có những sựkiện xảy ra và tạo ra các trạng thái mới của tập thực thể nhân viên Chúng ta xem xétbảng dữ liệu sau:
Trang 5TEN MANV LUONG MAPB VST VET
phòng có mã là 4, lương Nam nhận được là 25000, đây được coi là một trạng thái của
thực thể này Khoảng thời gian [1994-08-20, 1996-01-31] là thời gian mà trạng thái đó
là đúng trong mô hình thực tế và được gọi là thời gian hợp lệ của trạng thái đó Khimột sự kiện xảy ra (sự kiện ở đây đó là nhân viên này được chuyển sang phòng có mã
là 5) sẽ tạo ra 1 trạng thái mới của thực thể này Và tương tự, trạng thái này cũng cóthời gian hợp lệ của nó trong mô hình thực tế và được lưu trữ trữ
Thứ hai đó là thời gian giao tác: Thời gian giao tác của một sự kiện đó là thời
gian khi sự kiện là hiện thời ở trong CSDL Không giống như thời gian hợp lệ, thờigian giao tác có thể được kết hợp không chỉ với các sự kiện mà còn với bất kỳ một thựcthể CSDL Ví dụ, thời gian giao tác có thể được kết hợp với các đối tượng và giá trị
không phải là sự kiện Như vậy, tất cả các thực thể CSDL đều có một thời gian giao
tác Thời gian giao tác lưu giữ các trạng thái thay đổi theo thời gian của CSDL Nó cóthể được lưu giữ hay không trong CSDL tùy thuộc vào chủ ý của người thiết kế CSDL.Khi một thực thể được kết hợp với thời gian giao tác thì sẽ làm cho việc xóa một thựcthể chỉ được thực hiện về mặt logic Việc xóa một thực thể không phải là loại bỏ vềmặt vật lý một thực thể ra khỏi CSDL, mà đúng hơn là nó vẫn còn tồn tại trong CSDLnhưng tạm ngừng trạng thái hiện tại trong CSDL Đối với các ứng dụng đòi hỏi tráchnhiệm phải giải thích hoặc có thể theo dõi dựa vào CSDL thì đều sử dụng thời giangiao tác
Ví dụ: Trở lại với tập thực thể nhân viên
Trang 6TÊN MANV LUONG MAPB TST TET
13:05:58
1998-06-04,08:56:12
09:23:57
Uc
Ở đây ta cũng chưa cần xét đến việc lưu trữ, xét dòng thứ nhất của bảng dữ liệu.Dòng này lưu trữ 1 trạng thái của thực thể nhân viên có tên là An, mức lương 25000 vàlàm việc tại phòng có mã là 5 với khoảng thời gian được kết hợp vào là [1997-06-08,13:05:58 ; 1998-06-04,08:56:12] Ở đây, thời điểm 1997-06-08,13:05:58 là thời điểm
mà trạng thái này được tạo ra trong thực tế , thời điểm 1998-06-04,08:56:12 là thờiđiểm trạng thái này được xóa đi
1.2 Lược đồ CSDL ở mức khái niệm
Lược đồ CSDL ở mức khái niệm của một hệ thống thông tin là một mô hìnhthông tin cơ bản trong suốt quá trình thiết kế Lược đồ đó là những đòi hỏi, những yêucầu của người sử dụng đối với phạm vi của ứng dụng, và nó được chuyển thành cáccấu trúc thông tin tóm tắt Khi phát triển các yêu cầu này trong thiết kế ở mức kháiniệm, yếu tố thời gian đã được đưa vào Điều này làm tăng thêm tính phức tạp của môhình khái niệm, làm cho nó khó hiểu và khó sử dụng Để làm giảm bớt các trở ngạinày, chúng ta chọn phải ra một hình thức đơn giản nào đó nhưng phải cải thiện được độtin cậy của quá trình phân tích
Trang 7Những yêu cầu của mô hình ở mức khái niệm mà người thiết kế cần phải quan tâm:
Thứ nhất, những người phát triển ứng dụng cho rằng nó phải dễ sử dụng hơn khicác loại thời gian được đưa vào trong các bản ghi thông tin của mô hình ứngdụng
Thứ hai, phải đảm bảo cho khoảng cách giữa mô hình ở mức khái niệm và môhình quan hệ của nó hẹp hơn, một chất lượng mà được các nhà lập trình đánhgiá cao
Thứ ba, lược đồ biểu diễn trong mô hình có thể được chuyển đổi thành các cấutrúc đơn giản hơn mà không làm mất thông tin khi chuyển đổi
Mô hình ở mức khái niệm như chúng ta biết đó là mô hình thực thể – mối quan
hệ gồm có ba cấu trúc chính, đó là các tập thực thể, các thuộc tính nguyên tử có giá trịđơn và các mối quan hệ Mỗi cấu trúc có thể là phi thời gian hay có yếu tố thời gian.Trong trường hợp các cấu trúc là phi thời gian, thì chỉ những trạng thái hiện thời làđáng quan tâm Còn trường hợp các cấu trúc là có yếu tố thời gian, thì chúng ta lạiquan tâm đến việc lưu giữ các trạng thái quá khứ, hiện tại và tương lai
Vậy trên mô hình thực thể- mối quan hệ, để biểu diễn một cấu trúc có yếu tốthời gian thì như thế nào?
Nếu các loại yếu tố thời gian có thể là thời gian hợp lệ (/v), thời gian giao tác(/t) hay cả hai loại (/b) Một cấu trúc là phi thời gian nếu nó không được đánh dấu kèmtheo với một thẻ thời gian: /v, /t hay /b Một thực thể có thể có một định danh chính(hay khóa chính) và một vài khóa phụ khác Một mối quan hệ có hai hoặc nhiều nhánh,mỗi nhánh được tạo ra bởi một tập thực thể Một nhánh có một ràng buộc chính đượcxác định bởi hai con số, các giá trị chung thường sử dụng đó là 0-1, 1-1, 0-N
Hình 1.5: Lược đồ ở mức khái niệm.
Theo đó thì trong lược đồ ở mức vật lý này các thông tin về thời gian có phải là
bộ phận thuộc tính của tập thực thể hay không? Nếu một tập thực thể là có yếu tố thời
DuAn/bTENDA PhongBan/bid: TENDA
Trang 8gian, thì với mỗi thực thể đã hay đang tồn tại, lúc nó ra đời hay lúc kết thúc đều có thểnhận biết được (đây chính là thời gian hợp lệ), hay lúc ghi lại chúng (trong CSDL) vàlúc xóa bỏ chúng cũng có thể biết được (đây chính là thời gian giao tác) Trong lược đồ
ở mức vật lý này các thông tin này đều là ngầm ẩn và không phải là bộ phận thuộc tínhcủa tập thực thể Nếu một thuộc tính là có yếu tố thời gian, thì tất cả các giá trị củathuộc tính đó trong một thực thể cũng có thể nhận biết được Nếu một mối quan hệ là
có yếu tố thời gian, thì lúc bắt đầu hay lúc chấm dứt mối quan hệ đó đều có thể nhậnbiết được
Để đảm bảo độ ổn định của CSDL có yếu tố thời gian, và cũng để giới hạn độphức tạp của nó và để làm cho việc xây dựng mô hình ở logic và mức vật lý của nóđược dễ dàng hơn và hiệu quả hơn, thì mô hình này phải xử lý tốt một số ràng buộc củacác lược đồ:
1) Các thuộc tính có yếu tố thời gian của một tập thực thể phải có cùng thẻ thờigian;
2) Thẻ thời gian của một tập thực thể phải giống với thẻ của các thuộc tính cóyếu tố thời gian của nó; không có ràng buộc nào nếu nó không có thuộc tính
có yếu tố thời gian nào;
3) Mỗi tập thực thể có yếu tố thời gian có một định danh chính (hay khóachính) bắt buộc, ổn định và các thuộc tính không lặp; không có ràng buộcnào trên các định danh khác;
4) Tập thực thể xuất hiện trong nhánh [i-1] của mối quan hệ theo thời gian nhiều R thì có cùng thẻ thời gian như R; mối quan hệ một-một được ràng buộc như một-nhiều;
một-5) Tập thực thể xuất hiện trong nhánh [0-N] của mối quan hệ theo thời gian
một-nhiều R thì có một thẻ thời gian thích hợp (khi được chuyển thành khóa ngoài hợp lệ) với các thẻ của R; mối quan hệ một-một được ràng buộc như một-nhiều;
Một lược đồ ở mức khái niệm mà gặp tất cả các điều kiện này có thể đượcchuyển đổi thành một lược đồ quan hệ thích hợp
2 Thiết kế ở mức lôgíc
Mô hình này thường là mô hình quan hệ, được chuyển từ mô hình thực thể –mối quan hệ
Trang 9Mô hình này gồm có các bảng, các cột, các khóa chính, khóa phụ và các khóangoài Những cấu trúc này có thể là có yếu tố thời gian (ngoại trừ khóa chính) hoặc phithời gian tương ứng với thẻ thời gian của cấu trúc đó trong mô hình ở mức khái niệm.Một bảng dùng để mô tả cho một tập thực thể được gọi là bảng thực thể, còn bảng
chuyển từ một mối quan hệ nhiều–nhiều sang được gọi là bảng mối quan hệ.
Cấu trúc của các bảng có yếu tố thời gian cũng như thường lệ:
1) Các bảng thời gian hợp lệ có thêm hai cột là VST và VET sao cho mỗi hàng mô
tả một sự kiện (trạng thái của một thực thể hay của mối quan hệ) hợp lệ suốtkhoảng thời gian [VST, VET]; những cột mới này có thể được cập nhật một cách
rõ ràng bởi những người sử dụng;
2) Bất kỳ bảng thời gian giao tác nào cũng có hai cột TST và TET, được xác định
là khoảng thời gian mà sự kiện được ghi lại trong CSDL; những cột này khôngthể được cập nhật bởi những người sử dụng;
3) Trong một bảng theo hai loại thời gian luôn có bốn cột này
Một bảng thực thể gồm có ba loại cột đó là: thứ nhất là cột định danh của thựcthể có dạng là khóa chính của tập trạng thái hiện thời của các thực thể, thứ hai là cáccột thời gian VST, VET, TST, TET và thứ ba là các cột còn, đó là các cột thuộc tính cóthể có hay không có yếu tố thời gian Một bảng mối quan hệ cũng có cấu trúc tương tự:định danh của mối quan hệ được tạo thành từ các khóa chính của các tập thực thể thamgia vào, các cột thời gian và các cột thuộc tính
Các bảng thực thể và bảng mối quan hệ hợp với nhau tạo thành tập các bảngCSDL Tuy nhiên, các bảng khác cũng có thể được xây dựng và được sử dụng bằng cáchsuy dẫn từ các bảng CSDL Những bảng này đòi hỏi phải được quan tâm đặc biệt khi được
sử dụng cùng với các bảng CSDL
Tính chất của các bảng cơ sở trong CSDL: (Để đơn giản, các cột thời gian đượcgọi chung là Start và End, vì cả hai loại đó có cùng tính chất giống nhau)
Tính chất 1: với bất kỳ trạng thái s nào, s.Start < s.End
Tính chất 2: 2 trạng thái s1, s2 trong một thực thể gọi là liên tiếp nhau, nếus1.End = s2.Start
Tính chất 3: bất kỳ hai trạng thái (s1, s2), mà s1.End = s2.Start (nghĩa là hai trạngthái liên tiếp nhau) thì hai trạng thái đó phải khác nhau
Trang 10Trong một bảng quan hệ có yếu tố thời gian, một dòng cho biết rằng các thực thểtham gia vào được nối với nhau trong suốt khoảng thời gian [Start, End] Với hai dòng r1
và r2 nào được xác định trên cùng tập thực thể, thì r1.End < r2.Start hay r2.End < r1.Start
Dưới đây chúng ta sẽ đi xem xét cụ thể về cách lưu trữ cũng như việc cập nhật,xóa, chèn trên các mô hình bảng dữ liệu được kết hợp thời gian
2.1 Bảng thời gian hợp lệ
Trong mục này chúng ta đi giải quyết một số vấn đề sau:
Đưa yếu tố thời gian hợp lệ vào mô hình dữ liệu như thế nào?
Kiểu dữ liệu của yếu tố thời gian là kiểu dữ liệu gì?
Xem xét một giá trị đặc biệt là now tại thuộc tính VET.
Ý nghĩa của mỗi bộ giá trị trong bảng dữ liệu
Cách thức thực hiện việc cập nhật, xóa, chèn dữ liệu trong mô hình thờigian hợp lệ
Khóa của bảng dữ liệu trong mô hình bảng thời gian hợp lệ
Trong quan hệ thời gian hợp lệ, để thấy được các loại thời gian khác nhau đượcbiểu diễn như thế nào trong mô hình CSDL, ta xét hai quan hệ NHÂN VIÊN vàPHÒNG BAN (hình 1.1(a)), rồi chuyển chúng thành các quan hệ thời gian hợp lệ bằngcách thêm vào các thuộc tính thời gian bắt đầu hợp lệ VST (Valid Start Time) và thuộc
tính thời gian kết thúc hợp lệ VET (Valid End Time) có kiểu dữ liệu là kiểu Date Điều
này được trình bày trong hình 1.1(b) với các quan hệ được đổi tên thành NV_VT vàPB_VT tương ứng
Trang 11TEN MANV LUONG MAPB TST TET
(c)
TEN MANV LUONG MAPB VST VET TST TET
(d)
Hình 1.1: Các loại CSDL quan hệ theo thời gian khác nhau
(a) CSDL phi thời gian (b) CSDL thời gian hợp lệ
(c) CSDL thời gian giao tác (d) CSDL theo hai loại thời gian
Bây giờ chúng ta xét xem quan hệ NV_VT khác như thế nào với quan hệ NHÂNVIÊN (phi thời gian) Trong quan hệ NV_VT, mỗi bộ V biểu diễn một phiên bản thông tincủa nhân viên trong suốt khoảng thời gian hợp lệ [V.VST, V.VET] Ngược lại, trong quan
hệ NHÂN VIÊN, mỗi bộ biểu diễn trạng thái hiện thời của mỗi nhân viên Trong NV_VT,
một phiên bản hiện thời của một nhân viên có một giá trị đặc biệt là now tại thuộc tính VET được coi là thời gian kết thúc hợp lệ của phiên bản đó Giá trị now này là một biến
thời gian ngầm đại diện cho thời gian hiện thời Quan hệ phi thời gian NHÂN VIÊN chỉ
gồm những bộ từ quan hệ NV_VT có VET là now mà thôi.
Long 103 28000 4 1996-05-01 1997-08-10
TEN_PB MAPB MA_NQLY TST TET
TEN_PB MAPB MA_NQLY VST VET TST TET
NV_TT
NV_BT
PB_TT
PB_BT
