Giáo trình

Giáo trình Cơ Sở Dữ Liệu

Science and Technology

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

Tác giả: unknown

Hệ tiên đề Armstrong

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 = (A1, A2,..., An) 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=ZX size 12{ ital "ZX"=Z union 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)).

Bổ đề 1:

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

Bổ đề 2:

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 tập phụ thuộc hàm F (F+)

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.Bao đóng của tập thuộc tính (X+)

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à 

YS size 12{Y nsubset 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 X0, X1, X2,..., Xi

BC0: Đặt X0 = X

BC1: Nếu tồn tại phụ thuộc hàm f: Y->Z ∈ F sao cho Y∈ X0, Z ∈ U thì X1=X0Z size 12{X rSub { size 8{1} } =X rSub { size 8{0} } union Z} {} BC2: Tương tư.

Until Xi = Xi+1.

Kết luận X+ = Xi.

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 X0 = AB

BC1: Tồn tại A -> E thuộc F, mà A∈ X0, E ∈ U vậy X1=X0E size 12{X rSub { size 8{1} } =X rSub { size 8{0} } union E} {} = ABE

BC2: Tồn tại AB -> C thuộc F, mà AB∈ X1, C ∈ U vậy X2=X1C size 12{X rSub { size 8{2} } =X rSub { size 8{1} } union C} {} = ABCE

BC3: Tồn tại C -> D thuộc F, mà C∈ X2, D ∈ U vậy X3=X2D size 12{X rSub { size 8{3} } =X rSub { size 8{2} } union D} {}= ABCDE

BC4: Tồn tại BC -> EM thuộc F, mà BC∈ X3, EM ∈ U vậy X4=X3M size 12{X rSub { size 8{4} } =X rSub { size 8{3} } union M} {} = ABCDEM

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

Vậy kết luận (AB)+ = X4 = ABCDEF.

Định nghĩa: Phụ thuộc hàm bộ phận và phụ thuộc hàm toàn bộ:

Ví dụ:

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

Định nghĩa: Phụ thuộc hàm gián tiếp và phụ thuộc hàm trực tiếp:

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.

Định nghĩa hai tập phụ thuộc hàm tương đương:

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

Định nghĩa phủ cực tiểu (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 - XAZA size 12{ left lbrace X - >A right rbrace union left lbrace Z - >A right rbrace } {} 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=GXA,AY size 12{G=G union  left lbrace X - >A,A in Y right rbrace } {}

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

WHILE ∃Z ⊂ X, Z ≠ X, G ≅ G \ 

fZA size 12{ left lbrace f right rbrace  union  left lbrace Z - >A right rbrace } {}

DO G = G \ 

fZA size 12{ left lbrace f right rbrace  union  left lbrace Z - >A right rbrace } {}

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}.

Khoá của quan hệ

Khoá của tập thực thể

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ể.

Khoá của quan hệ

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(A1, A2,...,An) và tập phụ thuộc hàm F, X ⊆ A1, A2,...,An . Ta nói X là một khoá của R khi và chỉ khi X -> A1, A2,...,An ∈ 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 -> A1A2...An ∈ 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ệ R2.

Thuộc tính khoá, thuộc tính không khoá

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 (

TNXi size 12{ ital "TN" union X rSub { size 8{i} } } {}
)+ = Q+ then 

 Si = 

TNXi size 12{ ital "TN" union X rSub { size 8{i} } } {}

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:

Xi

TNXi size 12{ ital "TN" union X rSub { size 8{i} } } {}

TNXi size 12{ ital "TN" union X rSub { size 8{i} } } {}
Siêu khoá khoá
S S
C SC Q+ SC SC
Z SZ Q+ SZ SZ
CZ SCZ Q+ SCZ

Kết quả quan hệ trên có hai khoá là : {D, C} và {S, Z}

Tách một quan hệ

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.

Định nghĩa phép tách lược đồ quan hệ

Phép tách một lược đồ quan hệ U = A1, A2,...,An là việc thay thế lược đồ quan hệ U bằng một tập lược đồ con: U1, U2,...,Un trong đó Ui ⊆ U, i = 1..n.

U=U1U2...Un size 12{U=U rSub { size 8{1} } union U rSub { size 8{2} } union "." "." "." union U rSub { size 8{n} } } {} và Ui Uj với i j

Phép tách bảo toàn thông tin

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 R1, R2, ..., Rn, 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 Ri:

∀ r(r) => r = ΠR1(r) * ΠR2(r) *...*ΠRn(r)

Thuật toán kiểm tra phép tách bảo toàn thông tin

INPUT: Lược đồ quan hệ R = {A1, A2,...,An }, tập phụ thuộc hàm F và phép tách ρ=(R1,..,Rk)

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 Aj, hàng i ứng với lược đồ Ri.

BC2: Ở vị trí hàng i và cột j, đặt aijnếu Aj thuộc Ri. 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 uY=aijvY=bij{ size 12{alignl { stack { left lbrace u left [Y right ]=a rSub { size 8{ ital "ij"} } {} # right none left lbrace v left [Y right ]=b rSub { size 8{ ital "ij"} } {} # right no } } lbrace } {} hoặc uY=bijvY=aij{ size 12{alignl { stack { left lbrace u left [Y right ]=b rSub { size 8{ ital "ij"} } {} # right none left lbrace v left [Y right ]=a rSub { size 8{ ital "ij"} } {} # right no } } lbrace } {} 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)}.

Với A -> B ta có:

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

Định lý

Trong trường hợp ρ = {R1, R2 }, 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 ρ = {R1(U1), R2(U2)}là bảo toàn thông tin khi và chỉ khi

U1U2 size 12{U rSub { size 8{1} } intersection U rSub { size 8{2} } } {}→ U1\U2 hay U1U2 size 12{U rSub { size 8{1} } intersection U rSub { size 8{2} } } {}→ U2\U1

Phép tách bảo toàn phụ thuộc

Tính bảo toàn phụ thuộc

  • Lược đồ quan hệ R, tập phụ thuộc F, ρ = {R1, R2,..,Rk }.
  • Phụ thuộc hình chiếu: Hình chiếu của F trên lược đồ Ri 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 R1(A,B) và R2(BC).

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

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

(2) B -> C, khi chiếu trên R2(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.

Kiểm tra tính bảo toàn phụ thuộc.

INPUT: Lược đồ quan hệ R = A1, A2,...,An, tập phụ thuộc hàm F, phân rã ρ = {R1, R2,..,Rk }

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((ZRi) size 12{Z:=Z union  \(  \( Z intersection R rSub { size 8{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 Ri = AB;

Z = D ( ( D AB ) + AB ) = D size 12{Z= left lbrace D right rbrace intersection \( \( left lbrace D right rbrace intersection left lbrace ital "AB" right rbrace \) rSup { size 8{+{}} } intersection left lbrace ital "AB" right rbrace \) = left lbrace D right rbrace } {}

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

Với Ri = CD:

Z = D ( ( D CD ) + CD ) size 12{Z= left lbrace D right rbrace union \( \( left lbrace D right rbrace intersection left lbrace ital "CD" right rbrace \) rSup { size 8{+{}} } intersection left lbrace ital "CD" right rbrace \) } {}

= D ( D ) + CD ) size 12{ {}= left lbrace D right rbrace union \( left lbrace D right rbrace \) rSup { size 8{+{}} } intersection left lbrace ital "CD" right rbrace \) } {}

= D ( ABCD ) CD ) size 12{ {}= left lbrace D right rbrace union \( left lbrace ital "ABCD" right rbrace \) intersection left lbrace ital "CD" right rbrace \) } {}

= CD size 12{ {}= left lbrace ital "CD" right rbrace } {}

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

Với Ri = 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.