trungkienairvn
New Member
Download miễn phí Luận văn Phân tích các dạng chuẩn hoá dữ liệu trong mô hình quan hệ và một số thuật toán
Trong phần này chúng ta sẽ khảo sát một số phép toán sử lý bảng ( Tệp dữ liệu ). Chúng tạo nên ngôn ngữ xử lý dữ liệu. Ngôn ngữ xử lý dữ liệu là một ngôn ngữ quan trọng trong hệ quản trị cơ sở dữ liệu ngững hệ quản trị Cơ sở dữ liệu này là những công cụ sắc bén cho chúng ta trong quá trình xử lý, đặc biệt là xử lý thông tin trong các hệ thông tin quản lý như: SQL for Windows, Orcale, IBM DB2, Foxpro, Access,.
Ngôn ngữ xử lý dữ liệu đều dựa trên mô hình dữ liệu quan hệ. Trong đó hạt nhân chủ yếu là tệp dữ liệu (bảng). Chúng ta sẽ khảo sát những phép toán xử lý tệp dữ liệu cơ bản nhất của cái nằm trong ngôn ngữ xử lý dữ liệu này. Các phép toán này được đề xuất bởi người sáng lập ra mô hình dữ liệu quan hệ.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ủa nó .A2: Giả sử rằng quan hệ r thoả X®Y.
Tồn tại hai bộ t,u sao cho t[XZ] = u[XZ] mà t[YZ] = u[YZ]. Vì rằng t[Z] = u[Z] nên để có t[YZ] # u[YZ] thì t[Y] # u[Y]. Nhưng vì t[X] = u[X]nên t[Y] # u[Y] là trái với giả thiết X®Y. Với t[YZ] = u[YZ].
A3: Cho X®Y và Y®Z đúng trên quan hệ r . Giả sử tồn tại hai bộ t và u Î 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à trái với giả thiết X ®Y.
Do vậy t[Z] = u[Z]. Suy ra X ®Z đúng trên quan hệ r.
Bổ đề 2:
a. Luật hợp: nếu X ®Y và X ®Z thì X ®YZ .
b. Luật tựa bắc cầu: nếu X ®Y và WY ®Z thì XW ®Z.
c. Luật tách: nếu X ®Y và Z Í Y thì X ®Z .
Chứng minh:
a. Từ X ®Y dùng luật tăng trưởng, thêm X ta có X ®XY .
khi X ®Z, dùng luật tăng trưởng thêm Y ta có XY ®YZ
Và cuối cùng dùng luật bắc cầu suy ra cho X ®XY và XY ®ZX có X®YZ.
b. Từ X ®Y dùng luật tăng trưởng thêm W có WX ®WY . Dùng luật bắc cầu cho WX ®WY và WY ®Z suy ra WX ®Z .
c. Vì Z Í Y nên X ®Z ( theo luật phản xạ )
Dùng luật bắc cầu cho X ®Y và Y ®Z có X ®Z.
Một hệ quả quan trọng của luật tách và luật hợp là nếu X ®Y suy ra X®Ai với mọi A i Î Y.
Để dễ dàng chứng minh cho tính đầy đủ của hệ tiên đề Amstrong, ở đây đưa thêm khái niệm bao đóng của tập các thuộc tính của tập các phụ thuộc hàm. Gọi F là tập các phụ thuộc hàm trên tập thuộc tính R, X Í R. X+ là bao đóng của X đối với F được định nghĩa như sau:
X+ = {A \ X ®A ÎF+ }
Nói cụ thể X+ là tập tất cả các thuộc tính A mà phụ thuộc hàm X®A có thể được suy diễn logíc từ F nhờ hệ tiên đề Amstrong.
Bổ đề 3:
X ®Y suy diễn từ hệ tiên đề Amstrong khi và chỉ khi Y Í X+
Chứng minh:
Giả sử Y = A1,A2,,...,An với A1,A2,,...,An là các thuộc tính và Y Í X+.
Từ định nghĩa X+ có X®Ai , áp dụng hệ tiên đề Amstrong cho mỗi i có X®Ai, Ai ÎY, nhờ luật tách. Từ đó suy ra Y Í X+ .
Định lý 1:
Hệ tiên đề Amstrong là đúng và đầy đủ.
Chứng minh:
Tính đúng đắn của hệ tiên đề đã được chứng minh qua bổ đề 1.ở đây chỉ cần chứng minh tính đầy đủ tức là nếu X®Y không thoả trên r thì X®Y không thể suy diễn từ F.
Gọi F là tập các phụ thuộc hàm trên tập thuộc tính R. Giả sử rằng X®Y là không thể suy dẫn được từ hệ tiên đề. Xét quan hệ r gồm hai tập sau: 11...1 11...1
11...1 00...0
Các thuộc tính thuộc X+ Các thuộc tính còn lại
Trước hết cần chỉ ra rằng tất cả các phụ thuộc hàm thuộc F đều thoả r. Thật vậy, giả sử (V®W) ÎF nhưng không thoả trên r. Do đó V Í X+ , hay hai bộ của r sẽ không bằng nhau ít nhất trên một thuộc tính của V. Như vậy W không thể là tập con của X+ hay V ® W thoả trên r .
Gọi A Î W nhưng A không thuộc X+. Vì XV Î X+, X®V suy ra từ bổ đề 3 .( X®V Î F ) do vậy, nhờ luật bắc cầu suy ra X®A, nhưng do A không thuộc X+ như giả thiết, do vậy là mâu thuẫn. Từ đó kết luận rằng mỗi (V®W) Î F đề thoả trên r .
Bây giờ cần chứng minh rằng X®Y không thoả trên r. Giả sử rằng X®Y là thoả trên r. Như trên có X Í X+ và suy ra Y Í X+, nếu không hai bộ là bằng nhau trên X nhưng không bằng nhau trên Y. Theo bổ đề 3 thì X®Y có thể suy ra được từ hệ tiên đề, điều đó là hoàn toàn mâu thuẫn. Do vậy X®Y không thể đúng trên r. Đến đây có thể kết luận rằng: Nếu X®Y không suy dẫn được từ hệ tiên đề Amstrong thì X®Y không suy dẫn logíc được từ F. Hệ tiên đề đầy đủ.
II.1.4. Phủ của các tập phụ thuộc hàm
Cho tập phụ thuộc hàm F, hãy thay thế F bằng phụ thuộc G sao cho G vẫn đảm bảo đúng chức năng của F. Khi đó ta gọi G là phủ của tập phụ thuộc hàm F.
Bổ đề 4:
Mỗi ttập phụ thuộc hàm F đều được phủ bằng tập các phụ thuộc hàm G sao cho G mà vế phải các phụ thuộc hàm đó bao gồm không quá một thuộc tính .
Chứng minh:
Gọi G là tập các phụ thuộc hàm X®A sao cho với X®Y thuộc F thì A Î Y . Từ X®Y suy ra X®A (theo luật tách)
Do vậy G Í F+ .
Ngược lại, có F Í G+ vì nếu Y = A1,...,An thì X®Y được suy ra
X®A1,. . . , X®An nhờ luật hợp .
Để có thể phục vụ quá trình thiết kế lược đồ cơ sở dữ liệu, sau đây sẽ đưa ra một số khái niệm.
Gọi các tập phụ thuộc hàm F là tối thiểu nếu :
a/ Mỗi vế phải của một phụ thuộc hàm F chỉ có một thuộc tính .
b/ Không tồn tại một phụ thuộc hàm X®A thuộc F mà
F+ = (F - { X®A}) +
c/ Không tồn tại một phụ thuộc hàm X®A thuộc F và một tập con Z của X mà : F+ = (F - { X®A} È { Z®A } ) +.
Thực vậy điều kiện b/ bảo đảm cho tập F không có phụ thuộc hàm nào là dư thừa và diều kiện c/ đảm bảo không có một thuộc tính nào tham gia phía trái của phụ thuộc hàm là dư thừa. Vế phải của phụ thuộc hàm ở điều kiện a/ chỉ có một thuộc tính bảo đảm chắc chắn không có một thuộc tính nào trên vế phải là dư thừa .
II.1.5. Định nghĩa sơ đồ quan hệ
Cho trước R = { a1, a2,..., an }
A,B Î R, đặt A® B là một phụ thuộc hàm.
Khi đó S là một sơ đồ quan hệ nếu:
S = trong đó F =
F gồm t phụ thuộc hàm thì tập ấy gọi là sơ đồ quan hệ. t phụ thuộc hàm này do người thiết kế đặt ra, dựa trên cơ sở nội dung của các cột a1,a2,..,an.
Sơ đồ quan hệ đó là đầu biểu ( cấu trúc tệp ) cộng với các ràng buộc logíc (các phụ thuộc hàm ) do người thiết kế đề xuất ra ,các phụ thuộc hàm này làm nhiệm vụ không chỉ phân tích mối quan hệ lôgíc mà còn kiểm tra tính đúng đắn của dữ liệu nữa.
II.1.6. Định nghĩa khoá
Cho trước r = {h1,h2,...,hm} là tệp dữ liệu trên tập thuộc tính R = { a1, a2,..., an}.
Khi đó A Í R được gọi là khoá của tệp dữ liệu r nếu A®R.sao cho bất kỳ hai bộ khác nhau t1,t2 Î r luôn thoả mãn
t1(A) ¹ t2(A)
- A là khoá tối tiểu nếu :
A®R
Không tồn tại A’ sao cho A’ Ì A(A’ tập con thực sự của A)
mà A’ ® R
Khoá cho sơ đồ quan hệ: Cho trước s = là sơ đồ quan hệ .Trong đó F = .
Khi đó :
A Í R được gọi là khoá của s nếu A®RÎF+.
A là k hoá tối tiểu của s nếu :
- A®RÎF+
- Không tồn tại A’ sao cho A’ Ì A sao cho A’®RÎF+
Khoá đây chính là hình ảnh của cột mã số hay cột số thứ tự trong Tệp dữ liệu nào đó .
Ví dụ: Quan hệ Hàng_hoá được cho như sau:
MSMH
Tên hàng
Số lượng
10101
10102
10111
Xi măng
Thép
Tấm lợp
2000
1500
1000
Trong ví dụ này biểu diễn quan hệ Hàng_hoá, trong đó MSMH là khoá. Mỗi giá trị MSMH đều xác định duy nhất một loạI mặt hàng trong quan hệ Hàng_hoá. II.1.7. Định nghĩa bao đóng
Cho trước S = là sơ đồ quan hệ với R = {a1,a2,...,an} là tập hữu hạn các thuộc tính. Trong đó F = . Và A Í R. Khi đó bao đóng của A trong S là A+ .
Trong đó :
A+ = {a : a Î R và A®{a}ÎF+ }
Cho r = {h1,h2,...,hm} là tệp dữ liệu trên tập thuộc tính R = {a1,a2,...,an}, AÎ R.
A+r = {a : a Î R và Ar®{a}}
A+r được gọi là bao đóng của A trong r.
Nếu A là một tập bất kỳ ( tập cột bất kỳ ) thì A+ là tập hợp tất cả những cột mà phụ thuộc hàm vào A trong sơ đồ quan hệ S, chúng ta có A+r là tập hợp tất cả các cột mà phụ thuộc hàm vào {a} trong tệp dữ liệu r. Dễ thấy rằng theo hệ tiên đề của Amstrong thì.
A Í A+
A Í A+r
Trên cơ sở địmh nghĩa này chúng ta có các kết quả sau :
Giả sử S = là sơ đồ quan hệ .
A®B Î F B Í A+
Cho r = {h1,h2,...hm }là tệp dữ liệu trên R = {a1,a2,...,an} .
ta có A®B (B phụ thuộc hàm r vào A) B Í A+r
Kết quả này nói lên rằng một tập B nào đó mà phụ thu