Luận văn Thạc sĩ Khoa học máy tính: Lược đồ cơ sở dữ liệu chuẩn hóa

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGUYỄN THỊ MAI LAN

LƯỢC ĐỒ CƠ SỞ DỮ LIỆU CHUẨN HÓA

Ngành: Khoa học máy tính

Mã số: 8.48.01.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: PGS TSKH NGUYỄN XUÂN HUY

THÁI NGUYÊN - 2020

i

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn này do bản thân tôi thực hiện dưới sự hướng

dẫn khoa học của PGS TSKH Nguyễn Xuân Huy – Viện Công nghệ thông tin.

Các kết quả nghiên cứu được trình bày trong luận văn là trung thực và chưa

từng công bố trong bất kỳ công trình nào khác. Mọi thông tin trích dẫn trong

luận văn đều đã được chỉ rõ nguồn gốc.

Thái Nguyên, tháng 9 năm 2020

Tác giả

Nguyễn Thị Mai Lan

ii

LỜI CẢM ƠN

Tác giả xin được bày tỏ lòng biết ơn Ban Giám hiệu, giảng viên Trường

Đại học Công nghệ thông tin – truyền thông – Đại học Thái Nguyên đã tận tình

giảng dạy và tạo mọi điều kiện thuận lợi cho tác giả trong suốt quá trình học

tập, nghiên cứu và thực hiện luận văn.

Với tình cảm chân thành, tác giả xin được bày tỏ lòng biết ơn, cảm ơn sâu

sắc tới PGS. TSKH Nguyễn Xuân Huy đã tận tình hướng dẫn, giúp đỡ để luận

văn hoàn thành.

Cuối cùng, tác giả xin được gửi lời cảm ơn tới bạn bè, gia đình và đồng

nghiệp đã luôn động viên, giúp đỡ tác giả hoàn thành khóa học.

Thái Nguyên, tháng 9 năm 2020

Tác giả

Nguyễn Thị Mai Lan

iii

MỤC LỤC

LỜI CAM ĐOAN ........................................................................................ i

LỜI CẢM ƠN ............................................................................................ ii

MỤC LỤC ................................................................................................. iii

CÁC KÍ HIỆU ............................................................................................ v

DANH MỤC CÁC BẢNG ........................................................................ vi

MỞ ĐẦU ..................................................................................................... 1

1. Đặt vấn đề ................................................................................................ 1

2. Đối tượng và phạm vi nghiên cứu ........................................................... 4

3. Hướng nghiên cứu ................................................................................... 4

4. Phương pháp nghiên cứu ......................................................................... 4

5. Ý nghĩa khoa học và thực tiễn ................................................................. 5

6. Cấu trúc của luận văn .............................................................................. 5

Chương 1. CÁC KIẾN THỨC CƠ BẢN ................................................. 6

1.1.Quan hệ, bộ, thuộc tính .......................................................................... 6

1.2. Phụ thuộc hàm .................................................................................... 12

1.3. Bao đóng của tập thuộc tính ............................................................... 14

1.4. Phủ ...................................................................................................... 17

1.5. Khóa của lược đồ quan hệ .................................................................. 18

1.6. Các dạng chuẩn 1NF, 2NF, 3NF và BCNF ........................................ 19

1.7. Bảo toàn 3NF bảo toàn phụ thuộc hàm .............................................. 19

Chương 2. CÁC THUẬT TOÁN VỀ CHUẨN HÓA DỮ LIỆU QUAN

HỆ .............................................................................................................. 20

2.1. Các thuật toán đại số quan hệ ............................................................. 20

2.1.1. Phép chọn......................................................................................... 20

2.1.2. Phép chiếu ........................................................................................ 20

2.1.3. Kết nối tự nhiên ............................................................................... 21

2.1.4. Phép hợp .......................................................................................... 22

iv

2.1.5. Phép giao ......................................................................................... 22

2.1.6. Phép trừ ............................................................................................ 23

2.1.7. Phép chia .......................................................................................... 24

2.2. Các thuật toán quản lý phụ thuộc hàm ................................................ 25

2.2.1. Thuật toán tìm phủ thu gọn tự nhiên của tập PTH F ....................... 25

2.2.2. Thuật toán tìm phủ không dư của tập PTH F ................................... 26

2.2.3. Thuật toán tìm phủ thu gọn trái của tập PTH F ............................... 26

2.2.4. Thuật toán tìm phủ thu gọn phải của tập PTH F .............................. 27

2.2.5. Thuật toán tìm phủ thu gọn của tập PTH F ...................................... 28

2.3. Các thuật toán tìm bao đóng ............................................................... 29

2.4. Các thuật toán khóa ............................................................................. 30

Chương 3. CÀI ĐẶT VÀ ỨNG DỤNG .................................................. 30

3.1. Tiếp cận hướng đối tượng cho thiết kế ............................................... 30

3.2. Thiết kế lớp tập hợp Set ...................................................................... 30

3.2.1. Các thuộc tính của lớp Set ............................................................... 30

3.2.2. Các phương thức của lớp Set ........................................................... 30

3.2.3. Các phép toán tập hợp ..................................................................... 33

3.3. Thiết kế lớp lược đồ quan hệ RSC ..................................................... 40

3.3.1. Các thuộc tính của lớp lược đồ quan hệ RSC .................................. 40

3.3.2. Các phương thức của lớp lược đồ quan hệ RSC ............................. 40

KẾT LUẬN ............................................................................................... 65

TÀI LIỆU THAM KHẢO ....................................................................... 66

v

CÁC KÍ HIỆU

KÍ HIỆU Ý NGHĨA

Phần tử a thuộc tập S a  S

Phần tử a không thuộc tập S a  S

Tập X là tập con thực sự của tập Y X  Y

Tập X là tập con của tập Y X  Y

X  Y Giao của hai tập X và Y

X  Y Hiệu của tập X và Y

X  Y Hợp của hai tập X và Y

Lượng tử tồn tại 

Lượng tử với mọi 

PTH Phụ thuộc hàm

K Khóa

LĐ Lược đồ

vi

DANH MỤC CÁC BẢNG

Bảng 1. Quan hệ Bán hàng với 3 khách hàng đầu tiên ................................ 2

Bảng 2. Quan hệ Bán hàng với 4 khách hàng ............................................. 3

Bảng 3. Quan hệ Bán hàng với 4 khách hàng ............................................. 3

Bảng 1.1. Quản lý sinh viên ....................................................................... 8

Bảng 1.2. Bảng quy ước kích thước ............................................................ 8

1

MỞ ĐẦU

1. Lý do lựa chọn đề tài

Năm 1970 Codd đề xuất khái niệm phụ thuộc hàm như một cơ chế quản lý

ngữ nghĩa dữ liệu trong cơ sở dữ liệu quan hệ [8], [9].

Cho tập thuộc tính U. Một phụ thuộc hàm (PTH) trên U là công thức dạng

f: X  Y; X, Y  U

trong đó ta gọi X là vế trái và Y là vế phải của PTH f.

Cho quan hệ R(U) và một PTH f: X  Y trên U. Ta nói quan hệ R thoả

PTH f, hoặc PTH f đúng trong quan hệ R và viết R(f), nếu hai bộ tuỳ ý trong R

giống nhau trên X thì chúng cũng giống nhau trên Y,

R(XY)  (u,vR): (u.X = v.X)  (u.Y = v.Y)

Nếu f: X  Y là một phụ thuộc hàm trên U thì ta nói tập thuộc tính Y phụ

thuộc (hàm) vào tập thuộc tính X, hoặc tập thuộc tính X xác định hàm tập thuộc

tính Y.

Nếu Y không phụ thuộc hàm vào X thì ta viết X ! Y hoặc (XY).

Cho tập PTH F trên tập thuộc tính U. Ta nói quan hệ R(U) thoả tập PTH

F, và viết R(F), nếu R thoả mọi PTH trong F: R(F)  ( f  F): R(f)

Cho trước tập thuộc tính U, ký hiệu SAT(F) là tập toàn thể các quan hệ

trên U thoả tập PTH F.

Cho tập  các quan hệ trên U, ký hiệu FD() là tập các PTH trên U đúng

trong mọi quan hệ của .

Cho tập PTH F trên tập thuộc tính U. Bao đóng của F, ký hiệu F + là tập

nhỏ nhất các PTH trên U chứa F và thoả các tính chất F1 - F3 của hệ tiên đề

Armstrong Ao sau đây [1], [2], [3]:

 X, Y, Z  U:

2

F1. Tính phản xạ: Nếu X  Y thì X  Y  F +

F2. Tính gia tăng: Nếu XY  F + thì XZYZ  F +

F3. Tính bắc cầu: Nếu X  Y  F + và Y  Z  F + thì X  Z  F +

Sau đó hàng loạt công trình nghiên cứu đề xuất các dạng chuẩn cho các

lược đồ quan hệ. Một dạng biểu diễn của lược đồ quan hệ được gọi là dạng chuẩn

nếu nó cho phép người quản trị và người khai thác cơ sở dữ liệu đảm bảo được

tính nhất quán và toàn vẹn dữ liệu trong quá trình cập nhật và khai thác cơ sở dữ

liệu [4],[5].

Quá trình chuẩn hoá (do Codd đề nghị 1972) lấy một lược đồ quan hệ và

thực hiện một loạt các kiểm tra để xác nhận nó có thoả mãn một dạng chuẩn nào

đó hay không. Quá trình này được thực hiện theo phương pháp trên xuống bằng

việc đánh giá mỗi quan hệ với tiêu chuẩn của các dạng chuẩn và tách các quan

hệ nếu cần. Lúc đầu, Codd đề nghị ba dạng chuẩn gọi là dạng chuẩn 1, dạng

chuẩn 2 và dạng chuẩn 3. Tất cả các dạng chuẩn này dựa trên các phụ thuộc hàm

giữa các thuộc tính của một quan hệ.

Chuẩn hoá dữ liệu có thể được xem như một quá trính phân tích các lược

đồ quan hệ cho trước dựa trên các phụ thuộc hàm và các khoá chính của chúng

để đạt đến các tính chất mong muốn:

(1) Cực tiểu sự dư thừa và

(2) Cực tiểu các phép cập nhật bất thường.

Đơn giá

Thành tiền

Tên

Số

Bộ

Mã hàng

(nghìn

(nghìn

hàng

lượng

đồng)

đồng)

1

H1

Bút

2

20

10

2

H2

Vở

10

40

4

3

H3

Cặp

1

