Về thuật toán tìm tất cả các khóa của lược đồ quan hệ

Vũ Trí Dũng Tạp chí KHOA HỌC & CÔNG NGHỆ 58(10): 41 - 44

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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 tự

nhiên với thời gian tuyến tính theo chiều dài

dữ 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ượng

PTH trong F. Thuật toán tìm một khóa của

LĐQH, Key(V,F) xuất phát từ một siêu khóa

V cho trước có độ phức tạp đa thức theo

chiều dài dữ liệu vào là O(n2m) [1], trong đó

* Vu Tri Dung, Tel: 0983035969,

E-mail: [email protected]

O(nm) là độ phức tạp của thuật toán tìm bao

đóng [4].

Các định lý

Cho LĐQH p = (U,F) với n thuộc tính trong U

và m PTH trong F

* Gọi UI là giao các khóa của p. Khi đó có thể

xác định giao các khóa bằng một thuật toán

tuyến tính theo mn qua công thức

U

L R F

U I U R L Æ Œ

= \ ( \ )

* Gọi UI là giao của các khóa trong p. Khi đó

p có một khóa duy nhất khi và chỉ khi UI

+

=U.

* Định lý Lucchesi – Osborn [3]

Cho LĐQH p = (U,F), biết v khóa của p là

{K1, K2,..., Kv}, khi đó p còn khóa nữa khi và

chỉ khi tồn tại một khoá KŒ {K1, K2,..., Kv} và

tồn tại một PTH LÆR Œ F thoả: L»(K\R)

không chứa bất kỳ khoá nào trong số khoá đã

tìm được.

2. VỀ THUẬT TOÁN TÌM TẤT CẢ CÁC

KHOÁ CỦA LĐQH

Liệt kê tất cả các khoá của LĐQH là bài toán

thuộc lớp NPC [1,3], có độ phức tạp hàm mũ.

Thông thường, để tìm được tất cả các khoá

của LĐQH, ta sử dụng phương pháp vét cạn

các khả năng có thể tồn tại khoá, đó là xét tất

cả các tập con của tập thuộc tính U.

Bài báo này đề xuất phương pháp dựa trên

định lý Lucchesi - Osborn tìm tất cả các khoá

của LĐQH với số lần duyệt tối thiểu.

Trong các thuật toán sử dụng các biến và các

kí hiệu như sau: