BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC

HUỲNH THANH HI

Nghiªn cøu mét sè ph-¬ng ph¸p
g¸n nh·n thêi gian trªn c¬ së d÷ liÖu

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 60.48.01.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Huế, 2015


MỤC LỤC
Lời cam đoan
Lời cảm ơn
Mục lục
Danh mục các từ viết tắt
Danh mục bảng
Danh mục hình vẽ
MỞ ĐẦU .......................................................................................................... 1
Chương 1. KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU THỜI GIAN .................... 3
1.1. Giới thiệu .................................................................................................... 3
1.2. Các loại thời gian ....................................................................................... 4
1.2.1 Thời gian hợp lệ (VT) .............................................................................. 5
1.2.2 Thời gian giao tác (TT): ........................................................................... 5
1.3. Các kỹ thuật gán nhãn thời gian ................................................................. 7

3.5.1. Thao tác cập nhật................................................................................... 43
3.5.2. Thao tác xóa .......................................................................................... 46
3.5.3. Thao tác chèn ........................................................................................ 47
3.6. Ứng dụng cụ thể cho bài toán có gán nhãn thời gian trên cơ sở dữ liệu.. 47
3.6.1. Mô hình CSDL có yếu tố thời gian ở mức khái niệm. .......................... 49
3.6.2. Mô hình quan hệ có yếu tố thời gian ở mức logic. ............................... 51
3.6.3. Mô hình quan hệ có yếu tố thời gian ở mức vật lý ............................... 53
3.6.4. Xây dựng CSDL quản lý hội thảo khoa học có yếu tố thời gian .......... 55
3.7. Tiểu kết chương 3..................................................................................... 68
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................... 59
1. Kết luận ....................................................................................................... 59
2. Hướng phát triển đề tài ................................................................................ 59
TÀI LIỆU THAM KHẢO ............................................................................ 60


DANH MỤC CÁC TỪ VIẾT TẮT

Từ viết tắt

Diễn giải

BTC

Ban tổ chức

CSDL

Cơ sở dữ liệu

DBMS


VET

Valid End Time

VST

Valid Start Time


DANH MỤC CÁC BẢNG
Tên bảng

Số hiệu

Trang

bảng
1.1

CSDL phi thời gian của hai quan hệ

8

1.2

CSDL thời gian hợp lệ

8


2.4

Bộ dữ liệu trong quan hệ NV_TT sau khi thực hiện cập

23

nhật
2.5

Bộ dữ liệu trong quan hệ NV_TT

25

2.6

Bộ dữ liệu trong quan hệ NV_TT sau khi thực hiện chèn

25

2.7

Bảng kết quả cập nhật lương cho nhân viên An

27

3.1

CSDL thời gian hợp lệ

30


42

3.7

CSDL theo 2 loại thời gian của quan hệ nhân viên

43

3.8

Các bộ trong quan hệ theo hai loại thời gian NV_BT

43

3.9

Bộ dữ liệu của nhân viên An trong quan hệ NV_BT

44


3.10

Bộ dữ liệu của nhân viên An trong quan hệ NV_BT sau

45

khi cập nhật lương
3.11


Trang

hình vẽ
3.1

Giao tác T1 và T2

32

3.2

Sử dụng thời gian Commit cho Now

35

3.3

Sơ đồ thực hiện giao tác T1, T2 và T3

37

3.4

Current_Date trong truy vấn

40

3.5


Mô hình CSDLquan hệ có yếu tố thời gian

58


1

