103
TẠP CHÍ KHOA HỌC, Đại học Huế, Số 50, 2009 XÂY DỰNG PHỤ THUỘC HÀM THEO THỜI GIAN
D
ỰA VÀO CÁC QUAN HỆ HAI NGÔI
Hoàng Quang, Nguyễn Trung Dũng
Trường Đại học Khoa học, Đại học Huế

TÓM TẮT
Trong thời gian qua, đã có nhiều nghiên cứu quan tâm đến việc mở rộng các ràng buộc
trên các cơ sở dữ liệu thời gian nhằm biểu diễn ngữ nghĩa vốn phức tạp và phong phú của thế
giới thực.
Bài báo tập trung vào việc xây dựng các phụ thuộc hàm theo thời gian (viết tắt là các
TFD) dựa trên các quan hệ hai ngôi được gọi là các quan hệ thời gian với một nhân thời gian
cho trước. Cách tiếp cận này đã được đề xuất bởi J. Wijsen [1] và áp dụng trên mô hình dữ liệu
hỗ trợ thuộc tính định danh đối tượng. Trong bài báo này, chúng tôi thực hiện việc mở rộng mô
hình dữ liệu quy ước của J. Wijsen cho phép hỗ trợ thuộc tính đa trị và trình bày phương pháp
chuyển đổi các mô hình này thành mô hình dữ liệu quy ước của J. Wijsen.
Ngoài ra, chúng tôi xây dựng định nghĩa và các tính chất của các TFD theo cách tiếp
cận này trên mô hình quan hệ. Một trong những tính chất này cho thấy rằng các phụ thuộc hàm
là trường hợp đặc biệt của các TFD.
I. Giới thiệu
Trong th
ời gian qua, đã có nhiều nghiên cứu quan tâm đến việc mở rộng các
ràng bu
ộc trên các cơ sở dữ liệu (CSDL) có yếu tố thời gian (gọi tắt là CSDL thời gian)
nh
ằm biểu diễn ngữ nghĩa vốn phức tạp và phong phú của thế giới thực. Liên quan đến

ếp cận của J. Wijsen trên mô hình quan hệ truyền thống, và chứng minh rằng
cách ti
ếp cận này là một mở rộng của các phụ thuộc hàm truyền thống (FD).
Theo
đó, trong mục tiếp theo của bài báo này, chúng tôi trình bày việc xây dựng
các TFD trên mô hình d
ữ liệu hỗ trợ các đối tượng phức theo cách tiếp cận của J. Wijsen,
bao g
ồm các định nghĩa về quan hệ hai ngôi dựa trên một nhân thời gian, mô hình dữ
li
ệu quy ước, phụ thuộc hàm theo thời gian, và một số kết quả đáng quan tâm liên quan
đến tính đúng đắn và tính đầy đủ của hệ các tiên đề cho các ràng buộc phụ thuộc dữ liệu
theo th
ời gian. Trên cơ sở đó, trong mục 3, chúng tôi thực hiện việc mở rộng mô hình
d
ữ liệu quy ước của J. Wijsen nhằm cho phép hỗ trợ thuộc tính đa trị, và trình bày
ph
ương pháp chuyển đổi các mô hình này thành mô hình dữ liệu quy ước của J. Wijsen.
Vi
ệc hình thức hóa các TFD trên mô hình quan hệ truyền thống được trình bày trong
m
ục 4. Cuối cùng là phần kết luận của bài báo.
II. Ph
ụ thuộc hàm theo thời gian trên các đối tượng phức
2.1. Mô hình th
ời gian
Mô hình th
ời gian quy ước được sử dụng trong bài báo này theo cách tiếp cận
c
ủa J. Wijsen là dựa trên các quan hệ hai ngôi được gọi là các quan hệ thời gian với một

và class là t
ập các tên lớp. Cho C là một tập hữu hạn các tên lớp (C ⊆ class).
M
ột kiểu trên C là một tập {A
1
: τ
1
, …, A
n
: τ
n
}, với A
i
∈ att và mỗi τ
i
là một kiểu
nguyên t
ố hoặc một lớp của C (i ∈ [1 n]).
M
ột lược đồ là một cặp (C,
ρ
) với
ρ
là một toàn ánh trên C (ánh xạ mỗi tên lớp
c
ủa C đến một kiểu trên C).
Ví d
ụ 2.3. Xét lược đồ: C = {EMP, DEPT}

ρ

