- 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. - 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. - Các phép toán trên các quan hệ xác suất 81 CHƯƠNG 4. - 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ệ. - 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ệ. - 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 Cơ sở dữ liệu xác suất 7thiế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ệ. - 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ệ. - 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ể. - 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. - 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 Cơ sở dữ liệu xác suất 11trong hình 1.2 như các thế giới có thể của nó. - Đố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. - 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ể. - 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ệ. - 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. - 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). - LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 16Bâ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ệ. - Để 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. - LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 18Giả 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. - 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. - Đối với việc gán các ngữ nghĩa vào một cơ sở dữ liệu với sự có mặt của thông tin không đầy đủ hay thông tin không chắc chắn, mỗi quan hệ R phải được kết hợp giá trị của hàm biểu diễn REP(R), là tập thế giới có thể biểu diễn bởi quan hệ. - Nói một cách chung hơn, hàm biểu diễn cho phép kết hợp một cơ sở dữ liệu (tập các quan hệ) với một tập các cơ sở dữ liệu quan hệ cổ điển là các thế giới có thể của nó. - Nếu các giá trị Null chỉ nhận một giá trị và nếu quan hệ được thể hiện dưới giả định LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 22thế giới đóng, thế giới có thể của REP() được đưa ra như hình 2.2. - Trong việc biểu diễn tính không đầy đủ và không chắc chắn, các ngữ nghĩa này cho phép phát biểu chính xác "ý nghĩa" của thông tin bởi việc xác minh mối quan hệ giữa thông tin đã chứa trong cơ sở dữ liệu và cái gì nó biểu diễn, đó là một tập các thế giới có thể. - Quan hệ này có thể thu được việc tạo ra kết nối giữa hai quan hệ. - Thật vậy, theo quan hệ ban đầu trạng thái thực của thế giới r* là một trong những thế giới có thể trong REP (R). - Điều này có thể được phát biểu bởi: θ()()()()REP f R f REP R⊇ Và không có đa quan hệ R' mà. - LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 27tức là, quan hệ ()fR có thể giữ thông tin về tất cả các bộ mà chắc chắn thuộc vào ()*fr theo ()REP R . - LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 29Như vậy, khả năng có ý nghĩa của các quan hệ với các tập OR là không đủ để hỗ trợ phép chiếu và kết nối. - Cho một lược đồ quan hệ trên các thuộc tính {},,ABC , phụ thuộc hàm có thể được biểu diễn bằng công thức: A→ B . - →→LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 30Cho quan hệ Teaches như sau: professor course Department Thomas Thomas Algebra CalculusMathematicsPhysics Nếu quan hệ thuộc ()Pr of CourseSat. - Vấn đề sau đó là mô tả đặc điểm ý nghĩa của một cơ sở dữ liệu được xác định bởi một quan hệ r và một tập phụ thuộc. - Vì cơ sở dữ liệu không hoàn chỉnh biểu diễn một tập cơ sở dữ liệu quan hệ cổ điển, ý định làm cho thoả mãn của tập phụ thuộc khái quát hoá ()X Sat. - Khả năng duy nhất là bỏ đi quan hệ từ sự đầy đủ. - Xem xét thí dụ hai quan hệ sau: LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 41 professor Course Student course Dept. - Sự cập nhật này có thể giành được bằng C- quan hệ sau : student course Dept. - Bây giờ xem xét một sự cập nhật mà hoặc là Martin hoặc là Peter được xoá đi từ quan hệ thứ nhất LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 42Student ở trên. - Sự cập nhật như vậy có thể được biểu diễn với C-quan hệ: student course Dept. - CƠ SỞ DỮ LIỆU XÁC SUẤT Trong chương này chúng ta khái quát hoá mô hình quan hệ thích hợp để nắm bắt và thao tác một kiểu riêng biệt của thông tin xác suất. - Đối với điều này, chúng ta định nghĩa các quan hệ xác suất và xác định ngữ nghĩa của chúng. - Tuy nhiên, việc thao tác cơ sở dữ liệu xác suất ngụ ý chuyển cơ sở dữ liệu thành các t-quan hệ, áp dụng các phép toán quan hệ trên t-quan hệ và chuyển các kết quả thu được thành quan hệ xác suất. - 3.1.Các quan hệ xác suất Có hai kiểu khác nhau của thông tin xác suất có thể được đưa ra trong cơ sở dữ liệu quan hệ, đó là : Thông tin xác suất về sự kết hợp của các giá trị dữ liệu (xác suất mà một phần tử thuộc vào một quan hệ), và thông tin xác suất về giá trị. - Đối với điều này bây giờ chúng ta định nghĩa các quan hệ xác suất. - Các quan hệ này thu LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 44được bằng việc thêm vào các quan hệ cổ điển một thuộc tính bổ sung biểu diễn xác suất mà bộ phụ thuộc vào quan hệ. - Một quan hệ xác suất r của lược đồ quan hệ được xác định như sau: ℜ. - Một quan hệ xác suất r có thể được trình bày như một bảng trong đó thuộc tính ω được biểu diễn tại cột thêm vào. - ()tωω=0>()t 0Ví dụ 3.1 Cho quan hệ takes với các thuộc tính student và course là một quan hệ xác suất. - LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 45Hơn thế nữa, do nó được thừa nhận rằng mọi cặp (student, course) không xuất hiện trong quan hệ có xác suất là 0. - Do một cơ sở dữ liệu chứa một số quan hệ. - Trong chương này các quan hệ xác suất được biểu thị bằng các chữ cái hoa R,S. - Xem xét quan hệ takes của Ví dụ 3.1. - Do nó chắc chắn rằng Marry nhận môn Physics, quan hệ này biểu diễn bốn tình huống khác nhau phụ thuộc bất cứ LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 46trường hợp Paul nhận Algebra và bất cứ trường hợp Anne nhận Physics . - Do vậy, các thế giới khả năng của quan hệ takes được đưa ra trong hình sau . - (mary,physics) (mary,physics)(paul,algebra) (mary,physics)(anne,physics)(mary,physics)(paul,algebra) (anne,physics Hình 3.1: Các thế giới khả năng của quan hệ takes Cụ thể hơn, cho R là quan hệ xác suất với ()(){}11. - Quan hệ này biểu diễn nhiều nhất là 2n quan hệ cổ điển. - Bây giờ chúng ta định nghĩa ánh xạ PW, mà tính toán tất cả các thế giới khả năng của quan hệ xác suất. - Định nghĩa: Nếu R là quan hệ xác suất với ()(){}11. - Khái niệm này của thế giới khả năng đã được khái quát hoá cho đa quan hệ. - Nếu 1,...,k= RRR là một đa lược đồ, và 1,...,kRR=R là một đa quan hệ xác suất LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 47trên , các thế giới khả năng của R là các cặp R ,ps mà s là một đa quan hệ cổ điển trên R và p là một số thực thuộc []0,1 . - Cho một đa quan hệ xác suất 1,...,R=R , mỗi thế giới khả năng ,ps của PW(R) thu được từ dãy 11. - Định nghĩa: Cho 1,...,k= RRR là một đa lược đồ và 1,...,kRR=R là một đa quan hệ xác suất trên . - LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 48Định nghĩa: Cho 1,...,k= RRR là một đa lược đồ và 1,...,kRR=R là một đa quan hệ xác suất trên . - Các quan hệ này có thể có hai loại dư thừa như sau: (1). - Vì thế, John thuộc quan hệ RRR=∪ với xác suất . - là một đa quan hệ xác suất, thì ()1. - REP (REDUCE(R)) với mọi đa quan hệ xác suất . - R ∈ΓRHình 3.4 thể hiện REP(REDUCE(student)) và REP(student) cho quan hệ của Hình 3.3. - Thật vậy, với mỗi đa quan hệ R, nếu {}11. - LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 51Định lý 3.3: Với mọi đa quan hệ xác suất R. - Bây giờ chúng ta định nghĩa các phép toán trên quan hệ xác suất như sau. - Phép chiếu: Cho R1 là một quan hệ xác suất của lược đồ . - Phép chọn: Cho R1 là một quan hệ xác suất và cho F là một công thức chọn. - Phép hợp: Cho R1 và R2 là hai quan hệ xác suất khả hợp. - Phép trừ: Cho R1 và R2 là hai quan hệ xác suất khả hợp. - Phép giao: Cho R1 và R2 là hai quan hệ xác suất khả hợp. - Phép kết nối: Cho R1 và R2 là hai quan hệ xác suất của lược đồ ()1,ABR và (2,)BCR . - .Tích Đề các: Cho R1 và R2 là hai quan hệ xác suất. - Phép chia: Chúng ta chỉ xem xét phép chia của các quan hệ xác suất cho các quan hệ cổ điển. - Cho R1 và R2 , tương ứng là quan hệ xác suất và quan hệ cổ điển. - Quan hệ và P Q()3 ePQσ. - T-quan hệ có một số điểm giống với C-bảng ( của Imielinski và Lipski). - Một t-quan hệ R trên được xác định như sau: R(){}11. - Quan hệ R sau là một t-quan hệ abc. - ()Pac Qac Pad Qcd∨∨ Nếu cơ sở dữ liệu đã kết hợp với R chứa các quan hệ xác suất sau: P Q ab ac ad p1 p2 p3 ac bd p4 p5 t-quan hệ R biểu diễn, ví dụ abc R∈ trong thế giới khả năng trong đó mà. - LÊ VĂN TẤN Luận văn tốt nghiệp Cơ sở dữ liệu xác suất 56Định nghĩa: Cho R là một đa lược đồ, trong đó 1,...,k= RRR và mỗi là một lược đồ quan hệ. - Cuối cùng, chúng ta định nghĩa một ánh xạ TRANS mà kết hợp với mỗi quan hệ xác suất một t-quan hệ. - Khái niệm này là rất quan trọng khi thao tác cơ sở dữ liệu xác suất, do việc không thể định nghĩa một đại số trên các quan hệ xác suất. - Định nghĩa: Cho R là một quan hệ xác suất
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt