Bài viết sưu tầm

Khái niệm về cơ sở dữ liệu suy diễn được nhiều nhà nghiên cứu đề cập 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 cơ sở dữ liệu suy diễn có thể được coi như các chương trình logic với sự khái quát hóa khái niệm về cơ sở dữ liệu quan hệ

Nói cách khác,ta có thể khái niệm CSDL suy diễn như sau: Cơ sở dữ liệu suy diễn là cơ sở dữ liệu có khả năng suy diễn ra một số sự kiện mới từ những sự kiện được lưu trữ trong CSDL, nógồm hai thành phần: cơ sở dữ liệu ngoại diên và CSDL nội hàm (CSDL ngoại diên là một CSDL quan hệ tiêu chuẩn, có lược đồ gồm một tập các lược đồ quan hệ. CSDL nội hàm được xác định bởi một tập các lược đồ quan hệ và một chương trình Datalog định nghĩa các quan hệ đó. )

Đối với các nhu cầu thực hành, các cơ sở dữ liệu suy diễn xử lý các câu không phức tạp như các câu trong các hệ thống lập trình logic. Số các luật, tức là các câu với các điều kiện không trống trong cơ sở dữ liệu suy diễn nhỏ hơn số các sự kiện, tức là 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 cơ sở dữ liệu 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 cơ sở dữ liệu suy diễn nhấn mạnh tính hiệu quả. Cơ chế suy diễn trong cơ sở dữ liệu suy diễn để tính toán trả lời không được tổng quát như trong lập trình logic.

1.2 .Cấu trúc của 1 CSDL suy diễn

*Một CSDL suy diễn gồm 3 tập hữu hạn:

-Tập các sự kiện

-Tập các luật suy diễn

-Tập các ràng buộc toàn vẹn

Các sự kiện biểu diễn thông tin cơ sở được biết là đúng trong CSDL. Các luật suy diễn cho phép suy dẫn các sự kiện mới từ các sự kiện được lưu trữ trong CSDL. Các ràng buộc toàn vẹn tương ứng với các điều kiện mà mỗi trạng thái của CSDL phải thỏa mãn.

    Một CSDL bao gồm một tập hữu hạn hằng {c₁, c₂, …, c_n} và một tập các câu cấp một không có kí hiệu hàm. Dạng tổng quát của các câu biểu diễn sự kiện và luật suy diễn là :

                         P₁ ^ P₂ ^…^ P_k àR₁ v R₂ v…v R_m

 Tương đương với câu:

                        ¬P₁ v ¬ P₂ v. . . v ¬P_k v R₁ v R₂ v. . . v R_m

 Câu được gọi là có tầm hạn chế nếu mọi biến xuất hiện ở vế phải cũng xuất hiện ở vế trái

-  Ký pháp toán học để mô tả hình 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.

-  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 cơ sở dữ liệu 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.

Ưu điểm của tiếp cận logic bậc một như nền tảng lý thuyết của các hệ thống cơ sở dữ liệu suy diễn:

- Bản thân logic đã có ngữ nghĩa để hiểu.

-  Logic có thể được dùng như ngôn ngữ đồng nhất để diễn tả các sự kiện, các luật, các câu hỏi và các điều kiện toàn vẹn.

- Lý thuyết phát triển mạnh về logic có thể dùng để giải một số bài toán về cơ sở dữ liệu, bao gồm cả bài toán về giá trị rỗng và dữliệu không xác định.

- Việc dùng luật đơn có thể thay thế nhiều sự kiện hiển nhiên. Điều này đảm bảo một môi trường cởi mở và rẻ đối với việc mô hình hóadữ liệu.

- Khái niệm về cơ sở dữ liệu suy diễn tổng quát hóa khái niệm về cơ sở dữ liệu quan hệ.

VD:

Các sự kiện F:

Bo(An,Duong)

Bo(An,Mai)

Bo(Giap,Hong)

Me(Xuan,An)

Me(Xuan,Hong)

Me(Giang,Minh)

Các luật suy diễn DR:

R1: ChaMe(x,y)ßBo(x,y)

R2: ChaMe(x,y)ßMe(x,y)

R3: OngBa(x,y)ßMe(x,y) ^ ChaMe(x,y);

Các ràng buộc toàn vẹn:

IC1(x) ßChaMẹ(x,x)

 C2(x)ßBo(x,y)^Me(x,y).

2. Ngôn ngữ Datalog

2.2  Tổng quát

Là một ngôn ngữ luật cho các CSDL, cho phép xác định các quan hệ suy diễn nhờ phép kéo theo đơn giản không có kí hiệu hàm.

Datalog là một ngôn ngữ được dẫn xuất từ lập trình logic Prolog, để định nghĩa nội dung và cấu trúc thông tin được lưu trữ trong CSDL. Datalog là một ngôn ngữ khai báo, phi thủ tục và hướng tập, được xem là ngôn ngữ chuẩn trong lĩnh vực các hệ CSDL suy diễn

  Datalog là sự phát triển của Prolog với sự kết hợp của ngôn ngữ lập trình Prolog với cơ sở dữ liệu:

          Datalog = prolog + database relation

 Datalog cho phép người dùng phản ánh các luật và các sự kiện. Trong đó thứ tự của các luật không quan trọng. Các truy vấn và cập nhật cơ sở dữ liệu được sử dụng thông qua khai báo ngôn ngữ logic mà trong mỗi công thức là một hàm trong mệnh đề Horn và hầu hết các biến nếu xuất hiện trong đầu luật thì phải xuất hiện trong thân luật.

          Để thực thi Datalog thông qua câu lệnh và cú pháp dựa trên các bảng và các truy vấn hỏi thông qua các query trên các bảng kết quả.

  *  Một mô hình của một chương trình là một thể hiện thỏa mãn các tính chất sau :

 -Với mọi bộ (a₁, a₂, . , a_n) của một quan hệ B, B(a₁, a₂, …. , a_n) đúng trong thể hiện.

 -Với mỗi luật Q(t₁, t₂, …. t_n) ßP₁, P₂, …. P_n và với mọi phép gán Ø trong thể hiện : Nếu Ø(P₁, P₂, …, P_n) đúng trong thể hiện thì Ø(Q(t₁, t₂, . . , t_n)) cũng đúng.

Các mở rộng Datalog với các hàm:

    Đưa thêm kí hiệu hàm vào trong đối của các tân từ Datalog: Nhờ các hàm có thể tính toán, xử lý 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 số 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(t₁, t₂, . . , t_n)

 Thêm phép phủ định Datalog

Cập nhật tường minh trong một luật Datalog

  Đưa vào những điều kiện tổng quát vào các phép hội, tuyển, phủ định (phi Horn) Datalog.

2. 2   Cú pháp Datalog

Bảng chữ sử dụng các ký hiệu sau:

·        Các biến: được ký hiệu là x, y, z, …

·        Các hằng: thường được ký hiệu là a, b, c, …

·        Các tân từ: P, Q, R, …

·        Các liên kết logic: ‌→, ┐, . .

·        Các tân từ so sánh =, <, >, …

·        Các lượng từ: ", $

Hạng thức: là một biến, một hằng, hay kết quả của việc áp dụng một hàm cho một hạng thức.

Công thức nguyên tố: Literal dương (tức là các công thức nguyên tố không có dấu phủ định).

Công thức nguyên tố cá biệt: công thức nguyên tố không chứa biến (còn gọi là các sự kiện).

Luật suy diễn: biểu thức có dạng tổng quát sau: Q ← P₁, P₂, P₃, …

Trong đó:

·        Q: đầu luật, là công thức nguyên tố (kết luận).

·        Thân luật: P₁, P₂, … là các tân từ.

·        Luật được gọi là đệ quy nếu tân từ của đầu luật cũng xuất hiện ở thân luật.

·        Mỗi P_i được gọi là một đích con.