Một số thuật toán liên quan đến khoá
Một vấn đề thường xuyên xảy ra là đối với một sơ đồ quan hệ cho trước (s = <R, F>), và một phụ thuộc hàm A → B, chúng ta muốn biết A → B có là phần tử của F ...
Một vấn đề thường xuyên xảy ra là đối với một sơ đồ quan hệ cho trước (s = <R, F>), và một phụ thuộc hàm A → B, chúng ta muốn biết A → B có là phần tử của F + hay không. Để trả lời câu hỏi này chúng ta cần tính bao đóng F + của tập các phụ thuộc hàm F.
Tuy nhiên tính F + trong trường hợp tổng quát là rất khó khăn và tốn kém thời gian vì các tập phụ thuộc hàm thuộc F + là rất lớn cho dù F có thể là nhỏ. Chẳng hạn, F = {A → B 1 , A → B 2 ,.... A → B n }, khi đó F + bao gồm cả những phụ thuộc hàm A → Y với Y ⊆ {B 1 B 2 ... B n }, như vậy ta sẽ có 2 n tập con Y. Trong khi đó việc tính bao đóng của tập thuộc tính A lại không khó. Theo kết quả đã trình bầy ở trên thì việc kiểm tra A → B ∈ F + sẽ được thế bởi việc tính A + .
Thuật toán 1. (Tính bao đóng của một tập các thuộc tính đối với tập các phụ thuộc hàm trên sơ đồ quan hệ)
Input :s = < R, F > là một sơ đồ quan hệ trong đó
R = (a1, a2,.., an) là tập hữu hạn các thuộc tính.
F là tập các phụ thuộc hàm và A ⊆ R
Output : A+ là bao đóng của A đối với F.
Nhớ rằng A+ = { a: A →{a} ∈F+}.
A → B ∈ F+ nếu và chỉ nếu B ⊆ A+ .
Phương pháp: Lần lượt tính các tập thuộc tính Ao, A1 như sau:
1). A0 = A
2). Ai = Ai-1
{a} nếu ∃ (C → D) ∈ F, {a} ∈ D và C ⊆ Ai-1
3). Rõ ràng A = A0 ⊆ A1 ⊆ ... ⊆ Ai ⊆ R và R hữu hạn nên tồn tại i sao cho
Ai = Ai+1
Khi ấy thuật toán dừng và Ai chính là A+
Ví dụ: Xét sơ đồ quan hệ s = < R, F > trong đó
R = {c, t, h, r, s, g}
Tính {h, r}+ ?
A0 = {h, r}
A1 = {h, r, c} do {h, r}→ {c}∈F
A2 = {h, r, c, t} do {c}→ {t}∈ F
A3 = {h, r, c, t} = A2
Vậy {h, r}+ = {h, r, c, t}
Thuật toán 2. (Tính bao đóng cho một tập bất kỳ trên quan hệ r)
Input:r = {h1, h2,.., hm} là một quan hệ trên R = { a1, a2,.., an }, A ⊆ R
Output : A+r
Bước 1: Từ r xây dựng một tập Er = { Eij : 1 ≤ i < j ≤ m }
Eij = { a : a ∈ R và hi(a) = hj(a) }
Bước 2: Từ Er xây dựng một tập
M = { B ∈ P(R) : Tồn tại Eij ∈ Er : Eij = B}
ở đây P(R) là tập các tập con của R
Bước 3: A+r được tính như sau:
Có thể thấy rằng Eij = ∅ (trong trường hợp hai dòng i và j không có cột nào trùng nhau về giá trị, có nghĩa rằng chúng khác nhau hoàn toàn.
Không bao giờ có Eij = R ( có nghĩa rằng Eij = toàn bộ không gian), vì nếu xẩy ra thì có hai dòng trùng nhau, theo định nghĩa quan hệ thì không cho phép có hai dòng trùng nhau.
Ví dụ: xét quan hệ r
| A | B | C | D | E |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 2 | 0 | 0 |
| 2 | 0 | 2 | 0 | 1 |
Tính {B, C}+r
E12 ={ B, C }, E13 = {D, E}, E14 = {D}
E23 = {A}, E24 ={E}
E34 = {B, C, D}
M = {{A}, {B, C}, {B, C, D}, {D}, {D, E}, {E}}
Vậy {B, C}+r = {B, C} {B, C, D} ={B, C}
Một số thuật toán liên quan đến Khoá
Khi giải quyết các bài toán thông tin quản lý, người ta thường sử dụng các hệ quản trị cơ sở dữ liệu mà trong đó chứa cơ sở dữ liệu quan hệ . Các phép xử lí đối với bài toán này thường là tìm kiếm bản ghi sau đó thêm bản ghi mới , thay đổi nội dung bản ghi hoặc xoá bản ghi. Trong các thao tác trên, việc tìm kiếm bản ghi là rất quan trọng. Muốn tìm được bản ghi trong file dữ liệu thì chúng ta phải xây dựng khoá của file dữ liệu đó.
Có hai thuật toán tìm khoá của quan hệ và lược đồ quan hệ . Tìm khoá ở đây chính là tìm khoá tối tiểu.
Thuật toán 3: Tìm khoá tối tiểu của một quan hệ
Vào: r = {h1, .. , hm} là một quan hệ trên tập thuộc tính
R = {a1 , .. ,an}
Ra: K là một khoá tối tiểu của r.
Phương pháp:
Bước1: Tính E r= {A1, A2.. .. } trong đó E r là các hệ bằng nhau.
Bước 2: Tính M r là các hệ bằng nhau cực đại.
Bước 3: Lần lượt tính các thuộc tính K 0 , K 1 ,.., K n theo qui tắc:
K 0 =R={ a 1 ,.., a n } hoặc K 0 là một khoá đã biết.
Bước 4: Đặt K= K n. Khi đó K là khoá tối tiểu.
Nhận xét: Nếu ta thay đổi thứ tự các thuộc tính của r bằng thuật toán này chúng ta có thể tìm được một khoá tối tiểu khác.
Ví dụ : Cho quan hệ r là:
Bước 1: E 12={A,C,D} E 13={B} E 14={A,D,E}
E 23=∅ E 24={A,B,D} E 34={C}
Bước 2: M r={ {A, C, D}, {A, D, E},{A, B, D}}
Bước 3: (KH:P(Mr)-phần tử của Mr )
K 0={A, B, C, D, E}
Xét K 1= K 0- {A}= {B, C, D, E} 
P(Mr )⇒ K 1={B, C, D, E}.
Xét K 2= K 1- {B}= {C, D, E} 
P(Mr ) ⇒ K 2={C, D, E}.
Xét K 3= K 2- {C}= {D, E} ⊂P(Mr ) ⇒ K 3={C, D, E}.
Xét K 4= K 3- {D}= {C, E} 
P(Mr ) ⇒ K 4={C, E}.
Xét K 5= K 4- {E}= {C} ⊂P(Mr ) ⇒ K 5={C, E}.
Vậy {C, E} là một khoá tối tiểu của r.
Cũng ví dụ trên nhưng ta thay đổi tập thuộc tính theo thứ tự là
{A, C, E, B, D} Ta đi tìm khoá tối tiểu của r
Bước 1 và bước 2 giống như trên
Bước 3:
K 0={A, C, E, B, D}
Xét K 1= K 0- {A}= {C, E, B, D} 
P(Mr ) ⇒ K 1={C, E, B, D}.
Xét K 2= K 1- {C}= {E, B, D} 
P(Mr ) ⇒ K 2={E, B, D}.
Xét K 3= K 2- {E}= {B, D} ⊂P(Mr ) ⇒ K 3= K 2 ={E, B, D}.
Xét K 4= K 3- {B}= {E, D}⊂P(Mr ) ⇒ K 4= K 3= {E, B, D}.
Xét K 5= K 4- {D}= {B, E} 
P(Mr ) ⇒ K 5={E, B}.
Vậy khoá tối tiểu của r là{E, B}.
Như vậy thay đổi thứ tự của các thuộc tính, ta sẽ có những tập khoá tối tiểu khác nhau .
Ví dụ: Cho quan hệ r :
Bước 1 : E 12={B, C} E 13={E} E 14= ∅
E 23={A, D} E 24={E} E 34={B}
Bước 2 : M r={ {B, C}, {E},{A, D}}
Bước 3 :
*Các thuộc tính được lấy theo thứ tự r 1 ={A, B, C, D, E}
K 0 = R = {A, B, C, D, E}
Xét K 1= K 0- {A}= {B, C, D, E} 
P(Mr )⇒ K 1={B, C, D, E}.
Xét K 2= K 1- {B}= {C, D, E} P(Mr ) ⇒ K 2={C, D, E}.
Xét K 3= K 2- {C}= {D, E} 
P(Mr ) ⇒ K 3 ={D, E}.
Xét K 4= K 3- {D}= { E} ⊂P(Mr ) ⇒ K 4= K 3= {D, E}.
Xét K 5= K 4- {E}= { D} ⊂P(Mr ) ⇒ K 5= K 4= {D, E}.
Vậy khoá tối tiểu của r là {D, E}.
*Các thuộc tính được lấy theo thứ tự r 2 ={E, D, C, B, A}
K 0 = R = { E, D, C, B, A }
Xét K 1= K 0- {E}= { D, C, B, A } 
P(Mr ) ⇒ K 1={ D, C, B, A }.
Xét K 2= K 1- {D}= { C, B, A } 
P(Mr ) ⇒ K 2={ C, B, A }.
Xét K 3= K 2- {C}= { B, A } 
P(Mr ) ⇒ K 3 ={ B, A }.
Xét K 4= K 3- {B}= { A }⊂P(Mr ) ⇒ K 4= K 3= {B, A }.
Xét K 5= K 4- {A}= { B }⊂P(Mr ) ⇒ K 5= K 4= {B, A }.
Vậy khoá tối tiểu khác của quan hệ là{B, A}.
Thuật toán 4: Tìm khoá tối tiểu cho một sơ đồ quan hệ
Vào : sơ đồ quan hệ s = <R, F> trong đó
F là tập các phụ thuộc hàm
R={a1,.., an}là tập các thuộc tính
Ra: K là tối tiểu của s
Phương pháp: Tính liên tiếp các tập thuộc tính K 0, K 1,.., K n như sau: K 0 = R = {a1, .., an}
K= Kn là khoá tối tiểu.
Ta có thể dùng công thức tương đương:
Nhận xét:
- Thay đổi thứ tự các thuộc tính của R bằng thuật toán trên chúng ta có thể tìm được một khoá tối tiểu khác.
- Nếu như đã biết A là một khoá nào đó thì có thể đặt K 0=A , ta vẫn tìm ra được khoá tối tiểu và thời gian tìm nhanh hơn.
Giả sử s = < F, R > là một lược đồ quan hệ trong đó:
R={a, b, c, d}
F={{a, b}→{d},{c}→{b}}
Tìm khoá tối tiểu của sơ đồ quan hệ
Áp dụng thuật toán trên ta có:
+ K 0=R={a, b, c, d}
+Tính K 1
Xét K 1= K 0 － {a}={b, c, d}
{b, c, d}+={b, c, d}≠R
Vậy K 1={a, b, c, d}. (K1=K0)
+Tính K 2
Xét K 2= K 1－{b}={a, c, d}
{a, c, d}+ ={a, b, c, d}=R
Vậy K 2={a, c, d}
+Tính K 3
Xét K 3= K 2 －{c}={a, d}
{a, d}+={a, d}≠R
Vậy K 3={a, c, d} (K3=K2)
+Tính K 4
Xét K 4= K 3 －{d}={a, c}
{a, c}+={a, b, c, d}=R
Vậy K 4={a, c}
Vậy khoá tối tiểu là {a, c}.
Định nghĩa thuộc tính cơ bản, thuộc tính thứ cấp
Giả sử r là một quan hệ trên R và K r là tập tất cả các khoá tối tiểu của r. Ta nói a là thuộc tính cơ bản của r nếu tồn tại một khoá tối tiểu K (K∈ K r ) để a là một phần tử của K.
Nếu a không là thuộc tính cơ bản, a sẽ được gọi là thuộc tính thứ cấp.
Đối với lược đồ quan hệ, ta cũng có định nghĩa tương tự.
Thuật toán 5: Tìm tất cả các thuộc tính cơ bản của một quan hệ trên R
Vào : r ={h1,..,h m} là một quan hệ trên R.
Ra: V là tập tất cả các thuộc tính cơ bản của r.
Phương pháp:
Bước 1: Từ r ta xây dựng một tập E r={ E i j : m ≥ j 
i ≥1}
Trong đó E i j ={a∈R : hi(a)= h j (a)}
Bước 2: Từ E r ta xây dựng tập
M={B ∈ P(R) : ∃ E i j ∈Er : E i j =B }
Bước 3: Từ M ta xây dựng tập
M r = {B ∈M : ∀B’ ∈M : B B’}
(chỉ lấy tệp nào trong M mà không có tập khác bao nó, tức là bỏ bớt tập con thực sự)
Bước 4: Xây dựng tập V=R- B mà B 
M r .
Xét quan hệ
Bước1: Tính E r
E 12={B,C} E 13={A} E 14={D}
E 23={D} E 24={A} E 34={B,C}
Bước 2: Tính M={{B,C},{A},{D}}
Bước 3: Tính M r ={{B,C},{A},{D}} Vì giao của các tập con trong Mr bằng rỗng nên sang
Bước 4:V= R- ϕ ={A,B,C,D}.
Tính bao đóng
Tính {a, b}+ của sơ đồ quan hệ s = <R, F> với
R={a, b, c, d} F = {{a, b, d}→{c},{a, c}→{d}, {b}→{d}}
Tính{A, B}+r :
| A | B | C | D | E |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 2 | 3 |
| 1 | 1 | 1 | 2 | 1 |
| 1 | 1 | 3 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
Tính Khoá tối tiểu:
Tính khoá tối tiểu của r:
| A | B | C | D | E |
| 1 | 1 | 0 | 3 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 2 | 0 | 2 | 0 | 1 |
Tìm khoá tối tiểu của một lược đồ quan hệ s = < F, R > với
R={1, 2, 3, 4, 5, 6}
F={{1, 3}→{2},{2}→{1, 3, 4},{1,4,5}→{2,3,6},{3,6}→{1,5}}
Thuộc tính cơ bản:
Tìm thuộc tính cơ bản của r sau:
| A | B | C | D | E |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 1 | 1 | 0 | 2 |
| 1 | 0 | 1 | 1 | 0 |