70

70

Thí dụ, cho quan hệ bán hàng như sau:

3

Bảng 1. Quan hệ Bán hàng với 3 khách hàng đầu tiên

Ta biết, quan hệ Bán hàng các thỏa phụ thuộc hàm sau đây:

Mã hàng  Đơn giá

Mã hàng  Tên hàng

Mã hàng  Đơn giá, Tên hàng

Đơn giá, Số lượng  Thành tiền

Nếu khách hàng thứ tư mua vở nhưng bàn tính tiền nạp nhầm dữ liệu thì quan

Bộ

Mã hàng

Tên hàng

Số lượng

1 2 3 4

H1 H2 H3 H2

Bút Vở Cặp Vở

Đơn giá (nghìn đồng) 10 4 70 4

2 10 1 10

Thành tiền (nghìn đồng) 20 40 70 45

hệ Bán hàng có thể có dạng sau:

Bảng 2. Quan hệ Bán hàng với 4 khách hàng

Như vậy, quan hệ Bán hàng tại Bảng 2 chứa dữ liệu không chuẩn. Sự cố này do

bộ 4 gây ra.

Tuy nhiên, có trường hợp sinh ra dữ liệu không chuẩn nhưng ta không thể biết

nguyên nhân tại bộ nào.

Đơn giá

Thành tiền

Tên

Số

Bộ

Mã hàng

(nghìn

(nghìn

hàng

lượng

đồng)

đồng)

1

H1

Bút

2

20

10

2

H2

Vở

10

40

4

Giả sử khách hàng thứ tư cũng mua vở với dữ liệu được nạp như trong Bảng 3.

70

3

H3

Cặp

1

70

5

4

H2

Vở

10

50

4

Bảng 3. Quan hệ Bán hàng với 4 khách hàng

Lúc này ta chỉ có thể nói, quan hệ Bán hàng chứa dữ liệu mâu thuẫn tại bộ 2 và

bộ 4, nhưng ta không biết bộ nào sinh ra mâu thuẫn.

Trong trường hợp này ta nói quan hệ Bán hàng không chuẩn.

Luận văn được tập trung nghiên cưú các dạng chuẩn của lược đồ cơ sở dữ liệu

quan hệ. Vậy trong khuôn khổ khóa luận thạc sĩ, học viên chọn đề tài:

Lược đồ cơ sở dữ liệu chuẩn hóa

2. Đối tượng và phạm vi nghiên cứu

Luận văn tập trung khảo sát các đối tượng liên quan đến các lược đồ cơ

sở dữ liệu quan hệ sau đây:

 Lý thuyết phụ thuộc hàm.

 Các thuật toán cơ bản xử lý các đối tượng trong lược đồ quan hệ.

 Các thuật toán chuẩn hóa lược đồ quan hệ.

3. Hướng nghiên cứu

 Nghiên cứu lý thuyết liên quan đến đề tài: Cơ sở dữ liệu quan hệ,

phụ thuộc hàm, các dạng chuẩn, các thuật toán tính bao đóng, khóa,

chuẩn hóa.

 Cài đặt các lớp đối tượng quản lý tập hợp, thuộc tính, phụ thuộc

hàm, khóa, các dạng chuẩn 2NF và 3NF.

 Thử nghiệm các lược đồ quan hệ.

5

4. Phương pháp nghiên cứu

Trong luận văn học viên dự kiến sử dụng các phương pháp nghiên cứu chính

sau:

 Phương pháp nghiên cứu lý thuyết: Tổng hợp tài liệu, hệ thống lại các

kiến thức, tìm hiểu các khái niệm, thuật toán sử dụng trong đề tài.

 Phương pháp lập trình hướng đối tượng.

 Phương pháp đối sánh.

 Phương pháp trao đổi khoa học, lấy ý kiến chuyên gia.

5. Ý nghĩa khoa học và thực tiễn

 Việc nghiên cứu đề tài có thể đóng góp thêm một vài chức năng quản lý

ngữ nghĩa dữ liệu thông qua các dạng chuẩn.

 Luận văn thiết kế và cài đặt một hệ thống với các chức năng nhập xuất, lưu

trữ, tính bao đóng, khóa của các lược đồ quan hệ và các thuật toán chuẩn

hóa 3NF. Hệ thống có thể được sử dụng để khảo sát và kiểm định các dạng

chuẩn và các quy trình chuẩn hóa lược đồ quan hệ.

6. Cấu trúc của luận văn

Luận văn có cấu trúc gồm:

Phần mở đầu

Phần nội dung

Chương 1. Các kiến thức cơ sở.

Chương 2. Các thuật toán về chuẩn hóa dữ liệu quan hệ

Chương 3. Cài đặt và ứng dụng.

6

CHƯƠNG 1 - CÁC KIẾN THỨC CƠ BẢN

Trong chương 1 này, tôi sẽ giới thiệu một số cơ sở lý thuyết về cơ sở dữ

liệu gồm:

1.1 Quan hệ, bộ, thuộc tính

Định nghĩa

Cho tập hữu hạn U = {A1, A2 , ... , An} khác rỗng (n 1). Các phần tử của U

được gọi là thuộc tính. Ứng với mỗi thuộc tính AiU, i = 1,2,...,n có một tập

chứa ít nhất hai phần tử dom(Ai) được gọi là miền trị của thuộc tính Ai. Gọi D

là hợp của các dom(Ai), i = 1,2,...,n. Một quan hệ R với các thuộc tính U, ký

hiệu là R(U), là một tập các ánh xạ t: UD sao cho với mỗi AiU ta có

là một bộ của quan hệ R. t(Ai)dom(Ai). Mỗi ánh xạ được gọi

Mỗi quan hệ R(U) có hình ảnh là một bảng, mỗi cột ứng với một thuộc tính,

mỗi dòng là một bộ.

Ta ký hiệu t(U) là một bộ trên tập thuộc tính U.

Một quan hệ rỗng, ký hiệu , là quan hệ không chứa bộ nào.

Vì mỗi quan hệ là một tập các bộ nên trong quan hệ không có hai bộ trùng lặp.

Các ký hiệu và một số quy ước

Theo truyền thống của lý thuyết cơ sở dữ liệu chúng ta chấp nhận các quy

định sau đây:

Các thuộc tính được ký hiệu bằng các chữ LATIN HOA đầu bảng chữ A, B,

C,...

Tập thuộc tính được ký hiệu bằng các chữ LATIN HOA cuối bảng chữ X, Y,

Z,...

Các phần tử trong một tập thường được liệt kê như một xâu ký tự, không có

các ký hiệu biểu diễn tập, chẳng hạn ta viết X = ABC thay vì viết

7

X = A, B, C. XY biểu diễn hợp của hai tập X và Y, X Y. Phép trừ hai tập X

và Y được ký hiệu là X\Y, hoặc X-Y.

Một phân hoạch của tập M (thành các tập con rời nhau và có hợp là M), X1,

X2, ..., Xm được ký hiệu là M = X1 | X2 |... | Xm

với ý nghĩa M = X1  X2  ...  Xm và Xi  Xj = , 1  i, j  m, i  j.

Các bộ được biểu diễn bằng các chữ Latin thường có thể kèm chỉ số, thí dụ t,

u, v, t1 ...

Với mỗi bộ t trong quan hệ R(U) và mỗi tập con các thuộc tính X  U ta ký

hiệu t[X] hoặc t.X là hạn chế của bộ (ánh xạ) t trên tập thuộc tính X.

Ta chấp nhận quy ước tự nhiên là miền trị của mọi thuộc tính chứa ít nhất hai

phần tử. Trong trường hợp một miền trị của thuộc tính chỉ chứa một giá trị

duy nhất thì ta có thể loại bỏ cột tương ứng của thuộc tính đó trong quan hệ.

Ta chấp nhận quy ước sau đây: Mọi cặp bộ t và v trong mọi quan hệ giống

nhau trên miền rỗng các thuộc tính, t. = v..

 Hàm Attr(R) cho tập thuộc tính của quan hệ R.

 Hàm Card(R) cho lực lượng (số bộ) của quan hệ R.

Trong trường hợp tập thuộc tính U đã cho trước ta có thể viết đơn giản R thay

cho R(U)

Ký hiệu REL(U) là tập toàn thể các quan hệ trên tập thuộc tính U, REL_p(U)

là tập toàn thể các quan hệ có không qúa p bộ trên tập thuộc tính U, p  1.

Hai quan hệ R và S được gọi là tương thích nếu chúng có cùng một tập thuộc

tính, tức là nếu Attr(R) = Attr(S).

Với mỗi bộ t trong quan hệ R(U) và mỗi bộ v trong quan hệ S(V) ta ký hiệu tv

là phép dán hai bộ t và v. tv cho ta bộ r trên tập thuộc tính UV thoả điều kiện:

r.U = t và r.V = v.

Với mỗi bộ t trong quan hệ R(U) và với mỗi quan hệ S(V) ta ký hiệu tS là

phép dán bộ t với quan hệ S. tS cho ta quan hệ P(UV) = { tv | vS }

Thí dụ

8

Trong một trường học, chúng ta quản lý sinh viên theo biểu gồm các thuộc tính

STT

Mã SV

Họ tên SV

Lớp

Khoa

Giới tính

Năm sinh

Quê quán

1

DTS001

Nam

2001

A1

Thái Bình

Toán học

Nguyễn Duy Nam

2

DTS002

Nữ

2001

Phú Thọ

A2

Bùi Minh Hiền

Vật lí

3

DTS003

Nữ

2000

A1

Trần Ngọc Hà

Thái Nguyên

Toán học

…

…

…

…

…

…

130

DTS130

Nam

2001

Hà Nội

A3

Hóa học

Hoàng Mạnh Trung

sau:

Bảng 1.1. Quản lý sinh viên

Ta quy ước kích thước của các thuộc tính như sau:

Tên thuộc tính

Kích thước

Kiểu

STT

Kí tự

3

MASV

Kí tự

8

HOTEN

Kí tự

30

GIOITINH

Kí tự

4

NAMSINH

Số

4

QUE

Kí tự

15

LOP

Kí tự

3

KHOA

Kí tự

15

Bảng 1.2. Bảng quy ước kích thước

9

SINHVIEN={STT,MASV,HOTEN,GIOITINH,NAMSINH,QUE,LOP,KHOA}

Như vậy ta có tập thuộc tính

Ta có ứng với cột Mã SV có DTS01, DTS02…DTS130 là thuộc tính của bảng

