Siêu đồ thị và lược đồ cơ sở dữ liệu phi chu trình luận án ts toán học 1 01 10

CÁC KÝ HIỆU VIẾT TẮT DÙNG TRONG LUẬN ÁN CHG (Connection HyperGraph ) CSDL CT FD (Functional Dependency ) FD-d6 thi (FD-graph ) FD-đường di (FD-path ) FR (Full Reduction ) FRs (Full Reducer ) JD (Join Dependency ) MVD (Multivalued Dependency ) PC (Pairwise Consistensy ) PCT RED(H) SDD (System for Distributed Databases ) TC (Total Consistensy ) Siêu đồ thị nối kết Cơ sở dữ liệu Chu trình Phụ thuộc hàm Đồ thị phụ thuộc hàm Đường đi phụ thuộc hàm Rút gọn đây đủ (của một quan hệ) Bộ rút gọn đầy đủ Phụ thuộc kết nối Phụ thuộc đa trị Tính nhất quán từng cap Phi chu trình Rút gọn của siêu đồ thị H Cơ sở dữ liệu phân tán Tính nhất quán toàn phần MỤC LỤC MỞ ĐẦU CHƯƠNG1_ KHÁI QUÁT VE CO SG DU LIEU V1 1.3 QUAN HE VA FD-ĐỒ THỊ KHAI QUAT VE MO HINH DU LIEU QUAN HE Led Quan hé i 72 Lược đồ quan hệ 113 Thể hiện ĐẠI SỐ QUAN HỆ 12.6 Phép chon Lif Phép kết nối 1.8 Phép kết nối tự nhiên 12.9 Phép nửa kết nối 1.10 Phép chia CAC PHU THUOC DU LIEU 1.1 Phu thuộc hàm và hệ tiên để Armstrong 1.2 Phụ thuộc đa trị 1.3 Phụ thuộc kết nối và phân tách lược đồ quan hệ 10 10 I1 11 1] 1] 12 12 13 13 14 19 15 15 20 23 1. KHOA VA CAC DANG CHUAN CUA LUGC BO QUAN HE 1.1 Khoá của lược đồ quan hệ 1.42 Các dạng chuẩn của lược đồ quan hệ 1.5 SỬ DỤNG ĐỒ THỊ ĐỂ NGHIÊN CỨU CAC PHU THUỘC HÀM 1.1 Khái quát về FD-đồ thị 15:2 Sự liên hệ giữa FD-đồ thị và khái niệm xác định trực tiếp 1.6 KẾT LUẬN CHƯƠNG †1 CHƯƠNG2_ SIÊU ĐỒ THỊ VÀ LƯỢC ĐỒ CƠ SỞ DỮ LIỆU PHI CHU TRÌNH 2.1 LƯỢC ĐỒ CƠ SỞ DỮ LIỆU PHI CHU TRÌNH 2:2 Quel Siêu đồ thị biểu diễn lược đồ CSDL phi chu trình 212 Siéu d6 thi Chordal va Conformal 2.3 Phép rút gọn Graham trên các siêu đồ thị 2.4 Một phụ thuộc kết nối tương đương với tập phụ thuộc đa trị 2.5 Tính nhất quán từng cặp kéo theo nhất quán toàn phần 2.6 Tồn tại một bộ rút gọn đầy đủ OAT Tồn tại một cây kết nối 2.8 Tính giao chạy trên lược đồ CSDL 2.9 Tồn tại một biểu thức kết nối đơn điệu 2.10 Tồn tại một biểu thức kết nối tuần tự đơn điệu 2.11 Định lý tương đương cho các lược đồ CSDL phi chu trìnl PHÂN LOẠI CÁC LỚP LƯỢC ĐỒ CSDL PHI CHU TRÌNH 2.2:1 Siêu đồ thị và lược đồ CSDL œ- phi chu trình 29 29 29 32 32 35 39 41 4 42 46 48 49 51 52 54 55 55 57 57 58 59 2.2:2 Siêu đồ thị và lược đồ CSDL ÿ- phi chu trình 60 22.3 Siêu đồ thị và lược đồ CSDL y- phi chu trinh 62 2.4 Siêu đồ thị và lược đồ CSDL BERCE - phi chu trình 64 2.25 Mối liên hệ giữa các lớp lược đồ CSDL phi chu trình 67 2.3 CÁC THUẬT TOÁN ĐOÁN NHẬN TÍNH PHI CHU TRÌNH 72 2.1 Thuật toán đoán nhận tính œ- phi chu trình 72 2.2 Thuật toán đoán nhận tính B- phi chu trinh 74 2. Thuật toán đoán nhận tính y- phi chu trình 77 2.4 Thuật toán đoán nhan tinh BERGE - phi chu trinh 82 2.4 THUẬT TOÁN PHÂN LOẠI LƯỢC ĐỒ CSDL PHI CHU TRINH 83 2.5 KẾT LUẬN CHƯƠNG 2 86 CHƯƠNG3_ SIÊU ĐỒ THỊ TRONG BIỂU DIỄN VÀ TỐI ƯU HOÁ CÂU HỎI 87 3.1 BIỂU DIỄN CÂU HỎI BẰNG SIÊU ĐỒ THỊ 87 3.1 Xây dựng siêu đồ thị nối kết cho các biểu thức hỏi 88 3.12 Tối ưu hoá các biểu thức hỏi 90 3.2 TÍNH CHIẾU CỦA MOT KET NOI PHI CHU TRINH 94 3.2/1 Trình rút gọn day du cho lược đồ CSDL phi chu trình 94 3.2 Tìm cây kết nối cho lược đồ CSDL phi chu trình 102 3.3 Thuật toán tính chiếu của một kết nối phi chu trình 108 3.2 KET LUẬN CHƯƠNG 3 113 KET LUAN 114 CAC CONG TRINH CUA TÁC GIẢ LIEN QUAN ĐẾN LUẬN ÁN 116 TÀI LIỆU THAM KHẢO 117 Từ 1970 tới nay, mô hình cơ sở dữ liệu (CSDL) quan hệ do Codd E.F đề xuất đã thu được những thành tựu hết sức to lớn cả về phương diện lý thuyết cũng như thực hành, và mô hình quan hệ đã trở thành một trong những mô hình đữ liệu có cơ sở lý thuyết được xây dựng vững chắc nhất. Trừ mô hình hướng đối tượng là một mô hình hoàn toàn mới, các mô hình CSDL logic (CSDL suy diễn) và các mô hình CSDL phân tán đều được xây dựng với sự hỗ trợ của mô hình quan hệ.

