Hệ tiên đề cho phụ thuộc hàm

Gọi F là tập tất cả các phụ thuộc hàm đối với lược đồ quan hệ r(U) và X -> Y là một phụ thuộc hàm với X, Y ⊆ U, ta nói rằng X -> Y được suy diễn logic từ F nếu quan hệ trên r(U) đều thỏa mãn các phụ thuộc hàm của F thì cũng thỏa X -> Y. Sau đây là tập quy tắc của hệ tiên đề được Armstrong đề xuất vào năm 1974, được gọi là hệ tiên đề Armstrong.

Hệ tiên đề Armstrong

Gọi R(U) là lược đồ quan hệ với U = (A_1, A₂,..., A_n) là tập các thuộc tính: giả sử X, Y, Z ⊆ U, hệ tiên đề Armstrong bao gồm:

• Tính phản xạ: Nếu Y ⊆ X thì X -> Y
• Tính tăng trưởng: Nếu Z ⊆ U, X-> thì ZX -> ZY. Trong đó ZX=Z  X
• Tính bắc cầu: Nếu X -> Y và Y -> Zthì X -> Z.

Ví dụ:

Cho AB -> C, C -> A, chứng minh BC -> ABC

(1) C -> A (theo giả thiết)

(2) BC -> AB (áp dụng luật tăng trưởng tăng (1) lên B)

(3) AB -> C (theo giả thiết)

(4) AB -> ABC (tăng (3)AB)

(5) BC -> ABC (bắc cầu (1), (2)).

Hệ tiên đề Armstrong là đầy đủ, có nghĩa là nếu F là tập phụ thuộc hàm đúng trên quan hệ r và f : X -> Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ tiên đề Armstrong thì f đúng trên r

Tính hợp: nếu X -> Y và X -> Z thì X -> YZ .

Tính tựabắc cầu: Nếu X -> Y và WY -> Z thì XW -> Z.

Tính tách: Nếu X -> Y và Z ⊆ Y thì X -> Z.

Bao đóng của F được kí hiệu là F⁺, là tập tất cả các phụ thuộc hàm được suy diễn logic nhờ tiên đề Armstron, 3 bổ đề trên từ F, nếu F = F⁺ thì F là họ đầy đủ của các phụ thuộc hàm.

X -> Y là một phụ thuộc hàm suy ra từ F. Khi đó X⁺ được gọi là bao đóng của tập thuộc tính X nếu X⁺ là tập tất cả các thuộc tính U được suy dẫn bắt đầu từ tập X.

X⁺_F = { A | X -> A ∈ F⁺ }

Thuật toán tìm bao đóng của tập thuộc tính:

INPUT: X, F,U

OUTPUT: X⁺

S : = X

WHILE có (Z -> Y) thuộc F với Z ⊂ S và Y  S

DO S:= SY

ENDWHILE

X⁺ = S

Phương pháp: Tính liên tiếp các tập thuộc tính X_0, X_1, X_2,..., Xi

BC0: Đặt X₀ = X

BC1: Nếu tồn tại phụ thuộc hàm f: Y->Z ∈ F sao cho Y∈ X₀, Z ∈ U thì X₁ = X_{0 }Z BC2: Tương tư.

Until X_i = X_i+1.

Kết luận X⁺ = X_i.

Ví dụ:

Cho lược đồ quan hê R(U)=(ABCDEM), với U là tập thuộc tính, tập phụ thuộc hàm

F={AB -> C, C ->D, A -> E, BC ->EM}

Tính bao đóng của (AB)⁺

BC0: Đặt X₀ = AB

BC1: Tồn tại A -> E thuộc F, mà A∈ X₀, E ∈ U vậy X₁ = X_{0 }E = ABE

BC2: Tồn tại AB -> C thuộc F, mà AB∈ X₁, C ∈ U vậy X₂ = X_{1 }C = ABCE

BC3: Tồn tại C -> D thuộc F, mà C∈ X₂, D ∈ U vậy X₃ = X_{2 }D = ABCDE

BC4: Tồn tại BC -> EM thuộc F, mà BC∈ X₃, EM ∈ U vậy X₄ = X_{3 }M = ABCDEM

BC5: Xét toàn bộ các phụ thuộc hàm thuộc F, thì X₅ =X₄

Vậy kết luận (AB)⁺ = X₄ = ABCDEF.

Y gọi là phụ thuộc hàm bộ phận vào X nếu ∃ Z ⊂ X, Z -> Y

X ->Y

