NGHIÊN CỨU MÔ HÌNH CSDL SUY DIỄN VÀ ỨNG DỤNG TRONG KHAI THÁC MẠNG THÔNG TIN KHÔNG ĐỒNG NHẤT

Lưu trữ, quản lý và truy xuất dữ liệu một cách hiệu quả là một trong các vấn đề rất quan trọng của ngành khoa học máy tính. Hiển nhiên rằng, việc lưu trữ và quản lý dữ liệu có thể xem là một nhu cầu thiết yếu không thể thiếu của tất cả mọi lĩnh vực, như: kinh tếtài chính, quản lý xã hội, y tế, giáo dục, v.v. Trong xu thế phát triển của Internet cùng với sự bùng nổ của dữ liệu trong kỷ nguyên BigData như hiện nay, thì bài toán lưu trữ và quản lý dữ liệu càng được đặt nặng và có mức độ phức tạp cao hơn, vì ngoài yêu cầu có thể lưu trữ, quản lý được một khối lượng dữ liệu vô cùng lớn, thì các hệ quản trị CSDL còn phải có khả năng tự suy luận cũng như hỗ trợ rút trích hiệu quả các tri thức từ khối dữ liệu vô cùng lớn mà nó lưu trữ.

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

_

BÁO CÁO TIỂU LUẬN MÔN HỌC CƠ SỞ DỮ LIỆU NÂNG CAO

NGHIÊN CỨU MÔ HÌNH CSDL SUY DIỄN VÀ ỨNG DỤNG TRONG KHAI THÁC

MẠNG THÔNG TIN KHÔNG ĐỒNG NHẤT

(RESEARCHING ON DEDUCTIVE DATABASE SYSTEM AND APPLICATIONS IN HETEROGENEOUS INFORMATION

NETWORK MINING)

HVTH: ThS PHẠM THẾ ANH PHÚ GVHD: TS NGUYỄN GIA TUẤN ANH

1 GIỚI THIỆU CHUNG VỀ CSDL SUY DIỄN & CÁC VẤN ĐỀ LIÊN QUAN ĐẾN KHAI THÁC TRI THỨC TỪ CSDL

1.1 Nhu cầu về khả năng suy diễn và sinh tri thức từ dữ liệu

Lưu trữ, quản lý và truy xuất dữ liệu một cách hiệu quả là một trong các vấn đề rất quan trọng của ngành khoa học máy tính Hiển nhiên rằng, việc lưu trữ và quản lý dữ liệu có thể xem là một nhu cầu thiết yếu không thể thiếu của tất cả mọi lĩnh vực, như: kinh tế/tài chính, quản lý xã hội, y tế, giáo dục, v.v Trong xu thế phát triển của Internet cùng với sự bùng nổ của dữ liệu trong kỷ nguyên BigData như hiện nay, thì bài toán lưu trữ và quản lý dữ liệu càng được đặt nặng và có mức độ phức tạp cao hơn, vì ngoài yêu cầu có thể lưu trữ, quản lý được một khối lượng dữ liệu vô cùng lớn, thì các hệ quản trị CSDL còn phải có khả năng tự suy luận cũng như

hỗ trợ rút trích hiệu quả các tri thức từ khối dữ liệu vô cùng lớn mà nó lưu trữ

Phân tích cấu trúc

và các đặc tính của dữ liệu

Tập luật (rules) và sự kiện (facts)

Dữ liệu thô đầu vào Thông tin và tri

hệ quản trị CSDL suy diễn

Hình 1.1 Sự khác biệt giữa hai hình thức khai phá tri thức từ dữ liệu

Khai phá tri thức và tự sinh tri thức từ CSDL Hiển nhiên rằng các khái niệm rút trích thông tin (information

extraction) và khai phá tri thức (data mining / knowledge discovering) từ dữ liệu đã không còn là một lĩnh vực

xa lạ đối với chúng ta trong những năm gần đây Tuy nhiên, việc khai thác dữ liệu còn phụ thuộc quá nhiều vào việc phát triển các mô hình giải thuật, thuật toán, phương pháp,v.v thông qua việc nghiên cứu về cấu trúc của khối dữ liệu đã có Và hướng tiếp cận này chỉ có thể áp dụng được cho cụ thể trường hợp của khối dữ liệu đã

thức từ khối dữ liệu đã có sẵn, chúng ta có thể trực tiếp để CSDL tự sinh ra tri thức ngay từ khi dữ liệu mới được nạp vào hay không ? (minh họa Hình 1.1)

Bảng 1.1 Khác biệt giữa mô hình khai thác tri thức từ mô hình khai thác dữ liệu và áp dụng hệ CSDL suy diễn

Tiếp cận theo hướng xây mô hình/giải thuật

khai thác dữ liệu (data mining technique)

Tiếp cận theo hướng CSDL suy diễn (deductive and reasoning database) Phương pháp tiếp cận Thông qua việc phân tích khối dữ liệu có sẵn đã

biết trước và tri thức cần biết từ dữ liệu à xây dựng các giải thuật phù hợp để rút trích tri thức

Từ khối dữ liệu đã biết trước, thiết kế mô hình lưu trữ

và dựa tri thức của chuyên gia (con người) để định nghĩa các quy luật (rules) à hỗ trợ cho quá trình sinh tri thức mới từ dữ liệu

Linh hoạt trong sự mở

rộng của dữ liệu theo thời

gian

Tri thức được khai thác chỉ đúng cho khối dữ liệu được khai thác tại thời điểm đó Khi dữ liệu thay đổi (mở rộng) cần phải chạy lại mô hình để sinh lại tri thức mới tương ứng với khối dữ liệu mới đó

Có khả năng linh hoạt tự sinh ra tri thức mới khi có

dữ liệu được thêm vào (mở rộng), dựa trên các luật

đã được định nghĩa cũng như tri thức đã có của khối

Cần định nghĩa và quy định trước, và có thể sẽ tốn khá nhiều thời gian cho giai đoạn này Dữ liệu không được chuẩn hóa sẽ ảnh hưởng khá nhiều đến tri thức được sinh ra

Linh hoạt trong áp dụng

cho nhiều mô hình dữ liệu

khác nhau

Kém linh hoạt và chỉ có thể áp dụng cụ thể cho một loại dữ liệu nào đó mà thuật toán được thiết

kế (giao dịch, đồ thị, chuỗi thời gian, v.v.)

Có thể áp dụng được cho nhiều loại dữ liệu khác nhau, tùy thuộc vào hình thức tổ chức lưu trữ

Chi phí cho việc xây dựng

Gần như có thể đạt độ chính xác tuyệt đối nếu dữ liệu được chuẩn hóa tốt và sự đầy đủ cũng như chính xác của các luật được định nghĩa

liệu cần xử lý là vô cùng lớn, nhưng chúng ta không có đầy đủ sự hiểu biết về nó cũng như, kinh nghiệm chuyên gia,v.v để có thể rút ra được tập các quy luật tổng quát nhất Phù hợp cho việc xây dựng các hệ thống tư vấn, khuyến nghị và hỗ trợ ra quyết định với đặc thù độ chính

xác không yêu cầu phải là 100%

Yêu cầu phải có đầy đủ kiến thức nền tảng cũng như tri thức ở cấp độ chuyên gia để có thể xây dựng được các tập luật chuẩn cho khối dữ liệu lưu trữ Được áp dụng trong việc xây dựng các hệ chuyên gia trong ngôn ngữ, y tế, giáo dục, địa lý,v.v yêu cầu độ chính xác gần như tuyệt đối (100%), đóng vai trò làm nguồn