n
: τ
n
} là một tập {A
1
: v
1
, …, A
n
: v
n
} sao cho với mỗi i (i ∈ [1 n]), nếu τ
i
∈ C thì v
i
∈
π(C), n
ếu τ
i
là một kiểu nguyên tố thì v
i
thuộc miền của kiểu nguyên tố đó.
Định nghĩa 2.5. (Thể hiện của lược đồ)
M
ột thể hiện của lược đồ (C,
ρ
) là một cặp Ι
ΙΙ
Ι = (π, ν), trong đó:
π là phép gán

1
: v
1
, …, A
n
: v
n
} được gọi là một đối tượng
c
ủa c.
Định nghĩa 2.7. (Thể hiện theo thời gian)
M
ột thể hiện theo thời gian Τ
ΤΤ
Τ của lược đồ (C,
ρ
) là một dãy vô hạn các thể hiện
c
ủa (C,
ρ
). Thể hiện thứ i của Τ
ΤΤ
Τ được kí hiệu Τ
ΤΤ
Τ
i
= (π
i
, ν
i

ρ
) có
d
ạng c: X →
α
Y với c ∈ C, α là một quan hệ thời gian và X, Y ⊆ [
ρ
(c)]
λ
trong đó X ≠ ∅.
Cho T là m
ột thể hiện theo thời gian của (C,
ρ
). Khi đó, thể hiện theo thời gian
T
được gọi là thỏa TFD c: X →
α
Y khi và chỉ khi mọi (i, j) ∈ α, t
1
∈
T
i
(c), t
2
∈
T
j
(c),
n
ếu t

→
Year
Dept (Một nhân viên không thể thay đổi phòng ban trong vòng
m
ột năm)
EPM: E#
→
Month
Sal (Một nhân viên không thể có hai khoản lương khác nhau
trong vòng m
ột tháng)
DEPT: Name
→
Current
λ (Không có hai phòng ban cùng tên tại bất cứ thời điểm
nào)
2.4. Tính ch
ất
Định nghĩa 2.10. (Suy dẫn logic)
Cho ((C,
ρ
), ∑) là một lược đồ mở rộng. σ là một TFD trên (C,
ρ
). TFD σ được
suy d
ẫn logic bởi ∑, kí hiệu ∑ ⊨ σ, khi và chỉ khi mọi thể hiện theo thời gian của (C,
ρ
)
mà th
ỏa mãn ∑ thì cũng thỏa mãn σ.

ếu c: X →
α
Y và c: X →
β
Y thì c: X →
α
∪
β
Y
TFD5. c: X
→
∅
Y
TFD6. c: {
λ} →
Current
X.
TFD7. N
ếu α ⊆ β và c: X →
β
Y thì c: X →
α
Y
Cho ((C,
ρ
), ∑) là một lược đồ mở rộng. σ là một TFD trên (C,
ρ
). Chúng ta viết
∑ ⊢ σ để biểu thị rằng σ có thể được chứng minh từ ∑ bằng cách sử dụng các tiên đề
trong {TFD1, TFD2, TFD3, TFD4, TFD5, TFD6, TFD7}. Kí hi

+
(i)
Định lý 2.2. Cho ((C,
ρ
), Σ) là một lược đồ mở rộng sao cho (C,
ρ
) không có chu
trình ch
ứa c ∈ C. Nếu Σ ⊨ c: X →
α
Y thì Σ ⊢ c: X →
α
Y, là một suy dẫn hữu hạn.
Cho σ = c: X →
α
Y, với (C,
ρ
) không có chu trình chứa c ∈ C. Từ định lý 2 ta
th
ấy rằng nếu σ ∈ ∑
+
thì σ ∈ ∑
*
, tức là ∑
+
⊆ ∑
*
(ii)
Nh
ận xét: Từ (i) và (ii) chúng ta có ∑

th
ời gian không hạn chế của (C,
ρ
) thỏa mãn Σ thì cũng thỏa mãn σ.
Σ suy d
ẫn hữu hạn σ, kí hiệu Σ ⊨
fin
σ, khi và chỉ khi mọi thể hiện theo thời gian
h
ữu hạn của (C,
ρ
) thỏa mãn Σ thì cũng thỏa mãn σ.
Nh
ận xét: Rõ ràng, nếu Σ ⊨
unr
σ thì Σ ⊨
fin
σ.
Ví d
ụ 2.6. Giả sử các số tự nhiên được sử dụng thay cho các OID. Xét lược đồ
({c},
ρ
) với
ρ
(c) = {A: c}. Rõ ràng lược đồ có chu trình chứa c. Chúng ta sẽ tìm một thể
hi
ện theo thời gian thỏa mãn c: A →
Twin
λ và không thỏa mãn c: λ →
Twin

