ĐẠ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Ị DUNG
CÁC DẠNG BIỂU DIỄN KHÓA TRONG
LƯỢC ĐỒ QUAN HỆ LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Thái Nguyên – 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠ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Ị DUNG
KEY REPRESENTATIONS IN
RELATIONAL SCHEMATA
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
học tập, nghiên cứu để hoàn thành luận văn này.
Thái Nguyên, tháng 06 năm 2012
Học viên Nguyễn Thị Dung Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ii
LỜI CAM ĐOAN
Tôi xin cam đoan, luận văn là kết quả của tự bản thân tôi tìm hiểu, nghiên
cứu. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iii
MỤC LỤC
Trang
Lời cảm ơn i
Lời cam đoan ii
Mục lục iii
Danh mục các kí hiệu, chữ cái viết tắt v
Danh mục hình vẽ vi
MỞ ĐẦU 1
3.2.3 Bổ đề vế trái cực tiểu 42
3.2.4 Bổ đề các khóa sinh ra từ khóa của lược đồ 45
3.2.5 Bổ đề 48
3.3 Giới thiệu 50
3.4 Một số giao diện của chương trình 52
3.5 Các ví dụ 56
TÀI LIỆU THAM KHẢO 60
1. Kết luận 59
2. Kiến nghị 59
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
v
DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT
CSDL Cơ sở dữ liệu
LĐQH Lược đồ quan hệ
PTH Phụ thuộc hàm
FD Phụ thuộc hàm
Thuộc
Là con
Chứa
╞ Suy dẫn logic
├ Suy dẫn theo quan hệ
SAT(F) Là tập toàn thể các quan hệ trên U thỏa tập PTH
F
X
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1
MỞ ĐẦU
Cơ sở khoa học của luận văn
Cơ sở dữ liệu(CSDL) là một trong những lĩnh vực được tập trung nghiên
cứu và phát triển của công nghệ thông tin. Cùng với sự phát triển của công nghệ
thông tin, việc sử dụng các kiến thức về cơ sở dữ liệu ngày càng trở lên cần thiết.
Trong quản lý các cơ sở dữ liệu (CSDL), phụ thuộc dữ liệu được hiểu là những
mệnh đề mô tả các ràng buộc mà dữ liệu phải đáp ứng trong thực tế. Nhờ có
những mô tả phụ thuộc này mà hệ quản trị cơ sở dữ liệu có thể quản lý tốt được
chất lượng dữ liệu. Lý thuyết về các phụ thuộc dữ liệu đóng vai trò quan trọng
trong việc mô tả thế giới thực, phản ánh ngữ nghĩa dữ liệu trong cơ sở dữ liệu.
Phụ thuộc dữ liệu được Codd, tác giả của mô hình dữ liệu quan hệ đặt nền móng
từ những năm 70 với khái niệm phụ thuộc hàm. Sau đó một loạt tác giả khác tiếp
tục phát triển các dạng phụ thuộc bậc cao, phụ thuộc mờ cũng như xây dựng các
hệ tiên đề cho các lớp phụ thuộc - tức là đặt cơ sở lý thuyết về phụ thuộc dữ liệu.
Trong thực tế phụ thuộc dữ liệu nào cũng giới hạn ở việc so sánh hai bộ theo
đẳng thức, nghĩa là chỉ so sánh từng cặp trị tương ứng của hai bộ đó xem chúng
giống hay khác nhau. Ở đây từ kỹ thuật thu gọn các lược đồ quan hệ (LĐQH)
được gọi là phép dịch chuyển lược đồ quan hệ. Bản chất của kỹ thuật này là loại
bỏ khỏi LĐQH ban đầu một số thuộc tính không quan trọng theo nghĩa chúng
không làm ảnh hưởng đến kết quả tính toán các đối tượng đang được quan tâm
như bao đóng, khóa, phản khóa Chẳng hạn như nếu dịch chuyển LĐQH
a=(U,F) thu được LĐQH b=a/X(X
U) thì ta có khoá của LĐQH a sẽ được biểu
diễn như thế nào hay nếu ta có K=LM với L là vế trái cực tiểu của F thì M phải
3
3. Kết hợp chặt chẽ giữa lý thuyết và thực hành, sử dụng và phát triển các
phần mềm nói chung và các phần mềm toán học nói riêng để kiểm định
và thể hiện các kết quả lý thuyết.
Phạm vi nghiên cứu
Các kết quả thu được có thể vận dụng cho các quy trình thiết kế các cơ sở
dữ liệu quan hệ dùng tong các hệ thống thông tin, cụ thể là:
- Tính bao đóng của các tập thuộc tính
- Tìm khóa của LĐQH
- Thu gọn LĐQH
- Các dạng biểu diễn khóa của LĐQH
Cấu trúc của luận văn
Cấu trúc của luận văn gồm:
- Phần mở đầu
- Chương 1, 2 và 3
- Phần kết luận và đề nghị
- Tài liệu tham khảo
Nội dung chính của luận văn
Chương 1 giới thiệu các kiến thức cơ bản về CSDL, các định nghĩa về
quan hệ, thuộc tính, bộ. Phụ thuộc hàm cũng như thuật toán tính bao đóng của
các tập thuộc tính, tìm khóa của LĐQH.
Chương 2 trình bày một kỹ thuật thu gọn LĐQH hay còn gọi là phép dịch
chuyển LĐQH. Bản chất của kỹ thuật này là loại bỏ khỏi LĐQH ban đầu một số
thuộc tính không quan trọng theo nghĩa chúng không làm ảnh hưởng đến kết quả
tính toán các đối tượng đang được quan tâm như bao đóng, khóa, phản khóa Và
sau khi loại bỏ một số thuộc tính thì một số PTH sẽ được loại bỏ theo vì chúng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1
, A
2
, ,A
n
}
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 A
i
U (i=1,2, ,n) có một tập chứa ít nhất 2 phần tử dom(A
i
) được gọi là
miền giá trị của A
i
, gọi D là tập hợp các dom(A
i
) ( i = 1,2, ,n). Một quan hệ R
với các thuộc tính U, kí hiệu R(U) là một ánh xạ t: U
D sao cho với mỗi
A
i
U ta có t(A
i
)
dom(A
i
1
| X
2,
|
|X
m
với ý nghĩa M= X
1
X
2
X
m
và X
i
X
j
= Ø , 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, i
1
)
u,v
R: u.X = v.X
u.Y = v.Y
Cho quan hệ R(U) và tập PTH F trên tập thuộc tính U. Ta nói quan hệ R
thỏa tập PTH F, ký hiệu R(F), nếu R thỏa mọi PTH trong F
tức là R(F)
f
F: R(f)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8
1.3.2. Hệ tiên đề Armstrong
Cho quan hệ R(U). Giả sử X,Y,Z,W
U
F1. Tính phản xạ:
Nếu X
Y thì X
Y
+
thì X
Z
F
+
Chú ý: 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 thỏa trong mọi quan hệ.
1.3.3. Bao đóng của tập PTH
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à thỏa mãn các tính chất F1 – F3 của hệ tiên
đề Armstrong.
1.4. Bao đóng của tập thuộc tính
Cho tập hợ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 hợp các thuộc tính A
U mà PTH X
A có thể được suy diễn logic từ F nhờ hệ tiên đề Armstrong :
X
+
= {A
- Tập PTH F
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
Đánh giá độ phức tạp
X
+
Y
+Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10
5. (X
+
Y
+
) = (XY
+
)
+
= (XY)
+
6. X
Y
F
+
F
+
(f có là thành viên của F
+
) hay không.
X
Y
F
+
Y
X
+
Ý tưởng thuật toán : Kiểm tra X
Y
F
+
không?
- Tính X
+
- Kiểm tra Y
X
F
+
Method
IsMember: = (RS(f)
Closure (LS (f),F)
End IsMember.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11
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à khóa của LĐQH p
nếu:
i) K
+
= U
ii)
A
K: (K\{A})
+
U
K. Có thể thay kiểm tra (K\{A})
+
= U bằng kiểm tra A
(K\{A})
+
.
Algorithm Key
Function: Tìm một khóa của LĐQH
Fomat: Key (U,F)
Input: - Tập thuộc tính U
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12
- Tập PTH F
Output: Khóa K
U thỏa
(i) K
+
= U
(ii)
A
K : (K\{A})
+
BE
E
H
A
D
G
E
G
B
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13
}
Hãy tìm một khóa của p.
Dễ thấy, LĐQH p có khóa K = G, vì thỏa mãn hai điều kiện:
(i) K
+
= G
+
= ABCDEGH =U
(ii) G tối tiểu (theo nghĩa (K\{G})
+
AC
A
DE}
Tìm khóa của LĐQH đã cho ?
Ta thấy, LĐQH P có khóa K = A, vì thỏa mãn hai điều kiện :
(i) K
+
= A
+
= ABCD =U
(ii) A tối tiểu (theo nghĩa (K\{A})
+
U).
Mặt khác, tương tự như trên ta cũng thấy rằng LĐQH p còn khóa thứ 2, đó
là K = DE.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14
Để trả lời cho câu hỏi: Lược đồ có trên một khóa hay không, ta đi tìm giao
các khóa.
1.5.1. Cách tính giao các khóa
Những phần tử không xuất hiện ở vế phải thì nó có mặt ở mọi khóa, đó chính là
giao các khóa.
Vậy giao các khóa chính là những thuộc tính không xuất hiện ở vế phải.
Giả sử M là giao các khóa. Nếu m
+
Method
M : = U;
For each FD L
R in F do
M : = M \ (R\L) ;
Endfor;
Return M;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15
End KeyIntersec.
1.5.2. Thuật toán tìm 2 khóa của LĐQH
Bước 1: Tính giao các khóa
Bước 2: Lấy M
+
. Nếu M
+
= U
Lược đồ có 1 khóa M là duy nhất
M
+
U
Lược đồ có trên 1 khóa
Nếu không có khóa thứ 2: Ø
Method
M : = U;
For each attribute A in U \ K do
If A
(M\{A})
+
then
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Copyright: Tài liệu đại học ©