Với bản ghi thứ 2(dòng thứ 2) chúng ta có một bộ gồm STT(2), Mã SV(DTS02),

Họ tên SV(Bùi Minh Hiền), Giới tính(Nữ), Năm sinh(2001), Quê quán(Phú

Thọ), lớp(A2), Khoa(Vật lí).

1.2 Phụ thuộc hàm

Định nghĩa

Cho tập thuộc tính U. Một phụ thuộc hàm (PTH) trên U là biểu thức dạng

f: X→Y ; X,Y⊆ U

Nếu f: X→Y là một phụ thuộc hàm trên U thì ta nói tập thuộc tính Y phụ thuộc

vào tập thuộc tính X, hoặc tập thuộc tính X xác định hàm tập thuộc tính Y. X là

vế trái và Y là vế phải của PTH f. Ta cũng dùng hai toán tử LS(f) và RS(f) để xác

định vế trái và vế phải của PTH f, cụ thể là

nếu f: X→ Y thì LS(f) = X, RS(f) = Y.

Cho quan hệ R(U) và một PTH f: X→Y trên U. Ta nói quan hệ R thoả PTH f

và viết R(f), nếu hai bộ tuỳ ý trong R giống nhau trên X thì chúng cũng giống

nhau trên Y.

R(X→Y) (∀ u,v ∈ R): (u.X = v.X) (u.Y = v.Y)

Ta dùng ký hiệu X ↛Y với ý nghĩa tập thuộc tính Y không phụ thuộc hàm vào

tập thuộc tính X[7,8].

Cho tập PTH F trên tập thuộc tính U. Ta nói quan hệ R(U) thoả tập PTH F, và

viết R(F), nếu R thoả mọi PTH trong F

R(F)  (∀ f ∈ F): R(f)

10

Nếu quan hệ R thỏa PTH f ta cũng nói PTH f đúng trong quan hệ R.

Thí dụ: Cho quan hệ R(A, B, C, D, E) như sau

P (A B C D E) a 1 x d y a 1 x d x b 2 y 2 x b 2 y 2 y

Và các PTH f1: AA, f2: AB, f3: ACC, f4: AD, f5: DA, f6: AE.

Khi đó các PTH f1 - f5 đúng trong R, mặt khác, R không thỏa PTH f6.

Cho trước tập PTH F trên tập thuộc tính U, ký hiệu SAT(F) là tập toàn thể các

quan hệ trên U thoả tập PTH F, SAT_p(U), p  1 là tập toàn thể các quan hệ

Có không quá p bộ trên U và thoả tập PTH F , cụ thể là

SAT(F) = { R | RREL(U), R(F) }

SAT_p(F) = { R | RREL_p(U), R(F) }

Cho tập  các quan hệ trên U, ký hiệu FD() là tập các PTH trên U đúng

trong mọi quan hệ của .

Hệ tiên đề Armstrong

Bao đóng của tập PTH

Định nghĩa

Cho tập PTH F trên tập thuộc tính U. Bao đóng của F, ký hiệu F+ là tập nhỏ

nhất các PTH trên U chứa F và thoả các tính chất F1-F3 của hệ tiên đề

Armstrong Ao sau đây

X, Y, Z  U:

F1. Tính phản xạ: Nếu X  Y thì XY  F +

F2. Tính gia tăng: Nếu XY  F + thì XZYZ  F +

F3. Tính bắc cầu: Nếu XY  F + và YZ  F + thì XZ  F +

Chú ý :

11

Các PTH có vế trái chứa vế phải như mô tả trong F1 được gọi là tầm thường.

Các PTH tầm thường đúng trong mọi quan hệ. Ngoài ra, các quan hệ trên tập

thuộc tính U có không quá một bộ thỏa mọi PTH trên U.

Một số tính chất của PTH

Cho tập thuộc tính U và các tập phụ thuộc hàm F, G trên U, tập một số quan

hệ  trên U, các quan hệ R và S trên U. Dễ dàng chứng minh các tính chất sau

đây:

1. Nếu F  G thì SAT(F)  SAT(G)

2. SAT(FG) = SAT(F)  SAT(G)

3. FD(RS)  FD(R)  FD(S)

4. R  S  FD(R)  FD(S)

5. F  FD(SAT(F))

6.   SAT(FD())

7. SAT(FD(SAT(F))) = SAT(F)

8. FD(SAT(FD())) = FD()

Thí dụ

Chứng tỏ FD(RS)  FD(R )  FD(S).

Ta chọn U = AB; quan hệ R(U) chứa một bộ duy nhất u = (a,x); quan hệ S(U)

chứa một bộ duy nhất v = (a,y), x y.

R và S thỏa mọi PTH trên U. Quan hệ P = R S chứa 2 bộ u và v. P không thỏa

PTH AB.

Một số tính chất mở rộng của PTH

Sử dụng ba tiên đề Armstrong ta dễ dàng chứng minh các tính chất F4 - F11 sau

đây. Một số tính chất được chia nhỏ nhằm mục đích mô tả các hệ tiên đề khác

cho PTH trong các mục tiếp theo.

 X, Y, Z, V  U,  A  U:

F4. Tính tựa bắc cầu: XY, YZV  XZV

F5. Tính phản xạ chặt: X X

12

F6. Mở rộng vế trái và thu hẹp vế phải: XY  XZY\V

F7. Cộng tính đầy đủ: XY, ZV  XZYV

F8. Mở rộng vế trái: XY  XZY

F9. Cộng tính ở vế phải: XY, XZ  XYZ

F10. Bộ phận ở vế phải: XYZ  XY

F11.Tính tích luỹ: XYZ, ZAV  XYZA

1.3 Bao đóng của tập thuộc tính

Định nghĩa

Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong U.

Bao đóng của tập thuộc tính X, ký hiệu X+ là tập thuộc tính

X+ = {A U | X  AF+}

Thuật toán tìm bao đóng của một tập thuộc tính

Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong U.

Để xác định bao đóng X+ của tập thuộc tính X ta xây dựng dãy bao nhau

X(0)  X(1)  …  X(i) như sau

 Xuất phát: Đặt X(0)=X,

 Với i > 0, ta đặt

𝐿→𝑅∈𝐹 𝐿𝑋𝑖

𝑋(𝑖+1) = 𝑋𝑖 ⋃ 𝑅

 Nếu X(i+1) = X(i) thì dừng thuật toán và cho kết quả X + = X(i).

Algorithm Closure Format: thuộc tính X của U Output: - Y = X+ = {A U | XA F+} Method Y:=X; repeat

13

Z:=Y; for each FD LR in F do if L  Y then Y:=YR; endif; endfor; until Y=Z; return Y; end Closure.

Thuật toán trên có độ phức tạp O(mn2 ).

1.4 Phủ

Định nghĩa

Cho hai tập PTH F và G trên cùng một tập thuộc tính U. Ta nói F suy dẫn ra

được G, ký hiệu F╞ G, nếu gG: F╞ g. Ta nói F tương đương với G, ký hiệu

F  G, nếu F╞ G và G╞ F. Nếu F  G ta nói G là một phủ của F. Ký hiệu F ≢

G có nghĩa F và G không tương đương. Cho tập PTH F trên tập thuộc tính U và

X là tập con của U, ta dùng ký hiệu XF+ trong trường hợp cần chỉ rõ bao đóng

của tập thuộc tính X lấy theo tập PTH F.

+ Phủ không dư

Định nghĩa: Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ

không dư

của F nếu

(i) G là một phủ của F, và

(ii) G có dạng không dư theo nghĩa sau: gG: G \{g} ≢ G

Thuật toán tìm phủ không dư của tập PTH

Algorithm Nonredundant Format: Nonredundant(F) Input: - Tập PTH F Output: - Một phủ không dư G của F

14

(i) G  F  (ii) g  G: G\{g} ≢ G Method G:=F; for each FD g in F do If IsMember(g,G\{g})then G:=G\{g}; endif; endfor; return G; end Nonredundant.

+ Phủ thu gọn trái

Định nghĩa: Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ

thu gọn trái của F nếu

(i) G là một phủ của F, và

(ii) (LRG,AL): G\{LR}{L\AR} ≢ G

Thuật toán tìm phủ thu gọn trái của tập PTH

Để ý rằng AL ta có L\A L, nên

g: LRG,AL): G\{g}{L\AR}╞ LR,

do đó ta chỉ cần kiểm tra G ╞ L\AR ?

Algorithm Left_Reduced Format: Left_Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn trái G của F (i) G  F (ii) g:LRG,AL: G\{g}{L\AR}≢G Method G:=F; for each FD g:L  R in F do X:=L; for each attribute A in X do if IsMember(L\AR,G)then delete A from L in G; endif; endfor;

15

endfor; return G; end Left_Reduced.

+ Phủ thu gọn phải

Định nghĩa: Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ

thu gọn phải của F nếu

(i) G là một phủ của F, và

(ii) (LRG, AR): G\{LR}{LR\A} ≢ G

Thuật toán tìm phủ thu gọn phải của tập PTH

Algorithm Right_Reduced Format: Right_Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn của F Method G:=F; for each FD g:L  R in F do H:=G\{LR}; X:=R; for each attribute A in X do if A in Closure(L,H{LR\A})then delete A from R in G; endif; endfor; endfor; return G; end Right_Reduced.

+ Phủ thu gọn

Định nghĩa: Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ

thu gọn của F nếu G đồng thời là phủ thu gọn trái và thu gọn phải của F.

Thuật toán tìm phủ thu gọn của tập PTH

Algorithm Reduced

16

Format: Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn của F Method return Right_Reduced(Left_Reduced(F)); end Reduced

+ Phủ tối thiểu

Định nghĩa: Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ

tối thiểu của F nếu

(i) G là một phủ thu gọn của F

(ii) Vế phải của mọi PTH trong G chỉ chứa một thuộc tính.

Thuật toán tìm phủ tối thiểu của tập PTH

Algorithm MinCover Format: MinCover(F) Input: - Tập PTH F Output: - Một phủ tối thiểu G của F Method // Tách mỗi PTH LR trong F thành các PTH có // vế phải chỉ chứa một thuộc tính LA, A  R G:=; for each FD LR in F do for each attribute A in R\L do if LA not_in G then add LA to G; endif; endfor; endfor; G:=Nonredundant(Left_Reduced(G)); return G; end MinCover.

Thí dụ

17

Cho lược đồ quan hệ R = , Trong đó :

U = {ABC}

F = {A→B, B→A, C→B}

Hãy tìm một khoá tối thiểu K của lược đồ R

