Báo cáo nghiên cứu khoa học: " XÂY DỰNG PHỤ THUỘC HÀM THEO THỜI GIAN DỰA VÀO CÁC QUAN HỆ HAI NGÔI"

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

75
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: " XÂY DỰNG PHỤ THUỘC HÀM THEO THỜI GIAN DỰA VÀO CÁC QUAN HỆ HAI NGÔI"

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 việc thiết kế các CSDL có yếu tố thời gian ở mức logic, một số các nghiên cứu đã tập trung vào việc biểu diễn các ràng buộc phụ thuộc hàm theo thời gian (TFD) và xây dựng lý thuyết chuNn hoá trên các CSDL có yếu tố thời gian (gọi tắt là CSDL thời gian). Lý thuyết phụ thuộc hàm theo thời gian đã được nghiên cứu bởi X. S. Wang [2], C. S. Jensen [4], C. Combi [3], và J. Wijsen [1]. Mục đích của bài báo này tập trung vào việc xây dựng các ràng buộc TFD 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 (đơn vị cơ sở để đo 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 các đối tượng phức thuộc lớp các đối tượng hỗ trợ thuộc tính định danh và thuộc tính mối quan hệ. Trong nghiên cứu của mình, J. Wijsen đã chứng tỏ rằng các TFD theo cách tiếp cận này là một mở rộng so với cách tiếp cận của X. S. Wang. 103
Trong bài báo này, chúng tôi 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 cũng thực hiện việc hình thức hóa các định nghĩa TFD theo cách tiế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 nhân thời gian cho trước được biểu diễn bởi tập N các số nguyên dương {1, 2, 3, …}. Định nghĩa 2.1. (Quan hệ thời gian) Một tập con của N ⊗ N được gọi là một quan hệ thời gian. Trong đó: N ⊗ N = {(i, j) | i ∈ N, j ∈ N, i ≤ j} Ta ký hiệu: Forever = N ⊗ N Ví dụ 2.1. Month là quan hệ thời gian chứa (i, j) sao cho i, j thuộc về cùng một tháng. Giả sử rằng, số 1 tương ứng với ngày 1/1/2005, số 2 tương ứng với ngày 2/1/2005, … Khi đó Month có thể được định nghĩa như sau: 104
Ví dụ 2.2. Current và Twin là hai quan hệ thời gian đặc biệt: Current = {(i, i) | i ∈ N} Twin = {(1, 1), (1, 2), (2, 2)} Chú ý: ∅ và Forever cũng là các quan hệ thời gian. 2.2. Mô hình dữ liệu Định nghĩa 2.2. (Kiểu, lược đồ) Xét một số các kiểu nguyên tố: integer, string, boolean, float. Gọi: dom là hợp của các miền trị của các kiểu nguyên tố, att là tập các tên thuộc tính, obj là tập các OID, 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 {A1: τ1, …, An: τn}, với Ai ∈ 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} ρ(EMP) = {E#: string, Name: string, Sal: integer, Dept: DEPT, Chief: EMP } ρ(DEPT) = {Name: string, Head: EMP } Định nghĩa 2.3. (Phép gán định danh đối tượng) Cho C là một tập các tên lớp. Một phép gán định danh đối tượng cho C là một hàm π từ C đến P(obj) (tập tất cả các tập con của tập obj) mà mỗi c, d ∈ C, c ≠ d dẫn đến π(c) ∩ π(d) = ∅. Định nghĩa 2.4. (Bộ dữ liệu) Cho {A1: τ1, …, An: τn} là một kiểu trên C. Một bộ dữ liệu của kiểu {A1: τ1, …, An: τn} là một tập {A1: v1, …, An: vn} sao cho với mỗi i (i ∈ [1..n]), nếu τi ∈ C thì vi ∈ π(C), nếu τi là một kiểu nguyên tố thì vi 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 định danh đối tượng. 105
ν là một ánh xạ trên O (O = ∪{π(c) | c ∈ C}), ánh xạ mỗi OID của O đến một bộ dữ liệu của một kiểu xác định trên C, nghĩa là với mỗi c ∈ C, o ∈ π(c), ν(o) là một bộ dữ liệu của kiểu ρ(c). Một thể hiện của lược đồ (C, ρ) được gọi là rỗng nếu π(c) = ∅ với mỗi c ∈ C. Định nghĩa 2.6. (Đối tượng) Cho Ι = (π, ν) là một thể hiện của lược đồ (C, ρ). Cho c ∈ C và o ∈ π(c) với ν(o) = {A1: v1, …, An: vn}. Khi đó {λ: o, A1: v1, …, An: vn} đượ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). Cho c ∈ C, một phần tử của Ti (c) được gọi là đối tượng của c tại thời điểm i. Có thể xem Τi là giá trị dữ liệu tại thời điểm i. Định nghĩa 2.8. (Đồ thị biểu diễn lược đồ) Đồ thị biểu diễn lược đồ (SDG: Schema Dependency Graph) của một lược đồ (C, ρ) là một đồ thị có hướng mà mỗi lớp c ∈ C tương ứng với một nút có nhãn là c, và với mỗi thuộc tính phức A: d ∈ ρ(c), trong đó: d ∈ C, chúng ta vẽ một cạnh có hướng từ nút có nhãn c đến nút có nhãn d. Nếu SDG không có chu trình thì lược đồ được gọi là lược đồ không có chu trình. Nếu SDG có ít nhất một chu trình thì lược đồ được gọi là lược đồ có chu trình. Một lược đồ không hạn chế là lược đồ có chu trình hoặc không có chu trình. Ví dụ 2.4. Xét lược đồ trong ví dụ 2.3, ta có SDG như sau: Hình 2.1: SDG của lược đồ trong ví dụ 2.3 2.3. Phụ thuộc hàm theo thời gian Định nghĩa 2.9. Một phụ thuộc hàm theo thời gian (TFD) trên lược đồ (C, ρ) 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) ∈ α, t1 ∈ T i(c), t2 ∈ T j(c), nếu t1[X] = t2[X] thì t1[Y] = t2[Y]. 106
T được gọi là thỏa mãn tập các TFD ∑ nếu nó thỏa mỗi TFD của ∑. Một lược đồ mở rộng là một cặp ((C, ρ), ∑) với (C, ρ) là một lược đồ và ∑ là tập các TFD trên (C, ρ). Ví dụ 2.5. Xét lược đồ trong ví dụ 2.3 với các TFD cùng ngữ nghĩa tương ứng như sau: EPM: E# →Forever λ (Mã nhân viên không được sử dụng lại cho các nhân viên khác) EPM: E# →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 σ. Các quy tắc suy dẫn cho các TFD: Cho c ∈ C và X, Y, Z ⊆ [ρ(c)]λ ([ρ(c)]λ = att ∪ {λ}). TFD1. Nếu Y ⊆ X thì c: X →Forever Y (luật phản xạ) TFD2. Nếu c: X →α Y thì c: XZ →α YZ (luật tăng trưởng) TFD3. Nếu c: X →α Y và c: Y →β Z thì c: X →α ∩ β Z (luật bắc cầu) TFD4. 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ệu ∑* là tập các σ sao cho ∑ ⊢ σ. Bao đóng của ∑, kí hiệu ∑+, là tập các TFD trên (C, ρ) có thể được chứng minh từ ∑. 107
Định lý 2.1. Cho ((C, ρ), ∑) là một lược đồ mở rộng. σ là một TFD trên (C, ρ). Nếu ∑ ⊢ σ thì ∑ ⊨ σ. Từ định lý 2.1 ta thấy rằng nếu σ ∈ ∑* thì σ ∈ ∑+, tức là ∑* ⊆ ∑+ (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ó ∑+ = ∑*, có nghĩa là hệ tiên đề {TFD1, …, TFD7} là đúng đắn và đầy đủ trong trường hợp lược đồ không có chu trình. Định nghĩa 2.11. Cho ((C,ρ), Σ) là một lược đồ mở rộng. Cho σ là một TFD trên (C, ρ). Một thể hiện I = (π, ν) của (C, ρ) được gọi là hữu hạn nếu π(c) là hữu hạn với mọi c ∈ C. Ngược lại gọi là vô hạn. Một thể hiện không hạn chế là một thể hiện hoặc hữu hạn hoặc vô hạn. Một thể hiện theo thời gian T của (C, ρ) gọi là hữu hạn nếu mỗi Ti là hữu hạn. Ngược lại gọi là vô hạn. Một thể hiện theo thời gian không hạn chế là một thể hiện theo thời gian hoặc hữu hạn hoặc vô hạn. Σ suy dẫn không hạn chế σ, kí hiệu Σ ⊨ unr σ, khi và chỉ khi mọi thể hiện theo 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 Σ ⊨ σ thì Σ ⊨ σ. unr 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 A. Xây dựng các thể hiện T1 và T2 như sau: T1 (c) = {{λ: 1, A: 1}} và T 2 (c) = {{λ: 1, A: 2}, {{λ: 2, A: 3}}, {λ: 3, A: 4}, ...} ( T 2 (c) là vô hạn) Cuối cùng, xây dựng một thể hiện theo thời gian T với T1 và T2 như trên, và Ti rỗng với i > 2. Rõ ràng, T thỏa mãn c: A →Twin λ và không thỏa mãn c: λ →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 λ} ⊭ 108
c: λ →Twin A. Trong chứng minh của định lý sau, chúng ta khảo sát tất cả các thể hiện unr theo thời gian hữu hạn T của lược đồ ({c}, ρ) với ρ(c) = {A: c}, và chỉ ra rằng với T thỏa mãn c: A →Twin λ thì nó không thể không thỏa c: λ →Twin A. Định lý 2.3. 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 TFD. Hệ quả 2.1. Suy dẫn hữu hạn là khác nhau đối với lược đồ không chu trình và lược đồ không hạn chế. Chứng minh: Đối với các lược đồ không chu trình, ta có {c: A→Twin λ} ⊭ fin c: λ→Twin A (sử dụng giải thuật tính bao đóng logic). Định lý 2.3 cho thấy {c: A →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à ∑* ⊆ ∑+unr (iii) Định lý 2.5. Cho miền trị của mọi kiểu nguyên tố là vô hạn. Cho ((C,ρ), Σ) là một lược đồ mở rộng. Nếu Σ ⊨ unr c: X →α Y thì Σ ⊢ c: X →α Y, là một suy dẫn hữu hạn. Từ định lý 2.5 ta thấy rằng nếu σ ∈ ∑+unr thì σ ∈ ∑*, tức là ∑+urn ⊆ ∑* (iv) 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 {A1: τ1, …, An: τn} với A1, …, An là tên các thuộc tính khác nhau của att và mỗi τi là một trong các kiểu dữ liệu sau: Kiểu nguyên tố, tức τi có miền trị là dom. 109
Kiểu đa trị và đơn, tức τi có dạng set(a) (với a là kiểu nguyên tố), có miền trị là P(dom). Kiểu đa trị và phức hợp, tức τi có dạng set(tuple(τ′)) (với τ’ = A1: τ1’, …, An: τ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ợp: A: set(tuple(A1: τ1, ..., An: τn)) với τi là các kiểu nguyên tố (i ∈[1..n]). Khi đó ta bổ sung lớp cA ∈ C có kiểu {A1: τ1, ..., An: τn, B: c}. Ta thấy rằng, việc chuyển đổi thuộc tính đa trị và đơn (tức n = 1) là một trường hợp đặc biệt của việc chuyển đổi thuộc tính đa trị và phức hợp. Ví dụ 3.1. Xét lược đồ như sau: C = {EMP} ρ(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 cA ∈ C có kiểu {B1: c, B2: d}. Ví dụ 3.2: Xét lược đồ như sau: C = {EMP, PROJECT} ρ(EMP) = {E#: string, Name: string, Work_in: set(PROJECT)} ρ(PROJECT) = {Name: string, Head: EMP} Khi đó chúng ta tạo thêm lớp WORK_IN như sau: C = {EMP, PROJECT, WORK_IN} 110
ρ(EMP) = {E#: string, Name: string} ρ(PROJECT) = {Name: string, Head: EMP} ρ(WORK_IN) = {Emp: EMP, Project: PROJECT} Trong phạm vi của bài báo này, chúng tôi chỉ muốn chứng tỏ rằng từ mô hình dữ liệu mở rộng này ta có thể chuyển đổi thành mô hình dữ liệu quy ước ban đầu. Vấn đề xây dựng các ràng buộc TFD liên quan đến các thuộc tính đa trị là không được xét đến trong bài báo này. IV. Phụ thuộc hàm theo thời gian trên mô hình quan hệ Từ việc xây dựng các ràng buộc TFD trên các đối tượng phức theo cách tiếp cận củ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à Ti(r), được xác định như sau: Ti(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 t1, t2 ∈ r và (i, j) ∈ α, với: t1 ∈ Ti(r), t2 ∈ Tj(r), và t1[X] = t2[X] kéo theo t1[Y] = t2[Y]. Ví dụ 4.1: Cho quan hệ r như sau với nhân thời gian T* = Day: E# Name Sal Phone# Dept Day A1 Lê An 1.86 111 P1 4/5/2006 A1 Lê An 1.86 111 P2 9/5/2007 A1 Lê An 2.34 111 P2 7/6/2007 A1 Lê An 2.34 111 P2 8/6/2007 Nguyễn Huy B1 4.98 222 P3 8/6/2007 Nguyễn Huy B1 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 Phone# (Tại một thời điểm bất kỳ (ngày bất kỳ), họ tên xác định số điện thoại của nhân viên đó) 111
Nhận xét: Dựa vào định nghĩa 4.2, nếu xem thuộc tính định danh λ của một lớp c ∈ C trong mô hình đối tượng phức (đã nêu ở mục 2) như là khoá chính của một lược đồ quan hệ theo thời gian (R, T*), rõ ràng hệ 7 tiên đề đã xét trong mục 2.4 cũng đảm bảo tính đúng đắn. Ngoài ra, tính chất sau cho thấy các TFD là một mở rộng của các FD truyền thống. Tính chất 4.1. Cho lược đồ quan hệ theo thời gian (R, T*). Cho X, Y ⊆ R, quan hệ r trên R thỏa FD X → Y khi và chỉ khi r thỏa TFD X →Forever Y. Chứng minh: (⇒) Xét 2 bộ t1 và t2 thuộc r và (i, j) ∈ Forever sao cho t1 ∈ Ti(r), t2 ∈ Tj(r) và giả sử t1[X] = t2[X]. Vì r thỏa X → Y, ta suy ra t1[Y] = t2[Y]. Suy ra r thỏa X →Forever Y. (⇐) Xét 2 bộ t1 và t2 thuộc r, sao cho t1[X] = t2[X]. Khi đó ∃(i, j) ∈ N×N, t1 ∈ Ti(r), t2 ∈ Tj(r). Không mất tính tổng quát, ta có thể giả thiết: (i, j) ∈ Forever. Nhưng do r thỏa X →Forever Y, suy ra t1[Y] = t2[Y]. Vậy r thỏa X → Y. Tính chất 4.2. Cho lược đồ quan hệ theo thời gian (R, T*). Cho X ⊆ R và r là quan hệ trên R. Nếu r thoả TFD X →Current Y, ∀Y ⊆ R thì r thoả FD XT*→Y, ∀Y ⊆ R. Chứng minh: Xét 2 bộ t1 và t2 thuộc r, sao cho t1[XT*] = t2[XT*]. Suy ra t1[X] = t2[X] và t1[T*] = t2[T*]. Vì T* là thuộc tính chỉ nhân thời gian nên t1[T*] = t2[T*] = i (i ∈ N). Khi đó ∃(i, i) ∈ Current với t1 ∈ Ti(r) và t2 ∈ Ti(r) sao cho t1[X] = t2[X]. Vì r thoả TFD X →Current Y suy ra t1[Y] = t2[Y]. Vậy r thoả XT*→Y. Nhận xét: Từ tính chất trên, chúng ta thấy rằng, có thể tìm được khóa của lược đồ quan hệ theo thời gian (R, T*) nếu biết được khóa của Ti(r), ∀i = 1, n . V. Kết luận Thông qua việc trình bày vấn đề 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, chúng tôi thực hiện việc hình thức hóa các định nghĩa TFD trên mô hình dữ liệu quan hệ truyền thống. Tuy nhiên, cũng tương tự như lý thuyết phụ thuộc hàm truyền thống, việc xây dựng một loại ràng buộc phụ thuộc dữ liệu mới sẽ kéo theo một loạt các công việc cần phải giải quyết nhằm cho phép chuNn 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 112
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 In recent years, much research has been done about the extension of the constraints on the temporal databases to express rich and complicated meanings of the real world. This paper focuses on constructing temporal functional dependencies (TFD) based on binary relations which are called time relations with a certain granularity. This approach was first proposed by J. Wijsen [1] and was applied for the data model that supported complex objects. In this paper, an extension of this model with multivalued attributes is suggested. Then a method to convert the proposed model to Wijsen’s conventional model will be made. In addition, the definitions and properties of TFDs on the classical relational model are also constructed with this approach. It can be said that one of these properties proves that FDs are special cases of TFDs. 113