MỞ ĐẦU
Cơ sở dữ liệu là tài nguyên thông tin dùng chung cho nhiều người cùng sử
dụng. Bất kỳ người sử dụng nào trên mạng máy tính, tại các thiết bị đầu cuối về
nguyên tắc có quyền truy nhập, khai thác toàn bộ hay một phần dữ liệu theo chế
độ trực tuyến hay tương tác mà không phụ thuộc vào vị trí địa lý của người sử
dụng với các tài nguyên đó. Do đó, CSDL là một thành phần không thể thiếu
trong quá trình phát triển các hệ thống thông tin.
Tuy nhiên, Trong thời đại ngày nay nhiều lĩnh vực trong thế giới thực cần
thông tin về quá khứ, hiện tại và tương lai, như: quản lý học sinh, tài chính
(chứng từ, tiền gửi ngân hàng), y tế (theo dõi sức khỏe bệnh nhân), quản lý nhân
sự, lập thời gian biểu (quản lý việc đặt chỗ trước trong ngành hàng không, ga tàu
và khách sạn), khoa học (dự báo thời tiết, kết quả đo đạt),…
Ngoài ra, người sử dụng còn yêu cầu việc truy cập thông tin có yếu tố thời
gian không những phải cho kết quả nhanh chóng mà còn phải chính xác, đầy đủ.
Như vậy nếu CSDL không gán nhãn thời gian thì việc truy xuất vào cơ sở dữ
liệu đó gặp không ít khó khăn. Vì thế, để thuận tiện cho việc tìm kiếm, thống
kê, truy xuất thông tin . . . thì việc gán nhãn thời gian cho CSDL là một phần
không thể thiếu. Vì thế tôi đã lựa chọn đề tài: “Nghiên cứu một số phương
pháp gán nhãn thời gian trên cơ sở dữ liệu”. Nội dung chính của luận văn là
giới thiệu về cơ sở dữ liệu gán nhãn thời gian và một số phương pháp gán nhãn
thời gian hợp và thời gian giao tác.
Trong thời gian tìm hiểu và nghiên cứu đề tài, em đã đạt được những kết
quả bước đầu về cơ sở dữ liệu gán nhãn thời gian, làm cơ sở để hoàn thành cuốn


Chương 1
KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU THỜI GIAN
1.1. Giới thiệu
Cơ sở dữ liệu (CSDL) là một tập hợp dữ liệu tác nghiệp, bao gồm các loại
dữ liệu âm thanh, tiếng nói, chữ viết, văn bản, đồ hoạ, hình ảnh tĩnh hay hình
ảnh động....được tổ chức và lưu trữ theo 1 cấu trúc chặt chẽ nhằm phục vụ cho
nhiều đối tượng với nhiều mục đích khác nhau.
Vì vậy, CSDL là tài nguyên thông tin dùng chung cho nhiều người cùng
sử dụng. Bất kỳ người sử dụng nào trên mạng máy tính, tại các thiết bị đầu cuối,
về nguyên tắc có quyền truy nhập khai thác toàn bộ hay một phần dữ liệu theo
chế độ trực tuyến hay tương tác mà không phụ thuộc vào vị trí địa lý của người
sử dụng với các tài nguyên đó. Do đó, CSDL là một thành phần không thể thiếu
trong quá trình phát triển các hệ thống thông tin.
Tuy nhiên, Trong thời đại ngày nay nhiều lĩnh vực trong thế giới thực cần
thông tin về quá khứ, hiện tại và tương lai, như: quản lý học sinh, tài chính
(chứng từ, tiền gửi ngân hàng), y tế (theo dõi sức khỏe bệnh nhân), quản lý nhân
sự, lập thời gian biểu (quản lý việc đặt chỗ trước trong ngành hàng không, ga tàu
và khách sạn), khoa học (dự báo thời tiết, kết quả đo đạt),…
Ngoài ra, người sử dụng còn yêu cầu việc truy cập thông tin có yếu tố
thời gian không những phải cho kết quả nhanh chóng mà còn phải chính xác,
đầy đủ. Như vậy nếu CSDL không gán nhãn thời gian thì việc truy xuất vào cơ
sở dữ liệu đó gặp không ít khó khăn. Vì thế, để thuận tiện cho việc tìm kiếm,
thống kê, truy xuất thông tin . . . thì việc gán nhãn thời gian cho CSDL là một
phần không thể thiếu.


4

Để có 1 cách nhìn tổng quan về CSDL thời gian, trong chương 1 của luận

