Tài liệu Nghiên cứu lý thuyết xây dựng cơ sở dữ liệu suy diễn và ngôn ngữ Datalog

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Doãn Thị Thúy Hiền NGHIÊN CỨU LÝ THUYẾT XÂY DỰNG CƠ SỞ DỮ LIỆU SUY DIỄN VÀ NGÔN NGỮ DATALOG LUẬN VĂN THẠC SĨ 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Doãn Thị Thúy Hiền NGHIÊN CỨU LÝ THUYẾT XÂY DỰNG CƠ SỞ DỮ LIỆU SUY DIỄN VÀ NGÔN NGỮ DATALOG Ngành: Công nghệ thông tin Mã số: 1.01.10 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Tuệ Hà Nội - 2008 2 MỤC LỤC MỞ ĐẦU ..............................................................................................................1 DANH MỤC CÁC THUẬT NGỮ................................................................. 7 CÁC HÌNH VẼ ............................................................................................. 8 CHƢƠNG I: LOGIC VÀ CƠ SỞ DỮ LIỆU ....................................................9 1.1 Mở đầu ...........................................................................................................9 1.2 Logic bậc một ............................................................................................... 10 1.2.1 Cú pháp của logic bậc một...................................................................... 10 1.2.2 Ngữ nghĩa của logic vị từ bậc một .......................................................... 12 1.2.3 Các dạng mệnh đề của các công thức đóng ............................................. 14 1.3 Cơ sở dữ liệu logic ........................................................................................ 18 1.3.1 Biểu diễn các sự kiện .......................................................................... 18 1.3.2 Các truy vấn và các ràng buộc toàn vẹn .................................................. 21 1.4 Tính toán miền ........................................................................................... 21 1.4.1 Các nguyên tắc cơ bản......................................................................... 21 1.4.2 Một số ví dụ về tính miền ....................................................................... 22 1.5 Tính toán các bộ ........................................................................................... 23 1.5.1 Nguyên tắc tính bộ............................................................................... 24 1.5.2 Một số ví dụ về tính bộ ........................................................................... 24 1.6 Các kỹ thuật suy diễn .................................................................................. 26 1.6.1 Nguyên lý của một thuật toán suy diễn ................................................... 26 1.6.2 Thuật toán hợp ..................................................................................... 29 1.6.3 Phƣơng pháp giải ................................................................................. 29 1.7. Kết luận ....................................................................................................... 32 CHƢƠNG II: CƠ SỞ DỮ LIỆU SUY DIỄN .................................................... 33 2.1 Mở đầu ......................................................................................................... 33 2.2 Các vấn đề của hệ quản trị cơ sở dữ liệu suy diễn ............................... 33 2.2.1 Ngôn ngữ quy tắc (luật) ...................................................................... 34 3 2.2.2 Mắc nối hoặc tích hợp ......................................................................... 35 2.2.3 Vị từ mở rộng và vị từ mục tiêu .............................................................. 37 2.2.4 Kiến trúc kiểu của một Hệ quản trị CSDL tích hợp. ................................ 38 2.3 Ngôn ngữ DATALOG .................................................................................. 40 2.3.1 Cú pháp của DATALOG ........................................................................ 40 2.3.2 Ngữ nghĩa của DATALOG..................................................................... 47 2.3.2.1 Lý thuyết chứng minh ...................................................................... 47 2.3.2.2 Lý thuyết mô hình ............................................................................ 49 2.3.2.3 Lý thuyết điểm cố định .................................................................... 50 2.3.2.4 Sự trùng hợp của các ngữ nghĩa ....................................................... 53 2.4. Sự mở rộng của DATALOG ...................................................................54 2.4.1 Giả thuyết thế giới đóng ......................................................................... 55 2.4.2 Phủ định trong thân của các quy tắc........................................................ 56 2.4.3 Phủ định trong đầu quy tắc và cập nhật.................................................. 59 2.5 Tính giá trị của các truy vấn DATALOG ................................................... 60 2.5.1 Thực hiện dƣới lên ................................................................................. 60 2.5.2 Thực hiện trên xuống.............................................................................. 62 2.6 Đồ thị phụ thuộc vị từ (Predicate dependency graph): .............................. 64 2.7 Tính giá trị các quy tắc đệ quy ....................................................................66 2.7.1 Chiến lƣợc ngây thơ (Naive strategy): .................................................... 66 2.7.2 Chiến lƣợc bán ngây thơ ( Seminaive strategy): ...................................... 70 2.8 Kết luận chƣơng ........................................................................................ 74 KẾT LUẬN ........................................................................................................ 75 TÀI LIỆU THAM KHẢO ................................................................................. 76 4 MỞ ĐẦU Cơ sở dữ liệu quan hệ cho phép tiếp nhận, lƣu trữ và xử lý một lƣợng dữ liệu lớn. Việc nghiên cứu cơ sở dữ liệu quan hệ đã đạt đƣợc nhiều thành công, có nhiều đóng góp lớn trong việc quản lý. Tuy nhiên, ngoài việc tiếp nhận, lƣu trữ và xử lý dữ liệu, ngƣời ta cần một loại cơ sở dữ liệu có khả năng suy luận ra các thông tin từ các dữ liệu đƣợc lƣu giữ. Cơ sở dữ liệu suy diễn đáp ứng đƣợc yêu cầu ấy. Ngoài việc lƣu trữ các thông tin một cách rõ ràng theo kiểu cơ sở dữ liệu quan hệ, cơ sở dữ liệu suy diễn còn lƣu giữ các luật có khả năng suy diễn dựa trên các dữ liệu đã lƣu. Cơ sở dữ liệu suy diễn là sản phẩm tự nhiên của lập trình logic, trong đó logic toán đƣợc sử dụng cho các khái niệm tính toán mô hình trực tiếp. Kỹ thuật cơ sở dữ liệu suy diễn đƣợc ứng dụng nhiều trong các hệ hỗ trợ quyết định, và các hệ chuyên gia. Cùng với các kỹ thuật phát triển cơ sở dữ liệu quan hệ, điều cơ bản này trong logic có nghĩa là cơ sở dữ liệu suy diễn có khả năng lƣu một lƣợng lớn thông tin cũng nhƣ việc thực hiện suy diễn trên các thông tin đó. Có rất nhiều lĩnh vực ứng dụng kỹ thuật cơ sở dữ liệu suy diễn, nhƣ hệ hỗ trợ quyết định, các hệ chuyên gia. Nó cho phép phân tích một lƣợng lớn các dữ liệu, đƣa ra các suy luận cho tƣơng lai. Việc nghiên cứu cơ sở dữ liệu suy diễn đƣợc thực hiện trên thế giới từ những năm 80 của thế kỷ trƣớc, nhƣng ở nƣớc ta cho đến hiện nay vẫn còn rất ít những nghiên cứu về nó. Việc tìm hiểu cơ sở về cơ sở dữ liệu suy diễn và các ứng dụng của nó là một vấn đề có ý nghĩa lý thuyết và thực tiễn. Với lý do đó em chọn đề tài nghiên cứu luận văn là: “ Nghiên cứu lý thuyết xây dựng cơ sở dữ liệu suy diễn và ngôn ngữ Datalog ” Luận văn gồm hai chƣơng: 5 Chƣơng 1: Logic và cơ sở dữ liệu Trình bày các khái niệm cơ sở của logic bậc một – ngôn ngữ nền tảng để biểu diễn một cơ sở dữ liệu logic, các tính toán bộ và tính toán miền là các hình thức hoá logic của các ngôn ngữ truy vấn các cơ sở dữ liệu quan hệ. Chƣơng 2: Cơ sở dữ liệu suy diễn Trình bày về ngôn ngữ các quy tắc trong cơ sở dữ liệu suy diễn, vấn đề phân chia hay tích hợp một động cơ suy diễn với một hệ quản trị cơ sở dữ liệu. Chƣơng này cũng trình bày về ngôn ngữ Datalog, cú pháp, ngữ nghĩa, sự mở rộng của Datalog, vấn đề tính giá trị của các truy vấn Datalog cũng nhƣ vấn đề tính giá trị của các quy tắc đệ quy. Do việc nghiên cứu ở nƣớc ta còn ít, việc tìm kiếm và tham khảo tài liệu có khó khăn và trình độ của em còn nhiều hạn chế nên chắc chắn luận văn còn nhiều thiếu sót. Em rất mong đƣợc các thầy giáo và các bạn thông cảm và giúp đỡ để em có thể phát triển luận văn của mình hoàn thiện hơn, có nhiều ứng dụng thực tiễn hơn. 6 DANH MỤC CÁC THUẬT NGỮ Thuật ngữ tiếng Anh Thuật ngữ tiếng Việt Viết tắt Database Cơ sở dữ liệu CSDL First-order logic Logic bậc một Predicate dependency graph Đồ thị phụ thuộc vị từ Domain of discourse Miền thảo luận Domain relational calculus Tính toán quan hệ miền Tuple relational calculus Tính toán quan hệ bộ literal trực trị Extensional DataBase Cơ sở dữ liệu mở rộng EDB Intensional Database Cơ sở dữ liệu mục đích IDB Closed world assumption Giả thuyết thế giới đóng DataBase Management System Hệ quản trị cơ sở dữ liệu 7 DBMS CÁC HÌNH VẼ Hình 1.1 ....................................................................................................................... 27 Hình 2.1 ........................................................................................................................ 32 Hình 2.2 ........................................................................................................................ 33 Hình 2.3 ........................................................................................................................ 35 Hình 2.4 ........................................................................................................................ 36 Hình 2.5 ........................................................................................................................ 44 Hình 2.6 ........................................................................................................................ 61 Hình 2.7 ........................................................................................................................ 65 Hình 2.8 ........................................................................................................................ 69 8 CHƢƠNG I: LOGIC VÀ CƠ SỞ DỮ LIỆU 1.1 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ệ . 9 1.2 Logic bậc một 1.2.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,…. b. 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). f. Các lƣợng từ , . g. 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. Ví dụ1.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 a. 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ử. b. Nếu F1, F2 là các công thức, khi đó F1 F2, F1F2, F1F2, F1  F2 và F2 là các công thức. 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 : , , ,  . Ví dụ 1.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) xy(Q(x,y)  P(a,x)). x(R(x)  Q(x,a)  P(b,f(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. Ví dụ 1.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). x(LANHDAO(Nam,x)  NGUOILAM(Tinhoc,x)  NGUOILAM(Taichinh,x)) 11 xy(( LANHDAO(x,y)  LANHDAO(y,x)  CUNGPHONG(x,y). 1.2.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..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ó . Khái niệm 1.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. Ví dụ 1.4 : Công thức : xy((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 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. Ví dụ 1.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. Với ví dụ 1.5, các số nguyên là một mô hình đối với công thức x(x0)  (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 o A  o A  B o (A) A v B  B  (A B)  (B  A)  A Luật De Morgan: o (A v B)  A  B o (A  B)  A v B Luật giao hoán : o A v B  B v A o A  B  B  A Luật kết hợp: o (A v B) v C  Av( B v C) o (A  B)  C  A ( B  C) Luật phân phối: o A  (B v C)  (A  B ) v (A  C) o A v (B  C)  (A v B )  (A v C) Sử dụng các phép biến đổi tƣơng đƣơng ta có thể chuyển đổi một công thức đóng sang dạng một mệnh đề. Việc thực hiện đƣợc tiến hành bằng cách chuyển đổi liên tiếp nhƣ sẽ đƣợc mô tả sau đây, luận văn minh hoạ các chuyển đổi với công thức: xy((LANHDAO(x,y) LANHDAO(y,x)  CUNGPHONG(x,y)) a. Loại bỏ phép kéo theo: Điều đó đƣợc thực hiện một cách đơn giản bằng việc thay tất cả các biểu thức có dạng AB bằng AB. Thật vậy, các biểu thức này là tƣơng đƣơng theo quan điểm logic. Công thức đƣợc chọn trở thành: xy((LANHDAO(x,y) LANHDAO(y,x)) CUNGPHONG(x,y)) b. Làm giảm tầm các phủ định. Mục đích là làm cho các phủ định đƣợc áp dụng trực tiếp với các vị từ nguyên tử. Để làm điều đó, ngƣời ta sử dụng theo cách lặp các chuyển đổi: 15  (AB) trở thành A  B  (AB) trở thành A  B (xA) trở thành (xA) (xA) trở thành (xA) (A) trở thành A Ví dụ trở thành: xy((LANHDAO(x,y)  LANHDAO(y,x))  CUNGPHONG(x,y)). c. Đặt các dấu lượng từ cùng với biến định lượng lên đầu công thức. Bƣớc này có thể đặt lại tên các biến để tránh nhầm sự lƣợn g hoá. Ta có các công thức tƣơng đƣơng sau đây: o x G(x)  y G(y) x G(x)  y G(y) o x ( G(x))  (x G(x)) x ( G(x))  (x G(x)) o x G(x)  x H(x)  x (G(x)  H(x)) x G(x)  x H(x)  x (G(x)  H(x)) Ví dụ trên không thay đổi. d. Loại bỏ các dấu lượng hoá . Để đơn giản hơn nữa, các biến định lƣợng đang tồn tại đƣợc thay thế bằng một tham số hằng gọi là hằng Skolem. Thật vậy, nếu tồn tại x thoả mãn một công thức, có thể chọn một hằng s ký hiệu giá trị này của x. Nếu một biến đƣợc định lƣợng “với mọi” xuất hiện trƣớc biến đƣợc định lƣợng “tồn tại”, hằng đƣợc chọn phụ thuộc vào biến thứ nhất. Ví dụ, trong trƣờng hợp xy (với mọi x, tồn tại y, nhƣng y phụ thuộc vào x) ta thay thế y bằng s(x), nghĩa là một hàm Skolem cụ thể hoá hằng y phụ thuộc vào x. Nhƣ vậy có khả năng loại bỏ các biến định 16 lƣợng bởi “tồn tại”. Sau biến đổi này, mọi biến còn lại đƣợc định lƣợng bởi “với mọi”. Ta có thể không cần viết các dấu lƣợng hoá (nghĩa là ngần định các biến đều buộc với lƣợng tử ). Ví dụ trên trở thành: (LANHDAO(x,s(x)) LANHDAO(s(x),x)) CUNGPHONG(x,s(x)) e. Viết dưới dạng chuẩn hội . Công thức còn lại là một tổ hợp với các kết nối “hoặc” và “và” của các trực trị âm hoặc dƣơng (các vị từ nguyên tử có dấu phủ định đi trƣớc hay không). Nó có thể đƣợc viết nhƣ là một phép hội () của các phép tuyển () bằng cách phân phối các “và” đối với các “hoặc” nhờ quy tắc: A(BC) trở thành (AB)  (AC). Nhƣ vậy, ví dụ trở thành: (LANHDAO(x,s(x))  CUNGPHONG(x,s(x))) (LANHDAO(s(x),x)  CUNGPHONG(x,s(x))) f. Viết dưới dạng các mệnh đề . Cuối cùng, dễ dàng viết mỗi mệnh đề trên một dòng bằng cách thay các kết nối “và” bằng các thay đổi dòng. Hơn nữa, lợi dụng sự kiện AB đƣợc viết AB, ta có thể viết tất cả các vị từ âm trƣớc tiên bằng cách loại bỏ dấu phủ định và bằng cách nối chúng bằng  , sau đó viết các vị từ dƣơng đƣợc nối bằng  . Nhƣ vậy ta nhận đƣợc một dãy các mệnh đề, đƣợc định nghĩa nhƣ trên. Với công thức đã cho, ta nhận đƣợc hai mệnh đề (thậm chí là mệnh đề Horn): LANHDAO(x,s(x))  CUNGPHONG(x,s(x)). LANHDAO(s(x),x)) CUNGPHONG(x,s(x)). 17 1.3 Cơ sở dữ liệu logic Khái niệm cơ sở dữ liệu logic đƣợc đƣa ra ở Toulouse vào cuối thập kỷ 70. Ta định nghĩa ở đây cơ sở dữ liệu logic không suy diễn. Đó là tiếp cận đơn giản đầu tiên các cơ sở dữ liệu thông qua logic. Trong chƣơng sau cách tiếp cận này có thể đƣợc mở rộng với sự suy diễn. 1.3.1 Biểu diễn các sự kiện Một cơ sở dữ liệu có thể đƣợc định nghĩa nhƣ là một sự giải thích (một minh hoạ) của một ngôn ngữ logic bậc một. Trong thực tế, việc định nghĩa sự giải thích bao gồm việc định nghĩa các vị từ đúng. Một ràng buộc toàn vẹn có thể đƣợc xem nhƣ một truy vấn luôn luôn đúng, và đƣợc biểu thị cùng với ngôn ngữ. Ngôn ngữ cho phép biểu thị các truy vấn nhƣ vậy sẽ đƣợc trình bày dƣới đây. Khái niệm 1.4: Cơ sở dữ liệu logic (Logic Database). Cơ sở dữ liệu logic là tập hợp các sự kiện bao gồm sự giải thích của một ngôn ngữ bậc một cùng với nó có thể diễn đạt các truy vấn và các ràng buộc toàn vẹn trên các sự kiện. Trong tiếp cận đầu tiên, ngôn ngữ logic L không chứa các hàm. Cụ thể hơn, L bao gồm: a. Các vị từ với n đối, mỗi đối tƣơng ứng với một kiểu dữ liệu cơ bản b. Các hằng, mỗi hàng với một giá trị có thể của các kiểu dữ liệu cơ bản. Giống nhƣ trong mọi minh hoạ của một ngôn ngữ logic, một vị từ biểu diễn một quan hệ cụ thể giữa các đối tƣợng của miền thảo luận, nó có thể đúng hoặc sai. Ở đây các đối tƣợng của miền thảo luận là các giá trị có thể có của cơ sở. Định nghĩa quan hệ này trở thành định nghĩa các bản ghi hoặc các n-bộ thoả mãn vị từ. Tập hợp các n-bộ thoả mãn vị từ tạo nên mở rộng của nó. Sự mở rộng này có thể tƣơng tự với một file trong một cơ sở mạng hoặc với một bảng quan hệ nhƣ chúng ta sẽ thấy về sau. Để trở nên gắn bó 18 chặt chẽ với các cơ sở dữ liệu quan hệ mà chúng có thể nhận biết nhƣ sự giải thích (minh hoạ) đơn giản của các cơ sở dữ liệu logic, chúng ta gọi sự mở rộng của một vị từ là một bảng. Mỗi một cột tƣơng ứng với một đối và cũng đƣợc gọi là thuộc tính trong ngữ cảnh quan hệ. Nhƣ đã nói, một cơ sở dữ liệu logic có thể được bổ sung bởi các quy tắc suy diễn, khi đó nó được gọi là cơ sở dữ liệu suy diễn. Ví dụ 1.8 mô tả một cơ sở dữ liệu logic. Trong thuật ngữ bảng, nó tƣơng ứng với cơ sở đƣợc biểu diễn ở ví dụ1.9, bao gồm ba vị từ đƣợc định nghĩa nhƣ sau: - SANPHAM với các thuộc tính Mã sản phẩm (MaSP), tên sản phẩm (TenSP), Số lƣợng trong kho (SL) và màu (MAU). - BAN với các thuộc tính Mã số bán (MaB), tên khách hàng (TenKH), mã số của sản phẩm bán (MaSPB) số lƣợng sản phẩm bán (SLB) và ngày ban (NGB). - MUA với các thuộc tính Mã số mua (MaM), ngày mua (NGM), mã số của sản phẩm mua (MaSPM), số lƣợng sản phẩm mua (SLM), tên nhà cung cấp (TenNCC). Nhƣ vậy, trên đây là các sự kiện dƣơng, nghĩa là những đối tƣợng thoả mãn một trong ba vị từ, đƣợc ghi vào cơ sở. Điều này tạo nên giả thuyết thế giới đóng. Các sự kiện không đƣợc ghi vào trong một mở rộng của vị từ đƣợc giả thiết là sai. Ví dụ 1.8: Các sự kiện tạo nên một cơ sở dữ liệu logic SANPHAM(100, BUTBI, 100, XANH) SANPHAM(200, BUPBE, 50, ĐO) SANPHAM(300, ÔTÔ , 70, VANG) SANPHAM(400, BÌA, 350, TIM) BAN(1, BAC, 100, 30, 08-03-1999) 19 BAN(2, NAM, 200, 10, 07-01-1999) BAN(3, DONG, 100, 50, 01-01-2000) BAN(4, DONG, 300, 50, 01-01-2000) MUA(1, 01-03-1999, 100,70, TAY) MUA(2, 01-03-1999, 200, 100, TAY) MUA(3, 01-09-1999, 100, 50, THIEN) MUA(4, 01-09-1999), 300, 50, THIEN) Ví dụ 1.9: Các bảng biểu diễn một cơ sở dữ liệu logic: SANPHAM BAN MUA MaSP TenSP SL MAU 100 BUTBI 100 200 BUPBE 50 DO 300 OTO 70 VANG 400 BIA 350 XANH TIM MaB TenKH MaSPB SLB 1 NAM 100 30 08-03-1999 2 BAC 200 10 07-01-1999 3 DONG 100 50 01-01-2000 4 DONG 300 50 01-01-2000 MaM NGM MaSPM NGB SLM TenNCC 1 01-03-1999 100 70 TAY 2 01-03-1999 200 100 TAY 3 01-09-1999 100 50 THIEN 4 01-09-1999 300 50 THIEN 20