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



tải về 1.86 Mb.
trang12/17
Chuyển đổi dữ liệu17.08.2016
Kích1.86 Mb.
1   ...   9   10   11   12   13   14   15   16   17




Sửa bảng giá trị để nó thỏa AD

Sửa b5,b14 thành a4






Sửa bảng giá trị để nó thỏa DEC

sửa b2 thành a3  sửa tất cả b2 thành a3






A

B

C

D

E







A

B

C

D

E

Q1(AD)

a1

b1

b2

a4

b3




Q1(AD)

a1

b1

a3

a4

b3

Q2(AB)

a1

a2

b2

a4

b6




Q2(AB)

a1

a2

a3

a4

b6

Q3(BE)

b7

a2

b2

b9

a5




Q3(BE)

b7

a2

a3

b9

a5

Q4(CDE)

b10

b11

a3

a4

a5




Q4(CDE)

b10

b11

a3

a4

a5

Q5(AE)

a1

b12

b2

a4

a5




Q5(AE)

a1

b12

a3

a4

a5




Sửa bảng giá trị để nó thỏa CEA

Sửa b7,b10 thành a1.






Lần lượt xét lại các phụ thuộc hàm trong F, nếu bảng giá trị chưa thỏa phụ thuộc hàm nào thì tiếp tục làm cho nó thỏa.

Sửa bảng giá trị để nó thỏa AD






A

B

C

D

E







A

B

C

D

E

Q1(AD)

a1

b1

a3

a4

b3




Q1(AD)

a1

b1

a3

a4

b3

Q2(AB)

a1

a2

a3

a4

b6




Q2(AB)

a1

a2

a3

a4

b6

Q3(BE)

a1

a2

a3

b9

a5




Q3(BE)

a1

a2

a3

a4

a5

Q4(CDE)

a1

b11

a3

a4

a5




Q4(CDE)

a1

b11

a3

a4

a5

Q5(AE)

a1

b12

a3

a4

a5




Q5(AE)

a1

b12

a3

a4

a5

Dòng thứ Q3(BE) của bảng chứa toàn giá trị aj (j=1..n) nên phép phân rã trên là bảo toàn thông tin.



          1. Định lý

Bảng kết quả của thuật toán trên cho phép ta kết luận được tính bảo toàn hay không bảo toàn thông tin của phép tách.

Chứng minh:

Ta chứng minh nếu bảng kết quả thuật toán không có hàng chỉ chứa toàn giá trị a thì phép tách không bảo toàn thông tin. Thật vậy:

Ta xây dựng một quan hệ r có các giá trị như bảng kết quả của thuật toán, các hàng là các bộ. Quan hệ r thỏa tập phụ thuộc F vì thuật toán đã sửa các giá trị của r để nó khỏi vi phạm các phụ thuộc hàm trong F  r là một quan hệ của lược đồ Q. Ta tách quan hệ r thành các quan hệ ri với ri = r.Qi và dùng phép kết tự nhiên để kết chúng lại. Nếu:



  • k Qk+Qi+ =  i  r1|><|r2....|><|rk không tồn tại  phép tách không bảo toàn thông tin.

  • i,k Qi+Qk+ = Xik   mà mỗi ri đều có một bộ ti chứa toàn a  các ti nối được với nhau vì có cùng giá trị trên Xik  có một bộ tr1|><|r2....|><|rk có toàn giá trị a, bộ này lại không có trong r  r  r1|><|r2....|><|rk  phép tách không bảo toàn thông tin.

Ta chứng minh nếu bảng kết quả thuật toán có hàng chỉ chứa toàn giá trị a thì phép tách bảo toàn thông tin. Ta chứng minh điều này qua 2 bước:

  • Bước 1: chứng minh nếu tr tr1|><|r2....|><|rk. Suy ra rr1|><|r2....|><|rk.

Giả sử t=(a1,...,an) r . Ta tách quan hệ r thành các ri = r.Qi với ti = t.Qi. Có hai trường hợp:

    • i,k Qi+Qk+ = Xik    các ti nối được với nhau vì có cùng giá trị trên Xik  bộ tr1|><|r2....|><|rk  r  r1|><|r2....|><|rk.

    • k Qk+Qi+ =  i. Suy ra bảng kiểm tra bảo toàn thông tin ở giai đoạn chưa thỏa các phụ thuộc hàm, có dạng:




A1

A2

...

AK

AK+1

...

Q1










bk1

bk2

b..

Q2










b..

...

...

...










b..

...

...

QK(AK,AK+1,..)

b..

b..

b..

ak

ak+1

...

Với mọi XQ+ tk.X  ti.X với ik nên khi làm bằng các giá trị theo các phụ thuộc hàm XY thì các giá trị b ở dòng Qk không thay đổi còn các giá trị b ở các cột Ak,Ak+1,... không đổi thành a được. Suy ra bảng kết quả của thuật toán không bao giờ chứa dòng có toàn giá trị a. Vậy trường hợp k Qk+Qi+ =  i không xảy ra khi bảng kiểm tra bảo toàn thông tin có một dòng toàn a.

  • Bước 2: chứng minh nếu tr1|><|r2....|><|rk tr. Suy ra r1|><|r2....|><|rkr.