Ngược lại Y gọi là phụ thuộc hàm toàn bộ vào X.

Ví dụ:

F={AB -> C, C ->D, A -> C BC ->EM} => C phụ thuộc hàm bộ phận vào AB.

Y gọi là phụ thuộc hàm gián tiếp vào X nếu ∃ Z ⊂ U, sao choX -> Z, Z ->Y.

X ->Y

Ngược lại Y gọi là phụ thuộc hàm trực tiếp vào X.

Ví dụ:

F={AB -> C, C ->D, A -> C BC ->EM, AB -> D} => D phụ thuộc hàm gián tiếp vào AB.

Hai tập phụ thuộc hàm F và G được gọi là tương đương với nhau nếu mọi phụ thuộc hàm của G đều suy ra từ F và ngược lại mọi phụ thuộc hàm từ F cũng suy ra được từ G. Hoặc cũng có thể nói G là phủ của F và F cũng là phủ của G.

Chú ý:

Mỗi tập phụ thuộc hàm F tương đương với một tập phụ thuộc G trong đó các vế phải không có quá một thuộc tính

Mỗi tập phụ thuộc hàm F đều tương đương với một tập F’ tối thiểu

Cho tập thuộc tính U và tập phụ thuộc hàm F. Nguời ta nói F là tối thiểu khi và chỉ khi:

• Vế phải của mỗi phụ thuộc hàm trong F chỉ có một thuộc tính độc nhất.
• !∃ X -> A ∈ F tập F - {X -> A} tương đương với F (loại bỏ các phụ thuộc dư thừa).
• !∃ X -> A ∈ F, Z ⊂ X | F - {X -> A}  {Z -> A} tương đương với F (loại bỏ thuộc tính dư thừa vế trái)

Thuật toán: tìm phủ tối thiểu của tập phụ thuộc hàm F, với tập thuộc tính U:

INPUT: F, U

OUTPUT: G (G là phủ tối thiểu của F).

BC1: G = ϕ. Tách tất cả các phụ thuộc hàm f của F thành phụ thuộc hàm mà vế phải chỉ có một t thuộc tính:

FOR ∀f ∈ F, f = X -> DO G = G  {X -> A, A ∈ Y}

BC2: Loại bỏ những phụ thuộc hàm không đầy đủ:

WHILE ∃Z ⊂ X, Z ≠ X, G ≅ G {f}  {Z -> A} DO G = G {f} {Z -> A}

BC3: Loại bỏ những phụ thuộc hàm dư thừa:

FOR ∀ f ∈ G DO

IF G {f} ≅ THEN G = G {f}

BC4:RETURN (G).

Ta có thể diễn giải lại thuật giải như sau:

BC1: Tách tất cả các phụ thuộc hàm của F thành phụ thuộc hàm mà vế phải chỉ có một thuộc

tính, Ví dụ:

AB –> CD được tách thành AB ->C, AB -> D (luật tách)

BC2: Loại bỏ những phụ thuộc hàm không đầy đủ. Khi loại bỏ, ta phân bịêt hai loại phụ thuộc

hàm không đầy đủ sau:

Loại1: Phụ thuộc hàm mà vế phải là tập con của vế trái ( loại AB -> B)

Loai2: Hai phụ thuộc hàm có vế phải giống nhau, nếu vế trái của phụ thuộc hàm này chứa vế trái của phụ thuộc hàm kia thì ta loại ra khỏi F.

Ví dụ: Nếu có ABC -> D và BC - >D thì ta loại ABC -> D khỏi F.

BC3: Loại bỏ những phụ thuộc hàm dư thừa:

Giả sử hai phụ thuộc hàm có vế phải giống nhau: f1 = X -> A và f2 = Y -> A, lúc đó nếu có A ∈ X⁺_{F {f1}} thì loại f1 ra khỏi F:

Ví dụ:

Cho tập phụ thuộc hàm F = {A ->C, AB -> C,C ->DI, CD - >I, EC ->AB, EI ->C}, tìm phủ không dư thừa của F

BC1: Tách các phụ thuộc hàm sao cho vế phải chỉ có một thuộc tính duy nhất.

C -> D A -> C

C -> I AB -> C

EC -> A CD -> I

EC -> B EI ->C

BC2: Loại bỏ những phụ thuộc hàm không đầy đủ

Loại1: Giữ nguyên

Loại2: Loại AB -> C, CD -> I

Sau bước 2: F ={C -> D, C -> I, EC ->A, EC -> B, EI -> C, A -> C}