điểm hay một khoảng thời gian đặc biệt. 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ệu phi 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


5

điểm hiện thời không. Khi dữ liệu trong một CSDL thông thường được cập nhật,
chèn hay xóa thì nó được viết đè lên trạ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ái trước khi có thay đổi xảy ra sẽ không
còn nữa.
Căn cứ vào những đặc tính đó nên các nhà nghiên cứu CSDL thời gian đã
phân chia thời gian thành 2 loại cơ bản là thời gian hợp lệ (VT) và thời gian giao
tác (TT). Từng loại thời gian này có đặc điểm cụ thể như thế nào thì chúng ta sẽ
cùng tìm hiểu ở các mục 1.2.1 và 1.2.2 dưới đây.
1.2.1. Thời gian hợp lệ (VT)
Thời gian hợp lệ của 1 sự việc là tất cả các khoảng thời gian mà sự việc
xảy ra hay suốt quãng thời gian mà sự việc được coi là đúng trong thực tế. Thời
gian hợp lệ của 1 sự việc có thể được ghi lại bằng cách sử dụng hai thuộc tính
thời gian bắt đầu hợp lệ (VST) và thời gian kết thúc hợp lệ (VET).
CSDL có yếu tố thời gian hợp lệ được gọi là CSDL thời gian hợp lệ.
Khi nói đến thời gian hợp lệ, chúng ta sẽ nói đến những đặc tính sau:
+ Thời gian hợp lệ ghi nhận quá trình thay đổi trạng thái của các sự việc
trong thực tế.
+ Thời gian hợp lệ của một sự việc không phải bao giờ cũng được ghi
nhận trong CSDL vì một số lí do như: thời gian hợp lệ của một sự việc là không
thể biết hoặc khoảng thời gian hợp lệ không xác định được một cách chính xác.

ở trên. Nhưng trong một vài ứng dụng khác thì cần đến cả thời gian giao tác và
thời gian hợp lệ, vì thế trong trường hợp này CSDL thời gian được gọi là CSDL
theo hai loại thời gian.


7

1.3. Các kỹ thuật gán nhãn thời gian
Nếu CSDL không có yếu tố thời gian thì việc truy xuất vào CSDL đó gặp
không ít khó khăn. Vì thế việc gán nhãn thời gian vào CSDL là 1 phần không
thể thiếu trong thời đại ngày nay.
Các CSDL truyền thống trước đây không đưa các nhãn thời gian vào cho
dù trên thực tế vẫn có thời gian thực, nhưng người ta cố phớt lờ không để ý để
đưa yếu tố thời gian vào CSDL. Ngày nay, để gán nhãn thời gian vào CSDL
người ta sẽ mở rộng các CSDL thông thường không có nhãn thời gian bằng
những kỹ thuật gán nhãn thời gian.
Có 2 kỹ thuật gán nhãn thời gian cơ bản, kỹ thuật thứ nhất đó là kỹ thuật
ghi nhận thông tin thời gian liên quan đến mỗi bộ dữ liệu, kỹ thuật gán nhãn thời
gian thứ 2 đó là kỹ thuật ghi nhận thông tin thời gian liên quan đến mỗi thuộc
tính trong từng bộ dữ liệu. Việc gán nhãn thời gian vào CSDL theo từng kỹ
thuật cụ thể như thế nào sẽ được luận văn trình bày ở các mục dưới đây.
1.3.1. Kỹ thuật ghi nhận thông tin thời gian liên quan đến mỗi bộ dữ liệu
Như luận văn đã nêu ở mục 1.2, thời gian trong CSDL có yếu tố thời gian
gồm có 2 loại là thời gian giao tác (TT) và thời gian hợp lệ (VT). Để ghi nhận
thông tin thời gian liên quan đến mỗi bộ dữ liệu, ta sẽ thêm 4 trường thời gian
vào mỗi bộ dữ liệu đó để lưu các giá trị thời gian. Cụ thể mỗi bộ dữ liệu sẽ được
thêm 4 trường như sau: {TST, TET, VST, VET }. Trong đó:
+ TST : Thời gian bắt đầu giao tác
+ TET : Thời gian kết thúc giao tác
+ VST : Thời gian bắt đầu hợp lệ