Giả sử t=(a1,...,an) r1|><|r2....|><|rk theo định nghĩa suy ra i tiri sao cho t.Qi+ = ti. Nhưng ri=r.Qi+  ti’r sao cho ti’.Qi+=ti=t.Qi+i . Trường hợp xấu nhất là các ti’là các dòng khác nhau. Trong trường hợp này, ta có thể xem ti’là dòng Qi của bảng kiểm tra bảo toàn thông tin với các giá trị b xem như chưa biết. Nhưng các dòng Qi phải thỏa các phụ thuộc hàm trong F, phép làm bằng các giá trị theo các phụ thuộc hàm đã dần dần xác định được tất cả các giá trị b của một dòng ti’nào đo, là dòng có toàn giá trị a. Vậy có một i’ để ti’= t  tr  r  r1|><|r2....|><|rn (2)

(1) và (2)  r = r1|><|r2....|><|rn. Nói cách khác phép tách bảo toàn thông tin.



      1. Phép tách bảo toàn phụ thuộc hàm (decompositions that preserve dependencies)

        1. Tập phụ thuộc hàm Fi của Qi

Phần trên chỉ đề cấp vấn đề tách một lược đồ quan hệ Q(A1,A2,…An)thành các lược đồ con Q1,Q2,…,Qk còn không đề cập đến tập phụ thuộc hàm của các lược đồ con này. Nếu Q(A1,A2,…An) là lược đồ quan hệ, F phụ thuộc hàm, =(Q1,Q2,…,Qk)là phép phân rã bảo toàn thông tin, ri là quan hệ của Qi thì tính chất sau thỏa:

  • ri chỉ thỏa các phụ thuộc hàm XYF+ với XYQi+

Nói cách khác, tập phụ thuộc hàm của Qi chính là Fi có Fi+={XYF+| XYQi+}. Ta có thể hiểu F được phân rã thành các F1,...,Fk

Chứng minh tính chất trên:

Do ri được tách từ r mà r thỏa F+  ri thỏa các phụ thuộc hàm XYF+ với XYQi+.Theo định nghĩa phụ thuộc hàm, đương nhiên ri không thỏa các phụ thuộc hàm XYF+ với XYQi+. Ngoài ra ri không thỏa bất kỳ một phụ thuộc hàm nào XYF+ . Thật vậy nếu có XY như vậy thì r = r1|><|r2....|><|rn cũng phải thỏa XYF+. Điều này mâu thuẫn với định nghĩa của tập F+ .



        1. Định nghĩa:

Cho phân rã  =(Q1,Q2,…,Qk) của một lược đồ quan hệ, và một tập phụ thuộc hàm F. Hình chiếu của F trên một tập các thuộc tính Qi+ ký hiệu Qi(F) là tập các phụ thuộc hàm X  Y  F+ sao cho XY  Z.

Qi(F)=Fi+={ X  Y| X  Y  F+ và XY  Qi}

Ta nói phân rã  bảo toàn tập phụ thuộc hàm F nếu

F   Qi(F)  F+ = ( Qi(F))+ với i=1..k


Hệ quả: F+  ( Qi(F))+ với i=1..k

Nhận xét: từ hệ quả trên ta suy ra: để xác định phép phân rã  =(Q1,Q2,…,Qk) có bảo toàn phụ thuộc hàm hay không, với mỗi phụ thuộc hàm XYF ta xác định xem nó có là thành viên của tập phụ thuộc hàm G =  Qi(F) hay không. Ta không cần xác định chiều ngược lại.
Ví dụ12: Cho lược đồ quan hệ Q(A,B,C) và F={AB,BC,CA}. Phép phân rã =(Q1,Q2) tách Q thành hai lược đồ quan hệ Q1(A,B) và Q2(B,C). Hãy tính hình chiếu của F trên Q1+ và Q2+­­.Phép phân rã có bảo toàn phụ thuộc hàm F không?

Giải: về nguyên tắc ta có thể giải bài toán theo các bước dưới đây

Bước 1: Kê tất cả tập con của Q+




A

B

C



A

B

C







AB

AC










BC










ABC

Bước 2: Tính bao đóng của các tập con của Q+­­

=

A+=ABC

B+

=ABC

C+

=ABC







AB+

=ABC

AC+

=ABC













BC+

=ABC













ABC+

=ABC

Bước 3: Tính F+

AB

BA

CA

ABABC

ACB

BCA

AAB

BAB

CB

ABC

ACAB

BCAB

AC

BC

CAB

ABBC

ACBC

BCAC

AAC

BAC

CAC

ABABC

ACABC

BCABC

ABC

BBC

CBC










AABC

BABC

CABC












1   ...   9   10   11   12   13   14   15   16   17


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

    Quê hương