BC3: Loại bỏ những phụ thuộc hàm dư thừa

EI -> C C ∉ (EI)⁺_{(F EI -> C)}

A -> C C ∉ (A)⁺_{(F A -> C)}

Do vậy ta giữ cả hai phụ thuộc hàm nay. Vậy F’ = {C -> D, C -> I, EC ->A, EC -> B, EI -> C, A -> C}.

Là một hoặc một tập các thuộc tính xác định duy nhất một thực thể trong một tập thực thể.

Tập các thuộc tính X của một quan hệ R là một khoá nếu. Không tồn tại 2 bộ khác nhau nhưng tất cả các phần tử của X đều giống nhau, và không có tập con thực sự nào của X có tính chất này.

Định nghĩa: Cho lược đồ quan hệ R(A₁, A₂,...,A_n) và tập phụ thuộc hàm F, X ⊆ A₁, A₂,...,A_{n .} Ta nói X là một khoá của R khi và chỉ khi X -> A₁, A₂,...,A_n ∈ F⁺ (tất cả các thuộc tính phụ thuộc vào tập thuộc tính X), ∃ Y ⊂ X | X -> A₁A₂...A_n ∈ F⁺.

Sau đây là một số định nghĩa về khoá của quan hệ:

• Khoá dự tuyển (candldate key): là khoá của quan hệ. Một quan hệ có thể có nhiều khóa dự tuyển.
• Khoá chính (Primary key): là khoá dự tuyển được chọn làm khoá chính của quan hệ. Khoá chính không thể rỗng ( NOT NULL).
• Siêu khoá (Supper key): một khoá gọi là siêu khoá nếu như ta bỏ đi một hay nhiều thuộc tính bất kỳ, thì không đảm bảo phần còn lại là khóa.
• Khoá ngoại (Foreign key): (khoá liên kết ) là một hoặc một tập thuộc tính trong quan hệ R1 nhưng là khoá chính trong quan hệ R_2.

Một thuộc tính trong lược đồ quan hệ R(U) được gọi là thuộc tính khoá nếu nó là một thành phần của một khoá nào đó của R. Ngược lại người ta gọi là thuộc tính không khoá (thuộc tính thứ cấp).

Ví dụ: Cho lược đồ quan hệ R = (ABCD) và tập phụ thuộc hàm

F = { A → C, AB → DC}, khoá là {AB}. Khi đó thuộc tính A, B gọi là thuộc tính khoá, còn thuộc tính D, C gọi là thuộc tính không khóa.

-Thuật toán tìm tất cả các khoá của một lược đồ quan hệ

Bước 1: Tạo tập thuộc tính nguồn TN, tập thuộc tính trung gian TG

Bước 2: if TG = ∅ then lược đồ quan hệ chỉ có một khoá K

K = TN

Kết thúc

Ngược lại

Qua bước 3

Bước 3: Tìm tất cả các tập con Xi của tập trung gian TG

Bước 4; Tìm các siêu khoá Si băng cách :

∀ Xi

if (TN  Xi)⁺ = Q⁺ then

Si = TN  Xi

Bước 5: Tìm kháo bằng cách loại bỏ các siêu khoá không tối tiểu

∀Si, Sj ∈ S

if Si ⊂ Sj then Loại Sj ra khoi tệp siêu khóa S

S còn lại chính là tập khoá cần tìm.

Ví dụ:

Tìm tất cả các khoá của lược đồ quan hệ sau và tập phụ thuộc hàm như sau:

Áp dụng thuật toán trên ta có lời giải như sau:

TN = {S}; TG ={C, Z}

Gọi Xi là các tập con TG:

Như ta đã biết mô hình quan hệ do Cood đề suất năm 1970, có những ưu điểm vượt trội so với các mô hình trước đó:

• Đơn giản: Các dữ liệu được biểu diễn dưới một dạng duy nhất, là các bảng giá trị, khá tự nhiên và dễ hiểu đối với mọi người sử dụng
• Chặt chẽ: Các khái niệm được hình thức cao, cho phép sử dụng các công cụ toán học, có thuật toán
• Trừu tượng hoá cao: Mô hình chỉ dừng ở mức quan niệm, nghĩa là độc lập với mức vật lý, với sự cài đặt, với các thiết bị. Nhờ đó làm tăng thêm tính độc lập của dữ liệu và chương trình.
• Cung cấp các ngôn ngữ truy nhập dữ liệu ở mức cao ( như SQL...) nhờ đó dễ sử dụng và trở thành chuẩn.