TEN_PB

MAPB

LUONG MAPB VST

MA_NQLY VST

VET

VET

Từ 2 quan hệ NHÂN VIÊN và PHÒNG BAN, chúng ta chuyển chúng
thành các quan hệ thời gian giao tác bằng cách thêm vào các thuộc tính thời gian
bắt đầu giao tác TST và thời gian kết thúc giao tác TET có kiểu dữ liệu là
Timestamp. Điều này được trình bày trong bảng 1.3 với các quan hệ được đổi
tên thành NV_TT và PB_TT tương ứng.


9

Bảng 1.3. CSDL thời gian giao tác
TEN MANV LUONG MAPB TST

TET

TEN_PB

TET


trong từng bộ dữ liệu thì mỗi thuộc tính của mỗi bộ dữ liệu sẽ có các giá trị thời
gian riêng tương ứng với nó.
Ở cách tiếp cận này, mỗi khi một giá trị của một thuộc tính thay đổi thì
một bộ phiên bản mới sẽ được tạo ra mặc dù tất cả các giá trị của các thuộc tính
khác sẽ giống hệt như bộ trước đó. Vì thế trong cách biểu diễn này thông tin sẽ


10

trở nên rất phức tạp. Do đó, các hệ quản trị CSDL phải hỗ trợ thêm các phương
pháp lưu trữ, xử lý, và truy vấn hiệu quả hơn.
Với kỹ thuật này, một đối tượng phức hợp đa trị được sử dụng để lưu trữ
tất cả các thay đổi về thời gian của đối tượng đó.
- Một thuộc tính thay đổi theo thời gian được gọi là thuộc tính timevarying và nó có giá trị bằng cách thêm các khoảng thời gian (period) vào thuộc
tính. Các khoảng thời gian này có thể biểu diễn cho thời gian hợp lệ, thời gian
giao tác hoặc thời gian theo hai loại thời gian phụ thuộc vào các yêu cầu của
ứng dụng.
- Mỗi thuộc tính time-varying được mô tả như một danh sách các bộ
<valid_start_time, valid_end_time, value> được sắp xếp bởi thời gian bắt đầu
hợp lệ.
- Các thuộc tính không thay đổi theo thời gian được gọi là thuộc tính
nontime-varying và chúng không được kết hợp với các khoảng thời gian nào cả.
Trong mô hình này, mỗi khi thuộc tính thay đổi thì phiên bản thuộc tính
hiện thời được đóng lại và phiên bản thuộc tính mới cho thuộc tính này được
thêm vào danh sách. Điều này cho phép các thuộc tính thay đổi một cách không
đồng bộ. Giá trị hiện thời của mỗi thuộc tính là now ở valid_end_time.
Khi sử dụng kỹ thuật này, tốt hơn ta nên kể đến một thuộc tính thời gian
sống (lifespan temporal attribute) được kết hợp với toàn bộ các đối tượng.
Thuộc tính đó có giá trị là một hay nhiều giai đoạn thời gian hợp lệ chính là thời
gian tồn tại hợp lệ của các đối tượng đó. Bất kì giai đoạn thời gian nào của một

SQL-92, TOQL, TOOSQL, OQL/T... Đây là những ngôn ngữ cho phép chúng ta
gán nhãn thời gian trên CSDL và truy vấn dữ liệu trên CSDL thời gian.
Trong mục này chúng ta sẽ tìm hiểu khái quát ngôn ngữ TSQL2 để có cái
nhìn tổng quan về ngôn ngữ cho phép chúng ta gán nhãn thời gian và truy vấn
dữ liệu theo thời gian.


12

