KHAI NIEM PHU THUOC HAM

Go down

KHAI NIEM PHU THUOC HAM

Post  Admin on 4/12/2007, 10:05

KHAI NIEM PHU THUOC HAM
Chúng ta đă có khái niệm cơ bản về phụ thuộc hàm (Functional Dependency) trong một quan hệ. Phụ thuộc hàm có tầm quan trọng rất lớn trong việc phân tích và thiết kế mô h́nh dữ liệu.
Khái niệm: Quan hệ R được định nghĩa trên tập thuộc tính U = { A1, A2, ..., An}. A, B̀ U là 2 tập con của tập thuộc tính U. Nếu tồn tại một ánh xạ f: A ® B th́ ta nói rằng A xác định hàm B, hay B phụ thuộc hàm vào A, và kư hiệu là A ® B.
Định nghĩa h́nh thức của phụ thuộc hàm như sau:
Quan hệ Q (A, B, C) có phụ thuộc hàm A xác định B (kư hiệu là A ® B) nếu:
" q, q’ Ỵ Q, sao cho q.A = q’.A th́ q.B = q’.B
(Nghĩa là: ứng với 1 giá trị của A th́ có một giá trị duy nhất của B)
A là vế trái của phụ thuộc hàm, B là vế phải của phụ thuộc hàm.
A ® B được gọi là phụ thuộc hàm hiển nhiên nếu B Í A. Nghĩa là, một tập A lớn hơn và bao tập con B th́ A xác định được giá trị của các thuộc tính trong tập B là điều hiển nhiên.
A ® B được gọi là phụ thuộc hàm nguyên tố, hoặc nói cách khác, B được gọi là phụ thuộc hàm đầy đủ (fully functional dependence) vào A nếu "A’ A đều không có A’ ® B.
Ví dụ 5.3.1 :
Trong lược đồ CSDL quản lư hóa đơn bán hàng đă cho trong ví dụ 4.1.2 và 4.2.10, quan hệ HÓAĐƠN (Số-hóa-đơn, Số_chủng_loại_mặt_hàng, Tổng-trị-giá) có các phụ thuộc hàm sau:
f1: Số-hóa-đơn ® Số_chủng_loại_mặt_hàng;
f2: Số-hóa-đơn ® Tổng-trị-giá;
bởi v́ Số-hóa-đơn là khóa của lược đồ quan hệ HÓAĐƠN. Nếu biết số hóa đơn th́ ta có thể xác định được tất cả các thông tin c̣n lại liên quan đến hóa đơn đó, trong đó có thông tin về Số_chủng_loại_mặt_hàng và Tổng-trị-giá tất cả các mặt hàng của hóa đơn. Các phụ thuộc hàm trên đều là nguyên tố.
Quan hệ CHITIẾT_HĐ (Số-hóa-đơn, Mă-hàng, Số-lượng-đặt, Đơn-giá, Trị-giá) có các phụ thuộc hàm sau:
f1: Số-hóa-đơn, Mă-hàng ® Số-lượng-đặt.
f2: Số-hóa-đơn, Mă-hàng ® Đơn-giá.
f3: Số-hóa-đơn, Mă-hàng ® Trị-giá.
f4: Số-lượng-đạt, Đơn-giá ® Trị-giá.
Thuộc tính Đơn-giá phụ thuộc hàm không đầy đủ vào khóa (Số-hóa-đơn, Mă-hàng), bởi v́ nó chỉ phụ thuộc vào mặt hàng (thông qua Mă-hàng).
Qua ví dụ vừa nêu chúng ta thấy, trên một lược đồ quan hệ có thể tồn tại nhiều phụ thuộc hàm. Tập các phụ thuộc hàm thường được kư hiệu bằng chữ F.
Gọi F là tập các phụ thuộc hàm đối với lược đồ quan hệ R định nghĩa trên tập thuộc tính U và X ® Y là một phụ thuộc hàm; X,Y Í U. Ta nói rằng X ® Y được suy diễn lôgic từ F nếu R thỏa các phụ thuộc hàm của F th́ cũng thỏa X ® Y và kư hiệu là:
F ½= X ® Y.

Ví dụ 5.3.2:
Với F = { X ® Y, X ® Z, Y ® T }
Th́ ta có các phụ thuộc hàm X ® YZ và X ® T.
Gọi F+ là bao đóng (Closure) của F , tức là tập các phụ thuộc hàm được suy diễn lôgic từ F. Nếu F = F+ th́ ta nói F là họ đầy đủ (full family) của các phụ thuộc hàm.
Bài toán thành viên (MemberShip) nêu vấn đề phụ thuộc hàm X ® Y có phải là được suy diễn lôgíc từ F hay không (tức là X ® Y Ỵ F + ? ) là một bài toán khó giải. Nó đ̣i hỏi chúng ta phải có một hệ luật dẫn để suy diễn lôgic các phụ thuộc hàm.
Năm 1974, Amstrong đă đưa ra hệ tiên đề (c̣n gọi là hệ luật dẫn Amstrong, hay các tính chất của phụ thuộc hàm) (D.Maier - 1983 [2]) như sau:
X, Y, Z, W Í U. Phụ thuộc hàm có các tính chất sau đây:
(i) Tính phản xạ:
Nếu Y Í X th́ X ® Y.
(ii) Tính tăng trưởng
Nếu X ® Y th́ X Z ® YZ.
(iii) Tính bắc cầu:
Nếu X ® Y v Y ® Z th́ X ® Z.

Và người ta đă chứng minh rằng hệ tiên đề Amstrong là đúng đắn và đầy đủ thông qua 3 bổ đề (ở đây không chứng minh):
Bổ đề 1: Hệ tiên đề Amstrong là đúng, nghĩa là, với F là tập phụ thuộc hàm đúng trên quan hệ R, nếu X ® Y là một phụ thuộc hàm
Bổ đề 2: Từ hệ tiên đề Amstrong suy ra một số luật bổ sung sau đây:
(iv) Tính phân ră (hoặc luật tách):
Nếu X ® YZ th́ X ® Y v X ® Z.
(v) Tính hợp (hoặc luật hợp):
Nếu X ® Y và X ® Z th́ X ® YZ.
(vi) Tính tựa bắc cầu, hoặc bắc cầu giả:
Nếu X ® Y và YZ ® W th́ XZ ® W.
Định nghĩa: Bao đóng (Closure) của tập các thuộc tính X đối với tập các phụ thuộc hàm F (kư hiệu là XF+ ) là tập tất cả các thuộc tính A có thể suy dẫn từ X nhờ tập bao đóng của các phụ thuộc hàm F+:
X+F = { A ½ X ® A Ỵ F+ }

Bổ đề 3: X ® Y được suy diễn lôgic từ F nhờ hệ tiên đề Amstrong khi và chỉ khi Y Ỵ X+F.
Định ly: Hệ tiên đề Amstrong là đúng và đầy đủ.
Đây là nền tảng để chứng minh các lư thuyết CSDL quan hệ, đặc biệt là trong “bài toán thành viên” - kiểm tra xem một phụ thuộc hàm f : X ® Y có thuộc bao đóng của tập F hay không? ...
avatar
Admin
Admin

Posts : 41
Join date : 2007-09-29

View user profile http://cntt207.forumotion.com

Back to top Go down

Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum