Thạc Sĩ Logic mô tả và ứng dụng trong cơ sở dữ liệu

LỜI GIỚI THIỆU
Nghiên cứu trong lĩnh vực biểu diễn tri thức và suy diễn thường tập trung vào các phương pháp có khả năng mô tả “thế giới” ở mức cao. Trong những năm gần đây, người ta thường nhắc tới “logic mô tả” (Description logic) như
là một phương pháp biểu diễn tri thức hiệu quả. Trong những ứng dụng cụ thể có sử dụng logic mô tả, tri thức của miền ứng dụng được đặc tả bằng các khái niệm và các mối quan hệ. Lĩnh vực ứng dụng của logic mô tả cũng rất đa dạng, ngay từ ngày đầu, logic mô tả đã được xem như là những ngôn ngữ với mục đích biểu diễn tri thức và suy diễn, vì thế nó phù hợp cho nhiều ứng dụng. Tuy nhiên những ứng dụng mang tính thương mại đến nay vẫn chưa thực sự phổ biến. Các ứng dụng của logic mô tả có thể kể đến như công nghệ phần mềm, thiết lập cấu hình, y học, các hệ thống thư viện điện tử, hệ thống thông tin web ngữ nghĩa, xử lý ngôn ngữ tự nhiên, quản trị cơ sở dữ liệu .
Mối quan hệ giữa logic mô tả và cơ sở dữ liệu khá khăng khít. Thực tế, nhu cầu xây dựng các hệ thống mà vừa có khả năng biểu diễn tri thức logic mô tả và quản trị cơ sở dữ liệu là cần thiết. Các hệ quản trị cơ sở dữ liệu giải quyết vấn đề toàn vẹn dữ liệu và quản trị một số lượng lớn dữ liệu, trong khi đó hệ biểu diễn cơ sở tri thức logic mô tả quản lý tri thức nội hàm. Hơn nữa, logic mô tả cung cấp một khung chuẩn mà được xem như rất gần gũi với các
ngôn ngữ được dùng để mô hình hoá dữ liệu, như mô hình thực thể - quan hệ. Logic mô tả tương đương với các công cụ lập luận. Chẳng hạn, bằng việc sử dụng tính nhất quán khái niệm ta có thể xác nhận một thực thể có ít nhất một thể hiện ngay tại thời điểm thiết kế. Một yếu tố nữa tăng cường cho hệ quản trị cơ sở dữ liệu bằng logic mô tả là ngôn ngữ truy vấn. Bằng việc biểu diễn truy vấn cơ sở dữ liệu trong logic mô tả người ta có khả năng phân loại chúng, vì thế xử lý kết quả như thực hiện và tối ưu hoá truy vấn. Hơn nữa, logic mô tả có thể được dùng để biểu diễn các ràng buộc và các câu trả lời nội hàm.
Trong thời gian qua em đã có điều kiện được tiếp xúc, nghiên cứu về logic mô tả. Từ những nghiên cứu này, nên trong luận văn em sẽ trình bày theo hướng nêu lên các vấn đề cơ bản của logic mô tả, sơ lược về các mô hình cơ
sở dữ liệu phổ biến, mối quan hệ giữa cơ sở dữ liệu và logic mô tả. Do vậy, các nội dung của luận văn này sẽ được trình bày như sau:
ã Chương 1. Logic mô tả: Đây là chương giới thiệu về những nội dung cơ bản của logic mô tả như khái lược về logic mô tả, các ngôn ngữ của logic mô tả, kiến trúc của một hệ cơ sở tri thức dựa trên logic mô tả, các bài toán quyết định. Đồng thời giới thiệu một ngôn ngữ lập trình logic Datalog.
ã Chương 2. Sơ lược về cơ sở dữ liệu: Trong chương này em xin đề cập một cách khái lược nhất về hai mô hình cơ sở dữ liệu đó là mô hình dữ liệu thực thể - quan hệ và mô hình dữ liệu hướng đối tượng.
ã Chương 3. Chuyển đổi cơ sở dữ liệu thành cơ sở tri thức của logic mô tả: Chương này sẽ giới thiệu phương pháp để biến đổi các lược đồ của mô hình dữ liệu thực thể - liên kết cũng như mô hình hướng đối tượng thành bộ thuật ngữ (TBox) của logic mô tả, đồng thời thảo luận về việc chuyển đổi dữ liệu của cơ sở dữ liệu vào bộ khẳng định (ABox) của logic mô tả.
Chương 4. Truy vấn: Chương này thảo luận về truy vấn cơ sở tri thức, từ các thành phần cơ bản của truy vấn như truy vấn nguyên tử khái niệm, truy vấn nguyên tử vai trò đến các truy vấn phức hợp bằng biểu thức hội các thành phần khái niệm và vai trò cơ sở. Đồng thời cũng đưa ra thuật toán nhằm chuyển đổi các câu truy vấn xây dựng theo cách thể hiện của ngôn ngữ lập trình logic Datalog sang biểu diễn mô tả khái niệm trong logic mô tả.
MỤC LỤC
Nội dung Trang
LỜI CAM ĐOAN .1
LỜI CÁM ƠN .2
MỤC LỤC .3
DANH SÁCH CÁC BẢNG 6
DANH SÁCH CÁC HÌNH .6
LỜI GIỚI THIỆU 7
Chương 1. LOGIC MÔ TẢ .10
1.1. GIỚI THIỆU .10
1.2. NGÔN NGỮ THUỘC TÍNH AL .11
1.2.1. Ngôn ngữ mô tả cơ bản AL 11
1.2.2. Ngữ nghĩa của các khái niệm AL .12
1.2.3. Họ ngôn ngữ logic mô tả AL 13
1.2.4. Ngôn ngữ mô tả là tập con của logic vị từ bậc nhất .15
1.3. HỆ CƠ SỞ TRI THỨC .15
1.3.1. Kiến trúc hệ logic mô tả .15
1.3.2. Bộ thuật ngữ (TBox) 16
1.3.2.1. Tiên đề thuật ngữ . 16
1.3.2.2. Định nghĩa khái niệm . 17
1.3.2.3. Mở rộng bộ thuật ngữ 20
1.3.2.4. Đệ quy 22
1.3.2.5. Thuật ngữ với các tiên đề bao hàm 22
1.3.3. Bộ khẳng định (ABox) .23
1.3.4. Cá thể 25
-4-
1.3.5. Suy luận 26
1.3.5.1. Lập luận đối với khái niệm 26
1.3.5.2 Loại trừ TBox . 28
1.3.5.3. Lập luận đối với ABox 29
1.3.5.4. Ngữ nghĩa “đóng”, ngữ nghĩa “mở” 30
1.4. CÁC THUẬT TOÁN SUY LUẬN 33
1.4.1. Thuật toán bao hàm cấu trúc 33
1.4.2. Thuật toán tableau 35
1.5. MỞ RỘNG NGÔN NGỮ MÔ TẢ .41
1.5.1. Các constructor vai trò .41
1.5.2. Biểu diễn các giới hạn số .42
1.6. NGÔN NGỮ DATALOG 42
1.6.1. Các khái niệm và thành phần của Datalog .43
1.6.2. Cú pháp của chương trình Datalog 44
1.7. TỔNG KẾT CHƯƠNG 46
Chương 2. SƠ LƯỢC VỀ CƠ SỞ DỮ LIỆU .48
2.1. MÔ HÌNH THỰC THỂ - QUAN HỆ .48
2.2. MÔ HÌNH HƯỚNG ĐỐI TƯỢNG 52
2.3. TỔNG KẾT CHƯƠNG 56
Chương 3. CHUYỂN ĐỔI CƠ SỞ DỮ LIỆU THÀNH CƠ SỞ TRI
THỨC CỦA LOGIC MÔ TẢ 57
3.1. MÔ HÌNH HOÁ LƯỢC ĐỒ THỰC THỂ - QUAN HỆ
BẰNG LOGIC MÔ TẢ 57
3.2. MỞ RỘNG KHẢ NĂNG BIỂU DIỄN CỦA NGÔN
NGỮ MÔ HÌNH HOÁ .63
3.2.1. Tổng quát hoá thực thể .63
3.2.2. Lọc các tính chất thuộc một cấu trúc IS-A .64
-5-
3.3. BIỂU DIỄN MÔ HÌNH DỮ LIỆU HƯỚNG ĐỐI
TƯỢNG BẰNG LOGIC MÔ TẢ .64
3.4. CHUYỂN DỮ LIỆU TỪ CƠ SỞ DỮ LIỆU VÀO
ABOX CỦA LOGIC MÔ TẢ .66
3.5 TỔNG KẾT CHƯƠNG .72
Chương 4. TRUY VẤN 73
4.1. NGUYÊN TỬ TRUY VẤN, ĐỐI TƯỢNG, CÁ THỂ VÀ BIẾN 73
4.1.1. Nguyên tử truy vấn khái niệm 73
4.1.2. Nguyên tử truy vấn vai trò .74
4.2. TRUY VẤN PHỨC HỢP .75
4.3. HỖ TRỢ MÔ TẢ - ĐỊNH NGHĨA VÀ THUẬT TOÁN .76
4.4. TỔNG KẾT CHƯƠNG 78
KẾT LUẬN .79
CÁC THUẬT NGỮ 80
TÀI LIỆU THAM KHẢO .82