Nghiên cứu, so sánh các phương pháp phân rã, dịch chuyển sơ đồ quan hệ

LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "Nghiên cứu, so sánh các phương pháp phân rã, dịch chuyển sơ đồ quan hệ": http://123doc.vn/document/1040792-nghien-cuu-so-sanh-cac-phuong-phap-phan-ra-dich-chuyen-so-do-quan-he.htm

4
sẽ giảm (hay không còn) các thông tin bị dư thừa trong
các quan hệ mới.
Mục đích của phép phân rã đó là nhằm loại bỏ các
file dữ liệu dư thừa và loại bỏ các dị thường: không nhất
quán, dị thường khi thêm dòng, dị thường khi xóa dòng
của quan hệ, khi thực hiện phép cập nhật (sửa, thêm,
xóa).
Trong phép dịch chuyển sơ đồ quan hệ. Bản chất
của kỹ thuật này là loại bỏ khỏi sơ đồ quan hệ 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 quan tâm như bao đóng, khóa, Mặc dù sơ đồ quan
hệ thu được qua phép thu gọn không tương đương với sơ
đồ quan hệ ban đầu, nhưng ta có thể thu được các đối
tượng cần tìm bằng những phép toán đơn giản như loại
bỏ hoặc thêm một số thuộc tính. Điều lý thú là sau khi
loại bỏ một số thuộc tính thì một số phụ thuộc hàm sẽ
được loại bỏ theo, vì chúng trở thành các phụ thuộc hàm
tầm thường (có vế trái chứa về phải) hoặc mang thông tin
tiền định (đó là các phụ thuộc hàm dạng Ø→X).



5

i.2. Nội dung của đề tài, các vấn đề cần giải
quyết
Mục tiêu của luận văn là tìm hiểu kỹ thuật thu gọn
sơ đồ quan hệ dựa trên “phương pháp phân rã sơ đồ
quan hệ” và “phương pháp dịch chuyển sơ đồ quan
hệ”.
- Sử dụng một số thuật ngữ như dịch chuyển, phân
rã, chiếu của các sơ đồ quan hệ để làm sáng tỏ khái niệm
thu gọn sơ đồ quan hệ là nội dung chính của luận văn.
Vấn đề cần quan tâm là phân rã, dịch chuyển SĐQH
có đảm bảo tái thiết được sơ đồ quan hệ hay không, quá
trình phân rã, dịch chuyển có làm mất thông tin không?
Các đối tượng chúng ta sẽ phân rã, dịch chuyển là
các sơ đồ quan hệ W thông qua phép phân rã, dịch
chuyển sơ đồ quan hệ theo một tập thuộc tính U. Khảo
sát sự phụ thuộc của phép phân rã, dịch chuyển thông
qua các tính chất của tập thuộc tính U. Khảo sát hai dạng
biểu diễn khóa của lược đồ quan hệ qua phép phân rã,



6
dịch chuyển. Xây dựng một hệ trình minh họa mô phỏng
kết quả thực tế và đánh giá các kết quả lý thuyết.
i.3. Phương pháp nghiên cứu
1. Tiếp cận chủ yếu để giải quyết các vấn đề đặt ra
trong phạm vi đề tài là tiên đề hóa. Các hệ tiên đề được
xây dựng trên cơ sở một hệ suy dẫn hình thức với các
tính chất cơ bản về các đối tượng cơ sở và các mối liên
hệ giữa chúng. Cơ sở toán học của các hệ tiên đề là định
lý về tính xác đáng và đầy đủ cùng với các định lý về
điều kiện cần và đủ cho các hệ tiên đề tương đương.
2. Tiếp cận hình thức vận dụng chủ yếu các phương
pháp và các cấu trúc của toán học rời rạc (bao gồm cả
logic hình thức), kết hợp với các phương pháp đối sánh,
mô hình hóa, tối ưu và quy hoạch rời rạc.
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.
i.4. Phạm vi ứng dụng



