Tiến Sĩ Một số phụ thuộc dữ liệu trong cơ sở dữ liệu dạng khối

Luận án tiến sĩ năm 2011
Đề tài: Một số phụ thuộc dữ liệu trong cơ sở dữ liệu dạng khối

mục lục
Trang
Danh mục các ký hiệu và chữ viết tắt 7
Danh mục bảng biểu và hình vẽ .8
Lời mở đầu 9
Chương 1: Mô hình cơ sở dữ liệu quan hệ .13
1.1. Các khái niệm cơ bản .13
1.1.1. Thuộc tính và miền thuộc tính 13
1.1.2. Quan hệ, lược đồ quan hệ .13
1.1.3. Khoá của quan hệ .14
1.2. Các phéptoán đại sốquan hệ .15
1.2.1. Phép hợp .15
1.2.2. Phép giao .15
1.2.3. Phép trừ .16
1.2.4. Tích đề các .16
1.2.5. Phép chiếu 17
1.2.6. Phép chọn 17
1.2.7. Phép kết nối 18
1.2.8. Phép chia 20
1.3. Phụ thuộc hàm 20
1.3.1. Các tính chất của phụ thuộc hàm 21
1.3.2. Hệ tiên đề Armstrong và phép suy dẫn .21
1.4. Bao đóng .22
1.4.1. Bao đóng của tập phụ thuộc hàm 22
1.4.2. Bao đóng của tập thuộc tính 22
1.4.3. Bài toán thành viên và thuật toán tìm
5
bao đóng của tập thuộc tính 22
1.5. Khóa của lược đồ quan hệ .24
1.6. Phủ của tập phụ thuộc hàm 26
1.7. Phủ tối thiểu của tập phụ thuộchàm 26
1.7.1. Phụ thuộc hàm có vế trái dưthừa 26
1.7.2. Tập phụ thuộc hàm có vế phải gồm 1 thuộc tính .27
1.7.3. Tập phụ thuộc hàm không dưthừa .27
1.7.4. Tập phụ thuộc hàm tối thiểu 28
(Phủ tối thiểu của tập phụ thuộchàm)
1.8. Các dạng chuẩn của lược đồ quan hệ 28
1.9. Phụ thuộc đa trị 30
1.9.1. Định nghĩa phụ thuộc đa trị 30
1.9.2. Các tính chất của phụ thuộc đa trị 31
1.10. Kết luận chương 1 32
Chương 2 : Mô hình cơ sở dữ liệudạng khối 33
2.1. Khối, lược đồ khối 33
2.2. Lát cắt .34
2.3. Khoá của khối .35
2.4. Đại số quan hệ trên khối .37
2.4.1. Phép hợp 37
2.4.2. Phép giao .37
2.4.3. Phép trừ 37
2.4.4. TíchĐề Các 38
2.4.5. TíchĐề Các theo tập chỉ số .38
2.4.6. Phép chiếu 38
2.4.7. Phép chọn 39
2.4.8. Phép kết nối .39
6
2.4.9. Phép chia .40
2.5. Phụ thuộc hàm 41
2.6. Bao đóng của tập thuộc tính chỉ số 43
2.7. Khoá của lược đồ khối R đối với
tập các phụ thuộc hàm F trên R 45
2. 8. Dạng chuẩn của khối .46
2.9. Phủ của tập phụ thuộc hàm .48
2.10. Kết luận chương 2 50
Chương 3: phụ thuộc đa trị, phụ thuộc đa trị xấp xỉ và
α-phụ thuộc hàm trong mô hình dữ liệu dạng khối 51
3.1. Phụ thuộc đa trị trong mô hình dữ liệu dạng khối .51
3.2. Các tính chất của Phụ thuộc đa trị .53
3.3. Phụ thuộc đa trị xấp xỉ trong mô hình dữ liệu dạng khối 61
3.4. Các tính chất của phụ thuộc đa trị xấp xỉ 63
3.5. α-Phụ thuộc hàm và α-bao đóng trong mô hình
dữ liệu dạng khối .71
3.5.1. Khái niệm xấp xỉ mức α .71
3.5.2. α-phụ thuộc hàm và α-bao đóng 73
3.6. Kết luận chương 3 .84
Phần kết luận .85
Danh mục công trình công bố của tác giả 87
Danh mục tài liệu tham khảo 88

