MÔ HÌnh quan hệ nguyên nhân ra đỜi của mô HÌnh quan hệ



tải về 1.86 Mb.
trang7/17
Chuyển đổi dữ liệu17.08.2016
Kích1.86 Mb.
1   2   3   4   5   6   7   8   9   10   ...   17

----oOo----

  1. .

PHỤ THUỘC HÀM

(functional dependency)
Phụ thuộc hàm (functional dependency) là một công cụ dùng để biểu diễn một cách hình thức các ràng buộc toàn vẹn (vắn tắt: ràng buộc). Phương pháp biểu diễn này có rất nhiều ưu điểm, và đây là một công cụ cực kỳ quan trọng, gắn chặt với lý thuyết thiết kế cơ sở dữ liệu.

Phụ thuộc hàm được ứng dụng trong việc giải quyết các bài toán tìm khóa, tìm phủ tối thiểu và chuẩn hóa cơ sở dữ liệu.



    1. KHÁI NIÊM PHỤ THUỘC HÀM

Cho quan hệ phanCong sau:

phanCong

(PHICONG,

MAYBAY,

NGAYKH,

GIOKH)




Cushing

83

9/8

10:15a




Cushing

116

10/8

1:25p




Clark

281

8/8

5:50a




Clark

301

12/8

6:35p




Clark

83

11/8

10:15a




Chin

83

13/8

10:15a




Chin

116

12/8

1:25p




Copely

281

9/8

5:50a




Copely

281

13/8

5:50a




Copely

412

15/8

1:25p

Quan hệ phanCong diễn tả phi công nào lái máy bay nào và máy bay khởi hành vào thời gian nào. Không phải sự phối hợp bất kỳ nào giữa phi công, máy bay và ngày giờ khởi hành cũng đều được chấp nhận mà chúng có các điều kiện ràng buộc qui định sau:

  • Mỗi máy bay có một giờ khởi hành duy nhất.

  • Nếu biết phi công, biết ngày giờ khởi hành thì biết được máy bay do phi công ấy lái.

  • Nếu biết máy bay, biết ngày khởi hành thì biết phi công lái chuyến bay ấy.

Các ràng buộc này là các ví dụ về phụ thuộc hàm và được phát biểu lại như sau:

  • MAYBAY xác định GIOKH

  • {PHICONG,NGAYKH,GIOKH} xác định MABAY

  • {MAYBAY,NGAYKH} xác định PHICONG

hay

  • GIOKH phụ thuộc hàm vào MAYBAY

  • MABAY phụ thuộc hàm vào {PHICONG,NGAYKH,GIOKH}

  • PHICONG phụ thuộc hàm vào {MAYBAY,NGAYKH}

và được ký hiệu như sau:

  • {MAYBAY} GIOKH

  • {PHICONG,NGAYKH,GIOKH} MABAY

  • {MAYBAY,NGAYKH} PHICONG

Trong ký hiệu trên ta đã ký hiệu MAYBAY thay cho {MAYBAY}.

Một cách tổng quát:



      1. Định nghĩa phụ thuộc hàm

Q(A1,A2,…,An) là lược đồ quan hệ.

X, Y là hai tập con của Q+={A1,A2,…,An}.

r là quan hệ trên Q.

t1,t2 là hai bộ bất kỳ của r.



X  Y  (t1.X = t2.X  t1.Y = t2.Y)

