CHƯƠNG I: TỔNG QUAN VỀ CSDL
I. KHÁI NIỆM CƠ BẢN:
1. Cơ Sở Dữ Liệu: là một tập hợp các tập tin có liên quan với nhau, được thiết kế nhằm làm giảm thiểu sự lặp lại của dữ liệu.
2. Hệ quản trị CSDL: là một hệ thống phần mềm cho phép tạo lập CSDL và điều kiện mọi truy vấn trên đối với CSDL đó.
VD: Access, DB2, SQL server, Oracle…
3. Hệ CSDL: là một hệ thống gồm 4 thành phần:
- CSDL hợp nhất: CSDL của hệ có 2 tính chất tối thiểu hoá dư thừa và được chia sẻ.
- Những người sử dụng: là 1 người nào đó có nhu cầu truy cập vào CSDL, người sử dụng gồm tất cả người sử dụng cuối, người viết chương trình ứng dụng và những người điều kiện toàn bộ hệ thống hay gọi là người quản trị CSDL.
- Phần mềm hệ quản trị CSDL.
- Phần cứng: phần cứng của hệ bao gồm các thiết bị nhớ thứ cấp được sử dụng để lưu trữ CSDL.
II. CÁC MÔ HÌNH CSDL
1. MÔ HÌNH THỰC THỂ - LIÊN KẾT:
- Thực thể: là các đối tượng của thế giới thực. VD: con người, tổ chức, phòng ban, sự kiện..
- Thuộc tính: Mỗi thực thể có những tính chất riêng của mình, các tính chất đó được gọi là thuộc tính.
- Các loại thuộc tính:
+ Thuộc tính đơn hay thuộc tính nguyên tử: là những thuộc tính không thẻ chia nhỏ thành các thuộc tính nhỏ hơn nữa.
+ Thuộc tính phức: là những thuộc tính có thể chia nhỏ thành các thuộc tính thành phần.
+ Thuộc tính đơn trị là những thuộc tính có thể chỉ có 1 giá trị duy nhất đối với 1 thực thể cụ thể.
+ Thuộc tính đa trị: những thuộc tính có thể nhận đồng thời nhiều giá trị.
+ Thuộc tính rỗng Null: là thuộc tính có thể không nhận bất kỳ 1 gía trị nào.
+ Thuộc tính khoá Key: là 1 thuộc tính hay 1 tập con các thuộc tính mà nó đại diện cho tập dữ liệu của đối tượng cần quản lý tức là không thể tồn tại 2 tập dữ liệu có cùng giá trị của 2 đối tượng khác nhau của thuộc tính khoá. Hay có thể hiểu là giá trị của nó xác định duy nhất 1 thực thể trong tập thực thể.
+ Thuộc tính suy diễn hay phụ thuộc: được suy ra từ thuộc tính khác.
2. LIÊN KẾT:
- Kiểu liên kết: là tập hợp các mối liên hệ giữa các thực thể từ những kiểu thực thể đã cho.
- Bậc của kiểu liên kết: là số các kiểu thực thể tham gia liên kết.
· Liên kết 1 – 1:
Liên kết một - một giữa 2 thực thể E1 và E2 là liên kết mà ứng với mỗi dữ liệu trong thực thể E1 có nhiều nhất 1 dữ liệu trong thực thể E2 và ngược lại.
· Liên kết 1 – n:
Liên kết một – nhiều từ thực thể E1 đến thực thể E2 là liên kết mà ứng với mỗi dữ liệu trong thực thể E1 có 1 hoặc nhiều hoặc không có dữ liệu nào trong thực thể E2 nhưng ngược lại mỗi dữ liệu trong thực thể E2 có duy nhất 1 dữ liệu trong thực thể E1.
· Liên kết n –n:
Một liên kết nhiều – nhiều từ thực thể E1 đến thực thể E2 là liên kết mà ứng với mỗi dữ liêyj trong thực thể E1 có một hoặc nhiều hoặc không có dữ liệu nào trong thực thể E2, ngược lại ứng với mỗi dữ liệu trong thực thể E2 có 1 hoặc nhiều hoặc không có dữ liệu nào trong thực thể E1.
3. SƠ ĐỒ THỰC THỂ - LIÊN KẾT:
Các bước xây dựng:
Bước 1: Liệt kê các thực thể.
Bước 2: Ứng với từng thực thể, xác định các tính chất của chúng: các thuộc tính
Bước 3: Liệt kê các liên kết và các thuộc tính tham gia liên kết.
Bước 4: Vẽ hình, xác định cụ thể kiểu liên kết của các thực thể.
4. VD: quản lý đề tài nghiên cứu khoa học
Trước hết, ta xác địnhc cá thực thể có liên quan đến bài toán:
- Đối tượng CÁN BỘ: người tham gia nghiên cứu đề tài và là thành viên trong cơ quan quản lý.
- Đối tượng PHÒNG BAN: là nơi quản lý nhân viên và đề tài.
- Đối tượng ĐỀ TÀI là gồm danh mục quản lý thông tin về đề tài.
Từ các đối tượng trên ta xây dựng các thực thể và các đặc tính liên quan đến thực thể.
Tập các thực thể gồm có 3 thực thể: CÁN BỘ, PHÒNG BAN, ĐỀ TÀI tương ứng chứa các thông tin về các cán bộ, các phòng ban và các đề tài.
· Tập các thuộc tính:
CÁN BỘ (Mã cán bộ, Họ tên, Ngày sinh, Chức vụ, Lương, Học vị)
PHÒNG BAN (Mã phòng, Tên phòng, Chức năng)
ĐỀ TÀI (Mã đề tài, tên đề tài, kinh phí)
· Tập các liên kết:
Nơi làm việc: là liên kết giữa thực thể CÁN BỘ và thực thể PHÒNG BAN. Là liên kết 1 – n.
Quản lý đề tài: là liên kết giữa thực thể ĐỀ TÀI và thực thể PHÒNG BAN. Là liên kết 1 – n.
Tham gia đề tài: là liên kết giữa thực thể ĐỀ TÀI và thực thể CÁN BỘ. Là liên kết n – n.
Từ đó ta xây dựng liên kết các thực thể : vẽ hình.
CHƯƠNG II: NGÔN NGỮ KHAI THÁC CSDL
I. ĐẠI SỐ QUAN HỆ:
1. Các định nghĩa:
- Định nghĩa 1: Đại số quan hệ là một tập các phép toán cho phép xử lý khai thác các quan hệ của một CSDL. Thông qua đại số quan hệ ta có thể nhận biết được các bước căn bản của việc khai thác CSDL.
- Định nghĩa 2: Biểu thức quan hệ là biểu thức được tạo nên bởi các quan hệ và một số các phép toán nào đó gọi là các phép toán quan hệ. Kết quả của biểu thức là một quan hệ.
- Định nghĩa 3: Các phép toán của đại số quan hệ là các phép toán thực hiện trên các quan hệ và cho kết quả là 1 quan hệ mới.
2. Các phép toán:
· Phép hợp:
Cho 2 quan hệ r và s là khả hợp trên tập thuộc tính U. Hợp của 2 quan hệ R và S là một quan hệ xác định trên tập thuộc tính U chứa các bộ dữ liệu thuộc quan hệ R hoặc thuộc quan hệ S hoặc thuộc cả 2 quan hệ. Ký hiệu R ∨S
R ∨S = { t | t R hoặc t S hoặc t R và S }
· Phép giao:
Cho 2 quan hệ r và s là khả hợp trên tập thuộc tính U. phép giao 2 quan hệ r và s là một quan hệ xác định trên tập thuộc tính U chứa các bộ dữ liệu thuộc đồng thời cả 2 quan hệ r và s.
R ∧S = { t | t R và t S }
· Phép trừ:
Cho 2 quan hệ r và s là khả hợp trên tập thuộc tính U. Phép trừ quan hệ r cho s là một quan hệ xác định trên tập thuộc tính U chứa các bộ dữ liệu thuộc quan hệ r nhưng không thuộc quan hệ s.
R\S ={ t| t R và t S }
· Phép chọn:
Cho một quan hệ R trên tập thuộc tính U và một biểu thức logic F trên U. Khi đó phép chọn quan hệ R theo biểu thức F là một quan hệ xác định trên tập thuộc tính U chứa các bộ dữ liệu của R thoả mãn F.
R(F) ={ t | t R và F(t) đúng }
Thao tác: khi đã có quan hệ R và biểu thức F, ta chỉ cần loại khỏi quan hệ R những bộ t ko thoả mãn F. Tập các bộ còn lại chính là R(F).
· Phép chiếu:
Cho 1 quan hệ r xác định trên tập thuộc tính U, và một tập con các thuộc tính X U. Khi đó phép chiếu của quan hệ r trên X là một quan hệ chứa các bộ dữ liệu của r xác định trên tập thuộc tính X.
Πx(r) ={t.X | t thuộc r }
Thao tác: trước hết bỏ đi các cột không thược tâp thuộc tính X sau đó bỏ đi những bộ trùng nhau chỉ giữ lại những bộ đại diện.
· Phép kết nối:
Phép kết nối có điều kiện:
Cho 2 quan hệ của R xác định trên U và S xác định V, biểu thức logic F trên (U,V). Phép kết nói của quan hệ r và s theo F là một quan hệ xác định trên tập thuộc tính (U,V) chứa các s bộ cặp dữ liệu ( t r và v s) sao cho (t,v) thoả mãn F.
S ={ t | t.U R và t. V S và F(t,v)}
Phép kết nối tự nhiên:
Cho 2 quan hệ của r xác định trên U và s xác định trên V và gọi
R = U V. Phép kết nối tự nhiên của quan hệ r và s là một quan hệ xác định trên tập thuộc tính (U V) chứa các bộ cặp dữ liệu
(t r và v s} sao cho t.R=v.R
r*s ={t| t.U r và t.V s và t.R=v.R}
· Phép chia:
Xét 2 quan hệ r xác định trên tập thuộc tính U và s xác định trên tập thuộc tính V với V là tập con của U, V khác rỗng. Phép chia quan hệ r cho quan hệ s là một quan hệ xác định trên tập thuộc tính (U-V) sao cho mọi bộ dữ liệu của r : s khi ghép với mọi bộ dữ liệu của s là một bộ dữ liệu thuộc r.
r : s = { t | t là bô trên tập thuộc tính U\V, t r:s, với mọi vs thì (t,v)r}
II. NGÔN NGỮ TRUY VẤN CẤU TRÚC SQL
1. CÁC LỆNH ĐỊNH NGHĨA CSDL
* Lệnh tạo bảng CSDL :
CREATE TABLE [Tên sơ đồ] < tên bảng >
( Tên cột 1 Kiểu dữ liệu [Not Null]
…….
Tên cột n Kiểu dữ liệu [Not Null]
PRIMARY KEY <các thuộc tính khoá>
UNIQUE <Khoá khác>
FOREIGN KEY <Thuộc tính khoá ngoài> REFERENCES <tên bảng>(<tên khoá tương ứng>));
VD: CREATE TABLE SV ( MASV CHAR(10) Not Null, HOTEN CHAR(30), GTINH CHAR(3), NSINH DATE, DIACHI CHAR(50), MALOP CHAR(10) Not null, HOCBONG INT PRIMARY KEY (MASV) FOREIGN KEY MALOP REFERENCES LOP (MALOP);
Chú ý: Các thuộc tính khai báo sau từ khoá PRIMARY KEY phải là not null và duy nhất.
* Lệnh xoá bảng:
DROP TABLE <tên bảng>;
* Lệnh thêm cột mới vào bảng:
ALTER TABLE <tên bảng> ADD <tên cột> <Kiểu dữ liệu>;
VD: ALTER TABLE SV ADD GHICHU CHAR(100)
* Lệnh xoá cột từ bảng:
ALTER TABLE <Tên bảng> DROP <tên cột>;
* Lệnh thêm dòng dữ liệu mới
INSERT INTO <Tên bảng> (Danh sách cột) VALUES (Các giá trị) [Mệnh đề SELECT];
VD: INSERT INTO SV (MASV, HOTEN, GTINH, NSINH, MALOP)\VALUES (‘CQ471234’, ‘Nguyen Van An’, ‘Nam’,’01/01/1990’,’CNTT47’);
* Lệnh sửa đổi dữ liệu:
UPDATE <Tên bảng>
SET <Tên cột = biểu thức>,....
[FROM Tên bảng]
[WHERE Biểu thức điều kiện];
VD: Sửa đổi tất cả những người có ngày sinh ‘01/01/1990’ thành ‘01/01/1994’ trong bảng SV?
UPDATE SV
SET NSINH =‘01/01/1994’
WHERE NSINH =‘01/01/1990’
* Lệnh xoá dữ liệu
DELETE <Tên bảng>
[FROM <[Tên bảng | Tên view]>]
[WHERE <Biểu thức điều kiện>];
VD: Xoá toàn bộ thông tin của sinh viên có mã CQ123456
DELETE FROM SV
WHERE MASV=’CQ123456’;
2. LỆNH TRUY VẤN CSDL
SELECT [DISTINCT] [*|<Danh sách cột>]
FROM <Danh sách bảng| Danh sách View>
[WHERE <Biểu thức điều kiện>]
[GROUP BY <Danh sách cột>]
[HAVING <Biểu thức điều kiện>]
[ORDER BY {Tên cột | Số Thứ Tự | Biểu thức} [ASC/DESC]]
[UNION | INTERSECT | MINUS (Mệnh đề SELECT)]
Trong đó mệnh đề WHERE được biểu diễn dưới dạng sau:
WHERE[NOT] <biểu thức><phép so sánh><biểu thức>.
WHERE[NOT] <Tên cột> [NOT]LIKE <Chuỗi ký tự>.
WHERE[NOT] <Biểu thức> [NOT] BETWEEN <biểu thức> AND <biểu thức>.
WHERE[NOT] <biểu thức> [NOT] IN (Câu lệnh SELECT)
WHERE[NOT] EXISTS (Câu lệnh SELECT)
GROUP BY: nhóm
HAVING: Là điều kiện sau GROUP BY
ORDER BY: sắp xếp ASC – tăng dần; DESC – giảm dần;
UNION: hợp 2 biểu thức
INTEREST: Giao 2 biểu thức
MINUS: Trừ 2 biểu thức
Ta có thể sử dụng bí danh để thay đổi tên bảng và tên cột trong CSDL
<Tên bảng cũ> <Tên bảng mới>;
<Tên cột cũ> AS <Tên cột mới>;
Truy cập bằng bí danh: <Tên bảng>.<Tên cột>;
VD: SELECT MASV, HOTEN, HOCBONG *10 AS HB
FROM SV;
Tìm kiếm có sử dụng chuỗi ký tự: Sử dụng toán tử LIKE trong mệnh đề WHERE
% - Thay cho 1 chuỗi
“_” Thay cho 1 ký tự
Sử dụng EXISTS : trả lại giá trị TRUE nếu kết quả truy vấn con không rỗng.
CHƯƠNG III: LÝ THUYẾT THIẾT KẾ CSDL QUAN HỆ
1. TẬP THUỘC TÍNH:
Xét U ={A1, A2,...An} là tập hữu hạn khác rỗng. Mỗi phần tử trong U được gọi là 1 thuộc tính.
2. PHỤ THUỘC HÀM:
a. Định nghĩa:
Cho tập thuộc tính U={A1,A2,...An} một phụ thuộc hàm trên U là một phát biểu có dạng X -> Y, trong đó X, Y là tập con của U. Ta nói X xác định hàm Y ( hay Y phụ thuộc hàm vào X). Với r là một quan hệ trên U, ta nói quan hệ r thoả mãn phụ thuộc hàm X -> Y nếu như tồn tại bất kỳ 2 bộ dữ liệu u, v thuộc r mà u.X=v.X thì u.Y=v.Y.
Chú ý:
Phụ thuộc hàm X -> Rỗng đúng với mọi quan hệ r.
Phụ thuộc hàm rỗng -> Y chỉ dúng trên quan hệ r có cùng giá trị với Y.
b. Tính chất:
* Hệ tiên đề AMSTRONG
T/c 1: Tính phản xạ
Với mọi X, Y là tập con của U, nếu Y là tập con của X thì X -> Y
T/c 2: Tính bắc cầu
Với mọi X, Y, Z là tập con của U, nếu X -> Y, Y -> Z thì X -> Z
T/c 3: Tính tăng trưởng
Với mọi X, Y là tập con của U, nếu có X -> Y, với mọi Z thì XZ -> YZ
* Tính chất khác
T/c 4: Tính tựa bắc cầu
Nếu X -> Y, YZ -> W thì XZ -> W
T/c 5: Tính phản xạ chặt
Với mọi X là tập con của U thì X -> X
T/c 6: Tính mở rộng trái
Với mọi X là tập con của U, nếu X -> Y, Với mọi Z cũng là tập con của U thì XZ -> Y
T/c 7: Tính thu hẹp phải
Với mọi X, Y, Z là tập con của U, nếu X -> YZ thì X-> Y, X-> Z
T/c 8: Tính cộng
Với mọi X, Y, Z, W là tập con của U
Nếu X -> Y và X -> Z thì X -> YZ
Nếu X -> Y và Z -> W thì XZ -> YW
* Một số bổ đề
- Bổ đề 1: Hệ tiên đề AMSTRONG là đúng. Có nghĩa là nếu X -> Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ tiên đề Amstrong thì X -> Y là đúng trên một quan hệ nào đó thoả mãn các phụ thuộc hàm trong F.
CM: Kiểm tra tính đúng đắn của các tiên đề trên như sau:
Tiên đề 1: Hiển nhiên, vì không có 2 bộ bằng nhau trên X mà lại không bằng nhau trên tập con của nó.
Tiên đề 2: Giả sử quan hệ r thoả X -> Y. Tồn tại 2 bộ t, u thuộc r sao cho t.XZ=u.XZ mà t.YZ <> u.YZ
Vì có t.Z = u.Z nên tiên đề có t.YZ <> u. YZ thì t.Y <> u. Y
Ta có t.YZ = u.YZ nên t.X=u.X
Nhưng lại có t.X=u.X và t.Y <> u.Y lại mâu thuẫn với giả thiết X -> Y. Vậy t.YZ=u.YZ hay XZ -> YZ là đúng trên quan hệ r.
Tiên đề 3: Cho X -> Y và Y -> Z đúng trên quan hệ r
Giả sử tồn tại 2 bộ t và u thuộc r sao cho t.X=u.X và t.Z <> u.Z
Từ X -> Y suy ra t.X=u.X nên t.Y=u.Y
Nhưng lại có t.Y = u.Y và t.Z <> u.Z là mâu thuẫn với giả thiết Y -> Z
Do đó t.Z = u.Z
Suy ra X -> Z là đúng trên quan hệ r.
- Bổ đề 2: X -> Y được suy dẫn từ hệ tiên đề Amstrong khi và chỉ khi Y thuộc bao đóng của X.
CM:
Giả sử Y= A1,A2....An với A1...An là các thuộc tính và Y thuộc bao đóng của X
Từ định nghĩa X+ ta có X -> Ai . Áp dụng tiên đề Amstrong cho mọi i suy ra X -> Y nhờ tính chất 8.
Ngược lại giả sử có X -> Y , áp dụng hệ tiên đề Amstrong mỗi i có X -> Ai mà Ai thuộc Y nhờ tính chất 7.
Suy ra Y thuộc bao đóng của X là đúng.
3. BAO ĐÓNG:
- Bao đóng của tập thuộc tính:
Cho một lược đồ quan hệ α=<U,F> và một tập thuộc tính X là tập con của U. Bao đóng tập thuộc tính X trên U là tát cả các thuộc tính A thuộc U sao cho X -> A thuộc F+, ký hiệu là X+.
- Tính chất:
1. X là tập con của X+
2. X là tập con của Y suy ra X+ là tập con của Y+
3. (X+)+ =X+
4. X+Y+ là tập con của (XY)+
5. (X+Y)+ = (XY+)+ =(XY)+
6. X -> Y thuộc F+ tương đương Y là tập con của X+
7. X ->Y thuộc F+ và Y -> X thuộc F+ tương đương X+ = Y+
- Bao đóng của tập phụ thuộc hàm:
Cho một lược đồ quan hệ α=<U,F>. Bao đóng tập phụ thuộc F là tất cả các phụ thuộc hàm được suy dẫn logic từ F mà mọi quan hệ trên lược đồ quan hệ α đều phải thoả mãn.
Bao đóng của tập phụ thuộc hàm F là tập thoả mãn 2 điều kiện:
1. F là tập con của F+
2. Khi áp dụng các luật phản xạ, bắc cầu và tăng trưởng đối với các phụ thuộc hàm trong F+ thì không thể thêm được 1 phụ thuộc hàm nào khác ngoài những phụ thuộc hàm của F+
Tính chất:
1. F là tập con của F+
2. F là tập con của G suy ra F+ là tập con của G+
3. (F+)+ =F+
4. (FG)+=(FG+)+=(F+G)+
5. F+G+ là tập con của (FG)+
4. KHOÁ VÀ SIÊU KHOÁ
Cho lược đồ quan hệ α=<U,F>. K là tập con các thuộc tính (K là tập con của U) được gọi là khoá (key) của lược đồ nếu K thoả mãn 2 điều kiện sau:
1. K+ = U ( nghĩa là K -> U thuộc F+)
2. Với mọi K’ là tập con của K thì (K’)+ khác U ( nghĩa là K’ -> U không thuộc F+)
Siêu khoá: Cho lược đồ quan hệ α=<U,F>. S là tập con các thuộc tính ( S là tập con của U) được gọi là siêu khoá (superkey) nếu S+=U
Các tính chất:
- Trong một quan hệ bất kỳ, không tồn tại 2 bộ giống nhau trên tập khoá.
- Một lược đồ luôn có ít nhất 1 khoá.
- Hai khoá bất kỳ của lược đồ là không bao nhau.
- Hợp hoặc giao của 2 khoá không thể là 1 khoá.
5. CÁC DẠNG CHUẨN VÀ CHUẨN HOÁ LƯỢC ĐỒ
a. Dạng chuẩn 1: 1NF
Một lược đồ quan hệ α=<U,F> được gọi là dạng chuẩn 1NF khi và chỉ khi mọi thuộc tính của nó đều là đơn trị.
b. Dạng chuẩn 2: 2NF
Định nghĩa phụ thuộc hàm hoàn toàn hay phụ thuộc hàm đầy đủ: Cho một lược đồ quan hệ α=<U,F> và X, Y là các tập con của U. Ta nói y phụ thuộc hàm hoàn toàn hay phụ thuộc hàm đầy đủ vào X nếu thoả mãn đồng thời điều kiện:
X -> Y và với mọi X’ là tập con của X thì X’ không xác định Y
Trong trường hợp ngược lại ta nói Y phụ thuộc một phần (hay phụ thuộc bộ phận) vào X.
Một lược đồ quan hệ α=<U,F> được gọi là dạng chuẩn 2NF nếu:
1. α đã ở dạng 1NF
2. Mọi thuộc tính không khoá đều phụ thuộc hàm đầy đủ vào khoá.
c. Dạng chuẩn 3: 3NF
Định nghĩa phụ thuộc bắc cầu: Cho lược đồ quan hệ α=<U,F>, X là một tập con của U; X là tập con của U. Thuộc tính A ( A là tập con của U) gọi là phụ thuộc bắc cầu vào X nếu tồn tại Y là tập con của U sao cho X -> Y, Y -> A nhưng Y ko xác định X với A ko thuộc XY.
Một lược đồ quan hệ α=<U,F> được gọi là dạng chuẩn 3NF nếu:
1. α đã ở dạng 1NF
2. Mọi thuộc tính ko khoá của lược đồ không phụ thuộc bắc cầu vào khoá.
d. Dạng chuẩn Boye – Codd : BCNF
Một lược đồ quan hệ α=<U,F> được gọi là dạng chuẩn BCNF nếu với mọi X là tập con của U, A ko thuộc X, X -> A thuộc F+ thì X chứa một khoá của α ( hay X là một siêu khoá).
CÁC THUẬT TOÁN
1. XÁC ĐỊNH BAO ĐÓNG CỦA TẬP THUỘC TÍNH:
Đầu vào: Cho α=<U,F> và X là tập con của U;
Đầu ra: Bao đóng X+ của tập thuộc tính X;sau
Phương pháp: Tính liên tiếp tập các thuộc tính X0, X1, X2,... theo các bước sau:
B1: Đặt X0 = X
B2: Lần lượt xét các phụ thuộc hàm của F
Nếu Y -> Z và Y là tập con của Xi thì Xi+1 = Xi hợp Z
Loại bỏ phụ thuộc hàm Y -> Z khỏi F.
B3: Vì U hữu hạn nên sẽ tồn tại một chỉ số i nào đó mà Xi=Xi+1 thì Xi chính là bao đóng của X ( có thể viết X+ = Xi).
2. XÁC ĐỊNH BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM
Đầu vào: Cho α=<U,F>;
Đầu ra: Bao đóng F+ của tập F;
B1: Tìm tất cả các tập con của U ( gọi là Xi)
B2: Tìm bao đóng của tất cả tập con của U đối với tập phụ thuộc hàm F.
B3: Dựa vào bao đóng Xi, xác định các phụ thuộc hàm F+
3. TÌM MỘT KHOÁ CỦA LƯỢC ĐỒ QUAN HỆ
Đầu vào: α=<U,F>
Đầu ra: K là khoá của lược đồ
B1: Bắt đầu từ một siêu khoá K ( Thông thường K = U)
B2: Xét từng thuộc tính A của K, đặt K’=K\A. Nếu (K’)+ =U thì gán lại K = K’. Lặp lại bước 2 cho đến khi tất cả các thuộc tính của U được xét hết và tập thuộc tính còn lại K khi đó là một khoá cần tìm.
K’= K\A (K’)+ khác U nên Không loại được A
K’= K\B (K’)+ = U nên loại được B
4. TÌM TẤT CẢ CÁC KHOÁ CỦA LƯỢC ĐỒ
Tập nguồn TN: tập chứa các thuộc tính xuất hiện ở vế Trái nhưng không xuất hiện ở vế Phải và các thuộc tính không tham gia trong tập phụ thuộc hàm.
Tập trung gian TG: tập chứa tất cả các thuộc tính xuất hiện ở cả 2 vế
VT\VP
TN = VT\VP hợp Thuộc tính ko tham gia PTH
TG = VT giao VP
Bước 1: Tìm tập nguồn TN , tập trung gian TG
Bước 2: Trường hợp (TN)+ = U thì kết luận lược đồ có 1 khoá duy nhát K = TN . Kết thúc.
Trường hợp (TN)+ khác U thực hiện bước 3.
Bước 3: Xác định tất cả tập con {Xi} của tập TG. Tính cả tập rỗng
Bước 4: Xác định (TN hợp Xi)+
Nếu (TN hợp Xi)+ = U thì có tập siêu khoá Si = ( TN hợp Xi)
Bước 5: Khoá K = { Si\Sj | Si là tập con của Sj}
5. KIỂM TRA LƯỢC ĐỒ QH THUỘC DẠNG CHUẨN 2NF
Bước 1: Tìm tất cả các khoá của α. Xác định tập thuộc tính không khoá.
Bước 2: Tính (Xi)+ trong đó Xi là tập con thực sự của các khoá K
Bước 3: Nếu Xi+ chứa thuộc tính ko khoá của α thì không là 2NF, ngược lại α là 2NF.
6. KIỂM TRA LƯỢC ĐỒ QH THUỘC DẠNG CHUẨN 3NF
Bước 1: Tìm tất cả khoá của α
Bước 2: Xác định tập thuộc tính không khoá
Bước 3: Nếu có các phụ thuộc hàm X -> Y trong đó Y chứa thuộc tính không khoá mà X là siêu khoá thì lược đồ α đạt 3NF, ngược lại α không là 3NF.
7. KIỂM TRA LƯỢC ĐỒ QH THUỘC DẠNG CHUẨN BCNF
Bước 1: Tìm tất cả các khoá của α;
Bước 2: Từ F tạo tập phụ thuộc hàm tương đương F1tt ( tập các phụ thuộc hàm có vế phải là 1 thuộc tính) loại bỏ phụ thuộc hàm tầm thường (VP là con của VT)
Bước 3: Nếu mọi phụ thuộc hàm X -> A thuộc F1tt với A ko thuộc X đều có X chứa khoá của lược đồ ( X là siêu khoá) thì α đạt chuẩn BCNF, ngược lại α ko đạt BCNF.
8. XÁC ĐỊNH DẠNG CHUẨN CAO NHẤT
Bước 1: Tìm tất cả các khoá của α;
Bước 2: Kiểm tra BCNF
1. Từ F tạo F1tt, loại bỏ phụ thuộc hàm tầm thường(VP là con của VT)
2. Nếu mọi X -> A thuộc F1tt với A không thuộc X, X là siêu khoá
=> BCNF
Bước 3: Kiểm tra 3NF
1. Tìm tập thuộc tính ko khoá
2. Nếu có các pth X -> Y trong đó Y chứa thuộc tính ko khoá, X là siêu khoá
=> 3αINNG INT PRIMARY KEY (MASV) FOREIGN KEY MALOP REFERENCES LOP (MALOP);
NF
Bước 4: Kiểm tra 2 NF
1. Xác định các thuộc tính không khoá
2. Tính (Xi)+ trong đó Xi là tập con thực sự của K
3. Nếu (Xi)+ không chứa thuộc tính ko khoá của X => là 2αINNG INT PRIMARY KEY (MASV) FOREIGN KEY MALOP REFERENCES LOP (MALOP);
3. NF
9. THUẬT TOÁN TÁCH α THÀNH CÁC LƯỢC ĐỒ CON ĐẠT BCNF/3NF VÀ KO MẤT MÁT THÔNG TIN
Bước 1. Tìm Ftt
Bước 2. Tìm khoá α, loại bỏ các thuộc tính không tham gia F
Bước 3. Xác định các phụ thuộc hàm có VT không là siêu khoá ( VP chứa thuộc tính không khoá với 3NF)
Các phụ thuộc hàm vi phạm dạng chuẩn giả sử
X -> Y, X không là siêu khoá (Y chứa thuộc tính không khoá với 3NF) thì tách theo nguyên tắc sau:
U1= XY tính F1 = πu1(F) => α1(U1, F1)
U2= U\Y tính F2=πu2(F) => α2(U2, F2)
Bước 4. Kiểm tra α1 và α2 đạt BCNF / 3NF chưa ?
10. PHÉP TÁCH KẾT NỐI – BẢO TOÀN THÔNG TIN KO ?
Bước 1. Xây dựng bảng cột là Ai là thuộc tính ; dòng là Ui
Ô (i,j) là aj nếu Aj thuộc Ui
Là bij nếu Aj không thuộc Ui
Bước 2. Xét phụ thuộc hàm F: X -> Y
Tại cột của X nếu có các giá trị bằng nhau thì tại cột của Y làm bằng nhau các giá trị là aj nếu có aj hoặc bij nếu không có aj
Bước 3. Lặp lại đến không thay đổi được hoặc xuất hiện 1 dòng a1...an
Bước 4. Kết luận: có a1....an => bảo toàn thông tin. Không có => ko bảo toàn.
11. TÌM PHỦ TỐI THIỂU CỦA 1 PHỤ THUỘC HÀM.
Bước 1. Tính Ftt
Bước 2. Bỏ các thuộc tính dư thừa ở vế trái: Bỏ thuộc tính bên VT khi và chỉ khi bao đóng của các thuộc tính còn lại chứa nó.
Bước 3. Loại các Phụ thuộc hàm dư thừa: Nếu bao đóng của tập thuộc tính VT chứa thuộc tính VP => bỏ đi.
VD: U=ABCDEG
F={ A -> B; C -> AD; AG -> CE}
Hãy tìm phủ tối thiểu của F
F1tt={ A->B; C -> A; C->D; AG -> C; AG -> E}
Kiểm tra A -> B có dư thừa ko ?
Tìm A+ trên F1tt/(A->B) : A+ =A , B không thuộc A+
Suy ra A->B ko dư thừa.
Bạn đang đọc truyện trên: Truyen2U.Pro