Đặt T = {ABC}; P = {AB} ; K = U\P = {C}

Tính thử K +

Ta có K+ = {CBA} = U

Vì K+ = U, nên khóa tối thiểu tìm được là: K = {C} là một khoá của R.

1.5 Khóa của lược đồ quan hệ

Cho LĐQH p = (U,F). Tập thuộc tính K  U được gọi là khoá của LĐ p nếu

(i) K + = U

(ii)  A  K: (K  {A})+  U

Hai điều kiện trên tương đương với

(i') K  U

(ii')  A  K: (K  {A}) ! U

Nếu K thoả điều kiện (i) thì K được gọi là một siêu khoá.

Thuộc tính A  U được gọi là thuộc tính khoá (nguyên thuỷ hoặc cơ sở)

nếu A có trong một khoá nào đấy. A được gọi là thuộc tính không khoá (phi

nguyên thuỷ hoặc thứ cấp) nếu A không có trong bất kỳ khoá nào. Cho LĐQH

(U,F), ta kí hiệu UK là tập các thuộc tính khóa và Uo là tập các thuộc tính

không khóa.

Thí dụ:

Tìm khóa biết: U = ABCDEGF = {B -> C, AC -> D, D -> G, AG -> E}

Đặt: T = { BACDG}- P = {CDGE}- K = U\P

Ta được: K = {AB}, T ∩ P = {CDG}

Tính K+ ta có: K+ = {BEACDG} U

18

Vậy khóa tìm được là: K = {AB}

Chú ý: Trong một số tàì liệu thuật ngữ khoá được dùng theo nghĩa siêu

khoá và thuật ngữ khoá tối tiểu được dùng theo nghĩa khoá.

1.6 Các dạng chuẩn 1NF, 2NF, 3NF và BCNF

LĐQH p = (U,F) được gọi là LĐ

a) dạng chuẩn 1 (1NF) nếu mọi thuộc tính trong U đều không phải là thuộc

tính phức hợp. Chính xác ra là: LĐ p được gọi là LĐ dạng chuẩn 1 nếu chỉ sử

dụng các phép toán quan hệ thì không thể truy nhập đến một thành phần của

một thuộc tính có hơn một thành phần.

b) dạng chuẩn 2 (2NF) nếu p là LĐ 1NF và mọi thuộc tính không khoá đều

phụ thuộc đầy đủ vào mọi khoá,

 A  Uo ,  K  Key(p) : K + A

c) dạng chuẩn 3 (3NF) nếu p là LĐ 1NF và mọi thuộc tính không khoá đều

phụ thuộc trực tiếp vào mọi khoá,

 A  Uo ,  K  Key(p) : K * A

d) dạng chuẩn 3 (3NF) nếu p là LĐ 1NF và mọi PTH không tầm thường

XA, A là thuộc tính không khóa đều cho ta X là một siêu khoá,

 (X  A, A  Uo – X )  X + = U

e) dạng chuẩn Boyce-Codd (BCNF) nếu p là LĐ 1NF và mọi thuộc tính

đều phụ thuộc trực tiếp vào mọi khoá,

 A  U ,  K  Key(p) : K * A

f) dạng chuẩn Boyce-Codd (BCNF) nếu p là LĐ 1NF và mọi PTH không tầm

thường XY đều cho ta X là một siêu khóa.

 (X  Y, Y – X   )  X + = U

Sơ đồ tương quan giữa các dạng chuẩn

BCNF  3NF  2NF

1.7 Bảo toàn 3NF bảo toàn phụ thuộc hàm

19

Algorithm 3NF Function: Chuẩn hóa 3NF không tổn thất và bảo toàn PTH. Input: LĐQH p = (U,F) Output: Các LĐQH 3NF (U1,K1),(U2,K2),...,(Us,Ks) thoả RREL(U): R[U1]R[U2]...R[Us] = R K1, K2,..., Ks - khoá của các lược đồ tương ứng F  {F+[Ui] | i = 1,2,...,s} Method 1. Tìm một phủ tối thiểu của F: G = {K1A1, K2A2,..., KmAm} 2. Ghép các PTH có cùng vế trái trong G để thu được phủ G = {K1X1, K2X2,..., KsXs}. 3. /* Xét phép tách  = (K1X1,...,KsXs). Nếu  chứa một siêu khóa nào đó của p thì return {(K1X1,K1),...,(KsXs,Ks)} nếu không return {(K1X1,K1),...,(KsXs,Ks),(K,K)} với K là một khóa của p. */ construct  = (K1X1,K2X2,...,KsXs); for each component V = KiXi in  do if V+ = U then // V = KiXi là siêu khóa return {(K1X1,K1),...,(KsXs,Ks)}; endif; endfor; K = Key(U,F); return {(K1X1,K1),...,(KsXs,Ks),(K,K)}; End 3NF

20

CHƯƠNG 2 - CÁC THUẬT TOÁN VỀ CHUẨN HÓA DỮ LIỆU

QUAN HỆ

Trong chương này tôi sẽ trình bày các thuật toán của đại số quan hệ, thuật toán

quản lý phụ thuộc hàm, các thuật toán tìm bao đóng và các thuật toán tìm khóa

gồm các thuật toán sau:

2.1. Các thuật toán của đại số quan hệ

Các thuật toán của đại số quan hệ gồm:

2.1.1 Phép chọn

Algorithm Selection Function: Thực hiện phép Chọn Format: P = R(e) Input: - Quan hệ R(U) - Biểu thức chọn e trên U. Output: - Quan hệ P(U) = R(e) = {tR | Sat(t,e)} Method // Tạo lập quan hệ P tương thích với R

Create(P,Attr(R)); for each tuple t in R with Sat(t,e) do

add t to P ;

endfor; return P;

end Selection.

Độ phức tạp tính toán: Thuật toán duyệt r bộ, phép kiểm tra Sat(t, e) kiểm tra

trên n thuộc tính, tổng cộng cần O(n.r) phép kiểm tra. [1,2]

2.1.2 Phép chiếu

Algorithm Projection Function: Thực hiện phép Chiếu Format: P = R[X] Input: - Quan hệ R(U) - Tập con thuộc tính X của U.

21

Output: - Quan hệ R[X]={t.X | tR} Method Create(P,X); for each tuple t in R with t.X not_in P do add t.X to P ; endfor;

return P;

end Projection.

Độ phức tạp tính toán: Giả sử mỗi lần thuật toán chỉ nạp được 1 bộ vào quan

hệ kết quả P. Để kiểm tra bộ t.X có trong P ta cần tối đa r phép so sánh theo n

thuộc tính. Vậy độ phức tạp tính toán là O(n.r2). [1,2]

2.1.3 Kết nối tự nhiên

Algorithm Join Function: Thực hiện phép Kết nối tự nhiên hai quan hệ. Format: P = RS Input: - Quan hệ R(U) - Quan hệ S(V) Output: - Quan hệ RS={uv | uR,vS,u.M = v.M, M = U  v} Method X = Attr(R)  Attr(S); M = Attr(R)  Attr(S); Create(P,X); for each tuple u in R do for each tuple v in S with (u.M = v.M) do add uv to P ; endfor; endfor; return P; end Join.

22

Độ phức tạp tính toán: Giả sử hai quan hệ R và S có k thuộc tính chung, khi đó

độ phức tạp tính toán sẽ là O(r.s.k) thao tác trên bộ. [1,2]

2.1.4 Phép hợp

Algorithm Union Function: Thực hiện phép Hợp hai quan hệ Format: P = R+S Input: - Quan hệ R(U) - Quan hệ S(U) Output: - Quan hệ R+S = {t | tR  tS} Method P := R; for each tuple v in S with (v not_in R) do add v to P ; endfor; return P; end Union.

Độ phức tạp tính toán: Phép kiểm tra v thuộc R đòi hỏi r lần duyệt và so sánh

trên n thuộc tính. Vậy độ phức tạp tính toán sẽ là O(s.r.n) thao tác trên bộ. [1,2]

2.1.5 Phép giao

Algorithm Intersection Function: Thực hiện phép giao hai quan hệ Format: P = R & S Input: - Quan hệ R(U) - Quan hệ S(U) Output: - Quan hệ R & S = { t | t  R  t  S } Method

Create(P,Attr(R)); for each tuple u in R with (u in S) do add u to P; endfor; return P;

end Intersection.

Độ phức tạp tính toán: O(s.r.n). [1,2]

23

2.1.6 Phép trừ

Algorithm Substraction Function: Thực hiện phép Trừ hai quan hệ Format: P = R-S Input: - Quan hệ R(U) - Quan hệ S(U) Output: - Quan hệ R - S = {t | t  R  t  S} Method

Create(P,Attr(R)); for each tuple u in R

with (u not_in S) do add u to P;

endfor;

return P;

end Substraction.

Độ phức tạp tính toán: O(s.r.n). [1,2]

2.1.7 Phép chia

Algorithm Division Function: Thực hiện phép Chia hai quan hệ Format: P = R:S Input: - Quan hệ R(U) - Quan hệ S(V) Output: Quan hệ R:S = {t.M | tR,(t.M)S  R, M = U-V} Method

M = Attr(R)-Attr(S); c := Card(S);//số bộ của S Create(P,M); for each tuple t in R with (t.M not_in P) do

d := 0;//khởi tạo biến đếm for each tuple v in S if (t.M)v in R then d := d + 1

else breakfor;

endif; endfor; if d = c then add t.M to P;

24

endif; endfor; return P;

end Division.

Độ phức tạp tính toán: Thuật toán duyệt r bộ của quan hệ R. Phép kiểm tra t.M

thuộc P đòi hỏi r lần duyệt và so sánh trên n thuộc tính. Tiếp đến là duyệt s lần

các bộ v của quan hệ S và kiểm tra (t.M)*v có trong R. Vậy độ phức tạp tính toán

sẽ là O(r2.s.n) thao tác trên bộ. [1,2]

2.2. Các thuật toán quản lý tập phụ thuộc hàm.

Các thuật toán quản lý phụ thuộc hàm gồm:

2.2.1 Thuật toán tìm phủ thu gọn tự nhiên của tập PTH F.

Định nghĩa: Cho hai tập PTH F và G trên cùng một tập thuộc tính U. G là phủ

thu gọn tự nhiên của F nếu

1. G là một phủ của F, và

2. G có dạng thu gọn tự nhiên theo nghĩa sau:

2a. Hai vế trái và phải của mọi PTH trong G rời nhau (không giao nhau.)

