tailieunhanh - Về thuật toán 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. 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ũng Tạp chí KHOA HỌC & CÔNG NGHỆ 58(10): 41 - 44 VỀ 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à Nam TÓM TẮT Lý thuyết thiết kế cơ sở dữ liệu (CSDL) đóng vai trò quan trọng trong công nghệ thông tin. Để 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ệc xá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á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. 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. Key words: Relational schema, key, functional dependency, database. * 1. MỞ ĐẦU Bài báo giả thiết rằng bạn đọc đã làm quen với các khái niệm cơ bản của cơ sở dữ liệu quan 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ác khoá 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ụng theo 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ập thuộc tính X Í U. Tập K Í U được gọi là khóa củ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ọn tự nhiên, trong đó các vế trái của mọi PTH khác nhau đôi một và mọi vế phải và trái của mọi PTH là rời nhau. Trong [1] chỉ ra rằng có thể đưa mọi tập PTH về dạng thu gọn .
đang nạp các trang xem trước
