Mở đầu Về lịch sử, các nhà nghiên cứu đã cố gắng mô hình hoá các ngôn ngữ truy vấn cơ sở dữ liệu thông qua logic. Các tính toán quan hệ đƣợc sinh ra nhƣ vậy là các ngôn ngữ truy vấn dựa trên logic bậc một. Từ cuối những năm 70 ngƣời ta đã tìm cách hiểu một cách toàn cục về các cơ sở dữ liệu thông qua logic. Điều đó cho phép chỉ ra rằng một hệ quản trị cơ sở dữ liệu là một chứng minh của các lý thuyết rất cụ thể, lý luận trên các sự kiện (fact) và cho các chứng minh của lý thuyết biểu diễn câu hỏi.
Các công trình ban đầu trong các hệ quản trị cơ sở dữ liệu suy luận bao gồm không chỉ là các sự kiện mà còn bao gồm cả các quy tắc (rule) suy diễn đƣợc diễn đạt theo logic bậc một xuất hiện ở CERT (Toulouse) vào cuối thập kỷ 70-80. Các công trình này tập trung vào việc hiểu các cơ sở dữ liệu suy diễn thông qua logic. Để cho phép quản trị các cơ sở kiến thức lớn ( hàng nghìn luật kết hợp với hàng triệu hàng tỷ sự kiện), các vấn đề nghiên cứu đầy đủ đã đƣợc giải quyết. Các vấn đề này nằm ở giao điểm của các cơ sở dữ liệu và trí tuệ nhân tạo và biểu thị các khía cạnh vừa lý thuyết, vừa thực tiễn.
Từ quan điểm lý thuyết, các tiếp cận thông qua logic cho phép hiểu tốt hơn các ngôn ngữ của hệ quản trị cơ sở dữ liệu, các cơ cấ u lý luận ở dƣới và các kỹ thuật tối ƣu. Từ quan điểm thực tiễn, sự phát triển của hệ quản trị cơ sở dữ liệu dựa trên logic hỗ trợ sự suy diễn dẫn đến các nguyên mẫu thao tác. Chƣơng này trƣớc tiên trình bày nhập môn về các khái niệm cơ bản của logic cần thiết để hiểu tốt cơ sở dữ liệu. Một cơ sở dữ liệu logic đƣợc xem nhƣ là một thể hiện của một ngôn ngữ logic.
Đó là một tập hợp các sự kiện đƣợc liệt kê trong các bảng. Chƣơng này cũng trình bày các ngôn ngữ logic truy vấn các cơ sở dữ liệu, đó là các tính toán miền và bộ. Chung là một sự hình thức hoá các ngôn ngữ của các cơ sở dữ liệu quan hệ .Datalog002 TIEU LUAN MOI download : skknchat@gmail.2 Logic bậc một 1.1 Cú pháp của logic bậc một Logic bậc một ( first-order logic), còn đƣợc gọi là phép tính vị từ, nó đóng vai trò quan trọng trong việc biểu diễn tri thức, là một ngôn ngữ hình thức đƣợc sử dụng để biểu diễn các thuộc tính của các đối tƣợng, quan hệ giữa các đối tƣợng và để suy diễn các quan hệ mới từ các quan hệ đã biết. Nó cũng có thể đƣợc xem nhƣ một hình thức đƣợc sử dụng để dịch cá c câu và suy diễn ra các câu mới từ các câu đã biết.
Logic bậc một dựa trên một bảng ký tự sử dụng các ký hiệu sau: a. Các biến, đƣợc ký hiệu là x, y, z,…. Các hằng, ký hiệu là a, b, c, true, false … c. Các vị từ, ký hiệu là P, Q, R, ….
Mỗi vị từ có thể nhận một số các tham đối cố định ( n tham đối với một vị từ n-ngôi) d. Các kết nối logic : , , , , e. Các hàm, ký hiệu là f, g, h,…, mỗi hàm có thể nhận một số có định các tham đối ( n tham đối với một hàm n ngôi). Các dấu mở ngoặc „(„ và đóng ngoặc „)‟.
Các quy tắc cú pháp đơn giản cho phép xây dựng các công thức. Một hạng (term) đƣợc định nghĩa một cách đệ quy nhƣ là một biến, một hằng hoặc là kết quả của việc áp dụng một hàm vào một hạng.1: Cho x là một biến, a là một hằng, f là một hàm thì x, a, f(x) và f(f(x)) là các hạng. Một công thức tốt (WFF-Well Formed Formular) của một phép tính vị từ là bất kỳ công thức nào bao gồm các lƣợng từ đƣợc kết hợp bởi các toán tử kết nối logic và các định lƣợng logic đƣợc kết hợp với tên biến, theo qui tắc: 10 (LUAN.Datalog002 TIEU LUAN MOI download : skknchat@gmail. Nếu P là một vị từ có n đối, và t1, t2,…., tn là các hạng thì P(t1,t2,….,tn) là một công thức nguyên tử.
Nếu F1, F2 là các công thức, khi đó F1 F2, F1F2, F1F2, F1 F2 và F2 là các công thức. Nếu F là một công thức và x là một biến không bị ràng buộc bởi các định lƣợng (đƣợc gọi là biến tự do) trong F, khi đó x F và x F là các công thức. Để chỉ ra mức ƣu tiên giữa các phép kết nối logic, có thể sử dụng các dấu ngoặc: Nếu F là một công thức đúng thì (F) cũng đúng. Để tránh các dấu ngoặc trong một số trƣờng hợp đơn giản, ta sử dụng mức ƣu tiên của các phép toán logic theo thứ tự giảm dần nhƣ sau : , , , .2: Dƣới đây là một số ví dụ về công thức hình thức: P(a,x) Q(x,y) Q(x,y) xy(Q(x,y) P(a,x)).
Để đƣa ra các ví dụ dễ đọc hơn về công thức, ta chọn một từ điển ít hình thức hơn, các vị từ và các hàm là các tên hoặc các động từ của ngôn ngữ hàng ngày và các hằng là các dãy ký tự ký hiệu các ph òng, các ngƣời làm.3: Dƣới đây là các ví dụ về công thức gần với ngôn ngữ tự nhiên: PHONG(Tinhoc, Nam) NGUOILAM(Tinhoc, Mai).Datalog002 TIEU LUAN MOI download : skknchat@gmail.2 Ngữ nghĩa của logic vị từ bậc một Nói đến ngữ nghĩa của logic vị từ bậc một là chúng ta nói đến ý nghĩa của các công thức trong một thế giới thực nào đó mà ta gọi là một minh họa. Một công thức có thể đƣợc giải thích nhƣ là một câu trên một tập hợp các đối tƣợng: có khả năng cho nó một ý nghĩa đối với tập hợp đối tƣợng này. Để thực hiện đƣợc điều đó cần phải gán một đối tƣợng cụ thể với mỗi hằng hay mỗi ký hiệu hằng sẽ đƣợc gắn với một đối tƣợng cụ thể trong tập hợp các đối tƣợng. Ví dụ, ta gán một đối tƣợng là phòng tin học của một công ty với hằng Tinhọc, nhân viên Mai gán với hằng Mai,v.
Tập hợp các đối tƣợng đƣợc xem xét đƣợc gọi là miền thảo luận; nó đƣợc ký hiệu là D. Mỗi hàm với n đối đƣợc giải thích nhƣ là một hàm từ Dn vào D. Một vị từ biểu diễn một quan hệ cụ thể giữa các đối tƣợng của D, nó có thể nhận giá trị đúng hoặc sai. Định nghĩa quan hệ này trở thành định nghĩa các bộ đối tƣợng thoả mãn vị từ.
Tập hợp các bộ thoả mãn vị từ tạo thành mở rộng của nó .1: Miền thảo luận ( Domain of Discourse) Miền thảo luận là tập hợp các đối tượng mà trên đó một công thức logic nhận giá trị thông qua việc minh hoạ các hằng như là các đối tượng cụ thể, các biến như là các đối tượng nào đó, các vị từ như là các quan hệ giữa các đối tượng và các hàm như là các hàm cụ thể giữa các đối tượng.4 : Công thức : xy((LANHDAO(x,y) LANHDAO(y,x) CUNGPHONG(x,y)) có thể đƣợc minh họa trên tập hợp ngƣời { Nam, Trung, Mai}, tạo ra một miền thảo luận. LANHDAO có thể đƣợc giải thích nhƣ là một quan hệ hai ngôi “Là sếp của”; CUNGPHONG có thể đƣợc giải thích nhƣ là một quan hệ 12 (LUAN.Datalog002 TIEU LUAN MOI download : skknchat@gmail.Datalog002 hai ngôi “ làm việc cùng phòng”. Công thức là đúng nếu Nam, Trung và Mai làm việc cùng một phòng.5 : Công thức x(x SUCC(x)) cho một miền thảo luận là vô hạn đối với minh hoạ của nó. Thật vậy, công thức này có thể đƣợc minh hoạ trên tập hợp các số nguyên dƣơng {1, 2, 3, ….}, là vô hạn.
Khi đó „<‟ là quan hệ “là nhỏ hơn” và SUCC là hàm liên kết với mọi số nguyên tiếp theo sau của nó. Do đó, công thức này đúng trên các số nguyên. Nhƣ vậy, cho trƣớc một minh hoạ của một công thức trên một miền thảo luận, có thể liên kết một giá trị chân lý với một công thức. Để tránh sự mập mờ (các công thức có thể có nhiều giá trị chân lý), chúng ta chỉ xem xét các công thức trong đó mọi biến đều bị ràng buộc bởi các định lƣợng, gọi là các công thức đóng.
Mọi công thức đóng F có một có một giá trị chân lý duy nhất đối với một dữ liệu minh hoạ trên một miền thảo luận D. Giá trị đó đƣợc ký hiệu là V(F) và tính toán nhƣ sau: V(F1 F2) = V(F1) V(F2) V(F1 F2) = V(F1) V(F2) V(F1) = V(F1) V(xF) = V(Fx = a) V(Fx=b)… trong đó a,b,.là các hằng của D V(xF) = V(Fx=a) V(Fx=b)… trong đó a,b,… là các hằng của D V(P(a,b,…)) = TRUE nếu [a,b,… ] thoả mãn quan hệ P và FALSE nếu không. Một mô hình của một công thức logic là một minh hoạ trên một miền thảo luận mà miền đó làm cho công thức đúng.5, các số nguyên là một mô hình đối với công thức x(x<SUCC(x)) với minh họa đƣợc chỉ ra nhƣ trên. Thật vậy, bằng việc các quy tắc ở trên, ta tính: V(x(x<SUCC(x)))= V(1<2) V(2<3) V(3<4).Datalog002 TIEU LUAN MOI download : skknchat@gmail.3 Các dạng mệnh đề của các công thức đóng Mọi công thức đóng, nghĩa là với các biến định lƣợng, có thể làm đơn giản và đƣợc viết dƣới dạng chính tắc không có các lƣợng hoá đƣợc gọi là dạng mệnh đề.
Dạng mệnh đề cần đƣợc viết công thức nhƣ là một tập hợp các mệnh đề.2 Mệnh đề (Clause) Các công thức có dạng P1 P2 ….Pn Q1 Q2 … Qn, trong đó Pi và Qj là các trực trị dương ( nghĩa là các vị từ nguyên tử không có dấu phủ định ở trước) được gọi là mệnh đề. Mệnh đề Horn ( Horn clause) Một mệnh đề chỉ có một trực trị nằm sau dấu kéo theo (ta nói là đầu của mệnh đề) nghĩa là chỉ một Qi được gọi là mệnh đề Horn: Mệnh đề có dạng P1 P2 ….6: Về các mệnh đề SONGUYEN(x) (x>0) (x < SUCC(x)) (x > SUCC(x)) LANHDAO(x,y)CUNGPHONG(x,y) YEU(x,y) GHET(x,y) Ví dụ 1.7 : Các mệnh đề Horn SONGUYEN(x) (x>0) (x < SUCC(x)) LANHDAO(x,y) CUNGPHONG(x,y) YEU(x,y) Hai công thức A và B đƣợc coi là tƣơng đƣơng ( ký hiệu A B ) nếu chúng có cùng một giá trị chân lý trong mọi minh họa, ta có cá c công thức tƣơng đƣơng sau đây: 14 (LUAN.Datalog002 TIEU LUAN MOI download : skknchat@gmail.