f  G: LS(f)  RS(f) = 

2b. Các vế trái của mọi PTH trong G khác nhau đôi một.

f, g  G: f  g  LS(f)  LS(g)

Thuật toán

Algorithm Natural_Reduced Function: Tính phủ thu gọn tự nhiên của tập PTH Format: Natural_Reduced(F) Input: - Tập PTH F

Output: - Một phủ thu gọn tự nhiên G của F

(i) G  F (ii)  LR  G: L  R =  (iii) LiRi,LjRjG: ij  LiLj

Method

G := ; for each FD L  R in F do

Z := R - L;

25

if Z   then

if there is an FD L  Y in G then

replace L  Y in G by L 

YZ

else add L  Z to G;

endif;

endif; endfor; return G;

end Natural_Reduced.

Độ phức tạp của thuật toán: Trong [2] độ phức tạp của thuật toán là O(mn) với

m là số lượng PTH trong tập F và n là số lượng thuộc tính trong U. [1.2]

2.2.2 Thuật toán tìm phủ không dư của tập PTH F.

Định nghĩa: Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ

không dư của F nếu

(i) G là một phủ của F, và

(ii) G có dạng không dư theo nghĩa sau: gG: G \{g} ≢ G

Thuật toán

Algorithm Nonredundant Function: Tính phủ không dư

Format: Nonredundant(F) Input: - Tập PTH F

Output: - Một phủ không dư G của F

(i) G  F (ii)  g G: G-{g} ! G Method U := Attr(F); // Tập thuộc tính của F G := F;

for each FD g: L  R in F do

if R  Closure(U,G-{g},L) then

G := G – {g};

endif; endfor; return G;

26

end Nonredundant.

2.2.3 Thuật toán tìm phủ thu gọn trái của tập PTH.

Định nghĩa: Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ

thu gọn trái của F nếu

(i) G là một phủ của F, và

(ii) (LRG,AL): G\{LR}{L\AR} ≢ G

Thuật toán

Để ý rằng AL ta có L\A L, nên

g: LRG,AL): G\{g}{L\AR}╞ LR,

do đó ta chỉ cần kiểm tra G ╞ L\AR ? [1,2]

Algorithm Left_Reduced Function: Tính phủ thu gọn trái của tập PTH Format: Left_Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn trái G của F

(i) G  F (ii)  g:LR G,AL: G-{g}{L-{A}R}!G Method U := Attr(F);// Tap thuoc tinh cua F G := F; for each FD g:L  R in F do

X := L;

for each attribute A in X do if R  Closure(U,G,L-{A}) then

delete A from L in G;

endif; endfor; endfor; return G; end Left_Reduced.

2.2.4 Thuật toán tìm phủ thu gọn phải của tập PTH F.

27

Định nghĩa: Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ

thu gọn phải của F nếu

(i) G là một phủ của F, và

(ii) (LRG, AR): G\{LR}{LR\A} ≢ G

Thuật toán

Algorithm Right_Reduced Function: Tính phủ thu gọn phải của tập PTH Format: Right_Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn phải G của F

(i) G  F (ii) g:LRG,AR:G-{g}{LR-{A}}!G

Method

U := Attr(F);// Tập thuộc tính của F G := F; for each FD g:L  R in F do X := R; for each attribute A in X do

if A in Closure(U,G-{g}{LR-{A}},L)

then delete A from R in G; endif;

endfor; if R =  then delete L  R from G; endif; endfor; return G;

Right_Reduced.

2.2.5 Thuật toán tìm phủ thu gọn của tập PTH F.

Định nghĩa: Cho hai tập PTH F và G trên tập thuộc tính U. G được gọi là phủ

thu gọn của F nếu G đồng thời là phủ thu gọn trái và thu gọn phải của F. [1,2]

Algorithm Reduced

28

Function: Tính phủ thu gọn của tập PTH Format: Reduced(F) Input: - Tập PTH F Output: - Một phủ thu gọn của F Method

return Right_Reduced(Left_Reduced(F));

end Reduced.

2.3. Các thuật toán tính bao đóng.

Định nghĩa: Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc

tính X trong U. Bao đóng của tập thuộc tính X, ký hiệu X+ là tập thuộc tính

X+ = {A U | X  AF+}

Thuật toán

Algorithm Closure Function: Tính bao đóng của tập thuộc tính. Format: Y = Closure(U,F,X) Input: - LĐQH p =(U,F) - Tập thuộc tính X  U Output: - Y = X+ = { A  U | XA  F+ } Method Y := X; repeat Z := Y; for each FD L  R in F do if L  Y then Y := Y  R; endif; endfor; until Y=Z; return Y; end Closure.

Độ phức tạp tính toán Giả sử mỗi lần lặp trong repeat ta chỉ thêm được 1 thuộc

tính. Khi đó repeat sẽ được lặp tối đa n lần. Mỗi lần lặp ta phải duyệt toàn bộ m

29

phụ thuộc hàm để thực hiện các thao tác trên các tập chứa tối đa n thuộc tính.

Vậy độ phức tạp tính toán sẽ là O(n2m). [1,2]

2.4. Các thuật toán khóa

Tư tưởng: Xuất phát từ một siêu khóa K tùy ý của LĐQH, duyệt lần lượt các

thuộc tính A của K, nếu bất biến (K{A})+ = U được bảo toàn thì loại A khỏi K.

Có thể thay kiểm tra (K{A})+ = U bằng kiểm tra A  (K{A})+. [2]

Algorithm Key Function: Tìm một khóa của LĐQH

Format: Key(U,F) Input:

- Tập thuộc tính U - Tập thuộc PTH F

Output: - Khóa K  U thỏa

(i) K+ = U (ii) AK: (K-{A})+  U Method K := U; for each attribute A in U do if A (K-{A})+ then K := K-{A} endif; endfor; return K;

end Key.

Độ phức tạp tính toán Trong thuật toán duyệt n thuộc tính, với mỗi thuộc tính

thực hiện phép lấy bao đóng với độ phức tạp n2m. Tổng hợp lại, độ phức tạp

tính toán của thuật toán là O(n3m). [1,2]

CHƯƠNG 3 – CÀI ĐẶT VÀ ỨNG DỤNG

30

Trong chương này tôi sẽ trình bày cài đặt và ứng dụng cho các thuật toán

theo hướng đối tượng cho thiết kế lớp tập hợp Set và lớp lược đồ quan hệ RSC

gồm:

3.1. Tiếp cận hướng đối tượng cho thiết kế

Theo tiếp cận hướng đối tượng ta có thể thiết kế và cài đặt một kiểu dữ liệu

mới. Luận văn sẽ tập trung thiết kế ba kiểu dữ liệu phục vụ cho các chương

trình xử lý các tập là:

 Lớp tập hợp Set

 Lớp lược đồ quan hệ RSC

3.2. Thiết kế lớp tập hợp Set

3.2.1 Các thuộc tính của lớp Set

const int __SETSIZE = 26;

typedef bitset<__SETSIZE> BS;

Ta định nghĩa kiểu dữ liệu BS như sau:

BS Data;

Trong lớp Set thuộc tính Data được định nghĩa là:

Như vậy, Data là trường dữ liệu chứa 0-25 bit

3.2.2 Các phương thức của lớp Set

Tạo tử (constructor)

inline Set() {

Data.reset();

}

Cú pháp

Ý nghĩa: Khởi tạo tập rỗng

Cú pháp

31

inline Set(const string s) {

for (int i = 0; i < s.length(); ++i)

if (IsAlpha(s[i]))

Data.set(Code(s[i]));

}

Data.reset();

Ý nghĩa: Khởi tạo Set nhận giá trị từ chuỗi s

Ví dụ: Set x(“ABC”);

Khi đó x chứa 2 phần từ A, B, C

inline Set(const Set &x) {

Data = x.Data;

}

Cú pháp

Ý nghĩa: Khởi tạo Set nhận giá trị của tập x cho trước

Set x(“ABC”);

Set y(x);

Ví dụ:

Khởi tạo x chứa 3 phần từ A, B, C

Set y(x) khởi tạo tập y nhận các giá trị của tập x là 3 phần từ A, B, C

inline void Reset() { Data.reset(); }

Cú pháp

Ý nghĩa: Reset một tập thành tập rỗng

Toán từ gán

Cú pháp

for (int i = 0; i < s.length(); ++i)

if (IsAlpha(s[i]))

Data.set(Code(s[i]));

32

inline void operator =(const string s) { Data.reset(); }

Ý nghĩa : Gán một chuỗi từ tập x

Lấy giá trị của tập hợp

return (Data[i]) ? ToAlpha(i) : NULL;

if (Data[i]) } return NULL;

inline char operator[](int i) const {

if (i >= 0 && i < __SETSIZE) { }

Cú pháp

Ý nghĩa: Lấy phần từ thứ i cuả tập hợp.

Kiểm tra tập hợp có phải là tập rỗng hay không

inline bool Empty() const {return Data.none();}

Cú pháp

Ý nghĩa:

Kiểm tra một phần tử có thuộc tập hợp hay không

return Data[Code(e)];

if (IsAlpha(e)) return 0;

inline bool IsIn(char e) { }

Cú pháp

Lực lượng của tập hợp

Cú pháp

inline int Card() const {return Data.count();

Ý nghĩa: trả về số của tập hợp

Thêm phần tử vào tập hợp

Cú pháp

33

} Ý nghĩa : Thêm phần từ e vào tập x

inline void Ins(char e) { if (IsAlpha(e)) Data.set(Code(e));

Xóa phần từ

inline void Del(char e) {

if (IsAlpha(e)) Data.reset(Code(e));

} Ý nghĩa : Xóa phần tử e từ tập hợp

Cú pháp

Thêm phần tử

inline void Add(char e) {Ins(e);

Cú pháp

Ý nghĩa: Thêm phần tử e vào tập hợp

3.2.3 Các phép toán tập hợp

Hợp của hai tập hợp

Set operator +(const Set &y) const {

Set z(*this); z.Data |= y.Data; return z;

}

inline void operator +=(const Set &y) { *this = *this + y; }

Ý nghĩa: Trả về hợp của 2 tập hợp

Cú pháp

Giao của hai tập hợp

Set operator *(const Set &y) const {

Set z(*this); z.Data &= y.Data;

return z;

}

inline void operator *=(const Set &y) { *this = *this * y;

Cú pháp

}

34

Ý nghĩa: Trả về giao của 2 tập hợp

Hiệu của hai tập hợp

Set operator -(const Set &y) const {

z.Data[i] = 1;

Set z;

for (int i = 0; i < __SETSIZE; ++i) if (Data[i] && (!y.Data[i])) return z;

}

inline void operator -=(const Set &y) {

*this = *this - y;

}

Cú pháp

Ý nghĩa: Trả về hiệu của 2 tập hợp

So sánh hai phần tử

So sánh bằng

inline bool operator ==(const Set & y) const {

return Data == y.Data;

} Ý nghĩa: So sánh hai tập hợp có bằng nhau hay không

Cú pháp

So sánh khác

inline bool operator !=(const Set & y) const {

return Data != y.Data;

} Ý nghĩa: So sánh hai tập hợp có khác nhau hay không

Cú pháp

So sánh nhỏ hơn hoặc bằng

inline friend bool operator <=(const Set & x, const Set & y){ for (int i = 0; i < __SETSIZE; ++i)

if (x.Data[i] && (!y.Data[i]))

return false;

return true; }

Cú pháp

35

Ý nghĩa: So sánh hai tập hợp có nhỏ hơn hoặc bằng nhau không.

So sánh lớn hơn hoặc bằng

inline friend bool operator >=(const Set & x, const Set & y){

return y <= x;

}

Cú pháp

Ý nghĩa: So sánh hai tập hợp có lớn hơn hoặc bằng nhau không.

So sánh nhỏ hơn

friend bool operator <(const Set & x, const Set & y) {

return((x <= y) && (x != y));

} Ý nghĩa: So sánh hai tập hợp có nhỏ hơn không

Cú pháp

So sánh lớn hơn

inline friend bool operator >(const Set & x, const Set & y) {

return y < x;

} Ý nghĩa: So sánh hai tập hợp có lớn hơn không

Cú pháp

Hiển thị

friend ostream & operator <<(ostream & os, const Set & s) {

}

os << "{}"; return os;

os << ToAlpha(i);

if (s.Empty()) { for (int i = 0; i < __SETSIZE; ++i) { if (s.Data[i]) } return os;

}

Cú pháp

Ý nghĩa: Hiển thị các phần tử ra màn hình

inline void Print(string msg = "") {

Cú pháp

return;

cout << "{}"; }

cout << ToAlpha(i);

36

cout << msg; if (Empty()) { for (int i = 0; i < __SETSIZE; ++i) { if (Data[i]) } } } Ý nghĩa: Hiển thị các phần tử ra màn hình và kèm theo thông báo msg

Ví dụ: Chương trình Demoset.cpp thực hiện các thao tác như sau:

1. Khai báo tập x, y

2. So sánh tập x có lớn hơn hoặc bằng tập y hay không

3. Hiển thị ra màn hình tập x, y

Như vậy ta thu được

Demoset.cpp

*************************************************/ #include #include #include using namespace std; const int __SETSIZE = 26; const int __UNIT = 16; typedef bitset<__SETSIZE> BS; class Set {

BS Data;

protected: public: inline Set() { Data.reset(); }

for (int i = 0; i < s.length(); ++i)

if (IsAlpha(s[i]))

Data.set(Code(s[i]));

inline Set(const string s) { Data.reset(); } inline Set(const Set &x) { Data = x.Data; }

/******************************************

Data.set(Code(s[i]));

if (IsAlpha(s[i]))

for (int i = 0; i < s.length(); ++i)

return (Data[i]) ? ToAlpha(i) :

if (Data[i]) } return NULL; // (char)0;

return Data[Code(e)];

inline bool IsIn(char e) { if (IsAlpha(e)) return 0;

inline int Card() const {return Data.count();}

z.Data |= y.Data; return z;

inline void Reset() { Data.reset(); } inline void operator =(const Set & y) { Data = y.Data; } inline void operator =(const string s) { Data.reset(); } inline char operator[](int i) const { if (i >= 0 && i < __SETSIZE) { NULL; } inline bool Empty() const {return Data.none();} } inline bool Has(char e) {return IsIn(e);} inline void Ins(char e) { if (IsAlpha(e)) Data.set(Code(e)); } inline void Del(char e) { if (IsAlpha(e)) Data.reset(Code(e)); } inline void Add(char e) {Ins(e);} Set operator +(const Set &y) const { Set z(*this); }

37

inline void operator +=(const Set &y) {

}

z.Data &= y.Data; return z;

inline void operator *=(const Set &y) {

}

z.Data[i] = 1;

for (int i = 0; i < __SETSIZE; ++i) if (Data[i] && (!y.Data[i])) return z;

inline void operator -=(const Set &y) {

}

return Data == y.Data;

inline bool operator ==(const Set & y) const { }

return Data != y.Data;

inline bool operator !=(const Set & y) const { }

inline friend bool operator <=(const Set & x, const

return false;

}

inline friend bool operator >=(const Set & x, const

return y <= x;

friend bool operator <(const Set & x, const Set &

*this = *this + y; Set operator *(const Set &y) const { Set z(*this); } *this = *this * y; Set operator -(const Set &y) const { Set z; } *this = *this - y; Set & y) { for (int i = 0; i < __SETSIZE; ++i) if (x.Data[i] && (!y.Data[i])) return true; Set & y) { } y) { return((x <= y) && (x != y)); }

38

inline friend bool operator >(const Set & x, const

return y < x;

}

if (s.Empty()) {

os << ToAlpha(i);

return;

cout << "{}"; }

cout << ToAlpha(i);

Set & y) { } friend ostream & operator <<(ostream & os, const Set & s) { os << "{}"; return os; for (int i = 0; i < __SETSIZE; ++i) { if (s.Data[i]) } return os; } inline void Print(string msg = "") { cout << msg; if (Empty()) { for (int i = 0; i < __SETSIZE; ++i) { if (Data[i]) } } };

void TestSet() {

cout << x[i];

if (y[i] != NULL) cout << y[i];

Set x, y; x = "AB"; y = "BDE"; cout << "\n x = " << x; cout << "\n y = " << y; cout << "\n x >= y ? " << (x >= y); cout << endl; for (int i = 0; i < 26; ++i) { } cout << endl; for (int i = 0; i < 26; ++i) { } cout << endl; for (int i = 0; i < 26; ++i) { }

cout << z[i];

}

39

40

TestSet(); cout << "\n T H E E N D .";

return 0;

Main() {

} Kết quả thực hiện

Màn hình

3.3 Thiết kế lớp lược đồ quan hệ RSC

3.3.1 Các thuôc tính của lớp lược đồ quan hệ RSC

Set Attr;

int FDNum;

FD * F;

int Cap;

Set Key;

Cú pháp

Ý nghĩa: Khai báo các thuộc tính, phụ thuộc hàm

3.3.2 Các phương thức của lớp lược đồ quan hề RSC

Tạo tử (constructor)

inline RSC() {Reset();}

inline RSC(const RSC &r) {

Reset(); Copy(r);

Cú pháp

} Hủy tử (destructor)

41

if (F != NULL) { delete [] F; F = NULL;

}

~RSC() { }

Cú pháp

Ý nghĩa: Xóa và thu hồi vùng nhớ đã cấp phát cho lớp lược đồ quan hề RSC

Cấp phát vùng chứa tên phần tử của lớp lược đồ quan hệ RSC

inline void Renew()

Cú pháp

Ý nghĩa: Cấp phát vùng nhớ đủ chứa size phần tử cho tập nền. Vùng nhớ này

để lưu trữ danh sách (tên) các phần tử của tập nền.

Trả về vùng chứa phần tử của lớp lược đồ quan hệ RSC

void Reset() { FDNum = 0; Cap = 0; F = NULL; Attr.Reset(); Key.Reset(); } Ý nghĩa: Gán độ thuộc 0 cho mọi phần tử của lớp lược đồ quan hệ RSC

Cú pháp

Toán tử gán

void Copy(const RSC & r) {

F = NULL;

for(int i = 0; i < FDNum; ++i)

F[i] = r.F[i];

Attr = r.Attr; FDNum = r.FDNum; // so PTH Cap = r.Cap; // Capacity Key = r.Key;

delete [] F; if (r.F == NULL) else {

F = new FD[Cap]; }

Cú pháp

42

}

Mở rộng vùng chứa lớp lược đồ quan hệ RSC

g[i] = F[i];

int newCap = Cap + __UNIT; FD *g = new FD[newCap]; for(int i = 0; i < FDNum; ++i) Cap = newCap; delete [] F; F = g;

void Extend() { } Ý nghĩa: Mở rộng vùng chứa lớp lược đồ quan hệ RSC

Cú pháp

Chèn mới

Cap = __UNIT; F = new FD[Cap]; F[0].Put(ls,rs); FDNum = 1; Attr = F[0].GetLR(); return;

if (F == NULL) { } if (FDNum == Cap) Extend(); F[FDNum].Put(ls,rs); ++FDNum; Attr += (ls + rs);

void Ins(const Set & ls, const Set & rs) { } void Ins(string ls, string rs) {Ins(Set(ls), Set(rs));}

Cú pháp

Set Closure(const Set & x, int k = -1) { bitset<1000> mark; // danh dau cac FD da dung Set y = x; int used = 0; while(true) {

used = 0; for (int i = 0; i < FDNum; ++i) {

if (i == k) continue; if (mark[i] == 0) { if (F[i].GetLS() <= y) {

Cú pháp

y += F[i].GetRS(); mark[i] = 1; ++used;

}

} } if (used == 0) break;

43

} return y; } Ý nghĩa: Tạo phụ thuộc hàm của lược đồ quan hệ RSC

k.Ins(c);

k.Del(c); if (!(Closure(k).Has(c))) }

Set FindKey() { Set k = Attr; for (char c = 'A'; c <= 'Z'; ++c) { if (k.Has(c)) { } return k; } inline Set SetKey() { Key = FindKey(); return Key; } inline void NewKey(const Set &k) { Key = k; } inline void NewKey(const string s) { Key = Set(s); } Ý nghĩa: Tìm khóa cho lược đồ quan hệ RSC

Cú pháp

Ví dụ:

Cho lược đồ quan hệ VẬN CHUYỂN (số_vận_đơn, kho_hàng, nơi_đến,

khoảng_cách)

Ta mã hóa đặt: số_vận_đơn = A, kho_hàng = B, nơi_đến = C, khoảng_cách =

D. Số thuộc tính U=ABCD

44

Với các tập phụ thuộc hàm: số_vận_chuyển xác định kho_hàng, nơi_đến,

khoảng_cách. Kho_hàng, nơi_đến xác định khoảng_cách.

F={A BCD, BC D}

Mở file”K.txt” rồi ghi vào file, ta thực hiện tìm khóa K của lược đồ quan hệ VẬN

CHUYỂN. Cuối cùng ta ghi vào output tổng số lượng khóa của lược đồ quan hệ

VẬN CHUYỂN.

Muốn tìm khóa của LĐQH:

Cho LĐQH p = (U,F). Tập thuộc tính K  U được gọi là khoá của LĐ p nếu

(i) K + = U

(ii)  A  K: (K  {A})+  U

Hai điều kiện trên tương đương với

(i') K  U

(ii')  A  K: (K  {A}) ! U

Nếu K thoả điều kiện (i) thì K được gọi là một siêu khoá.

Thuộc tính A  U được gọi là thuộc tính khoá (nguyên thuỷ hoặc cơ sở)

nếu A có trong một khoá nào đấy. A được gọi là thuộc tính không khoá (phi

nguyên thuỷ hoặc thứ cấp) nếu A không có trong bất kỳ khoá nào. Cho LĐQH

(U,F), ta kí hiệu UK là tập các thuộc tính khóa và Uo là tập các thuộc tính không

khóa.

*******************************************

Chương trình

#include #include #include using namespace std; const int __SETSIZE = 26; const int __UNIT = 16; typedef bitset<__SETSIZE> BS; class RSC {

protected:

*******************************************

Set Attr; // Attribute Set int FDNum; // number of functional dependencies FD * F; // functional dependencies int Cap; // Capacity Set Key; void Reset() { FDNum = 0; Cap = 0; F = NULL; Attr.Reset(); Key.Reset(); }

k.Del(c); if (!(Closure(k).Has(c)))

k.Ins(c);

if (k.Has(c)) { }

Set k = Attr; for (char c = 'A'; c <= 'Z'; ++c) { } return k;

Key = FindKey(); return Key;

Key = k;

}

Key = Set(s);

}

if (!(x <= Attr)) return false; if (Key <= x) return true; return Attr <= Closure(x);

}

return IsSuperkey(Set(s));

}

45

Set FindKey() { } inline Set SetKey() { } inline void NewKey(const Set &k) { inline void NewKey(const string s) { inline bool IsSuperkey(const Set &x) { inline bool IsSuperkey(const string s) { bool IsKey(const Set &x) {

k.Del(c); if (Closure(k).IsIn(c)) return false; k.Ins(c);

if (k.IsIn(c)) { }

if (!IsSuperkey(x)) return false; Set k = x; for (char c ='A'; c <= 'Z'; ++c) { } return true;

}

return IsKey(Set(s));

}

}

TestRSC(); cout << "\n T H E E N D ."; return 0;

46

inline bool IsKey(const string s) { void TestRSC() { RSC r; r.Read("K.txt"); r.Show("\n r: "); cout << "\n Key : " << r.GetKey(); main() { }

Kết quả ra màn hình

47

Nội dung file “K.txt”

Ví dụ: Chương trình DemoSC.cpp thực hiện các thao tác như sau: Cho một lược

đồ quan hê ĐƠN HÀNG (số_đơn, mã_KH, tên_KH, địa_chỉ_KH, ngày_đặt,

48

mã_hàng, tên_hàng, đơn_vị, mô_tả, số_lượng). Ta mã hóa đặt: số_đơn = A,

mã_KH = B, tên_KH = C, địa_chỉ_KH =D, ngày_đặt = E, mã_hàng = F,

tên_hàng = G, đơn_vị =H, mô_tả =I, số_lượng = J

Số thuộc tính U=ABCDEFGHIJ

Tập phụ thuộc hàm xác định: mã_KH xác định tên_KH, địa_chỉ_KH; mã_hàng

xác định tên_hàng, đơn_vị, mô_tả; số_đơn xác định mã_KH, ngày_đặt,

mã_hàng. Ta viết tắt như sau F={B  CD; F GHI; AF J; A BEF}. Mở

file “K.txt” rồi ghi vào file, ta hiển thị số tập thuộc tính, tìm khóa K của lược đồ

quan hệ ĐƠN HÀNG. Tìm tập phụ thuộc hàm của AB và tập phụ thuộc F, kiểm

tra E có phải là khóa của lược đồ quan hệ không. Cuối cùng ta ghi vào output

file của lược đồ quan hệ ĐƠN HÀNG.

Chương trình

DemoSC.cpp

*************************************************/ #include #include #include using namespace std; const int __SETSIZE = 26; const int __UNIT = 16; typedef bitset<__SETSIZE> BS; class RSC {

Set Attr; // Attribute Set int FDNum; // number of functional dependencies FD * F; // functional dependencies int Cap; // Capacity Set Key; void Reset() { FDNum = 0; Cap = 0; F = NULL; Attr.Reset(); Key.Reset(); }

protected:

/*******************************************

Copy(r);

inline RSC() {Reset();} inline RSC(const RSC &r) { Reset(); }

delete [] F; F = NULL;

if (F != NULL) { }

~RSC() { }

delete [] F;

Reset(); if (F != NULL) F = NULL;

public: inline void Renew() { } // Renew private:

F = NULL;

F = new FD[Cap]; for(int i = 0; i < FDNum; ++i)

F[i] = r.F[i];

Attr = r.Attr; // Tap thuoc tinh

FDNum = r.FDNum; // so PTH Cap = r.Cap; // Capacity Key = r.Key; delete [] F; if (r.F == NULL) else { }

inline int GetFDNum() const {return FDNum;} inline Set GetKey() const {return Key;}

49

int newCap = Cap + __UNIT; FD *g = new FD[newCap];

void Extend() {

void Copy(const RSC & r) { } public: inline void operator =(const RSC & r) {Copy(r);}

g[i] = F[i];

for(int i = 0; i < FDNum; ++i) Cap = newCap; delete [] F; F = g;

if (F == NULL) {

Cap = __UNIT; F = new FD[Cap]; F[0].Put(ls,rs); FDNum = 1; Attr = F[0].GetLR(); return;

} if (FDNum == Cap) Extend(); F[FDNum].Put(ls,rs); ++FDNum; Attr += (ls + rs);

} void Ins(const Set & ls, const Set & rs) { } void Ins(string ls, string rs) {Ins(Set(ls),

if (F[k].GetLS() == F[i].GetLS()) { F[k].AddRS(F[i].GetRS()); --j; break;

if (F[i].GetRS().Empty()) continue; ++j; F[j] = F[i]; for (int k = 0; k < j; ++k) { } }

int j = -1; int k; for (int i = 0; i < FDNum; ++i) { } FDNum = j+1; Attr.Reset(); for (int i = 0; i < FDNum; ++i) { }

Attr += F[i].GetLR();

void Norm() { }

Set Closure(const Set & x, int k = -1) {

50

Set(rs));}

y += F[i].GetRS(); mark[i] = 1; ++used;

if (F[i].GetLS() <= y) { }

if (i == k) continue; if (mark[i] == 0) { }

used = 0; for (int i = 0; i < FDNum; ++i) { } if (used == 0) break;

bitset<1000> mark; // danh dau cac FD da dung Set y = x; int used = 0; while(true) { } return y;

return Closure(Set(s),k);

k.Del(c); if (!(Closure(k).Has(c)))

k.Ins(c);

if (k.Has(c)) { }

Set k = Attr; for (char c = 'A'; c <= 'Z'; ++c) { } return k;

Key = k;

Key = Set(s);

} inline Set Closure(const string s, int k = -1) { } Set FindKey() { } inline Set SetKey() { Key = FindKey(); return Key; } inline void NewKey(const Set &k) { } inline void NewKey(const string s) { } inline bool IsSuperkey(const Set &x) {

51

if (!(x <= Attr)) return false; if (Key <= x) return true; return Attr <= Closure(x);

} inline bool IsSuperkey(const string s) {

return IsSuperkey(Set(s));

k.Del(c); if (Closure(k).IsIn(c)) return false; k.Ins(c);

if (k.IsIn(c)) { }

if (!IsSuperkey(x)) return false; Set k = x; for (char c ='A'; c <= 'Z'; ++c) { } return true;

return IsKey(Set(s));

return (Closure(g.GetLS(),k) >= g.GetRS());

return Derive(FD(ls,rs),k);

F[i] = F[FDNum-1];

if (FDNum-1 > i) { } --FDNum;

for(int i = FDNum-1; i >= 0; --i) { }

if (Derive(F[i],i)) { }

} bool IsKey(const Set &x) { } inline bool IsKey(const string s) { } bool Derive(const FD & g, int k = -1) { } bool Derive(string ls, string rs, int k = -1) { } // Derive void NonRedundant() { } void Read(const char * fn) {

ifstream f(fn); if (f.fail()) {

52

cerr << "\n Unable open in file " << fn; return;

rs += s[i];

if (IsAlpha(s[i]))

getline(f,s); cout << "\n " << s; if (s[0] == '.') break; // Left Side ls = ""; for (i = 0; s[i] != '-'; ++i) { if (IsAlpha(s[i])) ls += s[i]; } rs = ""; for (i = i+1; i < s.length(); ++i) { } Ins(ls,rs); // New FD ls -> rs

} Reset(); cout << "\n Reading ... "; string s; string ls, rs; int i; while(true) { } f.close(); Norm(); Show("\n Read: "); NonRedundant(); SetKey();

if (!IsSuperkey(F[i].GetLS())) return false;

for (int i = 0; i < FDNum; ++i) { } return true;

} inline bool IsBCNF() { }

void Print(string msg = "") {

cout << "\n " << i << ". "; F[i].Print();

}

53

cout << msg; Attr.Print("\n Attribute Set: "); Key.Print("\n Key: "); cout << "\n Functional Dependencies: "; for (int i = 0; i < FDNum; ++i) { }

os << s.Attr;

os << "\n Attribute Set: ";

os << "\n " << i << ". " << s.F[i];

return os;

cout << msg; cout << "\n Cap: " << Cap; cout << "\n Number of FDs: " << FDNum; Print();

void Show(string msg = "") { }

void TestRSC() { RSC r; r.Read("K.txt"); r.Show("\n r: "); cout << "\n Key : " << r.GetKey(); cout << "\n AB? " << r.Closure("AB");

cout << "\n E is a key? " << r.IsKey("ED");

}

TestRSC(); cout << "\n T H E E N D ."; return 0;

54

friend ostream & operator <<(ostream & os, const RSC & s) { os << "\n Functional Dependencies: "; for (int i = 0; i < s.FDNum; ++i) } }; cout << "\n F? " << r.Closure("F"); main() { }

55

Kết quả thực hiện

Màn hình

56

Nội dung file “K.txt”

Ví dụ: Chương trình Demo.cpp thực hiện các thao tác như sau: Cho một lược đồ

quan hê PHIEUMUONSACH (Maphieu, tenDG, Ngaymuon, Ngaytra, Masach,

Tensach). Ta mã hóa đặt: maphieu = A, tenDG = B, ngaymuon = C, ngaytra =D,

masach = E, tensach = F. Số thuộc tính U=ABCDEF

Tập phụ thuộc hàm xác định: maphieu xác định tenDG, ngaymuon, ngaytra;

masach xác định tensach. Ta viết tắt như sau F={A  BCD; E F). Mở file

“K.txt” rồi ghi vào file, ta hiển thị số tập thuộc tính, tìm khóa K của lược đồ

quan hệ PHIEUMUONSACH . Tìm khóa của lược đồ quan hệ, tìm tập phụ thuộc

hàm của A và kiểm tra D có phải là khóa của lược đồ quan hệ không. Cuối cùng

ta ghi vào output file của lược đồ quan hệ PHIEUMUONSACH.

57

Chương trình

Demo.cpp

Set Attr; // Attribute Set int FDNum; // number of functional dependencies FD * F; // functional dependencies int Cap; // Capacity Set Key; void Reset() { FDNum = 0; Cap = 0; F = NULL; Attr.Reset(); Key.Reset(); }

Copy(r);

inline RSC() {Reset();} inline RSC(const RSC &r) { Reset(); }

if (F != NULL) { }

delete [] F; F = NULL;

~RSC() { }

*************************************************/ #include #include #include using namespace std; const int __SETSIZE = 26; const int __UNIT = 16; typedef bitset<__SETSIZE> BS; class RSC {

protected: public: inline void Renew() {

Reset(); if (F != NULL)

delete [] F;

/*******************************************

F = NULL;

} // Renew private:

F = NULL;

F[i] = r.F[i];

F = new FD[Cap]; for(int i = 0; i < FDNum; ++i)

FDNum = r.FDNum; // so PTH Cap = r.Cap; // Capacity Key = r.Key; delete [] F; if (r.F == NULL) else { }

Attr = r.Attr; // Tap thuoc tinh

inline int GetFDNum() const {return FDNum;} inline Set GetKey() const {return Key;}

g[i] = F[i];

int newCap = Cap + __UNIT; FD *g = new FD[newCap]; for(int i = 0; i < FDNum; ++i) Cap = newCap; delete [] F; F = g;

Cap = __UNIT; F = new FD[Cap]; F[0].Put(ls,rs); FDNum = 1; Attr = F[0].GetLR(); return;

if (F == NULL) {

58

void Extend() { } void Ins(const Set & ls, const Set & rs) {

} if (FDNum == Cap) Extend(); F[FDNum].Put(ls,rs);

void Copy(const RSC & r) { } public: inline void operator =(const RSC & r) {Copy(r);}

++FDNum; Attr += (ls + rs);

} void Ins(string ls, string rs) {Ins(Set(ls),

if (F[k].GetLS() == F[i].GetLS()) { F[k].AddRS(F[i].GetRS()); --j; break;

if (F[i].GetRS().Empty()) continue; ++j; F[j] = F[i]; for (int k = 0; k < j; ++k) { } }

int j = -1; int k; for (int i = 0; i < FDNum; ++i) { } FDNum = j+1; Attr.Reset(); for (int i = 0; i < FDNum; ++i) { }

Attr += F[i].GetLR();

void Norm() { }

y += F[i].GetRS(); mark[i] = 1; ++used;

if (F[i].GetLS() <= y) { }

if (i == k) continue; if (mark[i] == 0) { }

used = 0; for (int i = 0; i < FDNum; ++i) { } if (used == 0) break;

bitset<1000> mark; // danh dau cac FD da dung Set y = x; int used = 0; while(true) { } return y;

Set Closure(const Set & x, int k = -1) { } inline Set Closure(const string s, int k = -1) {

59

Set(rs));}

return Closure(Set(s),k);

k.Ins(c);

k.Del(c); if (!(Closure(k).Has(c)))

if (k.Has(c)) { }

Set k = Attr; for (char c = 'A'; c <= 'Z'; ++c) { } return k;

Key = k;

Key = Set(s);

if (!(x <= Attr)) return false; if (Key <= x) return true; return Attr <= Closure(x);

} Set FindKey() { } inline Set SetKey() { Key = FindKey(); return Key; } inline void NewKey(const Set &k) { } inline void NewKey(const string s) { } inline bool IsSuperkey(const Set &x) { } inline bool IsSuperkey(const string s) {

return IsSuperkey(Set(s));

k.Del(c); if (Closure(k).IsIn(c)) return false; k.Ins(c);

} bool IsKey(const Set &x) {

if (!IsSuperkey(x)) return false; Set k = x; for (char c ='A'; c <= 'Z'; ++c) {

if (k.IsIn(c)) { }

60

} return true;

return IsKey(Set(s));

return (Closure(g.GetLS(),k) >= g.GetRS());

return Derive(FD(ls,rs),k);

F[i] = F[FDNum-1];

if (FDNum-1 > i) { } --FDNum;

if (Derive(F[i],i)) { }

for(int i = FDNum-1; i >= 0; --i) { }

cerr << "\n Unable open in file " << fn; return;

} inline bool IsKey(const string s) { } bool Derive(const FD & g, int k = -1) { } bool Derive(string ls, string rs, int k = -1) { } // Derive void NonRedundant() { } void Read(const char * fn) {

ifstream f(fn); if (f.fail()) { } Reset(); cout << "\n Reading ... "; string s; string ls, rs; int i; while(true) {

getline(f,s); cout << "\n " << s; if (s[0] == '.') break; // Left Side ls = ""; for (i = 0; s[i] != '-'; ++i) { if (IsAlpha(s[i])) ls += s[i]; } rs = ""; for (i = i+1; i < s.length(); ++i) {

if (IsAlpha(s[i]))

61

rs += s[i];

} Ins(ls,rs); // New FD ls -> rs

} f.close(); Norm(); Show("\n Read: "); NonRedundant(); SetKey();

if (!IsSuperkey(F[i].GetLS())) return false;

for (int i = 0; i < FDNum; ++i) { } return true;

} inline bool IsBCNF() { }

void Print(string msg = "") {

cout << "\n " << i << ". "; F[i].Print();

}

os << "\n Attribute Set: ";

os << s.Attr;

os << "\n " << i << ". " << s.F[i];

return os;

cout << msg; cout << "\n Cap: " << Cap; cout << "\n Number of FDs: " << FDNum; Print();

void Show(string msg = "") { }

62

void TestRSC() {

cout << msg; Attr.Print("\n Attribute Set: "); Key.Print("\n Key: "); cout << "\n Functional Dependencies: "; for (int i = 0; i < FDNum; ++i) { } friend ostream & operator <<(ostream & os, const RSC & s) { os << "\n Functional Dependencies: "; for (int i = 0; i < s.FDNum; ++i) } };

RSC r; r.Read("K.txt"); r.Show("\n r: "); cout << "\n Key : " << r.GetKey(); cout << "\n A? " << r.Closure("A");

}

TestRSC(); cout << "\n T H E E N D ."; return 0;

63

cout << "\n D is a key? " << r.IsKey("ED"); main() { }

Kết quả thực hiện

Màn hình

64

Nội dung file “K.txt”

65

KẾT LUẬN

Luận văn đã thu được những kết quả chính sau đây:

 Cài đặt các lớp đối tượng quản lý tập hợp, thuộc tính, phụ thuộc hàm,

khóa, dạng chuẩn 3NF.

 Thử nghiệm các lược đồ quan hệ.

 Việc nghiên cứu đề tài có thể đóng góp thêm một vài chức năng quản lý

ngữ nghĩa dữ liệu thông qua các dạng chuẩn.

 Luận văn thiết kế và cài đặt một hệ thống với các chức năng nhập xuất,

lưu trữ, tính bao đóng, khóa của các lược đồ quan hệ và các thuật toán

chuẩn hóa 3NF. Hệ thống có thể được sử dụng để khảo sát và kiểm định

các dạng chuẩn và các quy trình chuẩn hóa lược đồ quan hệ.

Hướng phát triển

 Theo gợi ý của các chuyên gia nghiên cứu về cơ sở dữ liệu, đề tài luận văn

có thể tiếp tục phát triển các thuật toán thiết kế cơ sở dữ liệu dạng phi chuẩn

theo tiếp cận cơ sở dữ liệu hướng đối tượng, trong đó các thuộc tính có thể

chứa các thuật tính khác.

66

TÀI LIỆU THAM KHẢO

[1] Nguyễn Xuân Huy (2003), Bài tập Cơ sở dữ liệu, NXB Thống Kê.

[2] Nguyễn Xuân Huy (2006), Các phụ thuộc logic trong cơ sở dữ liệu,

[3] Vũ Đức Thái (2016), Thiết kế cơ sở dữ liệu, NXB Đại học Thái

Viện Khoa học và Công nghệ Việt Nam.

[4] Vũ Đức Thi (1997), Cơ sở dữ liệu: Kiến thức và thực hành, NXB Thống

Nguyên.

[5] Lê Tiến Vương (2000), Nhập môn cơ sở dữ liệu quan hệ, NXB Thống

Kê.

[6] Date C. J., Nhập môn các hệ cơ sở dữ liệu, Những người dịch: Hồ Thuần, Nguyễn Quang Vinh, Nguyễn Xuân Huy, NXB Thống Kê, Hà Nội, Tập I (1985), Tập II (1986).

[7] Jaume Baixeries, Mehdi Kaytoue, Amedeo Napoli

Kê.

[8] Maier D. (1983), The Theory of Relational Database, Computer

(2014), Characterization of Database Dependencies with FCA and Pattern Structures, Procc. Third International Conference, Analysis of Images, Social Networks and Texts (AIST 2014), Yekaterinburg, Russia. Springer, 436, pp.3 - 14, 2014, Communications in Computer and Information Science.

[9] Ullman, J. (1982), Principles of Data-base and Knowledge-base Systems, Second Edition, Computer Science Press, Potomac. (Có bản dịch tiếng Việt của Trần Đức Quang.)

Science Press, Rockville.