Download Luận văn Logic mô tả và ứng dụng trong cơ sở dữ liệu
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
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
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.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Để nhìn nhận rõ hơn ngữ tính mở của ngữ nghĩa trong ABox ta xét một ví dụ
dựa trên câu truyện thần thoại Hy Lạp, Oedipus. Trong một ngôi làng nhỏ,
câu chuyện kể lại Oedipus đã giết cha và lấy người mẹ tên là Iokaste và có
con tên là Polyneikes với bà ta ra sao. Cuối cùng Polyneikes cũng có con tên
là Thersandros.
Ta giả sử rằng ABox Aoe được biểu diễn trong Hình 1.5 biểu diễn sơ bộ
sự thực này. Trong ABox khẳng định rằng Oedipus là kẻ giết cha còn
Thersandros không giết cha, nó được biểu diễn bằng khái niệm nguyên tố
Patricide.
hasChild(IOKASTE, OEDIPUS)
hasChild(OEDIPUS, POLYNEIKES)
hasChild(IOKASTE, POLYNEIKES)
hasChild(POLYNEIKES, THERSANDROS)
Patricide(OEDIPUS)
atricide(THERSANDROS)
Hình 1.5: ABox Aoe về câu truyện Oedipus
Giả sử ta muốn biết xem Iokaste có con là kẻ giết cha và bản thân
người con này không phải là kẻ giết cha. Ta có thể biểu diễn vấn đề đó như
sau:
Aoe j= (∃hasChild.(Patricide u ∃hasChild.atricide))(IOKASTE)?
-32-
Ai đó có thể gợi ý suy luận như sau: Iokaste có hai người con trong
ABox. Một người là Oedipus là kẻ giết cha. Ông ta có một người con là
Polyneikes. Nhưng không có gì cho ta biết rằng Polyneikes không phải là kẻ
giết cha. Như vậy, Oedipus không phải là người con mà ta đang tìm. Người
thứ hai là Polyneikes, nhưng không có gì cho ta biết Polyneikes là kẻ giết cha.
Như vậy Polyneikes cũng không phải là người con mà ta đang tìm. Dựa vào
lập luận này người ta đánh giá là khẳng định về Iokaste không được kế thừa.
Tuy nhiên, lập luận đúng thì khác. Tất cả các mô hình của Aoe có thể
được chia làm hai lớp, một lớp trong đó nói Polyneikes là kẻ giết cha, và lớp
còn lại nói Polyneikes không giết cha. Trong mô hình của dạng thứ nhất,
Polyneikes, con của Iokaste, là kẻ giết cha và có con không phải là kẻ giết cha
tên là Thersandros. Trong mô hình của dạng thứ hai, Oedipus, con của Iokaste
là kẻ giết cha và có con không phải là kẻ giết cha tên là Polyneikes. Như vậy,
trong tất cả các mô hình Iokaste có một người con là kẻ giết cha và bản thân
kẻ này có một người con không phải là kẻ giết cha. Điều đó có nghĩa rằng
khẳng định:
(∃hasChild.(Patricide u ∃hasChild.atricide))(IOKASTE) thực sự được kế
thừa bởi Aoe.
Ví dụ trên cũng nói rằng, lập luận "mở" có thể cần phân tích các trường
hợp.
-33-
1.4. CÁC THUẬT TOÁN SUY LUẬN
1.4.1. Thuật toán bao hàm cấu trúc
Thuật toán bao hàm cấu trúc xuất phát trong hai pha. Trước hết, mô tả
được kiểm tra để bao hàm được chuẩn hoá, sau đó cấu trúc cú pháp của dạng
chuẩn được so sánh. Để đơn giản, ta giải thích ý tưởng trên bằng cách tiếp cận
ngôn ngữ FL0 (ngôn ngữ chỉ cho phép thực hiện phép hội (C u D) và lượng từ
với mọi (∀R.C)). Tiếp đến ta xử lý đến các khái niệm đáy và phép phủ định
khái niệm.
Rõ ràng, FL0 và mở rộng bằng khái niệm đáy và phủ định khái niệm là
ngôn ngữ con của AL, một khái niệm mô tả FLo là dạng chuẩn khi và chỉ khi nó
có dạng:
A1 u ... u Am u R1.C1 u ... u Rn.Cn
Trong đó A1,..., Am là các khái niệm khác nhau, R1, ... Rn là các vai trò
khác nhau, còn C1,...,Cn là các mô tả khái niệm FLo ở dạng chuẩn. Ta dễ dàng
thấy rằng mô tả bất kỳ có thể chuyển được về một mô tả ở dạng chuẩn. Thực
tế, mô tả ∀R.(C u D) và (∀R.C) u (∀R.D) là tương đương nhau.
Mệnh đề 1.6. [8] Cho dạng chuẩn của mô tả khái niệm FLo:
A1 u ... u Am u ∀R1.C1 u ... u ∀Rn.Cn
và dạng chuẩn của mô tả khái niệm FLo (D):
B1 u ... u Bk u ∀S1.D1 u ... u ∀Sl.Dl
thì C v D khi và chỉ khi phù hợp hai điều kiện sau:
1) Đối với mọi i, 1 ≤ i ≤ k, tồn tại j, 1 ≤ j ≤ m để Bi = Aj
2) Đối với mọi i, 1 ≤ i ≤ l, tồn tại j, 1 ≤ j ≤ n để Si = Rj và Cj v
Di
Ta thấy rằng tính chất trên của bao hàm là đúng đắn và đầy đủ.
-34-
Nếu ta mở rộng FLo bằng các constructor có thể biểu diễn các khái niệm không
thoả, thì một mặt ta phải thay đổi định nghĩa dạng chuẩn, mặt khác, khi so
sánh cấu trúc của các dạng chuẩn ta phải lưu ý rằng một khái niệm không thoả
mãn được bao hàm bởi tất cả các khái niệm. Ngôn ngữ mở rộng đơn giản nhất
của FLo đó là mở rộng khái niệm đáy (?), ký hiệu là FL?.
Một mô tả khái niệm bằng FL? là một dạng chuẩn khi và chỉ khi là ? hay
có dạng:
A1 u... u Am u ∀R1.C1 u ... u ∀Rn.Cn.
Trong đó A1,..., Am là các khái niệm khác với ?, R1,...,Rn là các vai trò, còn
C1,...,Cn là các mô tả khái niệm FL? ở dạng chuẩn.
Về nguyên tắc, ta có thể tính dạng chuẩn FLo của mô tả (? được xử lý
như một khái niệm bình thường): B1 u ... u Bk u ∀R1.D1 u ... u ∀Rn.Dn. Nếu một
trong số Bi là khái niệm đáy ?, thì thay toàn bộ mô tả này bằng ?. Mặt khác,
áp dụng cùng thủ tục đối với Dj. Ví dụ dạng chuẩn FLo của ∀R.∀R.B u A u
∀R.(A u ∀R.?) là
A u ∀R.(A u ∀R.(B u ?)
thu được dạng chuẩn FL?:
A u ∀R.(A u ∀R.?).
Thuật toán bao hàm cấu trúc đối với FL? làm việc giống như đối với FLo, chỉ
khác là khái niệm đáy ? bị bao hàm bởi mô tả bất kỳ. Ví dụ:
∀R.∀R.B u A u ∀R.(A u ∀R.?) v ∀R.∀R.A u A u ∀R.A
khi so sánh đệ quy các dạng chuẩn FL?:
A u ∀R(A u ∀R.?) và A u ∀R.(A u ∀R.A) cuối cùng dẫn đến sự so sánh ? và
A.
Mở rộng FLo bằng phủ định khái niệm có thể được xử lý tương tự. Trong
khi tính dạng chuẩn, các khái niệm bị phủ định được xử lý giống như các khái
-35-
niệm thường. Tuy nhiên, nếu một khái niệm và phủ định của nó xuất hiện ở
cùng mức của dạng chuẩn, thì ta thêm vào ?. Ví dụ:
∀R.:A u A u ∀R.(A u ∀R.B)
Trước hết ta biến đổi thành
A u ∀R.(A u :A u ∀R.B)
Cuối cùng ta được
A u ∀R.?
Đối với các mô tả phức tạp hơn, thuật toán bao hàm cấu trúc thường
không đáp ứng được. Đặc biệt, thuật toán này không xử lý phép hợp, phép
phủ định hoàn toàn, và lượng từ tồn tại. Để khắc phục những điểm yếu của
thuật toán này, người ta đưa ra một thuật toán khá hữu dụng đó là thuật toán
tableau.
1.4.2. Thuật toán tableau
Ngoài việc trực tiếp kiểm tra bao hàm mô tả khái niệm, thuật toán
tableau còn dùng phép phủ định để đưa bài toán bao hàm về bài toán thoả
(không thoả). Như ta đã biết trong Mệnh đề 1.4: C v D khi và chỉ khi C u
không thoả.
Trước khi mô tả chi tiết thuật toán tableau đối với ngôn ngữ ALCN, ta
lược qua các ý tưởng bằng hai ví dụ đơn giản.
Cho A và B là các khái niệm, R là vai trò.
Ví dụ thứ nhất: giả sử ta muốn biết ∃R.A u (∃R.B) có bị bao hàm bởi ∃R(A u
B) hay không, nghĩa là ta phải kiểm tra xem mô tả khái niệm C = (∃R.A) u
(∃R.B) u∃R.(A u B)) có thoả hay không.
Trước hết ta dùng luật de Morgan và luật lượng từ để biến đổi, ta được kết
quả mô tả như sau:
Co = (∃R.A) u (∃R.B) u ∀R.A t :B)
-36-
Đây là dạng chuẩn phủ định, nghĩa là phủ định chỉ xuất hiện trước tên khái
niệm. Sau đó ta xây dựng một diễn dịch hữu hạn I để CoI ≠ ;. Nghĩa là, phải tồn
tại một cá thể trong 4I là phần tử của CoI.
Thuật toán tạo ra một cá thể gọi là b, và chịu sự ràng buộc b ∈ CoI. Khi mà Co
là hội của ba mô tả khái niệm, điều đó nghĩa là b phải thoả mãn ba ràng buộc:
b ∈ (∃R.A)I, b ∈ (∃R.B)I và b ∈ (∀R.A ...
Download miễn phí Luận văn Logic mô tả và ứng dụng trong cơ sở dữ liệu
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
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
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.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ống của cơ sở dữ liệu có đặc điểm là "đóng".Để nhìn nhận rõ hơn ngữ tính mở của ngữ nghĩa trong ABox ta xét một ví dụ
dựa trên câu truyện thần thoại Hy Lạp, Oedipus. Trong một ngôi làng nhỏ,
câu chuyện kể lại Oedipus đã giết cha và lấy người mẹ tên là Iokaste và có
con tên là Polyneikes với bà ta ra sao. Cuối cùng Polyneikes cũng có con tên
là Thersandros.
Ta giả sử rằng ABox Aoe được biểu diễn trong Hình 1.5 biểu diễn sơ bộ
sự thực này. Trong ABox khẳng định rằng Oedipus là kẻ giết cha còn
Thersandros không giết cha, nó được biểu diễn bằng khái niệm nguyên tố
Patricide.
hasChild(IOKASTE, OEDIPUS)
hasChild(OEDIPUS, POLYNEIKES)
hasChild(IOKASTE, POLYNEIKES)
hasChild(POLYNEIKES, THERSANDROS)
Patricide(OEDIPUS)
atricide(THERSANDROS) Hình 1.5: ABox Aoe về câu truyện Oedipus
Giả sử ta muốn biết xem Iokaste có con là kẻ giết cha và bản thân
người con này không phải là kẻ giết cha. Ta có thể biểu diễn vấn đề đó như
sau:
Aoe j= (∃hasChild.(Patricide u ∃hasChild.
atricide))(IOKASTE)? -32-
Ai đó có thể gợi ý suy luận như sau: Iokaste có hai người con trong
ABox. Một người là Oedipus là kẻ giết cha. Ông ta có một người con là
Polyneikes. Nhưng không có gì cho ta biết rằng Polyneikes không phải là kẻ
giết cha. Như vậy, Oedipus không phải là người con mà ta đang tìm. Người
thứ hai là Polyneikes, nhưng không có gì cho ta biết Polyneikes là kẻ giết cha.
Như vậy Polyneikes cũng không phải là người con mà ta đang tìm. Dựa vào
lập luận này người ta đánh giá là khẳng định về Iokaste không được kế thừa.
Tuy nhiên, lập luận đúng thì khác. Tất cả các mô hình của Aoe có thể
được chia làm hai lớp, một lớp trong đó nói Polyneikes là kẻ giết cha, và lớp
còn lại nói Polyneikes không giết cha. Trong mô hình của dạng thứ nhất,
Polyneikes, con của Iokaste, là kẻ giết cha và có con không phải là kẻ giết cha
tên là Thersandros. Trong mô hình của dạng thứ hai, Oedipus, con của Iokaste
là kẻ giết cha và có con không phải là kẻ giết cha tên là Polyneikes. Như vậy,
trong tất cả các mô hình Iokaste có một người con là kẻ giết cha và bản thân
kẻ này có một người con không phải là kẻ giết cha. Điều đó có nghĩa rằng
khẳng định:
(∃hasChild.(Patricide u ∃hasChild.
atricide))(IOKASTE) thực sự được kế thừa bởi Aoe.
Ví dụ trên cũng nói rằng, lập luận "mở" có thể cần phân tích các trường
hợp.
-33-
1.4. CÁC THUẬT TOÁN SUY LUẬN
1.4.1. Thuật toán bao hàm cấu trúc
Thuật toán bao hàm cấu trúc xuất phát trong hai pha. Trước hết, mô tả
được kiểm tra để bao hàm được chuẩn hoá, sau đó cấu trúc cú pháp của dạng
chuẩn được so sánh. Để đơn giản, ta giải thích ý tưởng trên bằng cách tiếp cận
ngôn ngữ FL0 (ngôn ngữ chỉ cho phép thực hiện phép hội (C u D) và lượng từ
với mọi (∀R.C)). Tiếp đến ta xử lý đến các khái niệm đáy và phép phủ định
khái niệm.
Rõ ràng, FL0 và mở rộng bằng khái niệm đáy và phủ định khái niệm là
ngôn ngữ con của AL, một khái niệm mô tả FLo là dạng chuẩn khi và chỉ khi nó
có dạng:
A1 u ... u Am u R1.C1 u ... u Rn.Cn
Trong đó A1,..., Am là các khái niệm khác nhau, R1, ... Rn là các vai trò
khác nhau, còn C1,...,Cn là các mô tả khái niệm FLo ở dạng chuẩn. Ta dễ dàng
thấy rằng mô tả bất kỳ có thể chuyển được về một mô tả ở dạng chuẩn. Thực
tế, mô tả ∀R.(C u D) và (∀R.C) u (∀R.D) là tương đương nhau.
Mệnh đề 1.6. [8] Cho dạng chuẩn của mô tả khái niệm FLo:
A1 u ... u Am u ∀R1.C1 u ... u ∀Rn.Cn
và dạng chuẩn của mô tả khái niệm FLo (D):
B1 u ... u Bk u ∀S1.D1 u ... u ∀Sl.Dl
thì C v D khi và chỉ khi phù hợp hai điều kiện sau:
1) Đối với mọi i, 1 ≤ i ≤ k, tồn tại j, 1 ≤ j ≤ m để Bi = Aj
2) Đối với mọi i, 1 ≤ i ≤ l, tồn tại j, 1 ≤ j ≤ n để Si = Rj và Cj v
Di
Ta thấy rằng tính chất trên của bao hàm là đúng đắn và đầy đủ.
-34-
Nếu ta mở rộng FLo bằng các constructor có thể biểu diễn các khái niệm không
thoả, thì một mặt ta phải thay đổi định nghĩa dạng chuẩn, mặt khác, khi so
sánh cấu trúc của các dạng chuẩn ta phải lưu ý rằng một khái niệm không thoả
mãn được bao hàm bởi tất cả các khái niệm. Ngôn ngữ mở rộng đơn giản nhất
của FLo đó là mở rộng khái niệm đáy (?), ký hiệu là FL?.
Một mô tả khái niệm bằng FL? là một dạng chuẩn khi và chỉ khi là ? hay
có dạng:
A1 u... u Am u ∀R1.C1 u ... u ∀Rn.Cn.
Trong đó A1,..., Am là các khái niệm khác với ?, R1,...,Rn là các vai trò, còn
C1,...,Cn là các mô tả khái niệm FL? ở dạng chuẩn.
Về nguyên tắc, ta có thể tính dạng chuẩn FLo của mô tả (? được xử lý
như một khái niệm bình thường): B1 u ... u Bk u ∀R1.D1 u ... u ∀Rn.Dn. Nếu một
trong số Bi là khái niệm đáy ?, thì thay toàn bộ mô tả này bằng ?. Mặt khác,
áp dụng cùng thủ tục đối với Dj. Ví dụ dạng chuẩn FLo của ∀R.∀R.B u A u
∀R.(A u ∀R.?) là
A u ∀R.(A u ∀R.(B u ?)
thu được dạng chuẩn FL?:
A u ∀R.(A u ∀R.?).
Thuật toán bao hàm cấu trúc đối với FL? làm việc giống như đối với FLo, chỉ
khác là khái niệm đáy ? bị bao hàm bởi mô tả bất kỳ. Ví dụ:
∀R.∀R.B u A u ∀R.(A u ∀R.?) v ∀R.∀R.A u A u ∀R.A
khi so sánh đệ quy các dạng chuẩn FL?:
A u ∀R(A u ∀R.?) và A u ∀R.(A u ∀R.A) cuối cùng dẫn đến sự so sánh ? và
A.
Mở rộng FLo bằng phủ định khái niệm có thể được xử lý tương tự. Trong
khi tính dạng chuẩn, các khái niệm bị phủ định được xử lý giống như các khái
-35-
niệm thường. Tuy nhiên, nếu một khái niệm và phủ định của nó xuất hiện ở
cùng mức của dạng chuẩn, thì ta thêm vào ?. Ví dụ:
∀R.:A u A u ∀R.(A u ∀R.B)
Trước hết ta biến đổi thành
A u ∀R.(A u :A u ∀R.B)
Cuối cùng ta được
A u ∀R.?
Đối với các mô tả phức tạp hơn, thuật toán bao hàm cấu trúc thường
không đáp ứng được. Đặc biệt, thuật toán này không xử lý phép hợp, phép
phủ định hoàn toàn, và lượng từ tồn tại. Để khắc phục những điểm yếu của
thuật toán này, người ta đưa ra một thuật toán khá hữu dụng đó là thuật toán
tableau.
1.4.2. Thuật toán tableau
Ngoài việc trực tiếp kiểm tra bao hàm mô tả khái niệm, thuật toán
tableau còn dùng phép phủ định để đưa bài toán bao hàm về bài toán thoả
(không thoả). Như ta đã biết trong Mệnh đề 1.4: C v D khi và chỉ khi C u
không thoả.
Trước khi mô tả chi tiết thuật toán tableau đối với ngôn ngữ ALCN, ta
lược qua các ý tưởng bằng hai ví dụ đơn giản.
Cho A và B là các khái niệm, R là vai trò.
Ví dụ thứ nhất: giả sử ta muốn biết ∃R.A u (∃R.B) có bị bao hàm bởi ∃R(A u
B) hay không, nghĩa là ta phải kiểm tra xem mô tả khái niệm C = (∃R.A) u
(∃R.B) u
∃R.(A u B)) có thoả hay không. Trước hết ta dùng luật de Morgan và luật lượng từ để biến đổi, ta được kết
quả mô tả như sau:
Co = (∃R.A) u (∃R.B) u ∀R.
A t :B) -36-
Đây là dạng chuẩn phủ định, nghĩa là phủ định chỉ xuất hiện trước tên khái
niệm. Sau đó ta xây dựng một diễn dịch hữu hạn I để CoI ≠ ;. Nghĩa là, phải tồn
tại một cá thể trong 4I là phần tử của CoI.
Thuật toán tạo ra một cá thể gọi là b, và chịu sự ràng buộc b ∈ CoI. Khi mà Co
là hội của ba mô tả khái niệm, điều đó nghĩa là b phải thoả mãn ba ràng buộc:
b ∈ (∃R.A)I, b ∈ (∃R.B)I và b ∈ (∀R.
A ...