Đăng ký Đăng nhập
Trang chủ Công nghệ thông tin An ninh bảo mật Cơ sở dữ liệu xác xuất...

Tài liệu Cơ sở dữ liệu xác xuất

.PDF
107
571
109

Mô tả:

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 -

Tài liệu liên quan