Như chúng ta đã nói ở trên, ngôn ngữ TSQL2 là một ngôn ngữ mở rộng
của SQL được xây dựng với cách tiếp cận có sử dụng CSDL thời gian. Ý tưởng
chính của TSQL2 là cho phép người dùng định hình một quan hệ là có yếu tố
thời gian hay không.
Trong CSDL quan hệ phi thời gian, những điều kiện lựa chọn phổ biến
trong truy vấn chỉ liên quan đến các điều kiện về thuộc tính, và các bộ thõa mãn
các điều kiện này sẽ được chọn ra từ tập các bộ hiện thời. Theo đó, các thuộc
tính thuộc diện truy vấn được chỉ định bởi một phép chiếu.
Trở lại ví dụ 1.1 trong truy vấn để truy xuất tên của tất cả các nhân viên
đang làm việc trong dự án chuyên ngành 5 có lương lớn hơn 30000 thì điều kiện
của phép chọn là: ((LUONG > 30000) AND (MAPB = 5)), thuộc tính dự kiến
trả về sẽ là TÊN. Trong CSDL có yếu tố thời gian, các điều kiện trong truy vấn
có thể bao gồm cả yếu tố thời gian thêm vào các thuộc tính. Một điều kiện thời
gian được gọi là đơn thuần nếu nó chỉ liên quan đến thời gian. Ví dụ như phép
chọn tất cả các bộ phiên bản của nhân viên hợp lệ trong thời điểm t nào đó hoặc
hợp lệ trong khoảng thời gian [t1, t2] nào đó. Trong trường hợp này, khoảng
thời gian được yêu cầu đó được so sánh với khoảng thời gian hợp lệ [t.VST,
t.VET] của mỗi bộ, và chỉ các bộ thõa mãn điều kiện đó mới được chọn. Trong
các phép toán so sánh đó, mỗi một giai đoạn hay khoảng thời gian được xem
tương ứng với tập các thời điểm từ t1 đến t2, do vậy tập các phép toán so sánh
chuẩn có thể được sử dụng. Dưới đây là một vài phép toán so sánh liên quan đến

thời gian. Nếu hai khoảng thời gian [t1, t2] và [t3, t4] là gần kề nhau thì chúng
được kết hợp lại thành một khoảng thời gian đơn [t1, t4]. Đây được gọi là tính
kết hợp của các khoảng thời gian. Tính kết hợp này cũng được sử dụng để kết
nối các khoảng thời gian giao nhau.
Trở lại với truy vấn có yếu tố thời gian, để minh họa các điều kiện truy
vấn đơn thuần chỉ có thời gian được sử dụng như thế nào, ta giả sử rằng người
sử dụng muốn chọn tất cả các bộ hợp lệ của nhân viên tại một thời điểm bất kỳ
trong suốt năm 1997. Điều kiện lựa chọn phù hợp cho quan hệ ở trong hình 1.2
sẽ là:
[t.VST, t.VET] OVERLAPS [1997-01-01, 1997-12-31]


14

Hầu hết các phép chọn có yếu tố thời gian được áp dụng với thời gian hợp
lệ. Trong CSDL theo hai loại thời gian, các điều kiện trong phép chọn thường
được dùng để truy vấn đối với những bộ đúng hiện thời có giá trị là uc ở thời
gian kết thúc giao tác. Tuy nhiên, nếu cần truy vấn đối với trạng thái CSDL
trước đó thì một mệnh đề khác nữa được bổ sung thêm vào truy vấn, khi đó truy
vấn sẽ được áp dụng với những bộ thời gian hợp lệ đúng trong CSDL tại thời
gian t nào đó.
Ngoài các điều kiện truy vấn chỉ có thời gian đơn thuần, còn có các phép
chọn khác mà điều kiện chọn gồm cả những thuộc tính và các điều kiện thời
gian. Chẳng hạn, nếu chúng ta muốn truy xuất tất cả các bộ phiên bản của tất cả
các nhân viên làm việc trong chuyên ngành 5 trong quan hệ NV_VT tại bất kì
thời điểm nào trong năm 1997, thì điều kiện sẽ là:
([t.VST, t.VET] OVERLAPS [1997-01-01, 1997-12-31]) AND (t.MAPB=5)
Cuối cùng, chúng ta sẽ đưa ra một cái nhìn chung về ngôn ngữ truy vấn
TSQL2. Ngôn ngữ TSQL2 là một mở rộng của SQL được xây dựng với cách
tiếp cận có sử dụng CSDL thời gian. Ý tưởng chính của TSQL2 là cho phép