Tuy vậy, khi thiết kế một cơ sở dữ liệu quan hệ thường phải chọn các lược đồ quan hệ. Việc chọn tập các lược đồ này có thể tốt hơn hay xấu hơn tập các lược đồ khác dựa trên một số tiêu chuẩn nào đó. Trọng tâm của việc thiết kế các lược đồ cơ sở dữ liệu là ta tổ chức bao nhiêu lược đồ và mỗi lược đồ có những thuộc tính nào để bảo đảm các tính chất sau:

• Không trùng lặp dữ liệu: Trong một quan hệ, giá trị của một thuộc tính nào đó chiếm dụng lượng bộ nhớ lớn không được lặp lại nhiều lần
• Nhất quán dữ liệu: Trong một lược đồ quan hệ xác định được nhiều phụ thuộc hàm, tất cả các quan hệ xác định trên lược đồ quan hệ phải thoả các phụ thuộc hàm trên lược đồ ấy.
• Không gây dị thường khi thêm bộ, xoá bộ.

Vậy để tạo một cơ sở dữ liệu tốt hơn, nghĩa là không trùng lặp thông tin, nhất quán dữ liệu, ta phải tách một lược đồ quan hệ thành nhiều lược đồ con.

Ví dụ:

Khảo sát về quan hệ cungcap: cungcap(tên, địachỉ, mặthàng, giá)

Dư thừa dữ liệu: Dễ dàng thấy rằng mỗi khi xuất hiện tên nhà cung cấp thì địa chỉ của ông ta lại lặp lại trong quan hệ.

Không nhất quán dữ liệu: là hệ quả của việc dư thừa dữ liệu khi sửa đổi địa chỉ của nhà cung cấp ở một bộ nào đó còn các bộ khác vẫn dữ nguyên, khi đó xẩy ra một nhà cung cấp lại không có địa chỉ duy nhất.

Dị thường khi thêm bộ: một nhà cung cấp khi chưa cung cấp một mặt hàng nào cả, khi đó không thể đưa địa chỉ, tên nhà cung cấp là một bản ghi vào quan hệ vì rằng sẽ phải đưa giá trị vào vị trí của thuộc tính mặt hàng.

Dị thường khi xoá bộ: là vấn đề ngược lại của dị thường khi thêm bộ. Không thể xoá tất cả các mặt hàng được cung cấp bởi một nhà cung cấp, vì mặt hàng đó có thể được nhiều người cùng cung cấp.

Phép tách một lược đồ quan hệ U = A_1, A₂,...,A_n là việc thay thế lược đồ quan hệ U bằng một tập lược đồ con: U_1, U₂,...,U_n trong đó U_i ⊆ U, i = 1..n.

U = U_{1 }U_{2 ... } U_n và U_{i ≠}U_j với i _≠j

Cho lược đồ quan hệ R và F là tập phụ thuộc hàm xác định trên r.

Phép tách lược đồ R thành các luợc đồ con R_1, R_2, ..., R_n, dựa trên tập F gọi là phép tách bảo toàn thông tin nếu: Với mọi quan hệ r trên R ta đều có r là phép kết nối tự nhiên của các phép chiếu của r lên các R_i:

∀ r(r) => r = Π_R1(r) * Π_R2(r) *...*Π_Rn(r)

INPUT: Lược đồ quan hệ R = {A_1, A₂,...,A_n }, tập phụ thuộc hàm F và phép tách ρ=(R_1,..,R_k)

OUTPUT: Kết luận phép tách ρ có phải là mất mát thông tin không?

Ta có thể diễn giải lại thuật giải như sau:

BC1: Dựng bảng S gồm n cột và k hàng, cột j ứng với thuộc tính A_j, hàng i ứng với lược đồ R_i.

BC2: Ở vị trí hàng i và cột j, đặt aijnếu A_j thuộc R_i. Nếu không đặt bij_.

BC3: Xét mỗi phụ thuộc hàm X -> Y trong F cho đến khi bảng S không còn thay đổi:

Lable :Với mỗi phụ thuộc hàm X -> Y trong F, nếu trong bảng S có chứa 2 dòng u, v mà:

u[X] = v[X ] = aij

thì sửa các giá trị tại cột Y như sau:

+ Nếu u[Y ] = v[Y] = aij thì không sửa

+ Nếu u[Y] = v[Y] = bij thì không sửa

+ Nếu u[Y] = aij u[Y] = bij

v[Y] = bij hoặc v[Y] = aij thì sửa bij bằng aij