Mở đầu
Để xây dựng được một hệ thống cơ sở dữ liệu tốt,người ta thường sử
dụng các mô hình dữ liệu thích hợp. Mỗi mô hình dữ liệu là một hệ hình thức
toán học gồm có hai phần:
1. Một hệ thống kí hiệuđể mô tả dữ liệu.
2. Một tập hợp các phéptoán thao tác trên dữliệu đó.
Từ trước đến nay đã có một số loại mô hình được sử dụng trong các hệ
thống cơ sở dữ liệu như: mô hình thực thể - liên kết, mô hình mạng, mô hình
phân cấp, mô hình hướng đối tượng, mô hình dữ liệu datalog và mô hình quan
hệ. Trong số các mô hình này thì mô hình quan hệlà một trong những mô
hình được nhiều nhà khoa học quan tâm nghiên cứu, khai thác ứng dụng vì nó
được xây dựng trên một cơ sởtoán học chặt chẽ [8], [15], [16], [20], [23],
[25]. Tuy nhiên, do các quan hệ có cấu trúc phẳng (tuyến tính) nên mô hình
này sẽ rất khó khăn khi biểu diễn các dữ liệu có tính chất động (phi tuyến).
Trong những năm gần đây, việc nghiên cứu nhằm mở rộng mô hình
quan hệ được nhiều nhà khoa học quan tâm. Theo hướng nghiên cứu này đã có
một số hướng mở rộng mô hình quan hệ được đề xuất nghiên cứu như: mô
hình dữ liệu đa chiều [2], [19], [26], [31]; khối dữ liệu [17], [27], [28],[33];
kho dữ liệu [22], [29], [32]; mô hình dữ liệu dạng khối [3], [4], [5], [6], [13],
Trong đó chúng tôi thấy ở mô hìnhdữ liệu dạng khối, các khối là khái
niệm cơ bản được mởrộng từ các quan hệ trong mô hình quan hệ, các khối
này có thể biểu diễn các dữ liệu có tính chất động (biểu diễn các dữ liệu có
thuộc tính thay đổi theo thời gian).
Ví dụ: khichúng ta dùng các quan hệ trong mô hình quan hệ để tạo cơ
sở dữ liệu trong chương trình quản lý lương của các cán bộ trong một cơ quan
thì mỗi khi cập nhật lương mới cho cán bộ được tăng lương nó sẽ làm mất dữ
liệu lương cũ trước đó. Do đó, khi đến kỳ hạn xét tăng lương cho các cán bộ
10
thì việc tìm kiếm các cán bộ đến kỳ hạn tăng lương cũng gặp không ít khó
khăn (bởi vì sẽ phải tìmkiếm các cán bộ đã được tăng lương trong thờigian 2
hoặc 3 năm trước tuỳ theo cán bộ đó ở ngạch lương nào). Tuy nhiên, nếu quản
lý lương bằng khối trong mô hình khốithìnhờviệc sử dụng trục id (cộtchỉ số)
làm trục thời gian để lưu trữ dữ liệu lương theo từng thời điểm thì chúng ta sẽ
dễ dàng đưa ra các cán bộ đến kỳ hạn tăng lương trong cơ quan đó.
Một ví dụ khác nữa là khi muốn mô tả các dữ liệu của con tàu khi nó di
chuyển vào bến cảng (vận tốc,khoảng cách so vớibờ, độ sâu, ) thì nếu ta
dùng mô hình quan hệ sẽ rất khó khăn trong việc mô tả các dữ liệu trên của
con tàu khi nó dichuyển dần vào cảng. Nhưng nếu chúng ta dùng khối trong
mô hình khối sẽ dễ dàng biểu diễn được các dữ liệu trên của con tàu trong quá
trình chuyển động bằng cách sử dụng trục idlàm trục thời gian, mỗi bộ giá trị
của các thuộc tính chỉ số sẽ biểu diễn dữ liệu của con tàu tại một thời điểm
nhất định khi con tàu di chuyển vào bờ.
Tuy nhiên, trong mô hình khốinày cũng còn nhiều loại phụ thuộc dữ
liệu chưa được nghiên cứu. Vì vậy:
Mục tiêu của luận ánlà nghiên cứu các phụ thuộc dữ liệu trong cơ sở
dữ liệu, cụthể là tập trung vào nghiên cứu các phụ thuộcdữ liệu trong mô
hình dữ liệu dạng khối nhằm để góp phần bổ sung thêm vào lý thuyết thiết kế
mô hình dữ liệu dạng khối.
Luận án bao gồm:Lời mở đầu, ba chương nội dung, phần kết luận,
danh mục công trình công bố vàtài liệu tham khảo.
Chương 1trình bày các khái niệm cơ bản nhất về mô hình quan hệ.
Trình bày các phép toán đại số trênmô hình quan hệ, các vấn đề về phụ
thuộc hàm, khoá, bao đóng, phủ của tập phụ thuộc hàm cũng được giới thiệu
cùng các tính chất của chúng. Phần cuối chương trình bày khái niệm về phụ
thuộc đa trị trong mô hình quan hệ và các tính chất của chúng [1], [7], [8],
[15], [16], [20].
11
Các kết quả nghiên cứu của luận án được trình bày trong phần cuối
của chương 2 và toàn bộ chương 3.
Chương 2giớithiệu tổng quan về mô hình khối:định nghĩa khối, lược
đồ khối, lát cắt, phụ thuộc hàm, các dạng chuẩn trong khối. Các phép toán đại
số trên khối, khoá của khối, lược đồ khối cũng được giới thiệu [3], [4], [5],
[6], [13].
Cuối chương 2chúng tôi xây dựng các khái niệmmới về: phủ, phủ
không dưthừa, phủ tối thiểu của tập các phụ thuộc hàm trên lược đồ khối; các
tính chất về phủ, phủ tối thiểu của tập các phụ thuộc hàm; đưa ra điều kiện
cần và đủ của một phủ tối thiểu trong mô hình dạng khối [12].
Chương 3trình bày khái niệm mới về phụ thuộc đa trị trong mô hình
dữ liệu dạng khối; phát biểu và chứng minh các tính chất của phụ thuộc đa trị
trong mô hình dữ liệu khối; đưa ra tiêu chuẩn cần và đủ của một phụ thuộc đa
trị trong mô hình này [14].
Khái niệm mới tiếp theo được trình bày trong chương này là khái niệm
phụ thuộc đa trị xấp xỉ mức k giữa các thuộc tính chỉ số của một khối trong
mô hình dữ liệu dạng khối. Trên cơ sở đó, các tính chất của phụ thuộc đa trị
xấp xỉ, mối liên hệ giữa phụ thuộc đa trị xấp xỉ trên các lát cắt với các phụ
thuộc đa trị xấp xỉ trên khối đã được phát biểu và chứng minh [10].
Chương này cũng trình bày thêm một khái niệm mới nữa về α-phụ thuộc
hàm; phát biểu và chứng minh các tính chất của nó trong mô hình dữ liệu
dạng khối,điều kiện cần và đủ của α-phụ thuộc hàm theo quan điểm tập thô
cũng đượcphát biểu và chứng minh [9], [11].
Ngoài ra ở chương này còn phát biểu và chứng minh điều kiện cần và
đủ của một α-phụ thuộc hàm từ X vào Y khi mà X, Y có dạng riêng;xây
dựng khái niệm mới về α-bao đóng trong mô hình cơ sở dữ liệu dạng khối,
chứng minh điều kiện cần và đủ của tập α-bao đóng đối với tập các phụ thuộc
12
hàm F
α
h
; xây dựng thuật toán tính α-bao đóng cho các tập thuộc tính chỉ số
đối với F
α
h
[11].
Cuối cùng, phần kết luận nêu những kết quả luận án đã đạt được và
hướng phát triển tiếp theo của luận án.
13
∈
Chương 1: Mô hình cơ sở dữ liệu quan hệ
1. 1. Các khái niệm cơ bản
1.1.1. Thuộc tính và miền thuộc tính
Định nghĩa 1.1 [7], [8]
- Thuộc tính là đặc trưng của các quan hệ.
- Tập tất cả các giá trị có thể có của thuộc tính A
i
gọi là miền giá trị của
thuộc tính đó, ký hiệu: Dom(A
i
) hay viết tắt là .
i A D
Ví dụ 1.1:Nhanvien(MaNV, Hoten, NgSinh, Đchi)
Dom(MaNV) = {char(4)} ; Dom(Hoten) = {char(3)} ;
Dom(NgSinh) = {date} ; Dom(Đchi) = {‘HN’, ‘HP’, ‘VP’, }.
1.1.2. Quan hệ, lược đồ quan hệ
Định nghĩa 1.2[7], [8]
Cho U= {A1, A
2, ,An
} là một tập hữu hạn không rỗng các thuộc tính.
Mỗi thuộc tính Ai
(i=1,2, , n) có miền giá trị là . Khi đó r là một tập
i A D
Ai
D ∪
các bộ {h
AUi
1, h
2, ,hm} được gọi là quan hệ trên U với hj
(j=1, 2, , m) làmột
hàm: hj
: U →saocho hj(A
i
) ∈ (i=1, 2, , n).
i A D
Ta có thể xem một quan hệ nhưmột bảng, trong đó mỗi hàng (phần tử)
là một bộ và mỗi cột tương ứng với một thành phần gọi là thuộc tính.
Biểu diễn quan hệ r thành bảng nhưsau:

tài liệu tham khảo
Tiếng Việt
[1] Nguyễn Kim Anh (1997), Nguyên lí của các hệcơ sở dữ liệu, Nhà
xuất bản Đại học Quốc gia Hà Nội.
[2] Nguyễn Kim Anh (2002) “Đại số khốitrên các cơ sở dữ liệu đa
chiều”, Tạp chí Tin học và Điều khiển học, 18(2), tr. 149-154.
[3] Nguyễn Xuân Huy, Trịnh Đình Thắng (1997), “Mô hình cơ sở dữ liệu
dạng khối”, Kỷ yếu các báo cáo khoa học của Hội thảo mộtsố vấn
đề chọn lọc của Công nghệ Thông tin, Đại lải, 8/1997, tr. 14-19.
[4] Nguyễn Xuân Huy, Trịnh Đình Thắng (1998), “Mô hình cơsở dữ
liệu dạng khối”, Tạp chí Tin học và Điều khiển học, 14(3), tr. 52-60.
[5] Nguyễn Xuân Huy, Trịnh Đình Thắng (1998), “Một số kết quả về
khoá trong mô hình cơ sở dữ liệu dạng khối”, Kỷ yếu Hội thảo quốc
gia về Tin học ứng dụng, Quy Nhơn, 8/1998, tr. 36-41.
[6] Nguyễn Xuân Huy, Trịnh Đình Thắng (1999), “Một vài thuật toán cài
đặt các phép toán của đại số quan hệ trong mô hình dữ liệu dạng
khối”, Tạp chí Tin học và Điều khiển học, 15(3), tr. 8-17.
[7] Lê Văn Phùng (2010), Cơ sở dữ liệu quan hệ và Công nghệ phân tích
- Thiết kế, Nhà xuất bản Thông tin vàTruyền thông, Hà Nội.
[8] Vũ Đức Thi (1997), Cơ sở dữ liệu - Kiến thức và Thực hành, Nhà
xuất bản Thống kê, Hà Nội.
[9] Vũ Đức Thi - Trịnh Đình Vinh (2009), “ Phụ thuộc hàm xấp xỉ và
bao đóng xấp xỉ mức αtrong mô hình dữ liệu dạng khối”, Tạp chí
khoa học Journal of Science, trường ĐHSP Hà Nội 2, số 8 năm 2009,
tr. 127-133.
[10] Vũ Đức Thi - Trịnh Đình Vinh (2009), “ Phụ thuộc đa trị xấp xỉ trong
mô hình dữ liệu dạng khối”, Kỷ yếu Hội thảo Quốc gia “Một số vấn
89
đề chọn lọc của CNTT và TT”, Biên Hoà, 05-06/08/2009, tr.341-350.
[11] Vũ Đức Thi - Trịnh Đình Vinh (2010), “ α-Phụ thuộc hàm và α-
Bao đóng trong mô hình cơ sở dữ liệu dạng khối”, Tạp chí Tin học và
Điều khiểnhọc, 26(2), tr. 131-139.
[12] Trịnh Đình Vinh - Vũ Đức Thi (2010), “ Phủ của tập phụ thuộc hàm
và vấn đề tựa chuẩn hoá trong mô hình dữ liệu dạng khối”, Tạp chí
Tin học và Điều khiển học, 26(4), tr. 312-320.
[13] Trịnh Đình Thắng (2001), “Một số kết quả về bao đóng, khoá và phụ
thuộc hàm trong mô hình dữ liệu dạng khối”, Kỷ yếu Hội thảo Quốc
gia “Một số vấn đề chọn lọc của Công nghệ Thông tin”, Hải Phòng,
tr. 245-251.
[14] Trịnh Đình Thắng, Trịnh Đình Vinh(2008), “ Phụ thuộc đa trị trong
mô hình dữ liệu dạng khối”, Kỷ yếu Hội thảo Quốcgia “Một số vấn
đề chọn lọc của CNTT và TT”, Huế , 12-13/06/2008, tr. 321-328.
[15] Nguyễn Bá Tường (2003), Nhập môn Cơsở dữ liệu phân tán, Nhà
xuất bản Khoa học vàkỹ thuật, Hà Nội.
[16] Lê Tiến Vương (1997), Nhập môn Cơ sở dữ liệu quan hệ, Nhà xuất
bản Khoa học và kỹ thuật, Hà Nội.