(Ta nói X xác định Y hay Y phụ thuộc hàm vào X (X functional determines Y,Y functional dependent on X )



Tính chất:

  • phụ thuộc hàm X   đúng với mọi quan hệ r

  • phụ thuộc hàm   Y chỉ đúng trên quan hệ r có cùng giá trị trên Y.

Ví dụ: Quan hệ sau thỏa mãn phụ thuộc hàm   GIOKH

phanCong

(PHICONG,

MAYBAY,

NGAYKH,

GIOKH)




Cushing

83

9/8

10:15a




Cushing

116

10/8

10:15a




Clark

281

8/8

10:15a




Clark

301

12/8

10:15a




Clark

83

11/8

10:15a




Chin

83

13/8

10:15a




Chin

116

12/8

10:15a




Copely

281

9/8

10:15a




Copely

281

13/8

10:15a




Copely

412

15/8

10:15a

trên thực tế không có quan hệ r nào thỏa tính chất trên nên từ đây về sau nếu không nói rõ thì với một quan hệ r bất kỳ ta luôn xem phụ thuộc hàm   Y luôn luôn không thỏa trên r.

      1. Phụ thuộc hàm hiển nhiên (Trivial Dependencies)

Hệ quả: Nếu X Y thì X Y.

Chứng minh:

Giả sử t1.X = t2.X do X  Y nên t1.Y = t2.Y theo định nghĩa suy ra X  Y

Trong trường hợp này X  Y được gọi là phụ thuộc hàm hiển nhiên.

Ví dụ phụ thuộc hàm X  X là phụ thuộc hàm hiển nhiên.

Vậy với r là quan hệ bất kỳ, F là tập phụ thuộc hàm thỏa trên r, ta luôn có F  {các phụ thuộc hàm hiển nhiên}


      1. Thuật toán Satifies

Cho quan hệ r và X, Y là hai tập con của Q+. Thuật toán SATIFIES sẽ trả về trị true nếu X  Y ngược lại là false
SATIFIES

Vào: quan hệ r và hai tập con X,Y

ra: true nếu X  Y, ngược lại là false

SATIFIES(r,X,Y)



  1. Sắp các bộ của quan hệ r theo X để các giá trị giống nhau trên X nhóm lại với nhau

  2. Nếu tập các bộ cùng giá trị trên X cho các giá trị trên Y giống nhau thì trả về true ngược lại là False


Ví dụ 1: SATIFIES(phanCong,MAYBAY,GIOKH)

phanCong

(PHICONG,

MAYBAY,

NGAYKH,

GIOKH)




Cushing

83

9/8

10:15a




Clark

83

11/8

10:15a




Chin

83

13/8

10:15a




Cushing

116

10/8

1:25p




Chin

116

12/8

1:25p




Clark

281

8/8

5:50a




Copely

281

9/8

5:50a




Copely

281

13/8

5:50a




Clark

301

12/8

6:35p




Copely

412

15/8

1:25p

cho kết quả là true nghĩa là MAYBAYGIOKH

Ví dụ 2: SATIFIES(phanCong,GIOKH,MAYBAY)

phanCong

(PHICONG,

MAYBAY,

NGAYKH,

GIOKH)




Clark

281

8/8

5:50a




Copely

281

9/8

5:50a




Copely

281

13/8

5:50a




Cushing

83

9/8

10:15a




Clark

83

11/8

10:15a




Chin

83

13/8

10:15a




Cushing

116

10/8

1:25p




Chin

116

12/8

1:25p




Copely

412

15/8

1:25p




Clark

301

12/8

6:35p

cho kết quả là false nghĩa là không có phụ thuộc hàm GIOKHMAYBAY

      1. Các phụ thuộc hàm có thể có

        1. Cách tìm tất cả tập con của Q+

Lược đồ quan hệ Phancong(PHICONG,MAYBAY,NGAYKH,GIOKH)có tập thuộc tính Phancong+={PHICONG,MAYBAY,NGAYKH,GIOKH} và tất cả các tập con có thể có của Phancong+­­ được cho bởi bảng sau:




PHICONG

MAYBAY

NGAYKH

GIOKH



{PHICONG}

{MAYBAY}

{NGAYKH}

{GIOKH}







{PHICONG,MAYBAY}

{PHICONG,NGAYKH}

{PHICONG,GIOKH}










{MAYBAY,NGAYKH}

{MAYBAY,GIOKH}










{PHICONG,MAYBAY,NGAYKH}

{PHICONG,MAYBAY,GIOKH}













{NGAYKH,GIOKH}













{PHICONG,NGAYKH,GIOKH}













{MAYBAY,NGAYKH,GIOKH}













{PHICONG,MAYBAY,NGAYKH,GIOKH}

Số tập con có thể có của Q+ = {A1,A2,...,An} là 2n

        1. Cách tìm tất cả các phụ thuộc hàm có thể có của Q

Ứng với mỗi tập con của Phancong+ cho 2n = 2= 16 phụ thuộc hàm có thể có. Số phụ thuộc hàm có thể có là 24 * 24 = 16 * 16 = 256


  

PTHHN

  {PHICONG}

F-

  {MAYBAY}

F-

  {MAYBAY,PHICONG}

F-

  {NGAYKH}

F-

  {PHICONG,NGAYKH}

F-

  {MAYBAY,NGAYKH}

F-

  {MAYBAY,PHICONG,NGAYKH}

F-

  {GIOKH}

F-

  {PHICONG,GIOKH}

F-

  {MAYBAY,GIOKH}

F-

  {MAYBAY,PHICONG,GIOKH}

F-

  {NGAYKH,GIOKH}

F-

  {PHICONG,NGAYKH,GIOKH}

F-

  {MAYBAY,NGAYKH,GIOKH}

F-

  {MAYBAY,PHICONG,NGAYKH,GIOKH}

F-

{PHICONG}  

PTHHN

{PHICONG}  {PHICONG}

PTHHN

{PHICONG}  {MAYBAY}

F-

{PHICONG}  {MAYBAY,PHICONG}

F-

{PHICONG}  {NGAYKH}

F-

{PHICONG}  {PHICONG,NGAYKH}

F-

{PHICONG}  {MAYBAY,NGAYKH}

F-

{PHICONG}  {MAYBAY,PHICONG,NGAYKH}

F-

{PHICONG}  {GIOKH}

F-

{PHICONG}  {PHICONG,GIOKH}

F-

{PHICONG}  {MAYBAY,GIOKH}

F-

{PHICONG}  {MAYBAY,PHICONG,GIOKH}

F-

{PHICONG}  {NGAYKH,GIOKH}

F-

{PHICONG}  {PHICONG,NGAYKH,GIOKH}

F-

{PHICONG}  {MAYBAY,NGAYKH,GIOKH}

F-

{PHICONG}  {MAYBAY,PHICONG,NGAYKH,GIOKH}

F-

{MAYBAY}  

PTHHN

{MAYBAY}  {PHICONG}

F-

{MAYBAY}  {MAYBAY}

PTHHN

{MAYBAY}  {MAYBAY,PHICONG}

F-

{MAYBAY}  {NGAYKH}

F-

{MAYBAY}  {PHICONG,NGAYKH}

F-

{MAYBAY}  {MAYBAY,NGAYKH}

F-

{MAYBAY}  {MAYBAY,PHICONG,NGAYKH}

F-

{MAYBAY}  {GIOKH}

F

{MAYBAY}  {PHICONG,GIOKH}

F-

{MAYBAY}  {MAYBAY,GIOKH}

F+

{MAYBAY}  {MAYBAY,PHICONG,GIOKH}

F-

{MAYBAY}  {NGAYKH,GIOKH}

F-

{MAYBAY}  {PHICONG,NGAYKH,GIOKH}

F-

{MAYBAY}  {MAYBAY,NGAYKH,GIOKH}

F-

{MAYBAY}  {MAYBAY,PHICONG,NGAYKH,GIOKH}

F-

{PHICONG,MAYBAY}  

PTHHN

{PHICONG,MAYBAY}  {PHICONG}

PTHHN

{PHICONG,MAYBAY}  {MAYBAY}

PTHHN

{PHICONG,MAYBAY}  {PHICONG,MAYBAY}

PTHHN

{PHICONG,MAYBAY}  {NGAYKH}

F-

{PHICONG,MAYBAY}  {PHICONG,NGAYKH}

F-

{PHICONG,MAYBAY}  {MAYBAY,NGAYKH}

F-

{PHICONG,MAYBAY}  {MAYBAY,PHICONG,NGAYKH}

F-

{PHICONG,MAYBAY}  {GIOKH}

F+

{PHICONG,MAYBAY}  {PHICONG,GIOKH}

F+

{PHICONG,MAYBAY}  {MAYBAY,GIOKH}

F+

{PHICONG,MAYBAY}  {MAYBAY,PHICONG,GIOKH}

F+

{PHICONG,MAYBAY}  {NGAYKH,GIOKH}

F-

{PHICONG,MAYBAY}  {PHICONG,NGAYKH,GIOKH}

F-

{PHICONG,MAYBAY}  {MAYBAY,NGAYKH,GIOKH}

F-

{PHICONG,MAYBAY}  {MAYBAY,PHICONG,NGAYKH,GIOKH}

F-

{NGAYKH}  

F-

{NGAYKH}  {PHICONG}

F-

{NGAYKH}  {MAYBAY}

F-

{NGAYKH}  {PHICONG,MAYBAY}

F-

{NGAYKH}  {NGAYKH}

PTHHN

{NGAYKH}  {PHICONG,NGAYKH}

F-

{NGAYKH}  {MAYBAY,NGAYKH}

F-

{NGAYKH}  {MAYBAY,PHICONG,NGAYKH}

F-

{NGAYKH}  {GIOKH}

F-

{NGAYKH}  {PHICONG,GIOKH}

F-

{NGAYKH}  {MAYBAY,GIOKH}

F-

{NGAYKH}  {MAYBAY,PHICONG,GIOKH}

F-

{NGAYKH}  {NGAYKH,GIOKH}

F-

{NGAYKH}  {PHICONG,NGAYKH,GIOKH}

F-

{NGAYKH}  {MAYBAY,NGAYKH,GIOKH}

F-

{NGAYKH}  {MAYBAY,PHICONG,NGAYKH,GIOKH}

F-

{PHICONG,NGAYKH}  

PTHHN

{PHICONG,NGAYKH}  {PHICONG}

PTHHN

{PHICONG,NGAYKH}  {MAYBAY}

F-

{PHICONG,NGAYKH}  {PHICONG,MAYBAY}

F-

{PHICONG,NGAYKH}  {NGAYKH}

PTHHN

{PHICONG,NGAYKH}  {PHICONG,NGAYKH}

PTHHN

{PHICONG,NGAYKH}  {MAYBAY,NGAYKH}

F-

{PHICONG,NGAYKH}  {MAYBAY,PHICONG,NGAYKH}

F-

{PHICONG,NGAYKH}  {GIOKH}

F-

{PHICONG,NGAYKH}  {PHICONG,GIOKH}

F-

{PHICONG,NGAYKH}  {MAYBAY,GIOKH}

F-

{PHICONG,NGAYKH}  {MAYBAY,PHICONG,GIOKH}

F-

{PHICONG,NGAYKH}  {NGAYKH,GIOKH}

F-

{PHICONG,NGAYKH}  {PHICONG,NGAYKH,GIOKH}

F-

{PHICONG,NGAYKH}  {MAYBAY,NGAYKH,GIOKH}

F-

{PHICONG,NGAYKH}  {MAYBAY,PHICONG,NGAYKH,GIOKH}

F-

{MAYBAY,NGAYKH}  

PTHHN

{MAYBAY,NGAYKH}  {PHICONG}

F

{MAYBAY,NGAYKH}  {MAYBAY}

PTHHN

{MAYBAY,NGAYKH}  {PHICONG,MAYBAY}

F+

{MAYBAY,NGAYKH}  {NGAYKH}

PTHHN

{MAYBAY,NGAYKH}  {PHICONG,NGAYKH}

F+

{MAYBAY,NGAYKH}  {MAYBAY,NGAYKH}

PTHHN

{MAYBAY,NGAYKH}  {MAYBAY,PHICONG,NGAYKH}

F+

{MAYBAY,NGAYKH}  {GIOKH}

F+

{MAYBAY,NGAYKH}  {PHICONG,GIOKH}

F+

{MAYBAY,NGAYKH}  {MAYBAY,GIOKH}

F+

{MAYBAY,NGAYKH}  {MAYBAY,PHICONG,GIOKH}

F+

{MAYBAY,NGAYKH}  {NGAYKH,GIOKH}

F+

{MAYBAY,NGAYKH}  {PHICONG,NGAYKH,GIOKH}

F+

{MAYBAY,NGAYKH}  {MAYBAY,NGAYKH,GIOKH}

F+

{MAYBAY,NGAYKH}  {MAYBAY,PHICONG,NGAYKH,GIOKH}

F+

{PHICONG,MAYBAY,NGAYKH}  

PTHHN

{PHICONG,MAYBAY,NGAYKH}  {PHICONG}

PTHHN

{PHICONG,MAYBAY,NGAYKH}  {MAYBAY}

PTHHN

{PHICONG,MAYBAY,NGAYKH}  {PHICONG,MAYBAY}

PTHHN

{PHICONG,MAYBAY,NGAYKH}  {NGAYKH}

PTHHN

{PHICONG,MAYBAY,NGAYKH}  {PHICONG,NGAYKH}

PTHHN

{PHICONG,MAYBAY,NGAYKH}  {MAYBAY,NGAYKH}

PTHHN

{PHICONG,MAYBAY,NGAYKH}  {PHICONG,MAYBAY,NGAYKH}

PTHHN

{PHICONG,MAYBAY,NGAYKH}  {GIOKH}

F+

{PHICONG,MAYBAY,NGAYKH}  {PHICONG,GIOKH}

F+

{PHICONG,MAYBAY,NGAYKH}  {MAYBAY,GIOKH}

F+

{PHICONG,MAYBAY,NGAYKH}  {MAYBAY,PHICONG,GIOKH}

F+

{PHICONG,MAYBAY,NGAYKH}  {NGAYKH,GIOKH}

F+

{PHICONG,MAYBAY,NGAYKH}  {PHICONG,NGAYKH,GIOKH}

F+

{PHICONG,MAYBAY,NGAYKH}  {MAYBAY,NGAYKH,GIOKH}

F+

{PHICONG,MAYBAY,NGAYKH}  {MAYBAY,PHICONG,NGAYKH,GIOKH}

F+

....................................................




{PHICONG,NGAYKH,GIOKH}  

PTHHN

{PHICONG,NGAYKH,GIOKH}  {PHICONG}

PTHHN

{PHICONG,NGAYKH,GIOKH}  {MAYBAY}

F

{PHICONG,NGAYKH,GIOKH}  {PHICONG,MAYBAY}

F+

{PHICONG,NGAYKH,GIOKH}  {NGAYKH}

PTHHN

{PHICONG,NGAYKH,GIOKH}  {PHICONG,NGAYKH}

PTHHN

{PHICONG,NGAYKH,GIOKH}  {MAYBAY,NGAYKH}

F+

{PHICONG,NGAYKH,GIOKH}  {MAYBAY,PHICONG,NGAYKH}

F+

{PHICONG,NGAYKH,GIOKH}  {GIOKH}

PTHHN

{PHICONG,NGAYKH,GIOKH}  {PHICONG,GIOKH}

PTHHN

{PHICONG,NGAYKH,GIOKH}  {MAYBAY,GIOKH}

F+

{PHICONG,NGAYKH,GIOKH}  {MAYBAY,PHICONG,GIOKH}

F+

{PHICONG,NGAYKH,GIOKH}  {NGAYKH,GIOKH}

PTHHN

{PHICONG,NGAYKH,GIOKH}  {PHICONG,NGAYKH,GIOKH}

PTHHN

{PHICONG,NGAYKH,GIOKH}  {MAYBAY,NGAYKH,GIOKH}

F+

{PHICONG,NGAYKH,GIOKH}  {MAYBAY,PHICONG,NGAYKH,GIOKH}

F+

{MAYBAY,NGAYKH,GIOKH}  

PTHHN

{MAYBAY,NGAYKH,GIOKH}  {PHICONG}

F+

{MAYBAY,NGAYKH,GIOKH}  {MAYBAY}

PTHHN

{MAYBAY,NGAYKH,GIOKH}  {PHICONG,MAYBAY}

F+

{MAYBAY,NGAYKH,GIOKH}  {NGAYKH}

PTHHN

{MAYBAY,NGAYKH,GIOKH}  {PHICONG,NGAYKH}

F+

{MAYBAY,NGAYKH,GIOKH}  {MAYBAY,NGAYKH}

PTHHN

{MAYBAY,NGAYKH,GIOKH}  {MAYBAY,PHICONG,NGAYKH}

F+

{MAYBAY,NGAYKH,GIOKH}  {GIOKH}

PTHHN

{MAYBAY,NGAYKH,GIOKH}  {PHICONG,GIOKH}

F+

{MAYBAY,NGAYKH,GIOKH}  {MAYBAY,GIOKH}

PTHHN

{MAYBAY,NGAYKH,GIOKH}  {MAYBAY,PHICONG,GIOKH}

F+

{MAYBAY,NGAYKH,GIOKH}  {NGAYKH,GIOKH}

PTHHN

{MAYBAY,NGAYKH,GIOKH}  {PHICONG,NGAYKH,GIOKH}

F+

{MAYBAY,NGAYKH,GIOKH}  {MAYBAY,NGAYKH,GIOKH}

PTHHN

{MAYBAY,NGAYKH,GIOKH}  {MAYBAY,PHICONG,NGAYKH,GIOKH}

F+

................

....
1   2   3   4   5   6   7   8   9   10   ...   17


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2016
được sử dụng cho việc quản lý

    Quê hương