Tổng quan thông tin đầy đủ và không chắc chắn, tri thức không hoàn chỉnh trong cơ sở dữ liệu quan hệ, Cơ sở dữ liệu xác xuất.
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
-------------------------------------------
LÊ VĂN TẤN
CƠ SỞ DỮ LIỆU XÁC SUẤT
Chuyên ngành: Công nghệ thông tin
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Người hướng dẫn khoa học: TS: NGUYỄN KIM ANH
Hà nội, năm 2004
MỤC LỤC
LỜI NÓI ĐẦU
3
CHƯƠNG I. TỔNG QUAN
5
1.1. Thông tin không đầy đủ và không chắc chắn
5
1.2. Việc thao tác thông tin không đầy đủ và không chắc chắn
8
1.2.1. Thông tin phân tách ( Disjunctive Information)
12
1.2.2. Thông tin xác suất
14
CHƯƠNG 2: TRI THỨC KHÔNG HOÀN CHỈNH TRONG CSDL QUAN HỆ17
2.1. Giới thiệu
17
2.2. Thế giới có thể (Possible worlds)
19
2.3 Truy vấn một cơ sở dữ liệu không hoàn chỉnh
23
2.4. Các ràng buộc toàn vẹn trong cơ sở dữ liệu không hoàn chỉnh
29
2.5. Cập nhật cơ sở dữ liệu không hoàn chỉnh
34
CHƯƠNG 3. CƠ SỞ DỮ LIỆU XÁC SUẤT
43
3.1.Các quan hệ xác suất
43
3.1.1. Các ngữ nghĩa của quan hệ xác suất
45
3.1.2. Sự dư thừa trong các quan hệ xác suất
49
3.1.3. Đại số quan hệ
51
3.2. T-quan hệ
54
3.2.1. Các ngữ nghĩa của t-quan hệ
56
3.2.2. Sự dư thừa trong các t-quan hệ
59
3.2.3. Từ các thế giới khả năng đến t-quan hệ
60
3.2.4. Sự ước lượng của các t-quan hệ
62
3.3 Tính đúng đắn của đại số quan hệ
65
3.4. Các phép toán quan hệ trên các tập thế giới khả năng
69
3.5. Các phép toán trên t-quan hệ
71
3.5.1. Phép chiếu
71
3.5.2. Phép chọn
72
3.5.3. Phép hợp
73
3.5.4 Phép trừ
75
3.5.5. Phép giao
76
3.5.6 Phép kết nối
77
3.5.7. Tích đề các
78
3.5.8. Phép chia
79
3.6. Các phép toán trên các quan hệ xác suất
81
CHƯƠNG 4. CÀI ĐẶT THỬ NGHIỆM
83
4.1. Xác định bài toán
83
4.2. Một số kiến thức liên quan
83
4.2.1. Logic vị từ
83
4.2.2 Các ánh xạ
86
4.3 Cài đặt các phép toán
86
4.3.1 Phép chiếu
86
4.3.2 Phép chọn
87
4.3.3 Phép giao
87
4.3.4 Phép hợp
88
4.3.5 Phép trừ
89
4.3.6 Phép kết nối tự nhiên
89
4.3.7 Tích Đề Các
90
4.3.8 Phép chia
91
4.4 Cài đặt biểu thức
92
4.4.1 Thủ tục chuyển biểu thức E thành biểu thức hậu tố
92
4.4.2 Thủ tục tính giá trị biểu thức
93
4.5 Một số kết quả
94
4.5.1 Các Form
94
4.5.2. Ví dụ
97
4.6 Nhận xét
101
KẾT LUẬN
102
TÀI LIỆU THAM KHẢO
106
LỜI NÓI ĐẦU
Trong thực tế cuộc sống thường có nhiều trường hợp mà tri thức có giá trị
là không hoàn chỉnh mà nó biểu diễn nhiều trạng thái có thể của thế giới bên
ngoài, chưa biết trạng thái nào tương ứng với tình huống thực tế của thế giới bên
ngoài. Tri thức không hoàn chỉnh có thể có hai loại khác nhau, như: Tri thức là
không đầy đủ nếu nó biểu diễn các trạng thái khác nhau, một trong những trạng
thái đó là đúng với thế giới bên ngoài. Ngược lại, tri thức là không chắc chắn
nếu nó biểu diễn các trạng thái khác nhau mà có thể được thoã mãn hay gần là
đúng với thế giới bên ngoài.
Tri thức không hoàn chỉnh có thể được xem xét dưới hai góc độ khác nhau,
đó là: Tiếp cận dựa theo đại số hoặc tiếp cận theo logic. Chúng ta đưa ra cả hai
cách tiếp cận trong quan hệ với mô hình quan hệ chuẩn, cung cấp cơ sở cho sự
phát triển tiếp theo.
Nghiên cứu tri thức không hoàn chỉnh đã là một lĩnh vực thực sự của việc
nghiên cứu, đặc biệt trong phạm vi của cơ sở dữ liệu quan hệ. Tuy nhiên, do sự
phức tạp của việc thao tác tri thức không hoàn chỉnh, cho nên cho đến nay có rất
ít kết quả thực tế được đưa ra. Trong luận văn này tôi chỉ đưa ra một cái nhìn
tổng quan về sự không đầy đủ và không chắc chắn trong cơ sở dữ liệu quan hệ.
Tập trung vào việc đưa ra một sự trình bày thống nhất cho các cách tiếp cận và
các kết quả khác nhau được tìm thấy trong tài liệu, như vậy cung cấp một trình
độ phát triển của khoa học kỹ thuật ở một giai đoạn cụ thể trong lĩnh vực nhất
định.
Trong luận văn này chúng ta tập trung nghiên cứu chi tiết kiểu của tri thức
không chắc chắn, hay thông tin xác suất trên cơ sở logic và đại số. Các phép toán
đại số quan hệ được đưa ra cho các quan hệ xác suất, và chúng ta chứng minh
tính đúng đắn của chúng. Thêm vào đó, cơ sở dữ liệu xác suất được chính thức
hoá việc sử dụng thích hợp các lý thuyết logic và đưa ra các giải thuật ước lượng
truy vấn một cách đầy đủ và đúng đắn.
Sự liên quan chủ yếu của các nghiên cứu này là một sự tin chắc rằng tính
không đầy đủ và không chắc chắn của các khía cạnh khác nhau của các vấn đề
giống nhau sẽ cho phép đạt được sự hiểu biết sâu hơn của tri thức không hoàn
chỉnh, mà hết sức cần thiết cho việc xây dựng các hệ thống thông tin có thể với
việc mô hình hoá các tình huống đời sống thực tế phức tạp.
Luận văn tốt nghiệp
5
Cơ sở dữ liệu xác suất
CHƯƠNG I. TỔNG QUAN
1.1. Thông tin không đầy đủ và không chắc chắn
Một trong những đặc trưng của trí tuệ con người là khả năng suy diễn với
trí thức không đầy đủ và không chắc chắn. Trong thực tế cuộc sống con người
hàng ngày luôn phải đương đầu với việc đưa ra các quyết định và hành động
trong các tình huống mà các tri thức về các sự việc là không hoàn chỉnh. Thường
nó là không thể hay không có khả năng thực tế để đạt được tri thức đầy đủ và
chắc chắn, do tri thức đó có thể là không tồn tại.
Trong các tình huống như vậy, thông tin có thể bị thiếu do hai khả năng.
Nếu chúng ta chỉ có một phần tri thức của thế giới, thì nó gọi là thông tin không
đầy đủ. Một cách khác, nếu chúng ta có thông tin mà sự chắc chắn của nó không
được bảo đảm tính toàn vẹn, nó được gọi là thông tin không chắc chắn. Tính
không đầy đủ và không chắc chắn có thể liên quan đến tri thức mà có liên quan
tới việc xảy ra của các sự kiện trong thế giới và có thể là nguyên nhân cho các sự
kiện tiếp theo.
Trong khi con người có khả năng thu nhận rất tốt khối lượng lớn các tri
thức không đầy đủ và không chắc chắn để tạo ra và thi hành các quyết định một
cách hiệu quả.Việc thao tác các tri thức không hoàn chỉnh như vậy đã trở thành
các bài toán lý thuyết rất phức tạp trong các ứng dụng của các hệ thống thông tin
và trí tuệ nhân tạo. Trong những thập kỷ cuối của thế kỷ 20, các nghiên cứu đã
có nhiều cố gắng để phát triển các phương pháp và mô hình cho việc biểu diễn
và thao tác tri thức không đầy đủ và không chắc chắn nhằm mục đích lột tả nhiều
tình huống thực tế trong đời sống.
Ba thập kỷ vừa qua cũng đã chứng kiến một sự phát triển kinh ngạc của
công nghệ cơ sở dữ liệu với các hệ thống thông tin. Từ sự cố gắng quản lý cơ sở
dữ liệu ban đầu trong những năm 1960, nhiều nỗ lực đã tạo ra việc mở rộng kỹ
LÊ VĂN TẤN
Luận văn tốt nghiệp
6
Cơ sở dữ liệu xác suất
thuật này để thu được các mô hình dữ liệu tốt hơn với các khả năng thao tác dữ
liệu đủ mạnh, hiệu quả và cần thiết để đáp ứng được các yêu cầu ngày càng phức
tạp hơn.
Sự phát triển của mô hình quan hệ đã trở thành sự kiện quan trọng trong
hướng này. Mô hình quan hệ phân ra hai khía cạnh khác nhau có quan hệ mật
thiết với các mô hình cơ sở dữ liệu khác, đó là: sự mô hình hoá của một ứng
dụng (hay việc biểu diễn thông tin), và sự thực thi vật lý của nó (hay cách thức
mà thông tin được lưu trữ trong máy tính). Trong cách này, sự quan tâm chính
của người sử dụng là các khía cạnh ngữ nghĩa của thông tin mà chúng ta muốn
mô hình hoá.
Hơn thế nữa, việc đưa vào các truy vấn khai báo trong cơ sở dữ liệu quan hệ
đã cho phép người dùng hay chương trình ứng dụng giải thoát được gánh nặng
đối với việc tra cứu các thông tin từ cơ sở dữ liệu .
Với lý do này, mô hình quan hệ đã có nhiều thành công và vì thế, một số hệ
cơ sở dữ liệu quan hệ như là ORACLE, DB2 và INGRES có giá trị thương mại
đã ra đời trong những năm cuối 1970 và đầu những năm 1980. Cùng thời gian
này, các cố gắng nghiên cứu cho phép chính thức hoá các khái niệm của mô hình
quan hệ và lý thuyết cơ sở dữ liệu quan hệ đã được phát triển.
Tuy nhiên, cuối những năm 70 và đầu những năm 80 đã dấy lên một sự cần
thiết mở rộng cơ sở dữ liệu quan hệ để xem xét các kiểu thông tin khác mà
không được đề cập trong mô hình của Codd. Việc đưa vào thông tin không đầy
đủ và không chắc chắn là một trong những sự mở rộng đã được đề xuất bởi các
nghiên cứu.
Một trong những sự thừa nhận cơ bản của mô hình quan hệ là thông tin
được chứa trong cơ sở dữ liệu là đầy đủ và chắc chắn. Tuy nhiên, do trong các
tình huống thực tế đời sống thông tin khó mà đầy đủ và chắc chắn, nó là sự cần
LÊ VĂN TẤN
Luận văn tốt nghiệp
7
Cơ sở dữ liệu xác suất
thiết để có thể thao tác thông tin không hoàn chỉnh trong phạm vi cơ sở dữ liệu
quan hệ.
Nhiều loại khả năng của thông tin không đầy đủ và không chắc chắn có thể
được đưa vào cơ sở dữ liệu . Một khái niệm đầu tiên có thể được sử dụng cho
việc biểu diễn thông tin không đầy đủ là các giá trị Null. Một giá trị Null là sự
biểu thị cho một thuộc tính của quan hệ mà giá trị của nó không thể biểu diễn
được bằng một hằng thông thường. Mặc dù nhiều ý nghĩa của giá trị Null đã
được xem xét, phần lớn thường rơi vào hai loại sau. Giá trị Null Unknown biểu
diễn giá trị của thuộc tính là thiếu vắng hay không biết; chẳng hạn "lương của
giám đốc John là không biết". Giá trị Null Inapplicable biểu diễn rằng giá trị của
thuộc tính là không thể áp dụng hay giá trị của nó không tồn tại; ví dụ "tên vợ
của John không thể áp dụng khi John chưa lập gia đình".
Một kiểu khác của tính không đầy đủ mà có thể được đưa vào cơ sở dữ liệu
là thông tin "phân tách" (Disjunctive Information). Thông tin được gọi là phân
tách nếu nó có dạng " Jean dạy môn Physics hay môn Algebra" trong đó hoặc
điều thứ nhất, hoặc điều thứ hai hoặc cả hai là đúng.
Thông tin có thể (Maybe information) thuộc loại thông tin không chắc chắn
do nó biểu diễn các sự việc mà chúng là có thể đúng, như "Jean có khả năng
nhận môn Database".
Một loại khác của tính không chắc chắn là thông tin mờ (Fuzzy
Information). Đây là kiểu thông tin sinh ra thông tin có thể, do nó gắn cho mỗi
sự việc có thể một giá trị thuộc [0,1]( biểu diễn rằng có bao nhiêu sự việc là có
thể đúng), chẳng hạn "Jean có xác suất bằng 1 là nhận môn Algebra và có xác
suất bằng 0.8 nhận môn Physics"
Cuối cùng, tính không chắc chắn có thể được đưa vào một cơ sở dữ liệu
thông qua các thông tin xác suất (Probabilistic Information) như "doanh số bán
hàng năm tiếp theo của một cửa hàng sẽ tăng 1.5% với xác suất là 0.75 và 2%
LÊ VĂN TẤN
Luận văn tốt nghiệp
8
Cơ sở dữ liệu xác suất
với xác suất 0.25". Đây là kiểu thông tin ngẫu nhiên (stochastic information)
thường được áp dụng nhiều trong các ứng dụng thực tế của cơ sở dữ liệu .
Khi đương đầu với các tri thức không hoàn chỉnh, vấn đề liên quan đầu tiên
là xác định "ngữ nghĩa" của nó. Nếu tri thức về thế giới là không đầy đủ hoặc
không chắc chắn, một vài "viễn cảnh" hay các trạng thái với thông tin chắc chắn
và đầy đủ là có khả năng, nhưng không biết cái nào biểu diễn trạng thái thực của
thế giới.
Như vậy, cơ sở dữ liệu chứa thông tin không chắc chắn hay không đầy đủ
biểu diễn toàn bộ tập trạng thái có thể (possible state) hay tập thế giới có thể
(possible world). Một thế giới có thể là một trạng thái mang tính giả thiết của thế
giới thực mà có thể được biểu diễn một cách đầy đủ bằng một cơ sở dữ liệu
thông thường với thông tin đầy đủ và chắc chắn. Thí dụ, xem xét một cơ sở dữ
liệu không đầy đủ chứa thông tin phân tách "John dạy môn Physics hoặc môn
Calculus". Nếu sự phân tách trên được thực hiện một cách triệt để, cơ sở dữ liệu
biểu diễn ba trạng thái khả năng: một là John dạy Physics, hai là John dạy
Calculus và thứ ba là John dạy cả hai môn. Các trạng thái phân tách mà một
trong ba thế giới có thể biểu diễn tình huống thực sự của thế giới, nhưng không
biết là cái nào.
1.2. Việc thao tác thông tin không đầy đủ và không chắc chắn
Trong phạm vi cơ sở dữ liệu quan hệ, một vài vấn đề đã được nghiên cứu và
từ nhiều quan điểm về thông tin không đầy đủ và không chắc chắn, như đã
chứng kiến bởi nhiều nghiên cứu trên cùng một vấn đề. Tuy nhiên, các công việc
này chủ yếu thu thập các kết quả lý thuyết của khả năng ứng dụng thực tế hạn
chế. Thật vậy, việc biểu diễn thông tin không đầy đủ và không chắc chắn trong
cơ sở dữ liệu trở nên phức tạp hơn và vấn đề chủ yếu của việc xử lý thông tin
LÊ VĂN TẤN
Luận văn tốt nghiệp
9
Cơ sở dữ liệu xác suất
này trong các thao tác cơ sở dữ liệu là: trả lời truy vấn, kiểm tra các ràng buộc
toàn vẹn, và cập nhật cơ sở dữ liệu .
Chúng ta chỉ ra ở đây hai cách tiếp cận khác nhau đã từng có trong các
nghiên cứu tính không chắc chắn và không đầy đủ trong cơ sở dữ liệu quan hệ.
Thứ nhất là sử dụng quan điểm đại số quan hệ, đặc biệt khi các phép toán đại số
quan hệ được khái quát hoá cho việc thao tác thông tin không đầy đủ. Cách tiếp
cận thứ hai là theo lôgic và hình thức hoá cơ sở dữ liệu quan hệ và sự mở rộng
các ý nghĩa của lý thuyết lôgic cụ thể. Ẩn ý của cả hai cách tiếp cận được giải
thích bằng các ý nghĩa của một ví dụ trong quan hệ với các giá trị Null.
Xem xét một cơ sở dữ liệu chứa hai quan hệ, một quan hệ Teaches với các
thuộc tính Professor và Course, biểu diễn giáo sư dạy một môn học, và quan hệ
takes, với các thuộc tính Student và Course, biểu diễn rằng một sinh viên nhận
một môn học. Hai thể hiện của các quan hệ này được cho như sau:
professor
Martin
X
Course
Physics
Algebra
Teaches
student
Paul
Peter
Course
Physics
Y
Takes
Trong đó các biến x và y biểu thị các giá trị Null Unknown. Giả sử rằng các
giá trị khả năng cho x là {Martin,Anne} và cho y là {Algebra,Calculus} . Thì mỗi
quan hệ biểu diễn trong thế giới thực hai tình huống khác nhau, phụ thuộc vào
các giá trị được nhận bởi x và y.
Như đã nói ở trên, thông tin chứa trong cơ sở dữ liệu là thông tin không đầy
đủ hay không chắc chắn có thể được biểu diễn bởi một tập các thế giới có thể,
tức là, biểu diễn bằng một tập cơ sở dữ liệu quan hệ cổ điển. Trong thí dụ này,
các thế giới có thể của cơ sở dữ liệu trên là:
LÊ VĂN TẤN
Luận văn tốt nghiệp
10
Teaches
Professor
Course
Cơ sở dữ liệu xác suất
Takes
student
Course
Martin
Martin
Physics
Algebra
Paul
Peter
Physics
Algebra
Martin
Martin
Physics
Algebra
Paul
Peter
Physics
Calculus
Martin
Anne
Physics
Algebra
Paul
Peter
Physics
Algebra
Martin
Anne
Physics
Algebra
Paul
Peter
Physics
Calculus
Hình 1.1: Các thế giới có thể của cơ sở dữ liệu không đầy đủ
Bây giờ xem xét việc thao tác của cơ sở dữ liệu không đầy đủ này đối với
việc ước lượng truy vấn, kiểm tra các ràng buộc toàn vẹn và sự cập nhật cơ sở dữ
liệu . Do các ngữ nghĩa của cơ sở dữ liệu được chỉ rõ bởi tập thế giới có thể của
hình 1.1, các ngữ nghĩa của sự ước lượng truy vấn, kiểm tra các ràng buộc toàn
vẹn và cập nhật cơ sở dữ liệu được thiết lập bởi việc áp dụng các thao tác này
cho mỗi thế giới có thể, như được cho trong hình sau:
professor course Student
Martin Physics
Paul
Martin Algebra Peter
professor course
Martin Physics
Student
Paul
professor course Student
Martin Physics
Paul
Anne
Algebra Peter
Hình 1.2: teaches
takes trong các thế giới có thể
Các thế giới có thể này xác định ý nghĩa chính xác cho kết nối mở rộng.
Bởi vậy, để giữ được các ngữ nghĩa của cơ sở dữ liệu, quan hệ thu được là kết
quả của sự kết nối các quan hệ mở rộng Teaches và Takes sẽ có các quan hệ
LÊ VĂN TẤN
Luận văn tốt nghiệp
11
Cơ sở dữ liệu xác suất
trong hình 1.2 như các thế giới có thể của nó. Tuy nhiên các yêu cầu này không
thể luôn luôn được thoả mãn, do khả năng có ý nghĩa của một số quan hệ mở
rộng là không đủ để biểu diễn kết quả của các biểu thức quan hệ bất kỳ trên một
tập thế giới có thể.
Đối với khía cạnh lôgic, Reiter đã cụ thể hoá cơ sở dữ liệu quan hệ bằng ý
nghĩa của các lý thuyết bậc nhất riêng biệt mà Reiter gọi là các lý thuyết quan hệ
mở rộng. Xem xét cơ sở dữ liệu sau:
professor
Jean
Paul
ω
teaches
Jean
Biology
Paul
Chemistry
Physics
ω
Course
Biology
Chemistry
Physics
Cơ sở dữ liệu này chứa một giá trị Null Unknown ω biểu diễn rằng có một
giáo sư mà ông ấy dạy môn Physics, nhưng không biết chính xác ông ấy là ai.
Ông ấy có thể là một trong những giáo sư đã biết, cũng có thể ông ấy là một
người chưa biết.
Trong các lý thuyết quan hệ mở rộng, mỗi quan hệ được gắn một tiên đề mở
rộng (extension axiom) ghi rõ tất cả và chỉ các bộ hằng thuộc vào quan hệ. Thí
dụ, các tiên đề mở rộng cho cơ sở dữ liệu trên là như sau.
( ∀x ) ( Pr ofessor ( x ) ↔ x = Jean ∨ x = Paul ∨ x = ω )
( ∀x ) ( Course ( x ) ↔ x = Biology ∨ x = Chemistry ∨ x = Physics )
( ∀x )( ∀y )(Teaches ( x, y ) ↔ x = Jean ∧ y = Bio log y ] ∨
[ x=Paul ∧ y=Chemistry] ∨ [ x = ω ∧ y = Physics] .
Hơn nữa, các lý thuyết quan hệ mở rộng chứa một tập các tên duy nhất mà
ký hiệu các hằng khác nhau biểu diễn các đối tượng riêng biệt. Reiter đã phát
biểu ban đầu rằng sự khác nhau giữa các giá trị Null chưa biết và các hằng thông
thường nằm trong sự thiếu vắng của một số các tiên đề tên duy nhất. Thí dụ, do
Jean, Paul và ω là các giáo sư, trong đó ω biểu diễn một giá trị Null, lý thuyết
LÊ VĂN TẤN
Luận văn tốt nghiệp
12
Cơ sở dữ liệu xác suất
quan hệ mở rộng chứa tên tiên đề duy nhất Paul ≠ Jean, nhưng không chứa các
tiên đề ω ≠ Jean và ω ≠ Paul.
Reiter cũng đã nghiên cứu sự ước lượng truy vấn trong các lý thuyết quan
hệ mở rộng và xác định một giải thuật đầy đủ và đúng đắn để tính toán các câu
trả lời cho các truy vấn. Một giải thuật ước lượng truy vấn là đúng đắn đối với
một lớp của các lý thuyết nếu, với mọi truy vấn, mỗi câu trả lời thu được bằng
giải thuật thoả mãn truy vấn. Giải thuật là đầy đủ nếu mỗi câu trả lời thoả mãn
truy vấn thu được bởi giải thuật.
Các cách tiếp cận lôgic và đại số là sự bổ sung, cả hai có thể được xem như
hai cách khác nhau của việc giải quyết bài toán mang tính không chắc chắn và
không đầy đủ. Cách tiếp cận đại số cho phép phát triển các phép toán lý thuyết
tập hợp cho việc thao tác thông tin không đầy đủ và không chắc chắn. Cách tiếp
cận này cho phép đo được làm thế nào các phép toán lý thuyết tập hợp này là
"trung thành (faithful)" để tri thức được biểu diễn bằng cơ sở dữ liệu, được xem
như một tập thế giới có thể.
Một cách khác trong cách tiếp cận lôgic, tri thức của cơ sở dữ liệu được
chính thức hoá bằng các ý nghĩa của các lý thuyết lôgic riêng biệt. Dưới quan
điểm của lý thuyết mô hình, các lý thuyết lôgic giữ được ý nghĩa của tri thức
không hoàn chỉnh do đó cho phép biểu diễn một tập các mô hình hay tập các thế
giới có thể. Dưới quan điểm của lý thuyết chứng minh (Proof - theoretic), các lý
thuyết lôgic cho phép chứng minh tính đúng đắn của các thao tác cơ sở dữ liệu .
Như vậy, các cách tiếp cận lôgic và đại số có thể được xem như là tương
ứng, tương ứng cho các quan điểm khai báo và thủ tục. Từ ý nghĩa của tri thức
được phát biểu một cách chính xác bằng các lý thuyết lôgic, các sự thao tác cơ sở
dữ liệu như xử lý truy vấn, kiểm tra ràng buộc toàn vẹn, và sự cập nhật có thể
được xác định khai báo trong cách thức này. Mặc dù các lý thuyết lôgic cung cấp
các ý nghĩa cho việc chứng minh sự thao tác cơ sở dữ liệu là đúng đắn theo ý
LÊ VĂN TẤN
Luận văn tốt nghiệp
13
Cơ sở dữ liệu xác suất
nghĩa đã định, chúng không cung cấp một cách có hiệu quả cho việc thực hiện
các thao tác này. Đây là vai trò của cách tiếp cận đại số với các phép toán lý
thuyết tập hợp của nó.
1.2.1. Thông tin phân tách ( Disjunctive Information)
Sự quan tâm trên thông tin phân tách đưa chúng ta trở lại những năm 70 khi
đó, nhiều công việc đã được nghiên cứu sự thao tác của kiểu thông tin này không
chỉ trong cơ sở dữ liệu quan hệ mà còn trong các lĩnh vực của lập trình lôgic và
cơ sở dữ liệu suy diễn.
Cho một quan hệ BG chứa thông tin về nhóm máu của các cá nhân, giả sử
rằng chúng ta muốn biểu diễn các thông tin phân tách sau trong quan hệ:
Nhóm máu của Marc hoặc là O hoặc là A ; và
Martha hoặc Peter có nhóm máu là A.
Các tình huống này có thể được biểu diễn bằng các cách thức sau:
BG ( Marc,O ) ∨ BG ( Marc,A ) , và BG ( Martha,A ) ∨ BG ( Peter,A ) .
Để có thể biểu diễn các sự việc phân tách như vậy trong cơ sở dữ liệu quan
hệ, việc xác định các bộ phải được khái quát hoá. Các bộ như
( Marc,O ) ∨ ( Marc,A ) , được gọi là các bộ phân tách (Disjunctive Tuples), cho phép
biểu diễn các sự việc phân tách cơ sở. Các bộ cổ điển như (Thomas,A), được gọi
là các bộ xác định (Definite Tuples), biểu diễn các sự việc nguyên tử.
Như đã được chú ý bởi Liu và Sunderraman, việc giải quyết của thông tin
phân tách được quan hệ chặt chẽ với việc giải quyết của thông tin có thể. Giả sử
rằng
BG ( Martha,A ) ∨ BG ( Peter,A ) .
được biểu diễn trong cơ sở dữ liệu , và giả sử rằng tại thời điểm cuối cùng nó
được xác nhận lại rằng Martha có nhóm máu A do BG(Martha,A) bây giờ là
đúng, thông tin này gộp vào sự phân tách trên. Nếu bộ phân tách
LÊ VĂN TẤN
Luận văn tốt nghiệp
Cơ sở dữ liệu xác suất
14
( Martha,A ) ∨ ( Peter,A ) được thay thế một cách dễ dàng bởi bộ xác định (Martha,A),
thông tin mà Peter cũng có thể có nhóm máu A bị mất, tuy nhiên, thông tin này
có thể được đưa vào dạng của một bộ có thể, đó là, một bộ mà có thể đúng hoặc
không thể đúng.
Bởi vậy, các quan hệ phân tách phải gồm một thành phần chắc chắn (Sure
Component), chứa các bộ phân tách và các bộ xác định, và thành phần có thể
(Maybe Component), chứa các bộ có thể. Một thí dụ của quan hệ phân tách BG
được cho như sau.
Sure component
Maybe component {
BG
(Thomas,A)
(Luc,O)
(Martha,A) ∨ (Peter,A)
(Marc,O) ∨ (Marc,A)
(Ross,B)
Cho quan hệ BG như trên, giả sử chúng ta muốn có tất cả các người có
nhóm máu A. Điều này có thể được biểu diễn bằng truy vấn
Q = x ( ∃y ) ( BG ( x, y ) ∧ y = A )
Câu trả lời của truy vấn này có thể được biểu diễn bằng một quan hệ phân
tách như sau:
Q
Sure component
Maybe component {
Thomas
Martha ∨ Peter
Marc
Đối với thành phần chắc chắn, Thomas chắc chắn có nhóm máu A và nó
chắc chắn rằng Martha hay Peter có nhóm máu A. Tuy nhiên, do Marc có thể có
nhóm máu O, anh ấy nằm trong thành phần có thể.
LÊ VĂN TẤN
Luận văn tốt nghiệp
15
Cơ sở dữ liệu xác suất
1.2.2. Thông tin xác suất
Cách tiếp cận xác suất đã không được nghiên cứu một cách rộng rãi cho
mô hình không chắc chắn trong cơ sở dữ liệu quan hệ. Mặc dù các mô hình xác
suất cho cơ sở dữ liệu quan hệ đã từng được đề cập, chúng ta nghĩ rằng các xác
suất này thiếu ngữ nghĩa rõ ràng.
Chúng ta sẽ nghiên cứu ở phần sau, hai kiểu thông tin xác suất có thể được
đưa vào trong cơ sở dữ liệu quan hệ. Một thí dụ của kiểu thứ nhất, xem xét một
nhận định sau " xác suất mà Martin dạy môn Biology là 0,9" kiểu thông tin này
gắn một giá trị xác suất p ∈ [ 0,1] cho một nhận định, việc biểu diễn một sự kiện
hay mối quan hệ nhận xác suất p và vì thế không nhận xác suất 1-p. Chú ý rằng
các cơ sở dữ liệu quan hệ cổ điển có thể được xem như các cơ sở dữ liệu xác suất
trong đó xác suất p chỉ nhận một trong các giá trị 0 hoặc 1. p=0 nếu nhận định là
sai và p=1 nếu nhận định là đúng.
Với việc biểu diễn thông tin loại này, các quan hệ cổ điển được khái quát
hoá bằng việc thêm vào chúng một thuộc tính bổ sung ωR ( t ) , biểu thị xác suất
mà bộ t thuộc vào quan hệ R. Các quan hệ như vậy được gọi là quan hệ xác suất
loại một (Type-1 Probabilistic relation). Một thí dụ thuộc quan hệ xác suất loại
một Takes được cho trong hình sau:
student
course
ωR
Paul
Martin
Jonh
Anne
Physics
Biology
Physics
Biology
1.0
0.9
0.5
0.6
Hình 1.3: Một quan hệ xác suất loại 1 takes
Quan hệ này được biểu diễn rằng: Paul chắc chắn nhận môn Physics,
Martin nhận môn Biology với xác suất là 0.9. Như vậy xác suất mà Martin
không nhận môn Biology là 0.1.
LÊ VĂN TẤN
Luận văn tốt nghiệp
16
Cơ sở dữ liệu xác suất
Bây giờ xem xét loại thông tin xác suất thứ hai mà có thể được đưa vào
trong cơ sở dữ liệu quan hệ. Giả sử rằng các điểm học lực thu được của các sinh
viên trong môn học Algebra được biểu diễn bằng phân phối sau.
Prob
0.7
0.2
0.1
Marks
0-14
15-17
18-20
Kiểu thông tin xác suất này mà các giá trị xác suất pi được kết hợp cho mỗi
tình huống khác nhau mà nó có thể xảy ra.
Để có được kiểu thông tin này, chúng ta sử dụng các quan hệ xác suất loại
hai. Các quan hệ này tương tự với các quan hệ của mô hình cơ sở dữ liệu xác
suất, mặc dù chúng ta cho chúng các ngữ nghĩa khác nhau. Các quan hệ xác suất
loại hai có các thuộc tính khoá xác định như trong các quan hệ cổ điển. Như vậy
mỗi bộ biểu diễn một thực thể thực hay quan hệ đã biết. Các thuộc tính khác mô
tả các đặc trưng của các thực thể và có thể là xác định hay ngẫu nhiên, tức là các
giá trị của chúng có thể được biểu diễn bằng một phân phối xác suất. Một thí dụ
của quan hệ xác suất loại hai Grade-Marks được cho như sau:
Course
Marks
Algebra 0.7(0-14)
0.2(15-17)
0.1(18-20)
Physics 0.7(0-14)
0.3(15-20)
Calculus 1.0(18-20)
Hình 1.4: Một quan hệ xác suất loại 2 Grade_marks
LÊ VĂN TẤN
Luận văn tốt nghiệp
17 Cơ sở dữ liệu xác suất
CHƯƠNG 2: TRI THỨC KHÔNG HOÀN CHỈNH TRONG
CƠ SỞ DỮ LIỆU QUAN HỆ
2.1. Giới thiệu
Cuối những năm 70, đầu những năm 80 loé lên một tia sáng cho sự cần mở
rộng cơ sở dữ liệu quan hệ để nghiên cứu các kiểu thông tin khác mà không được
xem xét trong mô hình của Codd. Việc giới thiệu thông tin không đầy đủ và
thông tin không chắc chắn là một trong những sự mở rộng được đưa ra từ các kết
quả nghiên cứu.
Thông tin chứa đựng trong một cơ sở dữ liệu là đầy đủ và chắc chắn nếu nó
biểu diễn một cách chính xác hình ảnh của miền ứng dụng tương ứng trong thế
giới thực. Tuy nhiên, trong thực tế hầu hết các thông tin khó có thể chính xác và
đầy đủ được; nói chung nó là không hoàn chỉnh, tức là, không đầy đủ và không
chắc chắn. Thông tin là không đầy đủ nếu nó chỉ diễn tả một phần tri thức của
thế giới. Thông tin là không chắc chắn nếu tình trạng thực tại mà sự chắc chắn
của nó là không được toàn vẹn.
Trong phạm vi của cơ sở dữ liệu quan hệ, các khía cạnh khác nhau thực
chất được mô hình theo 2 mức. Thứ nhất, mức độc lập với thời gian, lược đồ cơ
sở dữ liệu chỉ rõ với mỗi quan hệ là một tập các thuộc tính và các miền của nó
và tập các ràng buộc toàn vẹn. Thứ hai, mức biến đổi theo thời gian, cơ sở dữ
liệu mở rộng diễn tả tập các sự việc hay các sự kiện của thế giới thực.
Giả lược đồ thích hợp (Appropriate Scheme Assumption):
Mỗi lược đồ quan hệ là thích hợp cho việc mô tả mọi trạng thái của
mặt tương ứng; đặc biệt, các miền đủ phong phú để biểu diễn tất cả các mặt
khác nhau của sự thực. Ngoài ra, mỗi sự kiện trên thực tế, ở đó tồn tại một
bộ tương ứng và một bộ là một phần tử của một quan hệ nếu sự kiện được
biểu thị trên thực tế.
LÊ VĂN TẤN
Luận văn tốt nghiệp
18 Cơ sở dữ liệu xác suất
Giả sử rằng tồn tại một quan hệ r là một mô hình thích hợp của khía cạnh
tương ứng của thực tại. Trên thực tế quan hệ này là luôn luôn không biết một
cách đầy đủ. Nếu có thông tin không đầy đủ hay không chắc chắn, để lưu trữ
quan hệ r trong cơ sở dữ liệu, ta biểu diễn tất cả các thông tin có giá trị về quan
hệ này được đưa vào trong cơ sở dữ liệu. Hơn nữa, đôi khi cấu trúc cơ sở dữ liệu
không tương thích cho cấu trúc của thế giới bên ngoài, ví dụ khi thuộc tính của
quan hệ không thể áp dụng trong một số trường hợp riêng biệt. Thường, kiểu
tình huống này xuất hiện việc thêm vào thông tin không đầy đủ hay không chắc
chắn.
Việc đưa thông tin không đầy đủ hay thông tin không chắc chắn vào trong
cơ sở dữ liệu đã nảy sinh một vấn đề cố hữu cho việc thao tác thông tin như vậy.
Trả lời truy vấn, kiểm tra tính toàn vẹn của các ràng buộc và cập nhật cơ sở dữ
liệu bắt buộc phải được xác định lại để đánh giá tri thức không hoàn chỉnh. Vấn
đề này có thể được chia nhỏ thành các vấn đề sau:
- Xác định các kiểu không đầy đủ và không chắc chắn mà nó có thể được
biểu diễn trong cơ sở dữ liệu;
- Xác định cách thức cho phép biểu diễn các kiểu thông tin không đầy đủ và
thông tin không chắc chắn;
- Thiết kế các giải thuật để trả lời các truy vấn được xác định trong cơ sở dữ
liệu, chú ý tới các kiểu khác nhau của thông tin không đầy đủ và không chắc
chắn;
- Xác định các kiểu ràng buộc toàn vẹn mà cơ sở dữ liệu phải thoã mãn;
- Thiết kế các giải thuật để kiểm tra sự thoã mãn của các ràng buộc toàn
vẹn;
- Xác định các phương pháp để đưa thông tin mới vào trong cơ sở dữ liệu;
- Thiết kế giải thuật để đưa thông tin mới vào trong cơ sở dữ liệu.
LÊ VĂN TẤN
Luận văn tốt nghiệp
19 Cơ sở dữ liệu xác suất
Trong một cơ sở dữ liệu, thông tin không đầy đủ xuất hiện trong nhiều tình
huống khác nhau. Trước hết trong giai đoạn đầu của một cơ sở dữ liệu mới,
không phải tất cả các thông tin cần thiết đã được đưa ra; chúng ta có một cơ sở
dữ liệu không đầy đủ theo lý thuyết. Sau đó, thông tin mới có thể được sửa đổi
trong cơ sở dữ liệu, cho sự cập nhật của cơ sở dữ liệu không đầy đủ (theo lý
thuyết). Đó cũng là khả năng mà các lý do riêng tư hay an toàn, thông tin về một
số các thành viên của miền không được lưu trữ trong cơ sở dữ liệu. Cũng vì vậy,
một số thông tin có thể là thiếu vì nó là khó, hay không đúng quy cách để thu
được.
Trong trường hợp cơ sở dữ liệu phân tán, trách nhiệm của việc đưa vào
thông tin có thể là phân quyền. "Khung nhìn" của người sử dụng có thể bỏ qua
thông tin được lưu trữ trong cơ sở dữ liệu. Bởi vậy, các sự cập nhật khung nhìn
thường gây ra thông tin không đầy đủ.
Thông tin không chắc chắn xuất hiện do thông tin nguồn thiếu sự tin cậy
hay vì thông tin đến từ các nguồn là mâu thuẫn nhau. Thêm vào đó, sự không
chắc chắn cũng xuất hiện trong khi ước lượng và thao tác các thông tin lưu trữ.
Trong môi trường kinh tế, việc lập kế hoạch là một tình huống ở đó khả
năng thao tác trên thông tin không đầy đủ và không chắc chắc là rất quan trọng.
Thí dụ, các giá trị của một số tham số có thể là không biết, và nó là chung chung
để đưa ra hoặc nhiều giá trị khả năng hoặc các giá trị mặc định cho một số thuộc
tính để thực hiện sự giả định của các viễn cảnh kinh tế khác nhau.
2.2. Thế giới có thể (Possible worlds)
Một cơ sở dữ liệu biểu diễn tất cả các thông tin có giá trị về một phần của
thế giới thực đã được mô hình hoá. Nếu thông tin của cơ sở dữ liệu là đầy đủ và
chắc chắn, có sự tương ứng giữa cơ sở dữ liệu và thế giới thực. Ngược lại, khi tri
thức về thế giới là không đầy đủ và không chắc chắn, một số "viễn cảnh" hay các
LÊ VĂN TẤN
- Xem thêm -