Tuy cũng còn có một vài hạn chế, nhưng cho đến nay chưa có một mô hình CSDL nào được sử dụng rộng rãi trong các hệ quản trị CSDL như mô hình quan hệ. Xu hướng chung của các nhà nghiên cứu là vẫn muốn giữ lại mô hình quan hệ, nghiên cứu phát triển những tính chất tốt của nó trong việc thiết kế và khai thác các CSDL trên mô hình này. Ngay từ những năm 80 của thế kỷ trước, nhiều nhà nghiên cứu đã tập trung nghiên cứu một lớp lược đồ CSDL đặc biệt của mô hình quan hệ, đó là lớp lược đồ CSDL phi chu trình. Lớp lược đồ này có nhiều tính chất mong đợi (desirable) và lý thú được nhiều nhà nghiên cứu quan tâm.

Đối với các lược đồ CSDL, nếu chúng có chu trình thì việc quản lý, khai thác và cập nhật các CSDL trên các lược đồ này là cực kỳ khó khăn và tốn kém, các vấn đề về dư thừa dữ liệu và dị thường trong cập nhật là rất khó giải quyết, nhưng với các lược đồ CSDL phi chu trình thì mọi vấn đề lại trở nên thuận lợi hơn, chẳng hạn khi đó hầu hết các thuật toán tối ưu các câu truy vấn CSDL là đa thức, vấn đề dư thừa dữ liệu là kiểm soát được, v. Nếu xem một lược đồ CSDL là một tập các lược đồ quan hệ được xác định trên một tập vũ trụ các thuộc tính nào đó thì việc biểu diễn một lược đồ CSDL dưới dạng một siêu đồ thị với tập đỉnh là tập các thuộc tính, còn các siêu cạnh chính là các lược đồ quan hệ, là một cách biểu diễn rất tự nhiên và có thể sử dụng, mở rộng các kết quả của lý thuyết đồ thị để nghiên cứu các tính chất của lược đồ CSDL. Chẳng hạn ta hãy xem xét một lược đồ CSDL quản lý cung ứng vật tư của một doanh nghiệp: VAT_TU(NGUOIL_CC, DU_AN, H_HOA, GIA, NGAY_CC). Gia sử các danh mục (thuộc tính) được quản lý theo các nhóm, tức là ta có các lược đồ quan hệ sau: R, = { NGUOI_CC, DU_AN, NGAY_CC }, R, = { NGUOI_CC, H_HOA, GIA}, R, = { NGUOI_CC, H_HOA, DU_AN}.

