TÌM TẤT CẢ CÁC KHÓA CỦA LƯỢC ĐỒ QUAN HỆ

Bài báo phát triển thuật toán tìm tất cả các khoá của lược đồ quan hệ dựa trên kết quả của Lucchesi và Osborn <3> với những cải tiến như sau.

Bạn đang xem: Tìm tất cả các khóa của lược đồ quan hệ

Thứ nhất, giảm số lần duyệt các khóa xuống còn 1 cho mỗi khóa. Thứ hai, với số thuộc tính không nhiều, giới hạn đến 64, thuật toán tổ chức các tập thuộc tính dưới dạng số nguyên do đó tăng thêm tốc độ duyệt tìm.


*

Vũ Trí DũngTạp chí KHOA HỌC & CÔNG NGHỆ58(10): 41 - 44VỀ THUẬT TOÁN TÌM TẤT CẢ CÁC KHOÁ CỦA LƯỢC ĐỒ QUAN HỆVũ Trí Dũng*Trường trung cấp nghề Kinh tế - Kỹ thuật Hà NamTÓM TẮTLý thuyết thiết kế cơ sở dữ liệu (CSDL) đóng vai trò quan trọng trong công nghệ thôngtin. Để quản lý tốt được chất lượng dữ liệu và thiết kế một CSDL tốt, ta phải xác địnhđược dạng chuẩn và chuẩn hoá lược đồ quan hệ (LĐQH). Theo định nghĩa <1,2,4>, việcxác định dạng chuẩn của LĐQH (3NF, 2NF) với yếu tố tiên quyết là phải tìm được tất cảcác khoá của LĐQH, từ đó có thể chỉ ra các thuộc tính khoá, các thuộc tính không khoávà xác định được dạng chuẩn của LĐQH. Bài báo phát triển thuật toán tìm tất cả cáckhoá của lược đồ quan hệ dựa trên kết quả của Lucchesi và Osborn <3> với những cảitiến như sau. Thứ nhất, giảm số lần duyệt các khóa xuống còn 1 cho mỗi khóa. Thứ hai,với số thuộc tính không nhiều, giới hạn đến 64, thuật toán tổ chức các tập thuộc tínhdưới dạng số nguyên do đó tăng thêm tốc độ duyệt tìm.Key words: Relational schema, key, functional dependency, database.*1.

Xem thêm: Xã Hội Phong Kiến Ở Châu Âu Đã Được Hình Thành Như Thế Nào ?

MỞ ĐẦUBài báo giả thiết rằng bạn đọc đã làm quenvới các khái niệm cơ bản của cơ sở dữ liệuquan hệ <1,2,4>. Phần này chỉ nhắc lại một sốđịnh nghĩa, định lý và thuật toán liên quanđến việc phát triển thuật toán tìm tất cả cáckhoá của LĐQH. Các định nghĩa, định lý,thuật toán và kí hiệu trong bài báo sử dụngtheo tài liệu <1>.Các định nghĩa:Cho lược đồ quan hệ (LĐQH) p = (U,F), trongđó U là tập hữu hạn các thuộc tính, F là tập+phụ thuộc hàm (PTH) trên U. Tập X = {A ÎU+| X Î AÎF } được gọi là bao đóng của tậpthuộc tính X Í U. Tập K Í U được gọi là khóacủa LĐQH p nếu (i) K+ = U và (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á. Tập PTH trong bàiđược giả thiết là được cho dưới dạng thu gọntự nhiên, trong đó các vế trái của mọi PTHkhác nhau đôi một và mọi vế phải và trái củamọi PTH là rời nhau.

Xem thêm: Cách Đăng Ký 3G Sim Vietnamobile 20K 1 Tháng, Cách Đăng Ký 3G Vietnamobile 20K 1 Tháng

Trong <1> chỉ ra rằng cóthể đưa mọi tập PTH về dạng thu gọn tựnhiên với thời gian tuyến tính theo chiều dàidữ liệu vào, tức là theo n.m, trong đó n là sốlượng thuộc tính trong U và m là số lượngPTH trong F. Thuật toán tìm một khóa củaLĐQH, Key(V,F) xuất phát từ một siêu khóaV cho trước có độ phức tạp đa thức theochiều dài dữ liệu vào là O(n2m) <1>, trong đó*Vu Tri Dung, Tel: 0983035969,E-mail: vutridungvn