Chương I TỔNG QUAN VỀ CSDL QUAN HỆ VÀ CÁC RÀNG BUỘC TOÀN VẸN 1. TỔNG QUAN VỀ CSDL QUAN HỆ Có nhiều lý do để chọn mô hình dữ liệu quan hệ nhƣ: Cơ sở toán học của mô hình quan hệ là một ứng viên tốt cho xử lý lý thuyết. Mô hình quan hệ có thể đƣợc đặc trƣng bởi ít nhất 3 tính chất mạnh mẽ: a. Cấu trúc dữ liệu của nó là đơn giản.
Chúng là các quan hệ, các bảng hai chiều mà các phần tử của chúng là các mục dữ liệu. Điều này cho phép một mức độ độc lập cao đối với biểu diễn dữ liệu vật lý (tức là các tệp và các chỉ mục) b. Mô hình quan hệ cung cấp một cơ sở chắc chắn cho việc tƣơng thích dữ liệu. Việc thiết kế CSDL đƣợc giúp đỡ bằng quá trình chuẩn hóa loại bỏ các bất thƣờng của dữ liệu.
Các trạng thái tƣơng thích của CSDL cũng có thể đƣợc định nghĩa một cách đồng nhất và đƣợc duy trì thông qua các quy tắc toàn vẹn. Mô hình CSDL cho phép thao tác quan hệ hƣớng tập hợp. Tính chất này đã dẫn đến sự phát triển mạnh mẽ của các ngôn ngữ phi thủ tục hoặc dựa trên lý thuyết tập hợp (đại số quan hệ) hoặc dựa trên logic (tính toán quan hệ). Các khái niệm CSDL quan hệ Một CSDL là một tập hợp dữ liệu có cấu trúc liên quan đến một vài hiện tƣợng của cuộc sống thực mà ta muốn mô hình hóa.
Một CSDL quan hệ là CSDL mà ở đó cấu trúc dữ liệu ở dạng bảng. Một cách hình thức, một quan hệ đƣợc định nghĩa trên n tập hợp D1, D2, … , Dn (không nhất thiết phân biệt) là một tập hợp các n-bộ <d1, d2, …, dn> sao cho d1 D1, d2 D2, …., dn Dn Ví dụ 1.1 Xét CSDL mô hình hóa công ty cơ khí. Các thực thể đƣợc mô hình hóa là nhân viên (EMP) và dự án (PROJ). Với mỗi nhân viên chúng ta lƣu trữ mã số nhân viên (ENO), tên (ENAME), danh hiệu trong công ty (TITLE), lƣơng (SAL), mã số dự án mà nhân viên đang làm việc (PNO), trách nhiệm trong dự z 8 án (RESP) và khoảng thời gian làm việc (DUR).
Một cách tƣơng tự, với mỗi dự án chúng ta lƣu trữ mã số dự án (PNO), tên dự án (PNAME) và ngân sách của dự án (BUDGET). Các lƣợc đồ quan hệ cho cơ sở dữ liệu này có thể đƣợc định nghĩa nhƣ sau: EMP(ENO, ENAME, TITLE, SAL, PNO, DUR) PROJ(PNO, PNAME, BUGGET) Trong lƣợc đồ quan hệ EMP có bảy thuộc tính ENO, ENAME, TITLE, SAL, PNO, DUR. Các giá trị của ENO lấy từ miền của tất cả các mã số nhân viên hợp lệ, gọi là D1. Các giá trị ENAME lấy từ miền giá tất cả các tên hợp lệ D2, … Để ý rằng thuộc tính của mỗi quan hệ không đƣợc lấy giá trị từ miền khác.
Các thuộc tính khác nhau trong cùng một quan hệ trong một số quan hệ có thể đƣợc định nghĩa trên cùng một miền. Khóa (key) của một quan hệ là một tập con không rỗng bé nhất của các thuộc tính của nó sao cho giá trị tạo nên khóa xác định một cách duy nhất mỗi bộ của một quan hệ. Các thuộc tính tạo nên khóa đƣợc gọi là các thuộc tính chủ yếu. Các tập hợp lớn hơn của một khóa thƣờng đƣợc gọi là siêu khóa.
Nhƣ vậy, trong ví dụ trên, khóa của PROJ là PNO, khóa của EMP là (ENO, PNO). Mỗi quan hệ có ít nhất là một khóa. Đôi khi một quan hệ có nhiều khả năng cho khóa. Trong trƣờng hợp nhƣ vậy, mỗi khả năng đƣợc xem là một khóa dự tuyển và một trong các khóa dự tuyển đƣợc lựa chọn làm khóa chính.
Số các thuộc tính của quan hệ xác định cấp của nó, số các bộ giá trị của quan hệ xác định lực lƣợng của nó. Trong dạng bảng, CSDL ví dụ bao gồm hai bảng nhƣ đƣợc chỉ ra ở trong hình 1. Các cột của bảng tƣơng ứng với các thuộc tính của quan hệ. Nếu có các thông tin đƣợc nhập vào các bảng thì chúng tƣơng ứng với các bộ giá trị.
Bảng rỗng chỉ cấu trúc bảng, bởi vì thông tin bên trong một bảng biến đổi theo thời gian, nhiều ví dụ có thể đƣợc tạo là từ một quan hệ. Từ nay trở đi, thuật ngữ quan hệ dùng để chỉ một ví dụ của quan hệ.2 là các ví dụ của quan hệ đƣợc định nghĩa ở hình 1. z 9 EMP ENO ENAME TITLE SAL PNO RESP DUR PROJ PNO PNAME BUDGET Hình 1.1 Lƣợc đồ CSDL PROJ PNO PNAME BUDGET P1 Instrucmentation 150000 P2 Database Develop 135000 P3 CAD/CAM 250000 P4 maintenance 310000 EMP ENO ENAME TITLE SAL PNO RESP DUR E1 j.Smith Analyst 34000 P1 Analyst 24 E2 M.Smith Analyst 34000 P2 Analyst 6 E3 A.Miller Programmer 24000 P2 Programmer Null E5 B.2 Ví dụ về cơ sở dữ liệu Một giá trị của thuộc tính có thể không đƣợc xác định. Việc thiếu tính xác định có thể có các giải thích khác nhau, hay dùng nhất là không biết hoặc không áp dụng đƣợc.
Giá trị này thƣờng đƣợc gọi là giá trị null. Cần phân biệt giá trị null với giá trị 0 (zero). Giá trị 0 là giá trị đƣợc biết, giá trị null là giá trị không z 10 đƣợc biết. Việc hỗ trợ giá trị null là một tính chất quan trọng cần thiết để làm việc với các truy vấn có thể.
Chuẩn hóa “Chuẩn hóa là một quá trình thuận nghịch từng bƣớc thay thế một tập hợp quan hệ bằng các tập hợp tiếp theo, trong đó mỗi quan hệ có cấu trúc đơn giản hơn và chính quy hơn”. Mục đích của chuẩn hóa là loại bỏ nhiều bất thƣờng của một quan hệ để nhận đƣợc quan hệ “tốt hơn”. Bốn vấn đề sau có thể tồn tại trong một lƣợc đồ quan hệ: a. Bất thƣờng lặp (repetition anormaly) Một số thông tin có thể đƣợc lặp lại một cách không cần thiết.
Ví dụ, xét quan hệ EMP ở hình 2. ENAME, TITLE, SAL của một nhân viên đƣợc lặp với mỗi dự án mà nhân viên này phục vụ trên đó. Điều này dẫn đến một sự lãng phí bộ nhớ và trái với tinh thần của CSDL. Bất thƣờng cập nhật (update anormaly) Nhƣ là hệ quả của việc lặp dữ liệu, việc thực hiện cập nhật có thể gây rắc rối phiền hà.
Ví dụ, lƣơng của một nhân viên thay đổi, nhiều bộ giá trị phải đƣợc cập nhật để phản ánh sự thay đổi này. Bất thƣờng chèn (Insertion anormaly) Có thể không có khả năng thêm mới vào cơ sở dữ liệu. Ví dụ, khi một nhân viên mới vào công ty chúng ta không thể thêm thông tin cá nhân (ENAME, TITLE, SAL) vào quan hệ EMP nếu nhân viên đó chƣa làm cho dự án nào. Đó là vì khóa của EMP bao hàm thuộc tính PNO và giá trị null không phải là thành phần của một khóa.
Bất thƣờng loại bỏ (Deletion anormaly) Đó là sự trái ngƣợc của bất thƣờng chèn. Nếu một nhân viên chỉ làm việc trên một dự án và dự án đó đã kết thúc thì không thể loại bỏ thông tin dự án ra khỏi EMP. Làm nhƣ vậy dẫn đến việc loại bỏ bộ giá trị duy nhất về nhân viên, dẫn đến việc mất thông tin cá nhân mà chúng ta muốn lƣu giữ. Sự chuẩn hóa chuyển đổi các lƣợc đồ quan hệ thành các lƣợc đồ không có những vấn đề này.
Phƣơng pháp phổ biến nhất để chuẩn hóa một lƣợc đồ quan z 11 hệ là phƣơng pháp tách (decomposition), trong đó chúng ta bắt đầu với một quan hệ đơn, gọi là quan hệ phổ quát (universal relation), quan hệ này chứa tất cả các thuộc tính (và có thể bất thƣờng) và làm giảm nó liên tiếp. Tại mỗi lần lặp, một quan hệ đƣợc chia thành hai hoặc nhiều quan hệ ở dạng chuẩn cao hơn. Một quan hệ đƣợc gọi là ở một dạng chuẩn nếu nó thỏa mãn các điều kiện liên kết với dạng chuẩn đó. Đầu tiên Codd đã định nghĩa các dạng chuẩn thứ nhất (1NF), thứ hai (2NF) và thứ ba (3NF).
Boyce và Codd sau đó định nghĩa một phiên bản sửa đổi của dạng chuẩn 3, phiên bản này thƣờng đƣợc gọi là dạng chuẩn Boyce- Codd (BCNF). Điều đó đƣợc tiếp tục bằng định nghĩa các dạng chuẩn thứ tƣ (4NF, Fagin, 1977) và dạng chuẩn thứ năm (5NF, Fagin, 1979). Có một mối liên hệ phân cấp giữa các dạng chuẩn này. Một quan hệ đƣợc chuẩn hóa là ở 1NF.
Một số quan hệ ở 1NF cũng ở 2NF, một số trong các quan hệ đó là ở 3NF, … Các dạng chuẩn cao hơn có tính chất tốt hơn các dạng khác về bốn bất thƣờng đƣợc nêu ở trên. Một trong các yêu cầu của quá trình chuẩn hóa là sự phân tách không mất mát. Điều đó có nghĩa là sự thay thế một quan hệ bằng nhiều quan hệ khác sẽ không dẫn đến việc mất thông tin. Nếu có thể nối các quan hệ đƣợc phân tách để nhận lại đƣợc quan hệ ban đầu thì quá trình đó gọi là tách không mất mát.
Một cách trực quan, phép toán nối là phép toán lấy hai quan hệ và nối mỗi bộ của quan hệ thứ hai vào những bộ nào của quan hệ thứ nhất thỏa mãn một điều kiện đƣợc chỉ rõ. Ví dụ, điều kiện có thể là giá trị của một thuộc tính của quan hệ thứ nhất phải bằng giá trị của một thuộc tính của quan hệ thứ hai. Một đòi hỏi khác của quá trình chuẩn hóa là bảo toàn phụ thuộc. Một phép tách đƣợc gọi là bảo toàn phụ thuộc nếu bao đóng của hợp của phụ thuộc trong các quan hệ đƣợc tách là tƣơng đƣơng với bao đóng của quan hệ nguyên thủy (theo một tập các quy tắc suy diễn).
Các cấu trúc phụ thuộc Các dạng chuẩn dựa trên một số các cấu trúc phụ thuộc. BCNF và các dạng chuẩn thấp hơn dựa trên phụ thuộc hàm. 4NF dựa trên phụ thuộc đa trị và 5NF dựa trên phụ thuộc nối-chiếu. z 12 Chúng ta sẽ định nghĩa phụ thuộc gồm: a.
Phụ thuộc hàm Giả sử R là một quan hệ xác định trên tập thuộc tính A={A1, A2, …, An} và giả sử X A và Y A. Nếu với mỗi giá trị của X trong R chỉ kết hợp đƣợc với một giá trị duy nhất của Y thì ta nói rằng “X xác định hàm Y” hoặc “Y phụ thuộc hàm vào X”. Khóa của một quan hệ xác định hàm các thuộc tính không khóa của cùng quan hệ.2 Trong quan hệ PROJ ở hình 1.2 phụ thuộc hàm có hiệu lực là PNO → (PNAME, BUDGET) (1) Trong quan hệ EMP chúng ta có: (ENO, PNO) → (ENAME, TITLE, SAL, RES, DUR) (2) Phụ thuộc hàm này không phải là phụ thuộc hàm duy nhất trong EMP.