Lặp lại BC3.

BC4: Nếu thu được 1 hàng toàn aij thì phép tách này không mất thông tin, ngược lại phép tách mất thông tin.

Ví dụ:

Cho r = ABCD, F = { A -> B, AC ->D} và phân rã ρ = {(AB), (ACD)}.

T₁(R) A B C D

R₁ a₁₁ a₁₂ b₁₂ b₁₃

R₁ a₂₁ b₂₂ a₂₃ a₂₄

Với A -> B ta có: T₂(R) A B C D

R₁ a₁₁ a₁₂ b₁₃ b₁₄

R₁ a₂₁ a₂₂ a₂₃ a₂₄

Chúng ta thấy rằng ở bảng T₂(R) xuất hiện hàng thứ hai toàn a_ij nên phép tách ρ bảo toàn thông tin.

Trong trường hợp ρ = {R_1, R₂ }, nghĩa là phép tách chỉ có 2 lược đồ con. Để kiểm tra phép tách có bảo toàn thông tin, ta sử dụng định lý sau.

Phép phân rã R thành ρ = {R₁(U₁), R₂(U₂)}là bảo toàn thông tin khi và chỉ khi

U₁  U₂ → U₁U₂ hay U₁  U₂ → U₂U₁

• Lược đồ quan hệ R, tập phụ thuộc F, ρ = {R_1, R_2,..,R_k }.
• Phụ thuộc hình chiếu: Hình chiếu của F trên lược đồ R_i là tập các phụ thuộc X → Y ∈ F⁺ sao cho XY ⊆ Z, kí hiệu: Π_Ri(F).
• Phân rã ρ bảo toàn phụ thuộc hàm F nếu hợp các phụ thuộc hình chiếu Π_Ri(F) với i = 1...k khẳng định logic tất cả các phụ thuộc hàm trong F.

ví dụ:

Cho lược đồ quan hệ R(ABC), và F = {A -> B, A -> C, B -> C}, phân rã thành R₁(A,B) và R₂(BC).

Ta có tập phụ thuộc hình chiếu như sau

(1) A -> B, khi chiếu trên R₁(AB)

(2) B -> C, khi chiếu trên R₂(BC)

Từ (1) và (2) ⇒ A -> C (tính chất bắc câu). Vậy phân rã trên là bảo toàn phụ thuộc.

INPUT: Lược đồ quan hệ R = A_1, A₂,...,A_n, tập phụ thuộc hàm F, phân rã ρ = {R_1, R_2,..,R_k }

OUTPUT: Khẳng định ρ có phải là phân rã bảo toàn phụ thuộc.

Phương pháp:

• {X -> Y} ∉ {phụ thuộc hình chiếu của F lên các lược đồ}
• Cần kiểm tra xem {phụ thuộc hình chiếu của F lên các lược đồ }=>{ X -> Y}
• Nếu có thì khẳng định ρ bảo toàn F.

Thuật toán kiểm tra X -> Ycó được suy dẫn từ tập phụ thuộc hình chiếu:

BEGIN

Z:=X;

WHILE vẫn còn những thay đổi với Z DO

FOR I:=1 TO K DO

Z:=Z  (( Z  R_i) (bao đóng được lấy ứng với F)

END.

Kết luận: Nếu Y là tập con của Z thì X -> Y được suy ra từ tập phụ thuộc hình chiếu và ρ bảo toàn F.

Ví dụ:

Cho R(ABCD) và ρ ={ab, bc, cd}, F = {A -> B, B -> C, C -> D, D -> A}

Ta có tập phụ thuộc hình chiếu là: A -> B, B - > C, C -> D, còn D -> A Không thuộc tập phụ thuộc hình chiếu. Cần kiểm tra xem D -> A có được suy dẫn từ tập phụ thuộc hình chiếu không.

Áp dụng thuật toán :

Z = {D}

Với R_i = AB;

Z = {D}  (( {D}  {AB})⁺  {AB})={D}

Tương tự với R_i = BC cũng không làm thay đổi Z.

Với R_i = CD:

Z = {D}  (( {D}  {CD})⁺  {CD})

= {D}  ({D})⁺  {CD})

= {D}  ({ABCD})  {CD})

= {CD}

Với R_i = BC áp dụng cho Z ={CD} cho Z = {BCD}

Với R_i = AB áp dụng cho Z= {BCD} cho Z = {ABCD}

Z không thay đổi nhiều, và Z có chứa A nên ρ bảo toàn F.