ĐẠ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, F1F2, F1F2,
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)
xy(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
xy(( 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 :
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
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:
xy((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 AB bằng AB. 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:
xy((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
(AB) trở thành A B
(AB) trở thành A B
(xA) trở thành (xA)
(xA) trở thành (xA)
(A) trở thành A
Ví dụ trở thành:
xy((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 xy (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(BC) trở thành (AB) (AC).
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 AB đƣợc viết AB, 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
1.3.2 Các truy vấn và các ràng buộc toàn vẹn
Các truy vấn và các ràng buộc toàn vẹn trên cơ sở khi đó c ó thể đƣợc
diễn đạt nhƣ các công thức trong ngôn ngữ logic. Tuy nhiên, chúng cần đƣợc
mở rộng để chứa các dấu của các phép toán so sánh số học {, , , ,
, } giống nhƣ các vị từ đặc biệt mà giá trị chân lý của chúng đƣợc tính
toán thông qua các phép toán thông thƣờng của máy tính.
Trả lời cho một câu hỏi F(x1,x2,….,xn) trong đó x1,x2,…,xn là các
biến tự do trong công thức F là tập hợp các n-bộ sao cho
F(e1,e2,…,en) là đúng. Một số các công thức phải luôn luôn đúng trên
minh họa tạo nên cơ sở: đó là các ràng buộc toàn vẹn. Khung nhìn logic của
các cơ sở dữ liệu này sinh ra hai tính toán cho phép diễn đạt các truy vấn và
các ràng buộc toàn vẹn trên các cơ sở: Tính toán miền và tính toán bộ. Trong
tính toán miền, các đối tƣợng của thể hiện logic là các giá trị nguyên tử của
dữ liệu; trong tính toán bộ, đó là các sự kiện phức hợp tƣơng ứng với các
n-bộ (hay các bộ) . Luận văn xin trình bày các tính toán này dƣới đây.
1.4 Tính toán miền
Các tính toán quan hệ của miền và bộ cho phép diễn đạt các truy vấn
nhờ các công thức của logic bậc một trên một cơ sở dữ liệu logic hoặc biểu
diễn bảng của nó là một cơ sở dữ liệu quan hệ. Chúng đƣợc sử dụng đ ể hình
thức hoá các ngôn ngữ truy vấn đối với các cơ sở dữ liệu quan hệ.
1.4.1 Các nguyên tắc cơ bản
Tính toán quan hệ của miền đƣợc suy ra từ logic bậc một. Các dữ liệu
là các hằng. Các vị từ đƣợc sử dụng là:
a. Các vị từ mở rộng chứa các bản ghi của cơ sở; mỗi một bản ghi là
một bộ đƣợc định kiểu theo một vị từ mở rộng; các vị từ là n -chiều, một biến
21
- Xem thêm -