Học viện công nghệ BƯu chính viễn thông khoa viễn thông 1 Bài giảng Học phần: CƠ SỞ DỮ liệU
tải về 4.98 Mb. Chế độ xem pdf
|
TH CSDL 2015Sep, 6. Đề cương Cơ sở dữ liệu- sau nghiệm thu. 23.02.2022, Chuong01-CSDL
- Điều hướng trang này:
- 4.3.2. Phép tách-kết nối tự nhiên
| 4.3.
Phép tách - kết nối 4.3.1. Khái niệm Tách quan hệ: Các thuật toán thiết kế cơ sở dữ liệu quan hệ được trình bày trong phần này bắt đầu từ một lược đồ quan hệ vũ trụ đơn R(A 1 , A 2 , …,A n ) chứa tất cả các thuộc tính của cơ sở dữ liệu. Với giả thiết quan hệ vũ trụ, tên của mỗi thuộc tính là duy nhất. Tập hợp F các phụ thuộc hàm thỏa mãn trên các thuộc tính của R do những người thiết kế cơ sở dữ liệu chỉ ra sẽ được các thuật toán sử dụng. Sử dụng các phụ thuộc hàm, các thuật toán sẽ tách lược đồ quan hệ vũ trụ R thành một tập hợp các lược đồ quan hệ D = {R 1 , R 2 ,…, R k } trong đó R i ⊆ R, tập hợp đó sẽ là lược đồ cơ sở dữ liệu quan hệ. D được gọi là một phép tách (decomposition) của R. Chúng ta phải đảm bảo rằng mỗi thuộc tính trong R sẽ xuất hiện trong ít nhất là một lược đồ quan hệ R i trong phép tách để nó khỏi bị “mất ”. Một cách hình thức, ta có điều kiện bảo toàn thuộc tính sau đây: R = R 1 U R 2 U …U R k Yêu cầu của phép tách: - Bảo toàn thuộc tính, ràng buộc - Bảo toàn dữ liệu 4.3.2. Phép tách-kết nối tự nhiên Việc mỗi phụ thuộc hàm X → Y trong F hoặc được xuất hiện trực tiếp trong một trong các lược đồ quan hệ R i trong phép tách D hoặc có thể được suy diễn từ các phụ thuộc hàm có trong R i là có nhiều lợi ích. Ta gọi đó là điều kiện bảo toàn phụ thuộc. Chúng ta muốn bảo toàn phụ thuộc bởi vì mỗi phụ thuộc trong F biểu thị một ràng buộc trong cơ sở dữ liệu. Nếu như một trong các phụ thuộc không được thể hiện trong một quan hệ riêng rẽ R i nào đó của phép tách, chúng ta không thể ép buộc ràng buộc này đối với quan hệ riêng rẽ, thay vào đó, chúng ta nối hai hoặc nhiều quan hệ trong phép tách và sau đó kiểm tra rằng phụ thuộc hàm thỏa mãn trong kết quả của phép nối. 131 Rõ ràng đó là một thủ tục không hiệu quả và không thực tiễn. Việc các phụ thuộc chính xác được chỉ ra ở trong F xuất hiện trong các quan hệ riêng rẽ của phép tách D là không cần thiết. Chỉ cần hợp của các phụ thuộc thỏa mãn trên các quan hệ riêng rẽ trong D là tương đương với F là đủ. Bây giờ chúng ta định nghĩa các khái niệm này như sau. Cho trước một tập hợp các phụ thuộc F trên R, phép chiếu của F trên R i , ký hiệu là 𝜋 𝑅𝑖 (𝐹) trong đó R i là một tập con của R, là một tập hợp các phụ thuộc hàm X → Y trong F + sao cho các thuộc tính trong X U Y đều được chứa trong R i . Như vậy, phép chiếu của F trên mỗi lược đồ quan hệ R i trong phép tách D là tập hợp các phụ thuộc hàm trong F + , bao đóng của F, sao cho các thuộc tính ở vế trái và vế phải của chúng đều ở trong R i . Ta nói rằng phép tách D = {R 1 , R 2 ,…, R m } của R bảo toàn phụ thuộc đối với F nếu hợp của các phép chiếu của F trên mỗi R i trong D là tương đương với F. Điều đó có nghĩa là: ( 𝜋 𝑅1 (𝐹) U 𝜋 𝑅2 (𝐹) … 𝜋 𝑅𝑚 (𝐹)) + = F + Nếu một phép tách là không bảo toàn phụ thuộc, một vài phụ thuộc sẽ bị mất trong phép tách. Để kiểm tra xem một phụ thuộc hàm X → B, trong đó X là tập thuộc tính thuộc về R i , B là một thuộc tính thuộc R i có thỏa mãn trong Ri hay không ta làm như sau: Trước hết tính X + , sau đó với mỗi thuộc tính B sao cho - B là một thuộc tính của R i - B là ở trong X + - B không ở trong X Khi đó phụ thuộc hàm X → B thỏa mãn trong Ri. Một ví dụ về phép tách không bảo toàn phụ thuộc như sau: Xét lược đồ quan hệ: R = { A,B,C,D} với các phụ thuộc hàm: A → BCD; BC → DA; D → B Lược đồ này có hai khóa dự tuyển là A và BC. Nó được tách thành: R1 = {D,B}, lược đồ này chứa phụ thuộc hàm D → B, 132 R2 = {A,C,D}, lược đồ này chứa phụ thuộc hàm A → CD Rõ ràng sau khi tách, phụ thuộc hàm BC → DA bị mất. tải về 4.98 Mb. Chia sẻ với bạn bè của bạn:
|