Một cách tự nhiên, ta thường thể hiện các nhóm danh mục lên giấy để xem xét sự liên hệ giữa chúng, khi đó ta sẽ có một siêu đồ thị với tập đỉnh là tập các thuộc tính, còn các siêu cạnh chính là các lược đồ quan hệ. Siêu đồ thị của lược đồ CSDL VAT TU Việc biểu diễn các lược đồ CSDL dưới dạng siêu đồ thị như vậy đã làm cho việc nghiên cứu các lược đồ CSDL trở nên đơn giản, các mối liên kết giữa các lược đồ quan hệ được hình thức hoá đã trở nên sáng sủa và rõ ràng hơn. Đúng như Claude Berge đã khẳng định trong lời nói đầu cho cuốn sách của minh “Graphs and Hypergraphs” [16], rằng việc phát biểu các bài toán tổ hợp theo ngôn ngữ của siêu đồ thị thường đưa tới các kết quả đơn giản thật bất ngờ". Và như vậy, siêu đồ thị có thể được dùng để tổng quát hoá nhiều bài toán liên quan tới các lược đồ CSDL, và nhiều bài toán tổ hợp khác [4ó6, 47].

Như vậy, một hướng nghiên cứu mới là dùng công cụ siêu đồ thị để nghiên cứu các lược đồ CSDL đã được đặt ra và Namibar [44], từ cuối những năm 70, là một trong những nhà nghiên cứu đầu tiên đưa ra ý tưởng phát biểu các bài toán của lược đồ CSDL theo các thuật ngữ của siêu đồ thị. Dãn đầu trong lĩnh vực nghiên cứu này là những tên tuổi nổi tiếng nhu J. Tarjan, và nhiều nhà nghiên cứu khác. Fagin, Mendelzon và Ullman [26] đã đưa ra một phỏng đoán rằng mọi tình huống hợp lý của thế giới thực đều có thể được mô hình hoá bởi một lược đồ CSDL gồm một phụ thuộc kết nối đầy đủ và một tập phụ thuộc hàm, và trong thực tế cũng khó có thể tìm được một tình huống nào không đúng với phỏng đoán trên.

Trong [15] các tác giả cũng chỉ ra rằng khi siêu đồ thị của phụ thuộc két néi 1a phi chu trinh (acyclic) thì từ một phụ thuộc kết nối còn có thể suy dẫn ra một tập phụ thuộc đa trị. Như vậy, có thể thấy việc nghiên cứu các phụ thuộc kết nối có tầm quan trọng đặc biệt trong việc thiết kế lược đồ CSDL. Xuất phát từ các nghiên cứu về phụ thuộc kết nối dẫn đến yêu cầu sử dụng các siêu đồ thị để mô tả các lược đồ quan hệ và các điều kiện ràng buộc trên các lược đồ này. Lần đầu tiên khái niệm về các lược đồ CSDL phi chu trình xuất hiện trong các công trình nghiên cứu về phép nửa kết nối (semi-Jjoin) và về sự so sánh fính nhất quán từng cặp (PC-pairwise consistency) với tính nhất quán toàn phần (TC- total consistency).

Các phép nửa kết nối được sử dụng rộng rãi trong các giải thuật xử lý câu hỏi phân tán cho SDD-I, một hệ CSDL phân tán được phát triển bởi Rothnie, Bernstein và những người khác [48]. Graham [30] đã định nghĩa một lớp rộng các lược đồ CSDL mà với chúng PC kéo theo TC. Tuy nhiên, lớp của Graham chỉ là một tập con thực sự của các lược đồ CSDL phi chu trình. Bernstein và Chiu [17] là những người đầu tiên liên kết các cây kết nối (join trees) với các bộ rút gọn đây đủ (full reducers).

Tuy nhiên các tác giả này chỉ xem xét các kết nối trên một thuộc tính chung. Bernstein và Goodman [18, 19] đã mở rộng lý thuyết cho các phép nửa kết nối trên nhiều thuộc tính chung. Từ bài toán xác định xem khi nào một CSDL là phép chiếu của một quan hệ vạn nang (universal relation) da lam nẩy sinh mối quan tâm về sự nhất quán từng cặp và sự nhất quán toàn phần. Honeyman, Ladner và Yannakakis [34] đã chứng minh rằng trong trường hợp tổng quát, bài toán quyết định tính nhất quán toàn phần (TC) là NP-đây đủ.

Honeyman [35] đã thấy được mối liên kết giữa PC kéo theo TC và sự tồn tại của các bộ rút gọn đầy đủ, tuy nhiên, chứng minh của tác giả về sự tương đương lại có sự saI sót.