7
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 dùng trong các hệ thống
thông tin, cụ thể là:
Bảo toàn phụ thuộc hàm, không mất mát thông tin,
loại bỏ dư thừa dữ liệu. Đây là các tiêu chuẩn cơ bản của
hệ thống thông tin. Với các CSDL lớn và phức tạp có
nhiều thuộc tính, chúng ta phải dùng các phương pháp
biến đổi SĐQH để đưa chúng về dạng tối ưu, đáp ứng
được các tiêu chuẩn trên.
Về lý thuyết, luận văn tập trung vào các kết quả sau
đây:
- Khái niệm cơ sở lý thuyết của mô hình quan hệ.
- Khái niệm về phép phân rã sơ đồ quan hệ.
- Khái niệm về phép dịch chuyển sơ đồ quan hệ.
- Phát biểu và chứng minh các phương pháp phân rã
dọc sơ đồ quan hệ, phân rã có nối không tổn thất, phân rã
bảo toàn phụ thuộc, phân rã thành các dạng chuyển
BCNF.
- Phát biểu và chứng minh công thức tính bao đóng
qua phép dịch chuyển lược đồ quan hệ,



8
- Phân tích thuật toán Chase kiểm tra việc phân rã
có nối không tổn thất không, kiểm tra phân rã có bảo
toàn phụ thuộc không, thuật toán phân rã thành dạng
chuẩn BCNF.
- Phân tích thuật toán dịch chuyển SĐQH,
Về thực hành luận văn sẽ cài đặt chương trình ứng
dụng nhằm mục đích mô phỏng kết quả nghiên cứu được
của học viên.

Nội dung :
Chương 1
CƠ SỞ LÝ THUYẾT CỦA MÔ HÌNH QUAN HỆ
Chương 1 Giới thiệu về mô hình dữ liệu quan hệ là
một mô hình được sử dụng rộng rãi trong đời sống xã hội
của mọi tổ chức, cơ quan, xí nghiệp bởi tính do tính trực
quan, kiến trúc đơn giản và có cơ sở toán học chặt chẽ
của nó. Mô hình quan hệ biểu thị dữ liệu trong một
CSDL như một tập các quan hệ, có thể coi như là một
bảng giá trị gồm các hàng và các cột. Mỗi hàng trong
bảng là một tập các giá trị có liên quan với nhau, các giá



9
trị này biểu thị một sự kiện tương ứng với một thực thể
hay một mối quan hệ trong thế giới thực. Trong chương
này chúng ta sẽ nêu một số khái niệm cơ bản về quan hệ
và cơ sở quan hệ.
1.1.Khái niệm về quan hệ
Cho U={A
1
,A
2
, ,A
n
} 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 A
i
có một miền giá
trị là D(A
i
).
1.2. Các phép toán đại số quan hệ.
Trên các quan hệ ta có thể thực hiện các phép toán tập
hợp như hợp, giao, hiệu, các phép toán đó người ta
thường gọi là các phép toán đại số quan hệ,
1.2.1. Phép hợp
1.2.1. Phép giao
1.2.3. Phép trừ
1.2.3. Phép chiếu
1.2.5. Tích Descartes
1.2.6. Phép chọn
1.2.7. Phép chia



10
1.2.8. Phép nối tự nhiên
1.2.9. Phép nối có điều kiện


1.3. Phụ thuộc hàm
Trong các bảng quan hệ, chúng ta thấy giữa các
thuộc tính của quan hệ có một số ràng buộc (phụ thuộc
dữ liệu) đóng vai trò quan trọng trong lý thuyết CSDL.
1.3.1. Định nghĩa phụ thuộc hàm
Cho lược đồ quan hệ U = {A
1
, A
2
, , A
n
}. Giả sử X, Y
là các tập con của U, tức là X, Y  U.
1.3.2. Các tính chất của phụ thuộc hàm
Tính phản xạ, tính bắc cầu, tính mở rộng hai vế, tính
tựa bắc cầu, tính mở rộng trái và thu hẹp phải, tính cộng
đầy đủ, tính tích lũy.
1.3.3. Hệ tiên đề Armstrong
Hệ 3 tính chất tính phản xạ, tính bắc cầu, tính mở
rộng 2 vế được gọi là hệ tiên đề Armstrong của lớp các
phụ thuộc hàm trên lược đồ U.




11
1.3.4.Tính tương đương của các tập phụ thuộc hàm
Gọi F và G là hai tập phụ thuộc hàm. Ta nói F và G
là tương đương nếu F
+
=G
+
. Ký hiệu F  G.
1.3.5. Các tập phụ thuộc hàm tối thiểu
Một tập phụ thuộc hàm là tối thiểu nếu nó thoả mãn các
điều kiện sau đây :
1. Mỗi vế phải của các phụ thuộc hàm F chỉ có một
thuộc tính.
2. Không tồn tại một phụ thuộc hàm X→A thuộc F
và tập con thực sự Z của X mà F
+
=(F-
{X→A}{Z→A})
+
.
3. Không tồn tại 1 phụ thuộc hàm X→A thuộc F mà
F
+
={F-{X→A}}
+

1.3.6. Bao đóng
Bao đóng F
+
của tập phụ thuộc hàm F, cho
lược đồ U = {A
1
, A
2
, A
n
}. F là tập phụ thuộc hàm trên U.
Định nghĩa: Bao đóng của tập phụ thuộc hàm F



12
Bao đóng của tập phụ thuộc hàm F ký hiệu F
+
là
tập tất cả các phụ thuộc hàm f suy dẫn được từ tập F dựa
vào các luật của hệ tiên đề Armstrong.
Vậy F
+
= {f: F  = f} với F = f là ký hiệu F suy
dẫn được f.
1.4. Khoá và khoá chính, khoá ngoại
Trong các thuộc tính phụ thuộc hàm có các thuộc
tính đóng vai trò “xác định” các thuộc tính khác như
“khóa”.
1.4.1.Định nghĩa : Khoá (key) tối tiểu
Tập thuộc tính K

U được gọi là khoá tối tiểu của
W = <U, F> nếu nó thoả mãn hai điều kiện:
(1) K
+
= U (hay K

U).
(2) B  K: (K-{B})
+
 U.
Vậy tập K  U được gọi là khóa tối tiểu của sơ đồ
quan hệ W = <U, F> nếu K là tập tối tiểu kéo theo U.
1.4.2.Định nghĩa : Khoá của quan hệ R.
K

U được gọi là khoá của R nếu:



13
1. Mọi cặp t
i
và t
j
khác nhau của R ta luôn có t
i
.K 
t
j
.K
2. K là tối thiểu.
1.4.3.Định nghĩa : Khoá chính-khoá ngoại
Khoá chính của quan hệ R là một khoá của R được
chọn làm khoá chính.
Khoá ngoại của quan hệ R là trường dữ liệu đóng
vai trò khoá chính trong quan hệ khác.
1.5. Các dạng chuẩn của sơ đồ quan hệ
Trong quản lý, xử lý các hệ cơ sở dữ liệu chúng ta
thường phải đưa CSDL về dạng đơn giản nhất, ít công
kềnh nhất, tốn ít bộ nhớ nhất, xử lý nhanh nhất và có tính
đặc thù nhất. Để thực hiện mục đích đó chúng ta phải tiến
hành chuẩn hóa các hệ CSDL.
1.5.1. Dạng chuẩn 1 – 1NF (First Normal Form)
1.5.2. Dạng chuẩn 2 – 2NF (Second Normal Form)
1.5.3 Dạng chuẩn 3 – 3NF (Third Normal Form)
1.5.4. Dạng chuẩn Boyce Codd – BCNF