TRÊN CƠ SỞ DỮ LIỆU
2.1. Giới thiệu
Như chúng ta đã tìm hiểu ở chương 1, thời gian giao tác là thời gian khi
thông tin thực sự được lưu giữ trong CSDL. Thời gian đó là giá trị của đồng hồ
hệ thống khi thông tin được lưu giữ là hợp lệ. Trong quan hệ thời gian giao tác,
bất cứ khi nào có một thay đổi trong CSDL thì mốc thời gian thực tế của giao
tác thực hiện sự thay đổi đó (như chèn, xóa, cập nhật) sẽ được ghi lại. Thời gian
giao tác bị chặn hai đầu bởi các thời điểm khi CSDL được khởi tạo và trạng thái
hiện thời của chính nó.
Nếu ta chuyển CSDL phi thời gian sang CSDL thời gian giao tác, thì ta
sẽ tiến hành gán nhãn thời gian giao tác cho CSDL bằng cách thêm vào các
thuộc tính thời gian bắt đầu giao tác TST và thời gian kết thúc giao tác TET có
kiểu dữ liệu là Timestamp như chúng ta đã tìm hiểu ở mục 1.3.1.
Trong chương 2 của luận văn sẽ trình bày một cách cụ thể quá trình gán
nhãn thời gian giao tác trên CSDL sẽ diễn ra như thế nào. Trong chương này,
luận văn sẽ trình bày những nội dung như sau:
 Tìm kiếm một giá trị nhãn thời gian giao tác
 Liên kết định danh các giao tác với các bộ dữ liệu
 Biểu diễn giá trị until changed (UC)
 Các phương pháp gán nhãn thời gian giao tác


17

2.2. Tìm kiếm một giá trị nhãn thời gian giao tác
Nếu các bộ dữ liệu được gán nhãn thời gian với thời gian ủy thác, thì sự
thay đổi bộ phận phải được hoãn lại cho đến khi giao tác ủy thác [19], việc nêu
ra điều này làm cho giao tác không thể thấy được sự thay đổi của chính nó.
Các bộ gán nhãn thời gian với thời gian tạm thời trước thời gian ủy thác làm
cho giao tác có thể thấy được sự thay đổi của chính nó.


5

1997/06/08,

Uc

13:05:58
Trong đó có một giá trị đặc biệt là uc ở thời gian kết thúc giao tác TET. Giá trị
uc này cụ thể như thế nào sẽ được luận văn trình bày trong mục 2.4. bên dưới.


18

Bây giờ, ta tiến hành cập nhật lương mới cho nhân viên có tên “An” từ
25000 lên 30000 vào thời điểm là “1998/06/04; 08:56:12” và truy xuất lên nhãn
thời gian giao tác của NV_TT bằng câu lệnh truy vấn như sau:
--on 1998/06/04, 08:56:12:
UPDATE NV_TT SET LUONG =30000
WHERE TEN=’An’;
SELECT TEN, LUONG, TST, TET
FROM NV_TT;
COMMIT;
Với câu lệnh truy vấn này sẽ làm nảy sinh thêm 1 vấn đề đó là trong giao
tác có 1 thao tác cập nhật lương cho nhân viên An từ 25000 lên 30000 nên đã
làm thay đổi CSDL nhưng ngay sau đó lại có truy vấn đến các nhãn thời gian
giao tác trong CSDL đó. Đối với vấn đề này, chúng ta có thể xem xét giải quyết
như sau:
 Cách thứ nhất: Chúng ta có thể không cho phép truy vấn đó truy cập vào
nhãn thời gian.