Giáo trình Hệ cơ sở dữ liệu phân tán và suy diễn: Phần 2 - Nguyễn Văn Huân, Phạm Việt Bình

Giáo trình Hệ cơ sở dữ liệu phân tán và suy diễn: Phần 2 có nội dung trình bày cơ sở dữ liệu suy diễn, cơ sở dữ liệu hướng đối tượng, thực hành một số ứng dụng. Mời bạn đọc tham khảo nội dung phần 2 tài liệu để hiểu về các cơ sở dữ liệu trên.
Nội dung trích xuất từ tài liệu:
Giáo trình Hệ cơ sở dữ liệu phân tán và suy diễn: Phần 2 - Nguyễn Văn Huân, Phạm Việt Bình C H Ư Ơ N G III C ơ SỞ DỮ LIỆU SUY DIỄN 3 .1. G ỈÓ Ì T H IỆ U C H Ư N G - Khái niệm về CSDL suy diễn được nhiều nhà nghiên cứu đề cập đến theo hướng phát triển các kết quả mà Green đã đạt được vào năm 1969 về các hệ thống câu hòi - trả lời. - Xuất phát từ quan điểm lý thuyết, các CSDL suy diễn có thể được coi như các chương trình logic với sự khái quát hoá khái niệm về CSDL quan hệ. Đó là cách tiếp cận của Brodie và Manola vào năm 1989, của Codd vào năm 1970, của Date vào năm Ĩ986, của Gardarin và Valdurier vào nàm 1989 và của Ullman vào năm 1984. - Lập trình logic là mảng công việc trước tiên khi chứng minh định lý cơ học. Sự thật thì việc chứng minh định lý đã tạo nên cơ sờ cho hầu hết hệ thống lập trình logic hiện nay. Tư tưỏĩig cơ bản cùa lập trình logic là sử dụng logic toán học như ngôn ngữ lập trình. Điều này được đề cập trong tài liệu của Kowaski năm 1970, và được Colmerauer đưa vào thực hành năm 1975 trong các cài đặt ngôn ngữ lập trinh logic đầu tiên, tức là ngôn ngữ PROLOG (PROgramming LOGic). Nhờ sự hình thức hoá, Kowalski đã xem xét tập con của các logic bậc một, gọi là logic mệnh đề Hom. Một câu hay một mệnh đề theo logic có thể có nhiều điều kiện đúng nhưng chỉ có một hay không có kết luận đúng. - Đối với nhu cầu thực hành CSDL suy diễn xử lý các câu không phức tạp như các câu trong hệ thống lập trình logic, s ố các luật, tức là số các câu với các điều kiện không trống trong CSDL suy diễn nhỏ hon số các sự kiện, tức các câu với điều kiện rỗng. - Một khía cạnh khác nhau nữa giữa CSDL suy diễn và lập trình logic là các hệ thống lập trình logic nhẩn mạnh các chức năng, trong khi CSDL suy dierì rĩhấn mạnh tỉnh hiệu quá. ( 'ơ chế suy dien dùng trong CSDL suy diễn đê tỉnh toán trà lời không đuực tông quát như trong lập trình logic. -•N goài việc dùng logic đế diễn tá các câu CSDL, người ta còn dùng logic đế diễn tá những cáu hói V Ĩ các điều kiện toàn vẹn. C 3 .2 . C ơ S Ở D ữ L IỆ U S U Y D IỄ N 3 .2 .1 . M ô h ìn h c ơ s ở d ữ liệu su y d iễn Mô hinh dữ liệu gồiư: + Kí pháp toán học để mô tả hinh thức dữ liệu và các quan hệ ; + Kỹ thuật để xử lý dữ liệu như trả lời các câu hỏi, kiếm tra điều kiện toàn vẹn. 129 Ngôn ngữ bậc một được dùng như kí pháp toán học để mô tả dữ liệu trong mô hình CSDL suy diễn và dữ liệu được xử lý trong các mô hình như vậy nhờ việc đánh giá công thức logic. Tiếp cận của logic bậc một như nền tảng lý thuyết của các hệ thống CSDL suy diễn. Tuy nhiên, để dễ biểu diễn hình thức các khái niệm về CSDL suy diễn, ta thường dùng phép toán vị tìr, tức logic vị từ bậc nhất. Logic vị tìr bậc nhất là ngôn ngũ hình thức dùng để thể hiện quan hệ giữa các đối tượng và đế suy diễn ra quan hệ mới. Định nghĩa 1: Mỗi một hằng số, một biến số hay một hàm số áp lên các term là một hạng thức (term). Hàm n ngôi f(x l, x2,..., xn); xi I i = 1, 2,..., n là một hạng thức thì f(x l, x 2 ,..., xn) là một term. Định nghĩa 2: Công thức nguyên tổ (công thức nhỏ nhất) là kết quả của việc ứng dụng một vị từ trên các tham số của term dưới dạng P(tl, í2,..., ín). Nếu p là vị từ có n ngôi và ti I i = 1, 2,..., n là một hạng thức (term). Định nghĩa 3: (Literal) Dãy các công thức nguyên tố hay phủ định của công thức nguyên tố đã được phân tách qua các liên kết logic (a, V, -T V 3) thì công thức đó , , được thiết lập đúng đắn. (i): Một công thức nguyên tố là công thức thiết lập đúng đắn. (ỉi): F, G là Công thức thiết lập đúng đắn => F A G, F V G, F -> G, F 4-» G, F , G cũng là các công thức thiết lập đúng đắn. (iii): Nếu F là Công thức thiết lập đúng đắn, mà X là một biến tự do trong F => (Vx)F và (3x)F cũng là các công thức thiết lập đúng đắn (Vx, 3x trong F). Vỉ dụ 3.1: Cho quan hệ R(A1, A 2 ,.. An) với n bậc (tức n thuộc tính) => là một vị tìr n ngôi. Nếu reR (r bộ của R) => (r.A l, r.A 2,..., r.An) => R(A1, A2,..., An) nhận giá trị đúng. Nếu ríSR (r bộ của R) => gán (r.A l, r.A 2,..., r.An) => R(A1, A2,..., An) nhận giá trị sai. Định nghĩa 4: Câu (Clause) Công thức có dạng PlAP2A....APn Q1a Q2a .... a Qìi Trong đó: Pi và Qj (ij=l,2,...,n) là các Literal dương. Trong hệ thống logic, Literal dương có dạng nguyên tố, nhỏ nhất, trái với Literal âm là phủ định của nguyên tố. Định nghĩa 5: Câu Horn (Horn clause) Là câu cỏ dạng PlAP2A....APn -> Q1 Định nghĩa 6: CSDL sụy diễn tổng quát (General deductive database) CSDL suy diễn tồng quát, hay CSDL tổng quát, hay CSDL suy diễn được xác định như cặp (D,L), trong đổ D là íập hữu hạn của các câu CSDL và L là ngôn ngữ bậc một. Giả sử L có ít nhất hai ký hiệu, một là ký hiệu hằng số và một ký kiệu vị từ. + Một CSDL xác định (hay CSDL chuẩn) là CSDL suy diễn (D,L) mà D chỉ chứa các câu xác định (câu chuẩn). + Một CSDL quan hệ là CSDL suy diễn (D,L) mà D chi chứa các sự kiện xác định. 130 Vậy CSDL quan hệ là một dạnu đặc biệt cũa CSDL tồniì quát, hay chuẩn, hay xác định. Còn một CSDL. xác định là dạng đặc biệt của CSDL chiiấn hav tồng quát. 3 .2 .2 . Lý th u y ế t m ô h ìn h đối v ó i cơ sỏ’ d ữ iiệu q u a n hệ 3.2.2. L N h ìn nhận c ơ s ở d ữ liệu theo quan điểm logic Một CSDL có thể được nhìn nhận dưới quan điểm của logic như sau: • LÝ thuyết bậc một; • Diễn giải của lý thuyết bậc một. Theo quan điềm diễn giải, các câu hỏi và các điều kiện toàn vẹn là cô ...