Bài giảng Cơ sở dữ liệu nâng cao

Cơ sở dữ liệu nâng cao Phạm Thị Anh Lê – ĐH Sư phạm Hà nội Giới thiệu Lý thuyết CSDL quan hệ CSDL suy diễn CSDL phân tán CSDL hướng đối tượng Mở đầu Các hệ CSDL quan hệ đã thu được những thành tựu to lớn về cả phương diện lý thuyết và thực hành. Một số hạn chế của CSDL quan hệ: ngữ nghĩa của mô hình quan hệ chưa đủ phong phú, việc quản lý các dữ liệu động và phức tạp kém hiệu quả,... Một số hướng nghiên cứu mở rộng được đề xuất: CSDL suy diễn, CSDL hướng đối tượng, CSDL phân tán Chương I: Lý thuyết thiết kế các hệ CSDL quan hệ Quan hệ và lược đồ quan hệ Phụ thuộc hàm Khoá của lược đồ quan hệ Lý thuyết phân tách Lý thuyết chuẩn hoá Chương II: CSDL suy diễn(Deductive Database - DDB) Logic và CSDL suy diễn Ngôn ngữ luật Datalog (rule languages) Đánh giá và mô hình hoá các câu hỏi suy diễn Mở đầu CSDL cổ điển không có khả năng suy dẫn ra sự kiện mới, khả năng tiềm ẩn không được khai thác hết. Ví dụ: quan hệ cha-con không suy diễn được Hoa là cháu của ai. 1970-1980: có một trào lưu sôi nổi muốn đưa vào CSDL quan hệ những cơ chế suy diễn, những tri thức tổng quát Sự gặp gỡ của AI và CSDL Mở đầu Các hệ CSDL Có khả năng quản lý các khối lượng lớn DL Dữ liệu ngoại diên: các sự kiện Tính toàn vẹn, khôi phục, tối ưu hoá câu hỏi Được bảo trì bởi những nhà quản trị Cần những khả năng suy luận bên trong CSDL Có các khả năng suy luận Tri thức nội hàm: các luật Biểu diễn tri thức Được bảo trì bởi các chuyên gia Cần một hoàn thiện để quản lý các khối lượng lớn thông tin Các hệ chuyên gia CSDL suy diễn ? Mở đầu CSDL suy diễn: - bổ sung các khả năng suy diễn cho CSDL, CSDL chứa các sự kiện (intensional relations) và các luật để suy dẫn ra các sự kiện mới (extensional relations) CSDL là cơ sở tri thức - mở rộng việc truy vấn Datalog là một công cụ của DDB tương tự với Prolog có các sự kiện và các luật các luật định nghĩa – có khả năng đệ qui - views I.1 Logic và CSDL suy diễn Từ logic đến CSDL suy diễn Lý thuyết chứng minh Lý thuyết thể hiện Thế nào là CSDL suy diễn Vấn đề thông tin âm Chức năng và phương pháp luận của một CSDL suy diễn I.2 Các ngôn ngữ luật đối với các CSDL Cú pháp của Datalog Ngữ nghĩa của Datalog Mở rộng Datalog với: các hàm phép phủ định phép tập hợp phép cập nhật các điều kiện phi Horn I.3 Đánh giá và mô hình hoá các câu hỏi suy diễn Đánh giá dưới lên Đánh giá trên xuống Mô hình hoá các luật bằng đồ thị Cây và đồ thị quan hệ Cây VÀ/HOẶC và các đồ thị luật/đích Đánh giá các luật đệ quy Từ logic đến CSDL suy diễn Logic vị từ (tân từ) cấp một (first-order logic - FOL) là một ngôn ngữ hình thức diễn tả các quan hệ giữa các đối tượng và để suy diễn ra các quan hệ mới từ các quan hệ được xem là đúng Trong FOL, các công thức nguyên tố (atomic formulas) được diễn giải như các phát biểu về các quan hệ giữa các đối tượng. Từ logic đến CSDL suy diễn Ví dụ: x (Người(x)chết(x)) Mọi người đều phải chết x (Nữ(x)yêu(a, chị(x))  yêu(x)) Logic vị từ cấp một Vị từ và hằng: Xét các phát biểu « Mai là nữ Bình là nam Mai và Bình là vợ chồng” Trong FOL, các phát biểu nguyên tố được biểu diễn bởi các vị từ, với các hằng như các đối số: Nữ(mai) Nam(bình) Vợ_chồng(mai, bình) Kí hiệu hằng: a, b, c,... Kí hiệu vị từ: P, Q,... Logic vị từ cấp một Biến và lượng từ: Xét các phát biểu « Mọi người là nữ hoặc là nam” « Một người là nam thì sẽ không là nữ” Trong FOL, các vị từ có thể xem các biến như các đối số, mà giá trị của nó được giới hạn bởi các lượng từ x Nữ(x)  Nam(x) x Nữ(x)  Nam(x) Kí hiệu biến : x, y, z,... Kí hiệu lượng từ: ,  Suy diễn (tại sao ?) Mai không là nam Nam(mai) Logic vị từ cấp một Hàm Xét các phát biểu « Bố của một người là nam” Trong FOL, các đối tượng của miền có thể được biểu thị bởi các hàm áp dụng lên các đối tượng (đối tượng khác) x Nam(Bố (x)) Kí hiệu hàm : f(x1,...xn), g, h,... Logic vị từ cấp một Công thức được xây dựng: Trên bảng chữ: - hằng: a, b, c,... - biến: x, y, z,... - hàm: f(x1,...,xn), g, h,... - các ký tự tân từ: P, Q,... - các liên kết logic: , , , ,  - các lượng từ: ,  - dấu ngoặc Logic tân từ cấp một Công thức được xây dựng: Hạng thức (term): (i) Mọi biến và hằng (ii) Nếu f là hàm n-ngôi và t1,..., tn là các hạng thức thì f(t1, ..., tn) cũng là một hạng thức Công thức nguyên tố P(t1,...,tn) Logic tân từ cấp một Công thức được xây dựng: Công thức được thiết lập đúng đắn (wff – well-formed formula): (i) Mọi công thức nguyên tố (ii) Nếu f, g là các wff thì... (iii) Nếu f là wff thì tác động lượng từ vào f được công thức nguyên tố literal là một công thức nguyên tố hay phủ định của công thức nguyên tố công thức dương (không có ) Logic tân từ cấp một Biến tự do và biến giới hạn: x (R(y, z)  y (P(y, x)  R(y, z)) Các biến tô màu đỏ gọi là biến tự do, các biến còn lại là biến giới hạn Công thức đóng và mở Một công thức là đóng nếu nó không chứa biến tự do. Khi xây dựng các lý thuyết, người ta chỉ sử dụng các công thức đóng Logic tân từ cấp một Thể hiện (Interpretation) Cho D là một miền khác rỗng gán mỗi hằng một phần tử thuộc D gán cho mỗi hàm f n ngôi một ánh xạ DnD gán cho mỗi tân từ P n ngôi một ánh xạ Dn0, 1 Mô hình Cho W là tập hợp wff. Một mô hình là một thể hiện sao cho mọi công thức thuộc W đều nhận giá trị đúng. Logic tân từ cấp một Hệ quả logic của W Cho w là một wff, wW. Ta nói w là hệ quả logic của W nếu w nhận giá trị TRUE với mọi mô hình của W, Kí hiệu W╞ w Logic tân từ cấp một Hệ quả suy diễn của W Cho T là một lý thuyết cấp một {A1,...,An}(1) là hệ tiên đề {R1,...,Rm}(2) là tập qui tắc suy diễn W là tập các wff, w là một wff, wW. Ta nói w được suy diễn từ W nếu w được suy diễn từ W bằng cách sử dụng các tiên đề trong hệ(1) và các qui tắc suy diễn(2). Nói cách khác, có một dãy công thức thiết lập đúng đắn f1, f2, ..., ft (ftw), Kí hiệu W├ w Logic tân từ cấp một Cho một lý thuyết cấp một T Hệ qui tắc suy diễn gọi là đúng nếu x: W├ w kéo theo W╞ w Hệ qui tắc suy diễn được gọi là đủ nếu x: W╞ w kéo theo W├ w Logic tân từ cấp một Hợp nhất hai công thức Làm cho chúng giống hệt nhau bằng cách thay thế các biến trong một công thức bằng các hạng thức (hằng, biến khác, hàm) Không phải bao giờ cũng hợp nhất được Thuật toán hợp nhất Logic tân từ cấp một Hợp nhất hai công thức Ví dụ: P(a, b) và P(x, y) hợp nhất được x/a, y/b P(f(x),a) và P(f(f(a)),y) hợp nhất được x/f(a), y/a P(f(x),a) và P(f(f(x)),x) không hợp nhất được Logic tân từ cấp một Nguyên lý hợp giải (resolution principle): (c1) F1L1 (c2) F2 L2 sao cho L1 và L2 có thể hợp nhất với một phép thay thế biến hoặc hằng thích hợp Khi đó quá trình phép giải: Khử các vị từ đã được đồng nhất với nhau (1 có , 1 không có) và lấy tuyển các literal còn lại (sau khi áp dụng phép thế nói trên) (c3) F1sF2s được gọi là giải thức (resolvent) Modus Ponent chỉ là trường hợp đặc biệt Logic tân từ cấp một Nguyên lý hợp giải (resolution principle) Ví dụ: (c1) P(a,b,c)  Q(d,e) (c2) P(x,y,z)  R(x,y) s = {a/x, b/y, c/z} (c3) Q(d,e)  R(a,b) đây là công thức suy diễn được Nguyên lí giải chủ yếu được dùng để phản bác (Reputation proof) Để chứng minh W├w (W╞w), ta chứng minh hệ W{w} dăn tới câu rỗng. Từ đó suy ra w là chứng minh được. CSDL được nhìn dưới ánh sáng của logic Một CSDL có thể được xem như: Hoặc như thể hiện của một lý thuyết cấp một, trong đó các câu hỏi (và ràng buộc toàn vẹn) là các công thức được định giá trên thể hiện bằng cách sử dụng định nghĩa ngữ nghĩa của chân lý Hoặc như một lý thuyết cấp một, trong đó các câu hỏi và ràng buộc toàn vẹn được xem như các định lý phải chứng minh. CSDL là một thể hiện của lý thuyết cấp một Tại một thời điểm, 1 tập các quan hệ R1,...,Rm Rj tương ứng với một tân từ Pj Pj(e(j)1,...,e(j)n) đúng nếu (e(j)1,...,e(j)n)Rj sai nếu (e(j)1,...,e(j)n)Rj Trong ngữ cảnh CSDL thì lý thuyết cấp một tương ứng không có kí hiệu hàm. CSDL là một thể hiện của lý thuyết cấp một Công thức: câu hỏi công thức đóng công thức mở Cách tiếp cận này tỏ ra hạn chế khi xét tới các khái niệm: view các ràng buộc toàn vẹn CSDL là một thể hiện của lý thuyết cấp một Theo quan điểm mô hình Gọi DB là một thể hiện của một CSDL quan hệ DB gồm một tập các quan hệ R cho mỗi lược đồ quan hệ (LĐQH) R(A1,...,An) và một tập các ràng buộc toàn vẹn IC (Integrality Constraints) Gọi D là hợp của các miền của tất cả các thuộc tính xuất hiện trong các LĐQH Định nghĩa ngôn ngữ cấp một L bao gồm các ký hiệu tân từ n-ngôi R cho mỗi quan hệ n-ngôi trong DB và tập các hằng (một hằng cho một phần tử trong D) DB được xem như một thể hiện của các công thức của L CSDL là một thể hiện của lý thuyết cấp một Ngôn ngữ có thể được mở rộng để chứa các toán tử so sánh (>,, ... các liên kết logic v, ∧, ¬, , ⇔ Hạng thức: hằng hay biến Công thức nguyên tố: Literal dương P(t1, t2, ...tn) Công thức nguyên tố cá biệt (được làm cá biệt): công thức nguyên tố không chứa biến Datalog (cú pháp) Luật: biểu thức có dạng Q  P1 , P2 ,... , Pn Đầu luật Q là công thức nguyên tố (kết luận) thân luật P1 , P2 ,... , Pn là các tân từ (tiền đề hay điều kiện) mỗi Pi gọi là một đích con Luật được gọi là đệ qui nếu tân từ của đầu luật cũng xuất hiện trong thân luật Datalog (ví dụ về các luật) hằng: Hùng, Dũng, Mai, Thanh, .. các literal cá biệt còn gọi là các sự kiện: BO(Hùng, Dũng)  MẸ(Mai, Dũng)  .... Các luật khác: CHAMẸ(x,y)  BO(x,y) CHAMẸ(x,y)  MẸ(x,y) ONG(x,z)  BO(x,y), CHAMẸ(y,z) TOTIEN(x,y)  CHAMẸ(x,y) TOTIEN(x,z)  TOTIEN(x,y), CHAMẸ(y,z) ANHEMHO(x,y)  TOTIEN(z,x), TOTIEN(z,y) Datalog Một chương trình DATALOG là một tập các luật (thứ tự các luật không quan trọng} DATALOG cho phép người dùng phản ánh các luật và các sự kiện CSDL logic = CSDL cài đặt + CSDL tiềm ẩn (viết bằng DATALOG) Ngữ nghĩa của chương trình DATALOG Ngữ nghĩa của một chương trình DATALOG là cái mà chương trình đó tính được: Phương pháp khai báo/dựa trên việc tính mô hình của một chương trình logic Phương pháp thủ tục (từng bộ một)/ dựa trên phương pháp chứng minh bằng phương pháp giải và "phủ định bởi thất bại" Datalog Một mô hình của một chương trình DATALOG là một thể hiện thỏa mãn các tính chất sau: a) Với mọi bộ (a1,..., an) của một quan hệ B, B(a1,...,an) đúng trong thể hiện b) Với mọi luật Q(t1, t2, ..., tn)  P1, P2, ..., Pn và với mọi phép gán θ trong thể hiện: Nếu θ(P1, P2, ..., Pn) đúng trong thể hiện thì θ(Q(t1, t2, ..., tn)) cũng đúng Datalog Một mô hình của một chương trình DATALOG là một tập các tân từ cá biệt: chứa tất cả các sự kiện của CSDL và tất cả các sự kiện có thể được suy diễn bằng áp dụng các luật Ngữ nghĩa chính tắc của chương trình DATALOG Giao của hai mô hình cũng là mô hình Giao của tất cả các mô hình: mô hình nhỏ nhất được gọi là ngữ nghĩa chính tắc Dùng Toán tử Tr để tính (hệ quả trực tiếp - Van Edem 1976) Thủ tục đơn giản tính mô hình nhỏ nhất Tr Cho I là tập sự kiện Tính Tp(I) = {Q/ ∃ P1, P2, ..., Pn  I sao cho Q  P1, P2, ..., Pn là một luật cá biệt của P} Bắt đầu với I = Ø, khi đó Tp(Ø) = tập các sự kiện của chương trình Thủ tục đơn giản tính mô hình nhỏ nhất TrVí dụ Cho chương trình DATALOG sau: P = { BO(Hùng, Dũng)  ; MẸ(Mai, Dũng)  ; CHAMẸ(x,y)  BO(x,y); CHAMẸ(x,y)  MẸ(x,y); TOTIEN(x,y)  CHAMẸ(x,y) } Tính: bắt đầu Tp(Ø) = { BO(Hùng, Dũng)  ; MẸ(Mai, Dũng)  }  Thủ tục đơn giản tính mô hình nhỏ nhất TrVí dụ Tp(Ø) = { BO(Hùng, Dũng)  ; MẸ(Mai, Dũng)  } .... Tp(I) = I' I' là mô hình nhỏ nhất của chương trình P Với những chương trình lớn cần có những thuật toán tối ưu hơn. Ngữ nghĩa chính tắc của chương trình DATALOG Tính khi cần trả lời câu hỏi Câu hỏi được biểu diễn bằng SQL trên quan hệ được suy diễn hay Câu hỏi biểu diễn bằng một luật không đầu dạng  P1, P2, ..., Pn , trong đó thay  bởi ? Ví dụ ? TOTIEN(x, Mai) Liên hệ DATALOG với ĐSQH DATALOG có sức mạnh của ĐSQH với sự cho phép đệ qui (ĐSQH không cho phép đệ qui) Phép hợp: 1 số luật cùng đầu Phép chiếu: một luật có một số biến ở phần thân bị lấy đi khỏi phần đầu của luật Phép chọn: một luật có ít nhất một tân từ quan hệ (so sánh) trong phần thân Phép kết nối: luật gồm một số tân từ quan hệ ở phần thân Mở rộng DATALOG với các hàm Nhờ các hàm có thể tính tóan, xử lí trên những đối tượng phức tạp (hình vẽ, kiểu dữ liệu trừu tượng) Do vậy đưa vào DATALOG các hàm của logic tân từ cấp một: +, -, x, / LOG, EXP,... hàm định nghĩa bởi người dùng Đưa vào các kí hiệu hàm f, g,... có một số cố định đối số Các đối của tân từ có thể là hằng hoặc biến hoặc là hàm tác động lên các hạng thức f (t1, t2, ..., tn) Mở rộng DATALOG với các hàm (tiếp) Vi dụ: Có bản đồ đường đi nối các thành phố (đồ thị có hướng) {Đường_đi (x, y, d)  Cung (x, y, d); Đường_đi (x, y, e+d)  Đường_đi (x, z, e), Cung (z, y, d)} ? Đường_đi (Hà nội, Sài gòn, t) Mở rộng DATALOG với các hàm (tiếp) Ví dụ: {lương (100)  ; cao_hơn (y, x)  lương(x), x<y } ? cao_hơn (y, x) cho vô số đáp số {nguyên (0) ; nguyên(x+1)  Nguyên (x)} chương trình này phát sinh tất cả các số nguyên dương Một luật gọi là có trường hạn chế nếu tất cả các biến trong đầu luật đều xuất hiện trong một tân từ quan hệ ở thân luật. Một chương trình gọi là an toàn nếu không phát sinh vô hạn đáp số Mở rộng DATALOG với phép phủ định Ví dụ : tính độ dài các đường đi trên đồ thị có hướng, có sử dụng quan hệ lưu trữ các cung bị cấm {Đường_đi (x, y, d)  Cung (x, y, d), ¬ Cấm(x, y); Đường_đi (x, y, e+d)  Đường_đi (x, z, e), Cung (z, y, d), ¬ Cấm(z, y)} Giao của hai mô hình nói chung không là mô hình Mở rộng DATALOG với phép phủ định (tiếp) Ví dụ: {chim (ngựa_có_cánh)  ; chim_cánh_cụt (x)  chim (x), ¬bay(x); bay(x)  chim (x), ¬ chim_cánh_cụt (x)} Chương trình này có 2 mô hình: Mô hình 1: {chim (ngựa_có_cánh), chim_cánh_cụt (ngựa_có cánh)} Mô hình 2: {chim (ngựa_có_cánh), bay (ngựa_có cánh)} Giao của hai mô hình là {chim (ngựa_có_cánh)} không là mô hình Mở rộng DATALOG (tiếp) Mở rộng với các tập: để có ngôn ngữ khả năng xử lí các thuộc tính đa trị chứa tập các giá trị Mở rộng với các phép cập nhật Mở rộng với điều kiện phi Horn Xin cảm ơn !