Twin
A.
Nh
ận xét: Không thể xây dựng một thể hiện theo thời gian hữu hạn thỏa mãn
c: A →
Twin
λ và không thỏa mãn c: λ →
Twin
A.
Ti
ếp theo, chúng ta sẽ trình bày chứng minh suy dẫn hữu hạn và suy dẫn không
h
ạn chế là không thể thực hiện đồng thời đối với các lược đồ không hạn chế. Để chứng
minh
điều này, ta cần chứng tỏ rằng {c: A →
Twin
λ}⊨
fin
c: λ →
Twin
A trên một lược đồ
có chu trình ch
ứa c. Mặt khác, ví dụ 2.6 đã chứng tỏ rằng {c: A →
Twin
λ} ⊭

109
unr
c: λ →
Twin

fin
c: λ →
Twin
A đối với một lược đồ không hạn chế. Từ đó ta có điều
ph
ải chứng minh.
Nh
ận xét: Hệ quả 2.1 cho thấy rằng hệ tiên đề của chúng ta là không đầy đủ cho
suy d
ẫn hữu hạn trên các lược đồ không hạn chế.
Định lý 2.4. Cho ((C,
ρ
), Σ) là một lược đồ mở rộng. Cho σ là một TFD trên
(C,
ρ
). Nếu Σ ⊢ σ thì Σ ⊨
unr
σ.
Đối với trường hợp suy dẫn không hạn chế, bao đóng của ∑ kí hiệu là ∑
+
unr

T
ừ định lý 2.4 ta thấy rằng nếu σ ∈ ∑
*
thì σ ∈ ∑
+
unr
, tức là ∑
*

Nh
ận xét: Từ (iii) và (iv) chúng ta có ∑
+
urn
= ∑
*
,

có nghĩa là hệ tiên đề {TFD1,
…, TFD7} là
đúng đắn và đầy đủ đối với suy dẫn không hạn chế trên các lược đồ không
h
ạn chế.
III. Mở rộng mô hình dữ liệu quy ước
Trong mô hình d
ữ liệu quy ước của J. Wijsen chỉ hỗ trợ thuộc tính phức (thuộc
tính m
ối quan hệ). Nhằm hướng đến việc mở rộng mô hình dữ liệu này về mặt cấu trúc,
trong ph
ần này chúng tôi thực hiện việc mở rộng mô hình dữ liệu quy ước cho phép hỗ
tr
ợ thuộc tính đa trị. Từ đó, cho thấy rằng ta cũng có thể chuyển đổi các mô hình mở
r
ộng này thành mô hình dữ liệu theo quy ước của Wijsen.
3.1 Mô hình dữ liệu
Định nghĩa 3.1. Cho C là một tập hữu hạn các tên lớp (C ⊆ class). Một kiểu trên
C là m
ột tập {A
1
: τ

1
’, …, A
n
: τ
n
’),
có mi
ền trị là P(dom(τ
1
’)x xdom(τ
n
’)).
Ki
ểu phức và đơn trị, tức τ
i
là một lớp c nào đó của C, có miền trị là π(c).
Ki
ểu phức và đa trị, tức τ
i
có dạng set(c) (với c ∈ C), có miền trị là P(π(c)).
3.2 Chuyển đổi thuộc tính đa trị
3.2.1 Chuy
ển đổi thuộc tính đa trị và phức hợp thành các đối tượng phức
Cho l
ược đồ (C,
ρ
). Xét lớp c ∈ C. Gọi A ∈
ρ
(c) là thuộc tính đa trị và phức
h

ρ
(EMP) = {E#: string,
Name: string,
Lang_Stand: set(tuple(Language: string; Standard: string))}
Khi
đó chúng ta tạo thêm lớp LANG_STAND vào lược đồ như sau:
C = {EMP, LANG_STAND}

