LỚP CNTT 2 - 2007
Would you like to react to this message? Create an account in a few clicks or log in to continue.

KHAI NIEM PHU THUOC HAM

Go down

KHAI NIEM PHU THUOC HAM Empty KHAI NIEM PHU THUOC HAM

Post  Admin 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? ...
Admin
Admin
Admin

Posts : 41
Join date : 2007-09-29

https://cntt207.forumotion.com

Back to top Go down

Back to top

- Similar topics

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