cơ sở tri thức cho các hệ thống trí tuệ nhân tạo

Hay nói cách khác hơn hệ CSDL lúc này cần đóng vai trò như là một hệ cơ sở tri thức tự suy luận based system), hay còn gọi là các hệ chuyên gia (expert system) Từ đó khái niệm về việc xây dựng một hệ CSDL có khả năng suy luận và hỗ trợ đưa ra kết luận/quyết định (deduction) được ra đời, hay còn gọi vắn tắt

(knowledge-là CSDL suy diễn (deduction database)

1.2 Sơ nét về lịch sử phát triển và các hệ CSDL suy diễn

1.2.1 Lịch sử phát triển của CSDL suy diễn

Cơ sở dữ liệu suy diễn [1] [2] [3] ban đầu được đề xuất do nhu cầu cần gom nhóm các mối quan hệ giữa các thành phần của dữ liệu được tổ chức trên nền tảng CSDL bảng quan hệ (RDBMS) để hình thành các quy luật tổng quát nhất, hỗ trợ cho việc rút trích dữ liệu được thuận tiện hơn Ví dụ: trong CSDL bảng quan hệ truyền thống, để thể hiện một mối quan hệ trực tiếp giữa hai thực thể ta phải dùng tối thiểu 1 bảng để biển diễn và lưu trữ mối quan hệ này, ta có thể biểu diễn như sau: 𝐴"#$𝐵, 𝐵"#$𝐶, 𝐵()*𝐷 v.v Ta có thể thấy CSDL bảng quan

hệ chỉ hiệu quả khi thể hiện các mối quan hệ hai ngôi trực tiếp, còn lại đối với các mối quan hệ gián tiếp, thì rất

khó để biểu diễn và mô hình hóa, ví dụ: các quan hệ gián tiếp như: 𝐴???𝐶, 𝐴???𝐷 Do đó, đòi hỏi CSDL quan

hệ cần được mở rộng hơn để có thể suy diễn và khái quát hóa hơn các mối quan hệ trên dựa trên các tập luật và mệnh đề logic Ví dụ: dựa trên logic mệnh đề và luật: “cha” của “cha” thì tức là “ông”, ta có thể suy ra: 𝐴ô./𝐶,

𝐴ô./𝐷 Đây là một trong các hạn chế lớn của CSDL quan hệ truyền thống, trong khả năng tổng quát hóa cũng như suy diễn các mối quan hệ của dữ liệu

Về ý tưởng xây dựng và nguyên lý, CSDL suy diễn được phát triển từ các đóng góp của Green, C Cordell và Raphael, Bertram (1968) [4], trong việc phát triển các ứng dụng và hệ thống hỏi-đáp (question-answer) (trong hai mô hình QA1 và QA2) Xuất phát từ ý tưởng ban đầu của Green và cộng sự trong việc dùng toán học logic

để mô tả và hệ thống mối quan hệ của dữ liệu Trong đó, việc áp dụng tư duy logic toán học trong lập trình, hay còn có thể gọi là sử dụng toán học với các ký hiệu, hàm, v.v như một ngôn ngữ lập trình, đóng vai trò rất quan trọng trong việc phát triển các ứng dụng CSDL suy diễn

Điển hình nhất trong lập trình logic (logic programming) là sự ra đời của ngôn ngữ Prolog (là cách viết tắt của

cụm từ tiếng Pháp “Programmation en logique”), được giới thiệu bởi Alain Colmerauer và Robert Kowalski

(1972) với mục tiêu là hỗ trợ mô tả lại bài toán trên ngôn ngữ của logic toán học Việc áp dụng áp lập trình logic trong CSDL nhằm hỗ trợ hiệu quả cho việc khai báo các luật cũng như các suy luận logic dựa trên mối quan hệ giữa các luật với dữ liệu được lưu trữ

Bảng chứa quan hệ [cha]-[con]

Bảng chứa quan hệ [anh]-[em]

anh

C

em

D

cha

A B

con

B C

Hình 1.2 Minh họa về sự hạn chế của CSDL bảng truyền thống trong việc thể hiện cũng như suy diễn các mối quan hệ của dữ liệu

Do đó, nhu cầu cần có một ngôn ngữ lập trình logic riêng dành cho CSDL, để hỗ trợ thiết lập, biểu diễn các luật cũng như truy vấn dữ liệu một cách hiệu quả, là vô cùng cần thiết Năm, 1977, Hervé Gallaire and Jack Minker

đã đề xuất về nhu cầu này cũng như những tiềm năng cho việc ứng dụng lập trình logic trong CSDL, và ngôn ngữ Datalog, do David Maier đề xuất, đã ra đời Có thể nói Datalog là một phân hệ con của ngôn ngữ lập trình logic Prolog được thiết kế để dành riêng cho các phát triển các hệ CSDL suy diễn Khác với Prolog, Datalog có một số đặc điểm riêng, điển hình như:

• Mô tả mối quan hệ và suy diễn dựa trên mệnh đề Horn (Horn clause)

• Các vị từ (predicate) không được đóng vai trò làm tham số (arguments)

• Thứ tự của các mệnh đề khai báo luật không quan trọng

• Có số lần lặp đệ quy là hưu hạn và phải kết thúc

• …

Từ nguyên lý của Datalog, hàng loạt các nền tảng CSDL suy diễn đã được xây dựng, điển hình như: LDL++,

DLV, CORAL, XSB, SDS, DUDUCE-2, Declare, ConceptBase, NAIL, v.v

1.2.2 Khái quát về luật, sự kiện và sự kiện, tri thức mới được sinh ra và suy diễn đệ quy

Ý tưởng xây dựng máy tính thành các hệ cơ sở tri thức có khả năng tự suy luận và hỗ trợ ra quyết định, thông qua việc nạp dữ liệu kèm theo các tri thức đã được lưa chọn, ở dạng các tập luật (rules) và sự kiện (facts) đã được kiểm chứng tính đúng đắn Bản chất của tri thức được nạp cho máy tính rất đơn giản, chúng tồn tại ở ba yếu tố sau, bao gồm:

• Luật (rule - r): là dạng các mẫu/quy luật ở dạng tri thức khẳng định là luôn đúng, đã được kiểm chứng

bởi con người (các chuyên gia)

• Sự kiện (fact - f): có thể xem là các nguồn dữ liệu của thông tin hay sự kiện đã diễn ra trong thực tế,

sự kiện sau khi được áp dụng luật (rule) để suy diễn sẽ giúp sinh ra các sự kiện hoặc tri thức mới

• Sự kiện mới (new fact – nf): là một dạng thông tin, sự kiện mới được sinh ra sau khi áp dụng một

luật cụ thể nào đó để suy luận ra Sự kiện, thông tin mới được suy từ tập luật đã có mang một giá trị được gọi là tri thức (knowledge)

Dựa ba yếu tố đã đề cập bên trên, chúng ta có một số ví dụ điển hình như sau (xem Bảng 1.2):

Bảng 1.2 Một số ví dụ về luật (rule), sự kiện (fact) và sự kiện mới (new fact) hoặc tri thức (knowledge) được sinh ra

(r1) Mọi con “chó sói phương bắc” đều có “4

chân” và “màu trắng” (f1) [Bấc] là một con “chó sói phương bắc” trong tác phẩm “Tiếng gọi nơi hoang dã” của

(r3) Mọi con “cóc” đều có “màu xanh”

(f2) Tí có nuôi một con “cóc” tên [Tía]

à (nf3) Tía có “màu xanh” (r4) Mọi động vật “màu xanh” đều có thể “dễ

• Từ luật (r1), chúng ta có một sự kiện mới (nf1), cho biết Bấc có 4 chân và có màu trắng vì sự kiện đầu vào (f1) đã cho biết Bấc là một con chó sói phương bắc Tiếp theo đó, dựa vào luật (r2), chúng ta sẽ biết được rằng Bấc cũng có khả năng ẩn mình trong tuyết (nf2), vì trong sự kiện mới được suy ra (nf1)

đã cho biết là Bấc có màu trắng

• Tương tự như bên trên, với sự kết hợp của luật (r2) và sự kiện (f2), chúng ta có thể kết luận Tía sẽ có màu xanh vì Tía là con cóc Và sự kết hợp của luật (r3) với sự kiện mới được sinh (nf3) chúng ta có thể tiếp tục suy ra rằng, Tía có thể dễn dàng ẩn mình trong rừng, vì Tía có màu xanh (nf4)

Với việc áp dụng các luật khác tiếp theo lên một sự kiện/tri thức mới - được sinh ra do các luật trước đó – điển hình như: r2(nf1) à nf2, r3(nf3) ànf4, v.v chúng ta gọi là suy diễn hay truy vấn dạng đệ quy (recursion) Ở các loại CSDL bảng truyền thống sử dụng ngôn ngữ truy vấn SQL, thì truy vấn đệ quy (recursive querying) là hầu như không hỗ trỡ, hoặc tốn rất nhiều tài nguyên tính toán cũng như không gian lưu trữ để cài đặt Truy vấn

đệ quy là một khái niệm rất quan trọng cũng như thế mạnh của CSDL suy diễn cũng như ngôn ngữ lập trình Datalog

1.3 Sự kết hợp của trí tuệ nhận tạo (AI), CSDL suy diễn & các ứng dụng đã được xây dựng

Xuyên suốt quá trình phát triển, các nhà khoa học máy tính luôn nổ lực không ngừng trong việc tìm kiếm và phát triển các giải pháp tốt, mạnh mẽ hơn để giúp máy tính có thể đạt được khả năng suy nghĩ như một con người Hay nói cách khác hướng đến việc xây dựng các cỗ máy tính sẽ có khả năng tự suy luận cũng như liên cập nhật các thông tin để làm giàu thêm cho kho tri thức của riêng nó, để ngày càng mạnh mẽ và thông minh hơn Thế mạnh của máy tính là nó có thể học và làm việc vô cùng nhanh và không cần nghĩ ngơi, cũng như khả năng lưu trữ, thu nạp dữ liệu gần như là vô hạn và CSDL suy diễn được coi là hạt nhân cho các hệ thống trí thông minh nhân tạo mà con người đã từng xây dựng Bản chất của tri thức máy tính được cung cấp là các tập

dữ liệu đã được kiểm chứng bởi con người và định nghĩa lại theo dạng các tập luật Có thể nói, tập luật (rules) đóng vai trò là nền tảng cơ bản nhất của các hệ CSDL suy diễn nói chung hay các hệ cơ sở tri thức, chuyên gia nói riêng Điển hình như một số hệ CSDL tri thức nổi tiếng, được phát triển dựa trên hình thức khai thác tập luật, như:

• Hệ chuyên gia phát hiện sự cố SHINE (Spacecraft Health Inference Engine), NASA: được phát triển

bới NASA và JPL vào những năm 1970, SHINE hỗ trợ phát hiện các sự cố, lỗi tiềm ẩn có thể xảy ra trong quá trình phóng tàu không gian hay các vệ tinh vào vũ trụ Sau đó tiếp tục được đánh giá và phát triển với đại học Berkeley, Mỹ SHINE có ưu điểm thiết kế vượt trội hơn so với các hệ chuyên gia phát

hiện sự cố cùng loại, với số lượng luật có thể được nạp và xử lý lên đến hơn 500 triệu luật

• Hệ chuẩn đoán và điều trị bệnh MYCIN: được phát triển trong những năm 1970, tại đại học Stanford,

Mỹ, MYCIN giúp hỗ trợ chuẩn đoán các trường hợp nhiễm bệnh do các loại vi khuẩn gây ra và hỗ trợ đưa ra các quyết định về việc sử dụng loại thuốc kháng sinh điều trị nào cho hiệu quả Ở giai đoạn

công bố ban đầu, MYCIN được nạp khoảng hơn 600 luật, được rút kết và thu thập trực tiếp từ dữ liệu

bệnh án, điều trị với sự hỗ trợ của các chuyên gia trong lĩnh vực y tế

• Hệ chuyên gia hỗ trợ thăm dò địa chất, khoan dầu Dipmeter Advisor: là một hệ chuyên gia được xây

dựng bởi công ty khai thác dầu mỏ Schlumberger vào thập niêm 1980, dưới sự hỗ trợ của MIT Với

hơn 90 tập luật được nạp vào, Dipmeter Advisor rất thành công trong việc hỗ trợ đưa ra các quyết

định trong quá trình khoan thăm dò các mỏ dầu, thông qua việc đánh giá các thuộc tính địa chất của lớp đất

1.4 Các đóng góp, tính mới và cấu trúc của bài tiểu luận

Trong bài tiểu luận này, nội dung nghiên cứu của chúng tôi chú trọng vào việc hoàn thành bốn mục đích chính sau, bao gồm:

• Nghiên cứu tổng quan về kiến trúc cũng như cơ chế hoạt động của CSDL suy diễn, các khái niệm liên quan đến CSDL mở rộng (EDB) và CSDL theo mục đích (IDB)

• Nghiên cứu về nguyên lý và nền tảng của ngôn ngữ lập trình luật dành cho CSDL, Datalog

• Tìm hiểu, cài đặt và thực hành một số ví dụ với ngôn ngữ Datalog thông qua phần mềm DES (deductive educational system) – được phát triển bởi P Julián-Iranzo và F Sáenz-Pérez, đại học UCM, Tây Ban Nha dành cho mục đích giảng dạy lập trình logic Datalog cũng như các ngôn ngữ truy vấn khác nhau trên CSDL

• Ứng dụng mô hình CSDL suy diễn và Datalog trong việc suy diễn các quan hệ trong mạng thông tin không đồng nhất (heterogeneous information network), hỗ trợ giải quyết các bài toán liên quan đến tìm đường giữa các thực thể trong mạng thông tin dựa trên meta-path Cài đặt và thực nghiệm mô hình trên mạng thông tin học thuật DBLP

Cấu trúc bài luận được tổ chức thành năm phần chính, bao gồm: giới thiệu tổng quan, cơ sở lý thuyết, hướng dẫn cài đặt và thực hành Datalog với phần mềm DES, áp dụng mô hình CSDL suy diễn trong khai thác mạng

thông tin không đồng nhất và cuối cùng là kết luận & hướng phát triển trong tương lai

2 CƠ SỞ LÝ THUYẾT VỀ CSDL SUY DIỄN VÀ NGÔN NGỮ LUẬT DATALOG

2.1 Cơ sở dữ liệu suy diễn và nền tảng logic

Có thể nói, CSDL suy diễn là một nền tảng kết hợp của mô hình CSDL quan hệ truyền thống và lập trình logic, trong đó lập trình logic được áp dụng để mô hình hóa dữ liệu, các mối quan hệ cũng như tập các luật được định nghĩa CSDL suy diễn được áp dụng rộng rãi trong việc xậy dựng nền tảng cho các ứng dụng liên quan đến trí tuệ nhân tạo, các hệ cơ sở tri thức và các hệ chuyên gia Về cơ bản, một hệ CSDL suy diễn có ba tính năng chính là: lưu trữ, truy vấn và suy diễn, bao gồm hai thành phần chính (minh họa Hình 1.1):

• Nền tảng lưu trữ dữ liệu: thường là các hệ quản trị CSDL quan hệ, với các kiến trúc cơ sở để đầy đủ

để tổ chức lưu trữ, truy vấn dữ liệu Chúng ta có thể coi nền tảng này đóng vai trò lưu trữ tập các sự kiện (facts), điển hình như các mô hình lưu trữ dạng bảng quan hệ mà chúng ta hay gặp ở các hệ quản

trị CSDL phổ biến như: Oracle, Microsoft SQL Server, MySQL, v.v hay còn được gọi là CSDL mở rộng (Extensional Database - EDB)

• Nền tảng logic/suy diễn: từ các dữ liệu và quan hệ lưu cơ sở được lưu trữ, thành phần này giúp suy diễn ra các thành phần dữ liệu và quan hệ mới mới Bản chất của nền tảng này là tập các luật (rules)

đã được định nghĩa Thông thường nền tảng này được xây dựng dưới sự hỗ trợ của một ngôn ngữ lập trình logic phi thủ tục, điển hình và phổ biến nhất được dùng là Datalog Ha còn được gọi là CSDL theo mục đích (Intentional Database - IDB)

Trước hết để có một cái nhìn tổng quan nhất về ngôn ngữ lập trình logic dành cho CSDL, Datalog, chúng ta cần nhìn lại sơ nét về ngôn ngữ tiên khởi/cha đẻ của nó là ngôn ngữ lập trình logic phi thủ tục, Prolog

Nền tảng lưu trữ và truy vấn dữ liệu

Lưu trữ sự kiện (fact)

Extensional Database - EDB

Intentional Database - IDB

Nền tảng suy diễn và sinh tri thức mới

Lưu trữ luật (rule)

Thông tin và tri thức có giá trị

Hình 2.1 Minh họa về kiến trúc của một hệ CSDL suy diễn 2.2 Các quy tắc logic, lập trình logic Prolog

Từ khi được giới thiệu lần đầu vào năm 1978 bởi Hervé Gallaire and Jack Minker, bởi sự đơn giản trong cú pháp lập trình nhưng vô cùng mạnh mẽ của nó, Prolog đã được chấp nhận cũng như áp dụng rộng rãi trong việc phát triển và xây dựng các ứng dụng trong nhiều khác nhau Prolog đặc biệt được áp dụng trong việc xây dựng các hệ cơ sở tri thức có khả năng tự suy diễn hay các ứng dụng liên quan đến trí tuệ nhân tạo và xử lý ngôn ngữ

tự nhiên Trong dự án xây dựng máy tính thế hệ thứ 5 của chính phủ Nhật, khởi động từ năm 1982, thì ngôn ngữ Prolog được chọn làm nền tảng lập trình chính Cú pháp của ngôn ngữ lập trình Prolog dựa trên các nguyên

lý của logic toán học, để giúp lập trình viên mô tả lại bài toán cho máy tính Nói cách khác đơn giản hơn, thì thông qua Prolog, chúng ta giúp cho máy tính hiểu được bài toán thông qua việc mô tả nó, rồi sau đó để máy tính tự tìm lời giải, đáp án cho chúng ta

Thông thường, chúng ta sẽ sử dụng các ký hiệu và quy tắc của ngôn ngữ lập trình Prolog để làm quy tắc logic chuẩn Một chương trình Prolog được cấu tạo bởi một hay nhiều mệnh đề (clause), thông thường mà mệnh đề Horn (Horn clause) Mỗi mệnh đề được xây dựng từ một hay nhiều vị từ (predicate), một vị từ dùng để phát biểu, kết luận về tập các đối tượng nào đó kết quả trả về sẽ ở dạng đúng (true) hay sai (false) (hay còn gọi là dạng dữ liệu Boolean) Một mệnh Horn có dạng cú pháp như sau (xem công thức 1):

Với,

• 𝑄, là đầu mệnh đề, đại diện cho một vị từ logic phần đầu của mệnh đề, thường đại luật hay kết luận,

dùng để thể hiện phát biểu logic của bài toán trong trường hợp tập vị từ P không rỗng (P ≠ ∅)

• 𝑃, là thân mệnh đề, đại diện cho tập các vị từ logic trong phần thân của mệnh đề, P5, P7, … , P=, thông thường mệnh đề dạng Horn, chỉ chứa phép toán tử “và” (AND ∧) giữa các vị từ Trong một số trường hợp tập P rỗng, thì mệnh đề được hiểu là một dạng mô tả sự kiện (fact) của bài toán

• : −, được quy định là điều kiện để luật/kết luận trả về kết quả đúng, đọc là “nếu” (if) Trong trường hợp biểu diễn bằng logic toán học thì có thể đại diện là dấu “←”, đọc là “kéo theo”

Trong lập trình Prolog, một vị từ được dùng như dạng một thủ tục/hàm, với các đối/tham số (arguments) được gọi là logic nguyên tử (logic atom), và mỗi logic nguyên tử biểu diễn mối quan hệ giữa các hạng (term), hay nói cách khác hạng và các logic nguyên tử thể hiện mối quan giữa giữa chúng cấu thành một mệnh đề Chúng

ta có 2 loại hạng phân biệt, bao gồm:

• Hạng sơ cấp (elementary term): là các đối ở dạng hằng số (constant) hay biến số (variable), tương

tự như trong các ngôn ngữ lập trình thủ tục, ví dụ, các dạng hàm như: f(1,2,3), f(1, a, b),v.v

• Hạng phức hợp (compound term): là một thủ tục hay hàm (function) chứa một hay nhiều đối Ví dụ:

f5(f7 1 ), f5(f7(a, b, c, d), v.v., giá trị trả về của hàm có thể thuộc bất kỳ loại dữ liệu nào

Trong ngôn ngữ lập trình Prolog, ký hiệu của vị từ (predicate), hàm (function) và các hạng (term) được bắt đầu bằng một chữ thường, ký hiệu các biến phải bắt đầu bằng một chữ cái viết hoa Các câu lệnh logic hoặc khai báo luật sẽ được viết dưới dạng các mệnh đề Horn (mô tả trong công thức 1), và quy ước khi kết thúc một mệnh

đề sẽ có dấu “.” Một mệnh đề logic trong Prolog có thể ở 3 dạng sau:

• Một sự kiện (fact): ký hiệu: … tương đương khi tập vị từ trong phần thân của mệnh đề, (P) là rỗng, (P = ∅), hay có thể hiểu theo cách khác có nghĩa là sự kiện là một luật mà kết quả luôn trả về là đúng

… ∶ −𝑡𝑟𝑢𝑒 Ví dụ: chúng ta có các mệnh đề ở dạng sự kiển như sau: 𝑐ℎó_𝑠ó𝑖(𝐵ấ𝑐) – mô tả một con chó sói tên Bấc, 𝑐𝑜𝑛_𝑐ó𝑐(𝑇í𝑎) – mô tả một con cóc tên Tía, v.v

• Một luật / kết luận (rule): ký hiệu: … :- … tương đương khi tập vị từ (P) là không rỗng, (P ≠ ∅),

gọi là luật vì nó sẽ biểu diễn cho các khẳng định hay phát biểu của mệnh đề logic trong bài toán, ví dụ

ta dung mệnh đề logic để phát biểu các luật như: 𝑐ℎó_𝑠ó𝑖_𝑝ℎươ𝑛𝑔_𝑏ắ𝑐 ∶ − 4_𝑐ℎâ𝑛 ∧ 𝑚à𝑢_𝑡𝑟ắ𝑛𝑔 – cho luật mọi con “chó sói phương bắc” đều có “4 chân” và “màu trắng”, hay 𝑐ó𝑐 ∶ − 𝑚à𝑢_𝑥𝑎𝑛ℎ – cho luật mọi con “cóc” đều có “màu xanh” Một mệnh đề có số lượng vị từ trong thân lớn hơn 1, hay

P > 1, thì được gọi là luật đệ quy

• Một truy vấn / câu hỏi (query/question): ký hiệu: ? − … , là một mệnh đề logic ở dạng câu hỏi cho

một sự kiện nào đó trong chương trình, kết quả trả về sẽ ở dạng Boolean, tức là đúng hay sai, ví dụ: cho câu hỏi ? − 𝑐ℎó_𝑠ó𝑖(𝐵ấ𝑐)., thì câu trả lời sẽ là đúng “true”, và ngược lại ? − 𝑐ℎó_𝑠ó𝑖(𝑇í𝑎)., sẽ trả về kết quả sai hay “false” – vì Tía là một con cóc

2.3 CSDL dựa trên logic với ngôn ngữ Datalog

Đươc phát triển trên ý tưởng của ngôn ngữ lập trình logic Prolog, Datalog là một ngôn ngữ lập trình dựa trên logic vị từ nhằm hỗ trợ cho việc truy vấn và suy diễn trên dữ liệu Tương tự như Prolog, tuy nhiên Datalog được thiết kế để dành riêng cho các hệ quản trị CSDL suy diễn, đặc thì cho việc truy vấn và suy diễn dữ liệu Trong nền tảng CSDL suy diễn, Datalog không chỉ hỗ trợ để mô tả dữ liệu cũng như mới quan hệ giữa chúng mà còn truy vấn cũng như suy diễn trên các mối quan hệ đó, nhằm mục đích sinh ra các quan hệ hay dữ liệu ở dạng tri thức mới Và hiển nhiên rằng nó được đánh giá tốt và mạnh mẽ hơn các ngôn ngữ truy vấn truyền thống, điển

hình như SQL Ưu điểm vượt trội của Datalog trong CSDL là khả năng suy luận theo dạng các luật đệ quy mà

các ngôn ngữ truy vấn truyền thống không thể làm được

Tương tự như Prolog, cú pháp của Datalog cũng được viết ở dạng các mệnh đề logic Horn để đặc tả cũng như suy diễn dữ liệu Một cú pháp của mệnh đề Horn, trong Datalog có dạng: 𝑄 ∶ − 𝑃 = P5∧ P7∧ … ∧ P= , tương

tự như trong Prolog, với:

• (P) là tập các vị từ trong thân mệnh đề, P = P5∧ P7∧ … ∧ P=, vì các mệnh đề logic trong Datalog đều theo chuẩn Horn, nên các phép liên kết các vị từ trong thân phải là phép hội, hay “∧” hoặc “AND”

• (Q) là vị từ đầu mệnh đề, nếu tập các vị từ trong thân không rỗng thì Q sẽ đại diện cho các kết luận hay luật, còn ngược lại thì sẽ đại diện cho sự kiện Trong trường hợp tập các vị từ trong thân có số lượng nhiều hơn một thì luật được định nghĩa sẽ ở dạng đệ quy

Các ký hiệu/cú pháp thường dùng trong lập trình Datalog (xem Bảng 2.1):

Bảng 2.1 Ký hiệu/cú pháp sử dụng trong Datalog

Các phép so sánh: <, >, <=, >=, =,

\= Các phép so sánh: <, >, ≤, ≥, =, ≠ Đại diện cho các phép so sánh vị từ trong một mệnh

đề logic Ví dụ: A > B, A == B, A<> B, v.v Phép kéo theo: “:-”, có thể đọc là

“nếu” Phép kéo theo: “←” Phép kéo theo dùng để liên kết hai mệnh đề, ví dụ:

A ← B, đọc là B kéo theo A, mệnh đề vế B đúng sẽ làm A đúng, điển hình như: 𝑐ó_4_𝑐ℎâ𝑛 ← 𝑐ℎó_𝑠ó𝑖 𝐵ấ𝑐 , 𝑐ó_𝑚à𝑢_𝑥𝑎𝑛ℎ ← 𝑐𝑜𝑛_𝑐ó𝑐 𝑇í𝑎 , v.v

Phép hội: “,” Phép hội: ∧ hoặc “AND” Dùng để liên kết hai hay nhiều mệnh đề, và chỉ đúng

khi tất cả mệnh đề đều đúng Ví dụ: A ← B ∧ C, A chỉ đúng khi cả B và C cùng đúng

Phép tuyển: “;” Phép tuyển: ∨ hoặc “OR” Dùng để liên kết hai hay nhiều mệnh đề, trả về kết

quả đúng khi chỉ cần một mệnh đề là đúng Ví dụ:

A ← B ∨ C, A đúng khi B hoặc C đúng

2.3.1 Các hình thức của mệnh đề logic trong Datalog

Tương tự như trong lập trình Prolog, tùy thuộc vào tập vị từ (P) trong thân, mà một mệnh đề sẽ được hiểu theo

ba cách khác nhau, bao gồm sự kiện (fact), luật (rule) và câu hỏi (question), chi tiết như sau:

2.3.1.1 Một sự kiện (fact) mô tả cho dữ liệu hoặc quan hệ

Ký hiệu: … , khi tập vị từ trong thân (P) rỗng, thì mệnh đề có tác dụng mô tả về một sự kiện (fact) của dữ liệu hoặc mối quan hệ của dữ liệu, ví dụ như sau:

• (f1): 𝑐ℎ𝑎(𝑇𝑢ấ𝑛, 𝑁𝑎𝑚), (f2): 𝑚ẹ(𝑁𝑔𝑎, 𝑁𝑎𝑚), (f3): 𝑐ℎ𝑎(𝑁𝑎𝑚, 𝐻ư𝑛𝑔) – mô tả cho mối quan hệ cha,

mẹ của Nam là lượt là Tuấn và Nga Trong trường hợp này ta có thể thấy một sự kiện trong Datalog đặc tả cho mối quan hệ trực tiếp của dữ liệu ví dụ: 𝑇𝑢ấ𝑛()*Nam, 𝑁𝑔𝑎sẹNam, 𝑁𝑎𝑚()*Hưng

• (f4): 𝑛ℎâ𝑛_𝑣𝑖ê𝑛(𝑇𝑢ấ𝑛, "𝑈𝐼𝑇", "𝐾𝐻&𝐾𝑇𝑇𝑇"), mô tả cho dữ liệu, Tuấn là một nhân viên làm việc tại trường ĐH UIT thuộc bộ môn KH&KTTT Ở đây ta có thể thấy, tương tự như trong CSDL quan hệ, một sự kiện trong Datalog cũng có thể biểu diễn ở dạng một bộ dữ liệu (tuple), với các thuộc tính khác nhau, điển hình trong trường hợp này ở dạng là: 𝑛ℎâ𝑛_𝑣𝑖ê𝑛 𝑡ê𝑛, đơ𝑛_𝑣ị_𝑐ô𝑛𝑔_𝑡á𝑐, 𝑝ℎò𝑛𝑔_𝑏𝑎𝑛

2.3.1.2 Một kết luận/luật (rule) suy diễn từ các sự kiện

Ký hiệu: … :- … , mệnh đề được xem là một kết luận hay luật để suy ra các sự kiện mới (new facts) trên

tập sự kiện đã có sẵn, ta có hai dạng luật chính như sau, bao gồm:

Luật không đệ quy:

• (r1): 𝑐ℎ𝑎_𝑚ẹ(𝑋, 𝑌) ← 𝑐ℎ𝑎(𝑋, 𝑌) ∨ 𝑚ẹ(𝑋, 𝑌) – từ sự kiện (f1): 𝑐ℎ𝑎(𝑇𝑢ấ𝑛, 𝑁𝑎𝑚) , (f2): 𝑚ẹ(𝑁𝑔𝑎, 𝑁𝑎𝑚), (f3): 𝑐ℎ𝑎(𝑁𝑎𝑚, 𝐻ư𝑛𝑔), ta có hai sự kiện mới là (nf1): 𝑐ℎ𝑎_𝑚ẹ(𝑇𝑢ấ𝑛, 𝑁𝑎𝑚), (nf2): 𝑐ℎ𝑎_𝑚ẹ(𝑁𝑔𝑎, 𝑁𝑎𝑚), (nf3): 𝑐ℎ𝑎_𝑚ẹ(𝑁𝑎𝑚, 𝐻ư𝑛𝑔) Luật này có thể hiểu theo cách khá đơn giản là:

“cha_mẹ” của một thực thể (X) nào đó là cấu thành của hai mệnh đề: “cha” của (X) và “mẹ” của (X), dấu “∨” hoặc “OR”, trong trường hợp này để chỉ, chỉ cần quan hệ “cha” hoặc “mẹ” thì đều có quan hệ

là “cha_mẹ” Trong Datalog ta có thể ghi đơn giản luật này như sau: 𝑐ℎ𝑎_𝑚ẹ(𝑋, 𝑌) ∶

− 𝑐ℎ𝑎(𝑋, 𝑌) ; 𝑚ẹ(𝑋, 𝑌)., ký hiệu “;” tương đương cho phép tuyển hoặc “OR”

• (r2): ô𝑛𝑔_𝑏à(𝑋, 𝑌) ← 𝑐ℎ𝑎_𝑚ẹ(𝑋, 𝑍) ∧ 𝐜𝐡𝐚_𝐦ẹ(𝑍, 𝑌), tương tự như luật trên, ta có thể phát biểu một cách vắn tắt như sau: cha mẹ (X) của một thực thể (Z) nào đó, mà (Z) lại là cha mẹ của một thực thể (Y), thì mối quan hệ giữa (X) và (Y) là ông bà Điều kiện liên kết của hai mệnh đề trên là phép hội, đại diện cho dấu “∧” hoặc “AND” Tức có nghĩa là cả hai mệnh đề: (X) là “cha_mẹ” của (Z( và (Z) cũng phải là “cha_mẹ” của (Y), cả 2 đều phải cùng đúng – thì (X) mới được gọi là “ông_bà” của (Y) Như vậy, với ví dụ trên ta có thể suy ra hai sự kiện mới là: (nf4) ô𝑛𝑔_𝑏à(𝑇𝑢ấ𝑛, 𝐻ư𝑛𝑔), (nf5) ô𝑛𝑔_𝑏à(𝑁𝑔𝑎, 𝐻ư𝑛𝑔) Trong Datalog ta có thể ghi đơn giản lại luật này như sau: 𝑐ℎ𝑎_𝑚ẹ(𝑋, 𝑌) ∶

− 𝑐ℎ𝑎(𝑋, 𝑌) , 𝑚ẹ(𝑋, 𝑌)., ký hiệu “,” tương đương cho phép hội hoặc “AND”

Luật đệ quy (recursion rule):

mẹ cha Nam

Hưng cha

Hình 2.2 Minh họa một bài toán điển hình được giải quyết bằng đệ quy

Là các luật mà trong chính định nghĩa của nó có gọi lại chính nó, khả năng định nghĩa các luật đệ quy là một điểm mạnh của Datalog, vì nó cho phép thực hiện các truy vấn phức tạp vét cạn theo chiều sâu của dữ liệu, điển hình như các bài toán tìm nút gốc, tổ tiên trong cây gia phả gia đình, tìm tất cả các cấp quản lý mà một nhân

viên trực thuộc trong một công ty, bài toán tìm đường đi giữa hai điểm trong đồ thị, v.v Để hiểu rõ hơn vấn đề, chúng ta sẽ đi qua các ví dụ với một số bài toán điển hình sau:

Bài toán tìm tổ tiên của một người Đây là bài toán điển hình nhất trong các bài toán cần phải giải bằng đệ

quy, cho cây gia phả (như Hình 2.2-A), chúng ta có các luật và sự kiện sau:

Với luật (r1) thì chúng ta chỉ biết được “cha_mẹ” của một người (X) nào đó là sự kết hợp của 2 sự kiện “cha”

và “mẹ” Tuy nhiên, bài toán đặt ra là làm thế nào để lấy được danh sách các tổ tiên của (X) thông qua tìm kiếm cấp cao hơn là: “cha_mẹ” của “cha_mẹ” (X), rồi lên một cấp nữa là “cha_mẹ” của “cha_mẹ” của “cha_mẹ”,v.v

là số lương cấp này chúng ta không biết trước Do đó, để trả lời được câu hỏi này chúng ta phải định nghĩa một luật ở dạng đệ quy như sau:

• (r3): 𝑡ổ_𝑡𝑖ê𝑛(𝑋, 𝑌) ← 𝑐ℎ𝑎_𝑚ẹ(𝑋, 𝑍) , 𝑡ổ_𝑡𝑖ê𝑛(𝑍, 𝑌)

Luật này có thể diễn giải lại một cách đơn gian như sau, tìm kiếm cha mẹ (X) của một thực thể (Z) nào đó, với (Z) là tổ tiên của (Y) Bản chất của luật này có tính đệ quy vì chúng ta thấy vị từ đại diện cho luật đề xuất hiện trong đầu và thân của mệnh đề

Bài toán tìm các cấp quản lý trực thuộc Tương tự như bài toán tìm tổ tiên của một người dựa trên cây gia

phả, cho một cơ chế các cấp quản lý của một đơn vị như sau (Hình 2.2-B), ta cũng có một loạt các sự kiện (facts) như sau:

• Các sự kiện (facts) đã biết:

§ (f5): 𝑞𝑢ả𝑛_𝑙ý(𝑁𝑔ọ𝑐, 𝑇𝑢ấ𝑛) (“Ngọc” là quản lý của “Tuấn”)

§ (f6): 𝑞𝑢ả𝑛_𝑙ý(𝐻à, 𝑁𝑔ọ𝑐)

§ (f7): 𝑞𝑢ả𝑛_𝑙ý(𝑇ℎ𝑎𝑛ℎ, 𝐻à)

Câu hỏi đạt ra là làm sao để tìm cấp quản lý cao nhất của một nhân viên (X) nào đó, bắt đầu từ cấp trực thuộc của họ, và số lượng cấp là chúng ta không biết trước Để làm được việc này chúng ta cũng sẽ thiết lập một luật theo dạng đệ quy như sau:

• (r4): 𝑡ì𝑚_𝑞𝑢ả𝑛_𝑙ý(𝑋, 𝑌) ← 𝑞𝑢ả𝑛_𝑙ý(𝑋, 𝑍) , 𝑡ì𝑚_𝑞𝑢ả𝑛_𝑙ý(𝑍, 𝑌)

Luật trên khi được thực thi, sẽ giúp chúng ta tìm tất cả các cấp quản lý của một thực thể nào đó, ví dụ: 𝑡ì𝑚_𝑞𝑢ả𝑛_𝑙ý(𝑋, 𝑇𝑢ấ𝑛), sẽ lần lượt là: “Ngọc”, “Hà”, “Thanh”, v.v dựa trên tập sự kiện đã được định nghĩa

Bài toán tìm đường đi giữa hai đỉnh của đồ thị Đây cũng là một bài toán khá điển hình trong việc áp dụng

đệ quy để suy diễn Cho một đồ thị có hướng, ký hiệu: G = (V, E), với (V) đại diện cho tập các đỉnh/nút (vertex) của đồ thị, còn (E) đại diện cho tập các cạnh/cung (edge) của đồ thị Tương tự vậy, dựa trên đồ thị như hình

minh họa (Hình 2.2-C), ta cũng có tập các sự kiện (facts) được biết trước, như sau:

• Các sự kiện (facts) đã biết:

§ (f8): 𝑐ạ𝑛ℎ(𝑎, 𝑏)

§ (f9): 𝑐ạ𝑛ℎ(𝑎, 𝑐)

§ (f10): 𝑐ạ𝑛ℎ(𝑐, 𝑏)

§ (f11): 𝑐ạ𝑛ℎ(𝑏, 𝑑)

Bài toán đặt ra là tìm tất cả các cạnh nối giữa hai nút, ví dụ (a) và (d), bài toán này chúng ta sẽ thấy tương tự như việc giải quyết bài toán tìm đường đi (path) và tìm đường đi ngắn nhất (shortest path) trong lý thuyết đồ thị Ở góc nhìn của lập trình logic Datalog thì chúng ta có thể giải quyết bài toán này rất đơn giản bằng một luật

đệ quy như sau:

• (r5): 𝑡ì𝑚_đườ𝑛𝑔_đ𝑖(𝑋, 𝑌) ← 𝑐ạ𝑛ℎ(𝑋, 𝑍) , 𝑡ì𝑚_đườ𝑛𝑔_đ𝑖(𝑍, 𝑌)

Luật trên có thể diễn giải như sau, tìm cạnh nối (X) với một đỉnh (Z) nào đó, với (Z) là một đỉnh nối với (Y)

Ví dụ ta sẽ tìm đường đi, tập hợp các cạnh nối giữa hai đỉnh (a) và (d), 𝑡ì𝑚_đườ𝑛𝑔_đ𝑖(𝑎, 𝑑), bao gồm: [a → b,

b → d] và [a → c, c → b, b → d], v.v

2.3.2 Một câu hỏi (question/query) từ sự kiện và luật

Ký hiệu: ? − … , về cơ bản thì một câu hỏi trong lập trình Datalog giống như một việc ta gọi một hàm với các đối/tham số trong lập trình thủ tục, kết quả trả về có thể ở nhiều dạng khác nhau như ở dạng Boolean, hoặc các

sự kiện đã được mô tả, ví dụ:

• ? − 𝑐ó_𝑝ℎả𝑖_𝑐ℎ𝑎_𝑚ẹ(𝑋, 𝑌), với (X) và (Y) là các tham số, câu hỏi này muốn hỏi có phải thực thể (X)

là “cha_mẹ” của thực thể (Y) hay không ?, là một dạng câu hỏi đúng/sai, do đó với một câu hỏi trên ta

sẽ có kết quả đúng (true) cho: 𝑐ó_𝑝ℎả𝑖_𝑐ℎ𝑎_𝑚ẹ(𝑇𝑢ấ𝑛, 𝑁𝑎𝑚) , và sai (false) cho

? − 𝑐ó_𝑝ℎả𝑖_𝑐ℎ𝑎_𝑚ẹ(𝑇𝑢ấ𝑛, 𝐻ư𝑛𝑔), v.v

• ? − 𝑐ℎ𝑎_𝑚ẹ(𝑋, 𝑌), với (Y) là tham số đầu vào, dạng câu hỏi này là yêu cầu liệt kệt tất cả các thực thể

mà là “cha_mẹ” của (Y), là (X), câu trả lời hiển nhiên sẽ là một danh sách các thực thể mà có quan hệ

là “cha” hoặc “mẹ” của thực thể đầu vào (Y) ví dụ: 𝑐ℎ𝑎_𝑚ẹ(𝑌, 𝑁𝑎𝑚), với kết quả trả về sẽ là “Tuấn”

Sự kiện(fact) Luật(rule)

Hình 2.3 Ví dụ về đồ thị luật biểu diễn sự tương quan giữa các sự kiện và luật

Trong lập trình Datalog, để biểu diễn sự tương quan giữa các sự kiện và luật với nhau trong một chương trình,

ta dùng đồ thị luật để biểu diễn các mối tương quan này Về bản chất, đồ thị luật là một đồ thị có hướng mà mỗi nút trong đồ thị đại diện cho một sự kiện hay luật Đối với một luật cụ thể (Q), đại diện bởi một nút, các cạnh

có hướng, liên kết các nút khác đến nút đó (in-coming degrees), chỉ số lượng các luật có trong thân (P, P = P5∧

P7∧ … ∧ P=) của luật đó, ký hiệu: 𝑄: −𝑃

Trong lập trình Datalog, việc xây dựng đồ thị luật giúp chúng ta có cài nhìn tổng quan hơn về các luật được định nghĩa cũng như sự phụ thuộc của chúng với nhau Ngoài ra đồ thị luật cũng giúp chúng ta tránh được việc định nghĩa các luật trùng lắp nhau hoặc dư thừa không cần thiết

Ví dụ, với danh mục các sự kiện và như sau, ta sẽ xây dựng được một đồ thị luật như minh họa tại hình bên

Một phép toán cơ bản hỗ trợ trong lập trình Datalog

Trong lập trình Datalog, để đơn giản hơn cho quá trình lập trình cũng như biểu diễn các luật dễ dàng hơn Datalog hỗ trợ một số hàm tính toán tổ hợp cơ bản như sau (xem Bảng 2.2):

Bảng 2.2 Một số phép toán tổ hợp được hỗ trợ trong Datalog

Đếm (count): count Đếm số lượng các sự kiện có trong danh sách trả về, ví dụ:

• 𝑐𝑜𝑢𝑛𝑡(𝑛ℎâ𝑛_𝑣𝑖ê𝑛(_, "𝑈𝐼𝑇"), 𝑡ổ𝑛𝑔) – đếm tổng số lượng nhân viên hiện có của trường đại học UIT

Tổng tích lũy (cumulative sum): sum Dùng để tính tổng giá trị các phần tử có trong danh sách sự kiện trả về, ví dụ:

• 𝑠𝑢𝑚(𝑛ℎâ𝑛_𝑣𝑖ê𝑛(_, "𝑈𝐼𝑇", 𝑙ươ𝑛𝑔), 𝑙ươ𝑛𝑔, 𝑡ổ𝑛𝑔_𝑙ươ𝑛𝑔) – tính tổng lương tất cả giảng viên, nhân viên của trường đại học UIT

Tính trung bình (average): avg Trả về giá trị trung bình của các phần tử có trong danh sách sự kiện trả về, ví dụ:

• 𝑎𝑣𝑔(𝑛ℎâ𝑛_𝑣𝑖ê𝑛(_, "𝑈𝐼𝑇", 𝑙ươ𝑛𝑔), 𝑙ươ𝑛𝑔, 𝑎𝑣𝑔_𝑙ươ𝑛𝑔) – tính trung bình lương tất cả giảng viên, nhân viên của trường đại học UIT

Lấy giá trị nhỏ nhất (minimum): min Trả về giá trị nhỏ nhất của các phần tử có trong danh sách sự kiện trả về, ví dụ:

• 𝑚𝑖𝑛(𝑛ℎâ𝑛_𝑣𝑖ê𝑛(_, "𝑈𝐼𝑇", 𝑙ươ𝑛𝑔), 𝑙ươ𝑛𝑔, 𝑚𝑖𝑛_𝑙ươ𝑛𝑔) – lấy giá trị lương thấp nhất của giảng viên, nhân viên trường đại học UIT

Lấy giá trị lớn nhất (maximum): max Trả về giá trị lớn nhất của các phần tử có trong danh sách sự kiện trả về, ví dụ:

• 𝑚𝑎𝑥(𝑛ℎâ𝑛_𝑣𝑖ê𝑛(_, "𝑈𝐼𝑇", 𝑙ươ𝑛𝑔), 𝑙ươ𝑛𝑔, 𝑚𝑎𝑥_𝑙ươ𝑛𝑔) – lấy giá trị lương lớn nhất của giảng viên, nhân viên trường đại học UIT

2.3.4 Sự tương quan giữa Datalog và đại số quan hệ (Relational Algebra)

Về mặt cơ bản và các tính chất trong logic toán học, thì với các luật hoặc câu hỏi trong Datalog mà không ở dạng đệ quy được xem là tương đương với các phép toán trong đại số quan hệ Điển hình như các phép toán hai ngôi, như sau (xem Bảng 2.3):

Bảng 2.3 Mô tả một số phép toán quan hệ và sự tương quan với Datalog

Phép kết nối (Join): là tập hợp các luật có

cùng đầu luật và có biến chung ở các vị từ

trong thân luật (P), có dạng:

Phép chọn (Selection): là các luật mà trong

thân luật có chứa vị từ so sánh

Ví dụ, ta muốn tìm kiếm tổ tiên của một thực thể (Y) nào đó, trong đó (Y) được chọn

là “Hưng”, câu hỏi sẽ được định nghĩa theo dạng phép chọn, như sau:

• 𝑡ổ_𝑡𝑖ê𝑛(𝑋, 𝑌) :- 𝑡ổ_𝑡𝑖ê𝑛(𝑋, 𝑌), 𝑌 = "𝐻ư𝑛𝑔"

Hoặc, tìm kiếm danh sách các nhân viên làm việc tại bộ môn KH&KTTT, như sau:

• 𝑛ℎâ𝑛_𝑣𝑖ê𝑛(X, "UIT", Z), Z = “KH&KTTT”

Phép hiệu (Difference): là luật mà trong

thân có dùng điều kiện trừ, để lọc bỏ các giá

trị trả về thuộc một tập nào đó Điều kiện

lọc ký hiệu bằng dấu “-”, và “NOT” trong

Datalog

Ví dụ: tìm danh sách tất cả tổ tiên, nhưng không lấy ông bà (nội/ngoại):

• 𝑡ổ_𝑡𝑖ê𝑛(𝑋, 𝑌) :- 𝑡ổ_𝑡𝑖ê𝑛(𝑋, 𝑌) and NOT ô𝑛𝑔_𝑏à(𝑋, 𝑌)

Như vậy chúng ta có thể thấy rằng ngôn ngữ lập trình Datalog có đầy đủ các yếu tố và các phép toán của đại số quan hệ, hay nói cách khác hơn, nó là một dạng của đại số quan hệ và sử dụng logic để định nghĩa các luật theo các phép toán trong đại số quan hệ Tuy nhiên, Datalog có một tính năng mạnh mẽ hơn là có khả năng định nghĩa các luật theo dạng đệ quy, đầu luật của mệnh đề có thể xuất hiện lại trong thân của luật

2.4 Giới thiệu về ngôn ngữ SQL3 và truy vấn đệ quy

Được coi là một phần mở rộng của ngôn ngữ SQL truyền thống, SQL3 lần đầu được giới thiệu vào năm 1999, hay còn được gọi là SQL-99 Tương tự như các phiên quản SQL1 (1989) và SQL2 (1992, phiên bản phổ biến nhất), SQL3 có đầy đủ các tính năng về khai báo các loại kiểu dữ liệu cũng như hình thức truy vấn, ngoài ra SQL3 còn được mở rộng thêm khả năng truy vấn hồi quy (recursion querying) Cách phổ biến nhất để khai báo một truy vần hồi quy với SQL3, là chúng ta sẽ viết dưới dạng một thủ tục (view procedure) khởi tạo một view trong CSDL kết hợp với thủ tục “WITH RECURSIVE” được hỗ trợ Lấy ví dụ về bài toán tìm tổ tiên trong cây

gia phả, chúng ta có một bản để lưu trữ quan hệ [cha]-[con] và [mẹ]-[con], như sau (xem Bảng 2.4 và Bảng

2.5), câu hàm thủ tục tạo view truy vấn đệ quy nhằm mục đích liệt kê danh sách các tổ tiên của một người như

sau (xem Thuật toán 1):

1: create view cha_mẹ(cha_mẹ, con) as

5: create view tổ_tiên(tổ_tiên, hậu_duệ) as

6: with recursive rec_tổ_tiên(tổ_tiên, hậu_duệ) as

10: from cha_mẹ, rec_tổ_tiên

11: where cha_mẹ.con = rec_tổ_tiên tổ_tiên

12: select * from rec_tổ_tiên;

Về mặt mục đích đạ được, thì truy vấn đệ quy trong SQL3 vẫn có thể hỗ trợ chúng ta tìm kiếm và rút trích dữ liệu theo chiều sâu một cách hiệu quả Tuy nhiên, vì cấu trúc syntax quá phức tạp khi khai báo một thủ tục đệ quy, do đó ngôn ngữ SQL3 hầu như không được phổ biến rộng rãi

3 CÀI ĐẶT VÀ LẬP TRÌNH DATALOG VỚI CÔNG CỤ DES (DEDUCTIVE EDUCATIONAL SYSTEM)

DES (Datalog Educational System)[*] là một phần mềm mã nguồn mở được phát triển bởi P Julián-Iranzo và

F Sáenz-Pérez, đại học UCM Phần mềm DES được xây dựng dành cho mục đích giáo dục và thực hành ngôn ngữ Datalog, nó cung cấp một môi trường tương tác và lập trình Datalog, SQL mạnh mẽ

3.1 Hướng dẫn cài đặt và chạy phần mềm DES

Được phát triển dựa trên ngôn ngữ lập trình Prolog và Java, do đó DES có thể tương thích với nhiều nền tảng khác nhau bao gồm Windows, Linux và MacOS Để cài đặt phần mềm DES trên máy tính, chúng ta tiến hành download phần mềm này tại địa chỉ chính thức sau: http://des.sourceforge.net/html/download.html Tùy theo,

hệ điều hành của máy tính mà chúng ta sẽ lựa chon phiên bản cho phù hợp Sau khi tải hoàn tất về máy tính, phần mềm sẽ được đóng gói dạng file nén “.zip”, chúng ta bung nén và chạy file “des_acide.jar” để chạy phiên bản có giao diện của phần mềm

Hình 3.1 Giao diện chính của phần mềm DES

Lưu ý vì phần giao diện của phần mềm chạy trên nền tảng Java nên chúng ta cũng cần lưu ý cài Java trên máy Giao diện chính của DES, bao gồm:

• Project explorer: quản lý các file và project đã được tạo

• File/code editor: trình hỗ trợ soạn thảo file/code

• Console: hỗ trợ tương tác bằng dòng lệnh (command) với thư viện của DES

* Phần mềm DES: http://des.sourceforge.net/index.html