ρ
(EMP) = {E#: string, Name: string}
ρ
(LANG_STAND) = {Language: string, Standard: string, Emp: EMP}
3.2.2 Chuy
ển đổi thuộc tính đa trị và phức thành các đối tượng phức
Xét l
ớp c ∈ C. Gọi A ∈
ρ
(c) là thuộc tính đa trị và phức: A: set(d), với d ∈ C.
Khi
đó ta bổ sung lớp c
A
∈ C có kiểu {B
1
: c, B
2
: d}.
Ví d
ụ 3.2: Xét lược đồ như sau:
C = {EMP, PROJECT}


ủa J. Wijsen, trong phần này chúng tôi thực hiện việc hình thức hóa các khái niệm này
trên mô hình d
ữ liệu quan hệ truyền thống, đồng thời chứng tỏ rằng các FD truyền
th
ống là một trường hợp đặc biệt của các TFD theo cách tiếp cận này khi quan hệ thời
gian
α bằng Forever.
Định nghĩa 4.1. (Thể hiện của một quan hệ tại một thời điểm)
Cho l
ược đồ quan hệ R, trong đó có thuộc tính thời gian là thuộc tính T* dùng
để mô tả nhân thời gian, gọi tắt là lược đồ quan hệ theo thời gian (R, T*). Cho r là quan
h
ệ trên (R, T*). Khi đó, một thể hiện tại thời điểm i của r, ký hiệu là T
i
(r), được xác định
nh
ư sau: T
i
(r) = δ
T* =i
(r).
Định nghĩa 4.2. (Phụ thuộc hàm theo thời gian)
Cho l
ược đồ quan hệ theo thời gian (R, T*). Cho X, Y ⊆ R và α là một quan hệ
th
ời gian. Khi đó, quan hệ r trên R được gọi là thỏa TFD X →
α
Y, nếu với mọi t
1
, t


A1 Lê An 2.34

111 P2 7/6/2007

A1 Lê An 2.34

111 P2 8/6/2007

B1 Nguyễn Huy 4.98

222 P3 8/6/2007

B1 Nguyễn Huy 4.98

333 P3 20/6/2007

Ta thấy r thoả các TFD sau:
§ E#
→
Month
Sal (Lương của một nhân viên không thay đổi trong một
tháng)
§ E#
→
Year
Dept (Nhân viên không thay đổi phòng ban trong một năm)
§ Name
→
Current

(r), t
2
∈ T
j
(r) và
gi
ả sử t
1
[X] = t
2
[X]. Vì r thỏa X → Y, ta suy ra t
1
[Y] = t
2
[Y]. Suy ra r thỏa X →
Forever
Y.
(⇐) Xét 2 b
ộ t
1
và t
2
thuộc r, sao cho t
1
[X] = t
2
[X].
Khi
đó ∃(i, j) ∈ N×N, t
1

thuộc r, sao cho t
1
[XT*] = t
2
[XT*]. Suy ra t
1
[X] = t
2
[X] và
t
1
[T*] = t
2
[T*].
Vì T* là thu
ộc tính chỉ nhân thời gian nên t
1
[T*] = t
2
[T*] = i (i ∈ N).
Khi
đó ∃(i, i) ∈ Current với t
1
∈ T
i
(r) và t
2
∈ T
i
(r) sao cho t

Nn hóa các lược đồ CSDL. Vấn đề này còn vấn đề mở và đáng quan tâm.
Ngoài ra, trong bài báo này, chúng tôi c
ũng đã thực hiện việc mở rộng mô hình
d
ữ liệu quy ước của Wijsen theo cách có hỗ trợ thuộc tính đa trị và trình bày phương

113
pháp chuyển đổi các mô hình này thành mô hình dữ liệu quy ước của Wijsen. Tuy nhiên,
các ràng bu
ộc TFD liên quan đến các thuộc tính đa trị đã không được xét đến trong bài
báo này, và
đây cũng là hướng nghiên cứu tiếp theo của chúng tôi trong lĩnh vực này.
TÀI LIỆU THAM KHẢO
7. J. Wijsen, Temporal FDs on Complex Objects, ACM Transactions on Database Systems,
Vol. 24, No.1, March (1999).
8. X. S. Wang, A. Brodsky, S. Jajodia and C. Bettini, Logical Design for Temporal
Databases with Multiple Granularities, ACM Transactions on Database Systems, Vol.
22, No.2, June (1997).
9. C. Combi, R. Rossato, Temporal Functional Dependencies with Multiple Granularities:
A Logic Based Approach, LNCS 3180, (2004), 864-873.
10. Christian S.Jensen, Senior Member, IEEE, and Richard T. Snodgrass, Senior Member,
IEEE, Temporal Database Management, 2001.
11. R. Elmasri, S. B. Navathe, Fundamentals of Database Systems – 5th Edition, Addison
Wesley, 2007.

CONSTRUCTING TEMPORAL FUNCTIONAL DEPENDENCIES
BASED ON BINARY RELATIONS
Hoang Quang, Nguyen Trung Dung
College of Sciences, Hue University
SUMMARY