intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Một hướng triển khai của cơ chế cho phép suy luận trên cơ sở dữ liệu mờ

Chia sẻ: Minh Minh | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST
Báo xấu
33
lượt xem 2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài báo này giới thiệu một hướng triển khai cơ chế kết hợp biểu diễn các luật suy luận và thông tin mờ được lưu trữ trong một cơ sở dữ liệu quan hệ truyền thống để xây dựng một module có khả năng suy ra dữ liệu mới từ dữ liệu đã có trong các bảng. Các suy luận có thể áp dụng trên dữ liệu rõ (dữ liệu chính xác), dữ liệu mờ hoặc cả hai loại dữ liệu rõ và mờ.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Một hướng triển khai của cơ chế cho phép suy luận trên cơ sở dữ liệu mờ

  1. JOURNAL OF SCIENCE OF HNUE FIT., 2013, Vol. 58, pp. 13-27 This paper is available online at http://stdb.hnue.edu.vn MỘT HƯỚNG TRIỂN KHAI CỦA CƠ CHẾ CHO PHÉP SUY LUẬN TRÊN CƠ SỞ DỮ LIỆU MỜ Nguyến Tiến Thành, Hồ Cẩm Hà1 1 Khoa Công nghệ Thông tin, Trường Đại học Sư phạm Hà Nội 1 Email: hahc@hnue.edu.vn Tóm tắt. Bài báo này giới thiệu một hướng triển khai cơ chế kết hợp biểu diễn các luật suy luận và thông tin mờ được lưu trữ trong một cơ sở dữ liệu quan hệ truyền thống để xây dựng một module có khả năng suy ra dữ liệu mới từ dữ liệu đã có trong các bảng. Các suy luận có thể áp dụng trên dữ liệu rõ (dữ liệu chính xác), dữ liệu mờ hoặc cả hai loại dữ liệu rõ và mờ. Từ khóa: Cơ sở dữ liệu quan hệ, suy luận mờ. 1. Giới thiệu Mô hình quan hệ được đưa ra bởi Codd [1], cho đến nay đã có được nền tảng lí thuyết phát triển đầy đủ và có phạm vi ứng dụng rộng rãi nhất trong thực tế. Trong những năm qua, với cách tiếp cận dùng lí thuyết tập mờ, đã có nhiều cách mở rộng mô hình quan hệ truyền thống để biểu diễn và thao tác với thông tin mờ được đề xuất [2,3,4,5,6]. Để một hệ CSDL quan hệ có thêm chức năng biểu diễn, suy luận và truy vấn được các giá trị mờ (chẳng hạn như “tìm những người còn trẻ”), cần có một ngôn ngữ truy vấn mềm dẻo, đồng thời cần có một cơ chế suy diễn trên tập dữ liệu rõ và mờ, Medina, Pons và Vila đã đưa ra hai ý tưởng đó trong [7]. Chúng tôi đã triển khai một hệ thống CSDL suy diễn theo ý tưởng của Igrancio Blanco, Juan C. Cubero, Olga Pons, và Amparo Vila [8], nhằm mở rộng cơ sở dữ liệu quan hệ để có thêm hai khả năng là biểu diễn được thông tin mờ và suy luận ra dữ liệu mới từ các dữ liệu đã có. 2. Nội dung nghiên cứu 2.1. Một mô hình cơ sở dữ liệu suy diễn mờ 2.1.1. Ý tưởng về hệ CSDL suy diễn của Media, Pons, Vila và Cubero Các tác giả Medina, Pons, Vila và Cubero [9] đã đặt tên FSQL cho ngôn ngữ truy vấn mờ, tức là một ngôn ngữ truy vấn mềm dẻo hoạt động trên các giá trị mờ và rõ, và đặt 13
  2. Nguyến Tiến Thành, Hồ Cẩm Hà tên DFSQL cho ngôn ngữ suy luận mờ, tức là ngôn ngữ truy vấn mà có thể suy luận trên cả dữ liệu rõ và mờ. Cấu trúc cho một Server CSDL suy diễn với ba thành phần được mô tả trong hình 1. Chức năng của mỗi thành phần được giải thích như sau: DFSQL Client: Nhận các câu DFSQL từ người sử dụng và chuyển nó đến DFSQL Server và trả ra kết quả của truy vấn được hiển thị cho người sử dụng. DFSQL Server: Nhận các câu truy vấn được gửi đến từ DFSQL Client, tách chúng thành các phần riêng biệt bao gồm phép xử lí mờ và các phép suy luận. Chúng ta cần phân biệt giữa FSQL (câu lệnh truy vấn mờ), DSQL (câu lệnh suy diễn) và các câu DFSQL. Tất cả chúng được chuyển thành một tập các câu SQL cố điển và các lời gọi hàm. Bộ thực thi phát biểu SQL: Nhận các câu SQL cố điển, theo đó DFSQL Server sẽ dịch các câu DFSQL của người dùng và thực thi nó trên cơ sở dữ liệu, sử dụng từ điển dữ liệu được lưu trữ trong Catalog dữ liệu bao gồm Catalog dữ liệu cổ điển và Catalog dữ liệu mở rộng được tạo nên từ FMB(Fuzzy Meta-Base) và Ruler base. Cơ sở dữ liệu: Bao gồm dữ liệu. Hình1. Tổ chức hệ thống DFSQL trong FREDDI Catalog: Bao gồm thông tin về dữ liệu trong cơ sở dữ liệu. Catalog mở rộng: Bao gồm thông tin về dữ liệu mờ được lưu trữ trong cơ sở dữ liệu (FMB hay Fuzzy Meta-Base) cũng như các luật logic được sử dụng để suy luận trên cơ sở dữ liệu (Ruler base). Mô tơ suy luận: Sử dụng thông tin về dữ liệu mờ và luật suy luận được lưu trữ trong Catalog mở rộng để suy luận ra dữ liệu mới từ dữ liệu đã có. 14
  3. Một hướng triển khai của cơ chế cho phép suy luận trên cơ sở dữ liệu mờ 2.1.2. Các hướng triển khai và các mô hình biến thể Khi mở rộng một hệ quản trị cơ sở dữ liệu quan hệ (RDBMS) để nó có thêm khả năng biểu diễn thông tin mờ và suy luận, chúng ta sẽ bị giới hạn bởi mô hình quan hệ và tất cả các cấu trúc được sử dụng trong mô hình đó. Các hướng triển khai Hai khả năng biểu diễn thông tin mờ và suy luận được triển khai trên hai thành phần riêng biệt mà không có mối liên hệ nào giữa chúng. Do đó, cần phải có một module hòa hợp kết quả của hai thành phần khi chúng ta thực hiện các thao tác. Oracle c đã được tích hợp thêm thành phần mới và theo cách khác nhau trên các phiên bản khác nhau của FREDDI. Mô tơ suy luận là một module ngoại diên, nó không làm ảnh hưởng gì đến các chức năng của hệ quản trị cơ sở dữ liệu quan hệ và được triển khai trên cơ sở một ngôn ngữ có khả năng kết nối với Oracle c . Hiện nay, Oracle c , đã cung cấp các ngôn ngữ lập trình có khả năng kết nối đó. Có hai khả năng lựa chọn và phụ thuộc vào ngôn ngữ được cung cấp bởi Oracle c : Thứ nhất là Pro*C c . Đây là ngôn ngữ C có thêm các câu lệnh mở rộng cho phép sử dụng hay kết nối với Oracle c . Thứ hai là PL/SQL c . Đây là ngôn ngữ lập trình cơ sở dữ liệu có ngay trong RDBMS. Các module được tạo ra, lưu trữ và thực thi trong RDBMS, vì vậy không cần đến khả năng kết nối. Tuy nhiên ngôn ngữ này lại không thông dụng và có nhiều hạn chế hơn lựa chọn đầu tiên. Các mô hình biến thể Phụ thuộc vào ngôn ngữ được lựa chọn, chúng ta có vài biến thể từ mô hình ban đầu. Máy suy luận ngoại diên: Là mô hình được gợi ý khi sử dụng những ngôn ngữ bên ngoài RDBMS như Pro*C c được sử dụng (Hình 2). Hình 2. Mô hình máy suy ngoại diên 15
  4. Nguyến Tiến Thành, Hồ Cẩm Hà Máy suy luận nội hàm: Là mô hình được gợi ý khi sử dụng những ngôn ngữ bên trong RDBMS, như PL/SQL c được sử dụng (Hình 3). Hình 3. Mô hình máy suy luận nội hàm 2.1.3. Biểu diễn thông tin mờ và luật logic trong mô hình quan hệ Catalog về dữ liệu được mở rộng để lưu trữ thông tin về dữ liệu mờ và các luật logic trong cơ sở dữ liệu. Nó gồm hai catalog con: - FMB catalog hay Fuzzy Meta-Base catalog: Lưu trữ thông tin về dữ liệu mờ. - Ruler Base catalog: Lưu trữ các luật logic phục vụ cho sự suy luận. a. FMB catalog Các kiểu thuộc tính mờ có thể biểu diễn trong hệ thống là: Các thuộc tính mờ loại 1: Là các thuộc tính có thể nhận các giá trị rõ nhưng được truy vấn bởi các câu truy vấn mờ trên các giá trị chúng được gán nhãn trong miền giá trị. Các thuộc tính mờ loại 2: Là các thuộc tính có thể lưu trữ các số mờ, như Zadeh đề xuất [10]. Các số mờ đó được biểu diễn bởi sự phân bố trên những miền liên tục hoặc rời rạc mà trong đó tồn tại mối quan hệ về thứ bậc. Các kiểu giá trị của các thuộc tính này có thể là: - Kiểu giá trị thuộc chuẩn hình thang: Được biểu diễn dựa trên một hàm thuộc mà dữ liệu được xác định bởi bốn thông số [α, β, γ, δ]. - Các nhãn ngôn ngữ: Được biểu diễn bởi các từ mang tính ngôn ngữ, cũng được biểu diễn bởi sự phân bố, chẳng hạn như nhãn “cao” hay “nặng” của một người. - Các giá trị xấp xỉ: Biểu diễn cho nội dung mờ “xấp xỉ n” khi n là một giá trị nằm 16
  5. Một hướng triển khai của cơ chế cho phép suy luận trên cơ sở dữ liệu mờ trên một miền có thứ tự. Sự phân bố được biểu diễn bởi một hình tam giác, xác định bởi một thông số gọi là margin và được biểu diễn bằng [n – margin, n, n, n + margin]. - Các giá trị khoảng: Đặc thù bởi sự phân bố trên hình thang khi mà không có sự nghiêng đi của các cạnh. Loại này do Grant đề xuất [11] và được biểu diễn bằng [α, α, β, β]. Các thuộc tính mờ loại 3: Là các thuộc tính được định nghĩa một cách rời rạc trên các miền không có thứ bậc, nơi mà mối quan hệ giữa các giá trị là như nhau. Các kiểu giá trị của loại này có thể là: - Các giá trị vô hướng: Là khả năng phân bố mà chỉ có một giá trị tồn tại. Kí hiệu (1, d) cho trường hợp chỉ có 1 giá trị d xuất hiện và độ thuộc của nó bằng 1. - Các giá trị phân bố trên một miền vô hướng: Là dữ liệu được xác định là nằm trên các miền các xác định giá trị vô hướng và không có thứ tự {(p1 , d1 ), .., (pn , dn )}. Đối với các kiểu mờ này, có những giá trị đặc biệt được giới thiệu bởi Cold [12-15] cần phải quan tâm đến đó là: UNKNOWN: biểu diễn sự không xác định của một giá trị thuộc tính. Nghĩa là một thuộc tính có thể nhận bất kì giá trị nào trong miền giá trị với khả năng là 1 vì vậy có thể được biểu diễn bằng {1/u, ∀u ∈ U} với U là miền xác định. UNDEFINED: được dùng khi không có giá trị nào trong miền xác định mà thuộc tính này có thể nhận được và vì vậy nó có thể được biểu diễn bằng {0/u, ∀u ∈ U} với U là miền xác định. NULL: để chỉ ra rằng không có thông tin nào về thuộc tính bởi vì không thể biết nó thuộc UNKNOWN hay UNDEFINED vì vậy có thể biểu diễn nó bằng 1/UNKNOWN, 1/UNDEFINED. Tóm lại, có thể lưu trữ các giá trị mờ loại 2 được trình bày trong bảng 1 và các giá trị mờ loại 3 trong bảng 2. Bảng 1. Biểu diễn của các thuộc tính mờ loại 2 trong một RDBMS Thuộc tính dữ liệu cho kiểu giá trị mờ loại 2 Kiểu giá trị FT F1 F2 F5 F4 UNKNOWN 0 NULL NULL NULL NULL UNDEFINED 1 NULL NULL NULL NULL NULL 2 NULL NULL NULL NULL RÕ 3 d NULL NULL NULL NHÃN 4 FUZZY_ID NULL NULL NULL KHOẢNG[n,m] 5 n NULL NULL m XẤP XỈ(d) 6 d d - margin d + margin margin HÌNH THANG 7 α β γ δ 17
  6. Nguyến Tiến Thành, Hồ Cẩm Hà Trong đó FT lưu trữ kiểu giá trị và F1, F2, F3 và F4 lưu mỗi giá trị thông số. Giá trị NULL trong bảng này mang ý nghĩa là giá trị không được lưu trữ để dùng trong một RDBMS. Bảng 2. Biểu diễn của các thuộc tính mờ loại 3 trong một RDBMS Thuộc tính dữ liệu cho kiểu giá trị mờ loại 2 Kiểu giá trị FT FP1 F1 FPn Fn UNKNOWN 0 NULL NULL NULL NULL UNDEFINED 1 NULL NULL NULL NULL NULL 2 NULL NULL NULL NULL ĐƠN 3 p d NULL NULL MIỀN 4 p1 d1 pn dn Trong đó FT lưu trữ kiểu giá trị và mỗi cặp (pn , dn ) biểu diễn rằng có thể nhân giá trị dn trên miền giá trị với độ chắc chắn là pn . Cấu trúc bảng của FMB được trình bày trong hình 4 và nó dựa trên cơ sở cấu trúc bảng của Oracle c . Hình 4: Cấu trúc bảng của FMB 18
  7. Một hướng triển khai của cơ chế cho phép suy luận trên cơ sở dữ liệu mờ Dưới đây là mô tả các thành phần của mỗi bảng: FUZZY_COL_LIST: bao gồm danh sách các thuộc tính trong cơ sở dữ liệu có thể được xử lí theo cách mờ. Mô tả thuộc tính đó trong bảng (OBJ#) thuộc về cột (COL#) với kiểu mờ (F_TYPE), số các giá trị trong phân bố nếu nó là thuộc tính mờ loại 3 là (LEN) và chú thích cho thuộc tính là (COM). FUZZY_OBJECT_LIST: chứa các đối tượng mờ biểu diễn các giá trị trong các thuộc tính của cơ sở dữ liệu. Mỗi đối tượng được mô tả bởi bảng và cột chứa nó, một định danh F_ID, một tên và một kiểu mờ. FUZZY_LABEL_DEF: chứa thông tin về sự phân bố theo chuẩn hình thang của các nhãn ngôn ngữ. Được mô tả bởi bốn thông số: α, β, γ và δ. FUZZY_APPROX_FCOMP: chứa các thông số margin và fcomp được sử dụng nếu làm việc với đối tượng thuộc kiểu mờ loại 1 hoặc kiểu mờ loại 2. Bảng bao gồm các cột MARGIN, MUCH, OBJ# và COL#. FUZZY_NEARNESS_DEF: chứa các giá trị về độ tương tự giữa các cặp giá trị trong cùng một miền. Quan hệ tương tự là quan hệ giữa các giá trị mờ loại 3. Bậc (DEGREE) là thông số so sánh giữa các cặp giá trị F_ID1 và F_ID2 có trong cột COL# của bảng OBJ#. FUZZY_COMPATIBLE_COL: chứa thông tin về sự đối sánh của các thuộc tính mờ loại 3 vì khi một thuộc tính được đối sánh với một thuộc tính khác thì nó sẽ không cần phải định nghĩa lại tất cả các nhãn và các mối quan hệ. Mỗi dòng biểu diễn một mối quan hệ giữa (OBJ#1, COL#1) và (OBJ#2, COL#2). FUZZY_QUALIFIERS_DEF: chứa thông tin về mỗi nhát cắt với lượng từ QUALIFIER của nhãn mang tính ngôn ngữ (F_ID) được chứa trong cột COL# của bảng OBJ#. Những bảng nói trên chỉ được lưu trữ trong DFSQLServer và được quản trị bởi người quản tri cơ sở dữ liệu, tất cả các Client truy cập tới chúng chỉ có quyền đọc, không có quyền ghi hay sửa. Ruler base catalog Bảng 3. Bảng cha mẹ Con trai / Con Bố / Mẹ gái John Mike Mary Mike Karl Louise Maggie Louise Mike Jake Louise Jake 19
  8. Nguyến Tiến Thành, Hồ Cẩm Hà Giả sử chúng ta có một bảng như bảng 3 và cần phải tìm thông tin về tổ tiên của một người nào đó. Có hai cách làm, cách thứ nhất là biểu diễn thông tin đó trong cơ sở dữ liệu thành một bảng có dạng như bảng 4. Bảng 4. Bảng tổ tiên Tổ tiên Con cháu John Mike John Jake Mary Mike Mary Jake Karl Louise Karl Jake Maggie Louise Maggie Jake Mike Jake Louise Jake Việc thêm một thông tin về bố mẹ trong bảng cha mẹ sẽ dẫn đến việc thêm thông tin về tổ tiên trong bảng tổ tiên. Trong nhiều trường hợp, số lượng thông tin phải thêm vào bảng tổ tiên là rất lớn. Tuy nhiên, có một cách làm khác mà vẫn có thể thu được thông tin về tổ tiên bằng việc biểu diễn cách hoàn thành bảng tổ tiên. Chúng ta biết rằng, cha mẹ của một người là tổ tiên của người đó, và cha mẹ của cha mẹ cũng là tổ tiên, và cứ thế. Nếu biểu diễn thông qua luật logic thì ta có: TOTIEN(X , Y) CHAME(X , Y) TOTIEN(X , Y) ⇐ CHAME(X , Z) AND TOTIEN(Z , Y) (1) Có thể thiết kế một module thu thập dữ liệu từ các luật này để bảng tổ tiên có thể được cập nhật một cách hoàn toàn tự động ngay khi thông tin mới được thêm vào bảng cha mẹ. Ta thấy có hai tân từ xuất hiện trong các luật ở (1). Thuộc tính CHAME là tân từ ứng với bảng chứa dữ liệu, trong khi tân từ TOTIEN thì lại không. Vì vậy ta có các kiểu của các tân từ là: Tân từ ngoại diên xuất hiện trên các bảng ngoại diên, là những bảng mà nội dung không phụ thuộc vào nội dung của các bảng khác. Mỗi biến của một tân từ ngoại diên thuộc về một cột trong bảng ngoại diên. Sự tham chiếu này được lưu trữ trong catalog luật. Tân từ nội hàm xuất hiện trong các bảng nội hàm, tức là những bảng mà nội dung phụ thuộc vào nội dung của các bảng khác. Các bảng và các tân từ nội hàm được đăng ký lưu trú trong bảng được gọi là INTENSIONAL_CATALOG. Trường hợp đơn giản nhất khi thực hiện suy diễn là các luật có chiều cao mức 1, 20
  9. Một hướng triển khai của cơ chế cho phép suy luận trên cơ sở dữ liệu mờ tức là các luật chỉ bao gồm các tân từ ngoại diên hoặc các hằng. Nhưng tiếc thay, đó lại là điều ít khi xảy ra. Suy diễn thường phải thực hiện với các luật có chiều cao ở mức lớn hơn 1 và bao gồm tân từ nội hàm hoặc cả những thông số không được tính toán từ trước. Trường hợp khó nhất là suy luận với những luật bao gồm các tân từ được định nghĩa bởi các luật khác. Một luật suy diễn có dạng: P ← K1 ∨ K2 ∨...∨ Km ∧ Km+1 ∧ Km+2 ∧...∧Kn (2) có thể chuyển về dạng: P ← (K1 ∨ K2 ∨ ...∨ Km ) ∧ (Km+1 ∧ Km+2 ∧ ...∧ Kn ) (3) Chuyển luật về dạng chuẩn tắc tuyển ta được: P ← (K1 ∧ (Km+1 ∧ Km+2 ∧ ... ∧ Kn )) ∨ (K2 ∧ (Km+1 ∧ Km+2 ∧ ... ∧ Kn )) ∨ ... ∨ (Km ∧ (Km+1 ∧ ∧ Km+2 ∧ ... ∧ Kn )) (4) và kết quả rút gọn là: P ← P1 ∨ P2 ∨ ... ∨ Pm (5) với: Pi ← Ki ∧ (Km+1 ∧ Km+2 ∧ .. ∧ Kn ) (6) Vì luật được chuyển thành tuyển của các luật nên trong biểu thức của các luật chỉ còn lại một phép tính liên từ. Cấu trúc bảng thể hiện thông tin này được mô tả ở hình 5. Hình 5. Cấu trúc bảng của rule base Dưới đây là mô tả chi tiết hơn về mỗi bảng: INTENSIONAL_TABLE_DESCRIPTION: lưu trữ các tân từ nội hàm P (TABLE_ID) được định nghĩa thông qua các luật Pi (RULER_ID). RULER_DESCRIPTION: mô tả mỗi luật Pi là một chuỗi các tân từ nội hàm, các tân từ ngoại diên hoặc cả tân từ nội hàm và cả tân từ ngoại diên được liên kết với nhau bởi các phép tính liên từ. Các tân từ có thể đi kèm các dấu phủ định. Một tân từ có thể xuất hiện nhiều hơn một lần trong một luật nhưng ở các vị trí khác nhau. TABLE_ID và RULER_ID định danh luật. PRED_ID định danh tân từ, OCC_NUMBER xác định vị trí của luật, NEGATED chỉ ra nếu như tân từ được cho là phủ định và TYPE cho biết tân từ là nội hàm, ngoại diên hay là so sánh. 21
  10. Nguyến Tiến Thành, Hồ Cẩm Hà PREDICATE_DESCRIPTION: mô tả thứ tự của các biến trong các tân từ Ki . Một biến có thể xuất hiện nhiều hơn một lần trong một tân từ nhưng trong nhiều trường hợp, vị trí xuất hiện của biến là quan trọng. TABLE_ID và RULER_ID định danh luật, PRE_ID xác đinh tân từ, OCC_NUMBER chỉ ra vi trí xuất hiện của tân từ trong luật, VAR_ID chỉ ra biến và COL_ID xác định vị trí của biến trong tân từ. CONDITION_DESCRIPTION: mô tả các điều kiện, kiểu đặc biệt của tân từ, nó chỉ bao gồm hai biến và các kiểu của nó là =, 6=, ≤, ≥ và >. TABLE_ID và RULER_ID định danh luật, PRED_ID định danh tân từ, OCC_NUMBER chỉ ra vi trí của tân từ trong luật. VAR_ID1 chỉ ra biến đầu tiên, VAR_ID2 chỉ ra biến thứ 2 trong tân từ, và COMP_OP chỉ ra kiểu của tân từ so sánh. 2.2. Đề xuất giải thuật suy luận và cách triển khai module mờ 2.2.1. Cấu trúc dữ liệu Ý tưởng của giải thuật suy luận mà chúng tôi giới thiệu sau đây tương tự như kĩ thuật suy luận prolog. Nó dựa trên ý tưởng của các tác giả Igrancio Blanco, Juan C. Cubero, Olga Pons, và Amparo Vila [8]. Kết quả của việc khai triển một luật là một tập các bộ giá trị biến thỏa mãn luật. Chẳng hạn trong dạng 2 của luật, tập giá trị các biến sẽ có dạng: X Y Z Cấu trúc cơ sở này của tập giá trị có thể được sử dụng để biểu diễn cho tất cả các kết quả có thể có của việc khai triển luật. Để lưu trữ được thông tin này, chúng ta sử dụng một bảng được gọi là PRED_RULER với biểu diễn tân từ thứ pred của luật thứ rule. Cấu trúc của các bảng này sẽ có dạng dưới đây: IDSET VAR1 ... VARn NEG INST APPL TABLEP IDSETP ACT CTRL Thuộc tính VARi biểu diễn giá trị của biến luật thứ i. Như trong dạng (2) của luật, một tân từ có thể khai triển nhiều hơn một lần, chúng ta có thể sử dụng các bảng PREDi_RULERj khác nhau nhưng nó sẽ đòi hỏi không gian nhớ quá lớn. Một lựa chọn khác là sử dụng cùng một bảng có cấu trúc tương tự bảng PREDi_RULERj nhưng phân biệt giữa những tập giá trị của các biến được dùng trong khai triển. Nếu như vậy, một thứ tự giữa các tâp giá trị phải được thiết lập, và thứ tự này được lưu trữ trong thuộc tính IDSET. Dựa vào đó ta có thể phân biệt được các tập giá trị với nhau. Hơn nữa, nếu có thể tạo ra một bộ đặc biệt dùng để phân biệt giữa tập giá trị cuối cùng của một khai triển với tập giá trị đầu tiên của khai triển tiếp theo (ta tạm gọi là bộ phân cách), thì tập giá trị của các khai triển được phân biệt. Kiểu của các bộ được lưu trong thuộc tính CTRL và nhận giá trị 1 nếu là bộ giá trị thông thường và 2 nếu là bộ phân cách. Các tập giá trị của cùng 22
  11. Một hướng triển khai của cơ chế cho phép suy luận trên cơ sở dữ liệu mờ một khai triển dùng chung dữ liệu cũng như các biến bởi vì các biến sẽ được gán các giá trị từ các khai triển sâu hơn. Thông tin này là chung cho tất cả các tập giá trị trong cùng một khai triển cho nên phần tử phân cách có thể được lưu trữ để sử dụng. Giải thuật suy luận chỉ có thể thực hiện tuần tự với mỗi tập giá trị một lần, vì vậy chúng ta cần đánh dấu vào tập giá trị đang được xử lí trong thuộc tính ACT. Điều này được hiểu là giải thuật suy luận đang khai triển luật trên một cây suy luận với thứ tự thực hiện là không quan trọng. Thuộc tính CTRL nhận giá trị 1 nếu là tập giá trị đang được xử lí và nhận giá trị là 0 nếu là tập giá trị thông thường. Giải thuật suy luận thực thi với một bộ một lần và sau đó trao quyền cho một bộ khác. Nhưng chúng ta cần phải lưu ý rằng các luật logic có thể là đệ quy, có nghĩa là, các tân từ đã được định nghĩa là tân từ nội hàm có thể bao hàm chính tân từ đó, do đó quyền điều khiển có thể được luân chuyển từ một bộ đến một bộ khác trong chính một khai triển của cùng một tân từ. Chính vì vậy, sẽ là cần thiết phải lưu trữ có bao nhiêu tân từ đã được khai triển trong mỗi bộ. Số tân từ này được lưu trữ trong thuộc tính APPL. Thêm nữa là các biến đã được gán các giá trị sẽ được lưu trong thuộc tính INST. Cả hai giá trị đều là quan trọng bởi sự khác biệt giữa hai khai triển của cùng một tân từ là số lượng của các biến được khai triển. Khi một tập các biến được gán giá trị thì điều cần thiết là phải định danh tập giá trị được gọi đến để điền vào các biến. Thông tin này được lưu trữ trong thuộc tính TABLEP và IDSETP. Thuộc tính NEG được sử dụng để chỉ ra rằng tập giá trị là thỏa mãn luật hoặc là có thể thực hiện nó vào giai đoạn cuối cùng của khai triển. Nó hữu ích khi mà ta phải khai triển một tân từ có dấu phủ định. Toán tử so sánh có thể thực hiện theo cách đặc biệt. Một toán tử so sánh có thể xuất hiện ở bất kì đâu trong luật, nhưng chỉ có thể thực hiện được khi có đủ các giá trị của các biến. Trường hợp thiếu giá trị của các biến thì phép so sánh được trì hoãn lại đến khi có đủ điều kiện thực hiện. 2.2.2. Giới thiệu giải thuật suy luận Khi khai triển một tân từ có thể nhận được kết quả nhiều hơn một khả năng. Vì vậy chúng ta phải tạo ra một bản sao cấu trúc của tập giá trị đang được sử dụng để khai triển tân từ và các giá trị được sử dụng để điền vào tập giá trị. Tất nhiên, tập giá trị gốc là không thay đổi bởi vì đây chỉ là các bản sao của nó. Giá trị 0 ở cột CTRL được sử đụng để đánh dấu một tập giá trị hằng sai. Giải thuật chỉ có thể thu được dữ liệu khi mà một tân từ ngoại diên được khai triển và lấy kết quả trên một bảng PREDj với dữ liệu từ một bảng ngoại diên. Đây là điều bắt buộc của giải thuật suy luận. Do đó có hai kiểu bảng, một cho các tân từ nội hàm 23
  12. Nguyến Tiến Thành, Hồ Cẩm Hà (PREDi_RULERj) và một cho các tân từ ngoại diên(PREDi). Giải thuật sẽ bắt đầu với một bảng PREDi_RULERj đối với mỗi luật chứa tân từ được khai triển và một tập giá trị trống chứa trong chúng. Với cách làm chỉ có một tập giá trị được thực thi một lần trong một thời điểm, thì chỉ có một bảng, như bảng PREDi_RULERj sẽ được gọi mỗi lần. Vì thế nên khi cần khai triển tân từ khác, giải thuật suy luận chỉ việc thay đổi bảng được kích hoạt. Một bảng lưu trữ các tập giá trị trong các bảng cho việc khai triển của một tân từ được khởi tạo. Bảng tương ứng với tân từ ở đầu luật sẽ được kích hoạt đầu tiên. Sau đó là tiến trình thực hiện tương tự với tất các bảng khác. Giải thuật suy luận chỉ định tập hợp giá trị được xử lí từ bảng đang được kích hoạt. Nếu nó đã được tính toán rồi thì giải thuật suy luận sẽ cố gắng khai triển nốt các tân từ so sánh chưa được khai triển do chưa có giá trị để so sánh. Nếu như tập này có các phép so sánh, bước đầu tiên là ước lượng xem chúng có thỏa tập giá trị hiện thời hay không: nếu có, tập giá trị sẽ được đánh dấu là thoả tân từ so sánh; nếu không phép so sánh lại bị trì hoãn lại. Ngược lại, tập giá trị mà thỏa mãn phép so sánh thì sẽ được xóa đi và giải thuật suy luận tiếp tục với các tập giá trị khác theo các bước sau: 1. Nếu tập giá trị là hằng sai (CTRL = 0), thì nó được thay đổi (đây là bản sao phần khai triển thực tế của nó). Tập giá trị và các phép so sánh được xóa đi. 2. Nếu là một tập giá trị hằng đúng (CTRL = 1), thì có nghĩa là nó vẫn là tân từ chưa khai triển được (Tổng số tân từ đó của luật trừ đi số tân từ đã được khai triển khác 0). Tân từ tiếp theo được khai triển. a. Nếu bảng nội hàm và chưa được tính toán từ trước, giải thuật suy luận xác định tân từ tếp theo được khai triển và dấu phủ định kèm theo của nó. Tùy thuộc vào kiểu của tân từ một trong các bước sau sẽ được thực thi: i. Tân từ ngoại diên: Giải thuật suy luận sẽ chèn một tập giá trị trống và thay đổi giá trị của các biến tương ứng với các thông số của các tân từ, kèm vào đó là các giá trị của các biến phù hợp với dữ liệu đã có và yêu cầu của bài toán. Tập giá trị này được chèn tương ứng vào các bảng PREDi_RULERj. ii. Tân từ nội hàm. Phương thức tương tự đối với tân từ ngoại diên được áp dụng, nhưng thay vào đó một tập giá trị trống được chèn vào tất cả các tân từ có liên quan đến tân từ đang được khai triển. iii. Tân từ so sánh: Phép so sánh được thực hiện. Nếu chưa đủ giá trị, nó sẽ được hoãn lại. Ngược lại thì nó được thực hiện và tập giá trị sẽ được đánh dấu và xóa đi nếu như nó không thỏa mãn phép so sánh. Thuộc tính APPL tăng lên bởi vì một thuộc tính mới đã được khai triển. Nếu tân từ có dấu phủ định. Tập giá trị sẽ được đánh dấu là phủ định. Cuối cùng 24
  13. Một hướng triển khai của cơ chế cho phép suy luận trên cơ sở dữ liệu mờ bảng mới được kích hoạt. b. Nếu bảng được tính toán từ trước, giải thuật suy luận sẽ gia tăng trong tập giá trị đang được xử lí thuộc tính APPL (APPL =1). Sau đó, dữ liệu thu được sẽ được chèn vào mỗi bộ của kết quả truy vấn. Tập giá trị được xử lí được đánh dấu là đã xử lí xong và được thay đổi (CTRL = 0). Hai trường hợp không có thuộc tính nào được khai triển là: i. Nếu không có biến nào nhận được giá trị phù hợp thì cũng có nghĩa là không có một tập giá trị nào thỏa mãn được luật. Khi đó tất cả các tân từ đã khai triển xong, nên tập có thể bị xóa. ii. Nếu như không có các biến rỗi, thì phần tử phân cách được sử dụng để gán tập giá trị đang xử lí cho một bản sao của tập giá trị dùng để khai triển của tân từ. Và tập giá trị được gọi được đánh dấu được thay đổi (CTRL = 0). Nó sẽ bị xóa. 3. Nếu tập giá trị là phần tử phân cách (CTRL = 2) thì có nghĩa là tất cả các tập khai triển này đã được thực thi xong. Ta có thể đánh dấu cho thuộc tính này là đã được khai triển. Cuối cùng, nếu tập giá trị được thay đổi (vì có các bản sao về mặt triển khai của nó có CTRL = 0), tập giá trị và các phép so sánh của nó bị xóa. Trong trường hợp tập giá trị không được thay đổi và bảng đang được kích hoạt là ngoại diên (PREDi), thì dữ liệu thu được từ các bảng ngoại diên được cho vào ngăn xếp. Đây chính là các thông tin âm, nó bằng tập tất cả các dữ liệu hiện có trừ đi các dữ liệu thoả mãn tân từ. Tập giá trị được sử dụng để khai triển tân từ được đánh dấu để thay đổi. Một tân từ có hiệu lực lên tất cả các bản sao của tập dữ liệu chứa trong bảng ngoại diên do đó thuộc tính APPL tăng lên 1 đơn vị. 2.2.3. Triển khai module mờ Suy luận là một quá trình được tiến hành trên cây suy luận. Các nút trung gian của cây thể hiện các tập giá trị chưa khai triển được và các nút lá thể hiện các tập giá trị đã được khai triển rồi. Khi đi qua các nút trung gian này đến nút trung gian khác là con của nó, chúng ta áp dụng luật với các biến. Nếu như biến là mờ thì ta cần phải tính toán độ thuộc kết hợp. Vì vậy, phép mờ là không áp dụng được trong trường hợp này. Trường hợp tương tự xảy ra khi đi từ nút lá đến nút trung gian. Nhưng khi ta đang xử lí nút lá, tức là một tân từ ngoại diên hay nội hàm đã được tính toán, chúng ta phải áp dụng phép mờ và kết quả là các giá trị và một độ thuộc. Theo đó, độ thuộc tổng hợp được định nghĩa trên các độ thuộc thành phần. Tóm lại, ta phải tạo ra một cấu trúc có dạng ngăn xếp để lưu trữ các độ thuộc của các biến có thể nhận giá trị mờ và độ thuộc của luật. Giải thuật sẽ tính toán và quản lí các độ thuộc này. 25
  14. Nguyến Tiến Thành, Hồ Cẩm Hà 3. Kết luận Trên đây, chúng tôi đã trình bày về sự mở rộng của mô hình quan hệ để có thể biểu diễn và quản lí được thông tin mờ và/ hoặc sự suy luận. Đây là sự mở rộng của hai công việc riêng biệt là quản lí thông tin mờ và suy luận thông tin. Cơ chế suy luận như đã đề cập có thể triển khai được trong một hệ cơ sở dữ liệu quan hệ. Hai cơ chế là “mờ” và “suy luận” có thể được kết hợp lại với nhau để trở thành module suy luận mờ. Việc triển khai module suy luận không những có liên quan đến việc đọc dữ liệu về luật trên từ điển, từ các bảng dữ liệu mà còn liên quan đến việc khởi tạo các bảng để phục vụ cho giải thuật suy luận. Giải thuật có hai điểm hạn chế lớn đó là: sự suy luận chỉ có thể thực hiện với mỗi bộ giá trị một lần trong một thời điểm và có thể rơi vào tình trạng lặp vô hạn vì có tân từ đệ quy đồng thời có hạn chế lớn khi làm việc với các thông tin âm. Đây là một hạn chế lớn cho cả người lập trình lẫn người quản trị cơ sở dữ liệu. Để thực thi một câu truy vấn mờ thì chỉ cần chuyển đổi nhưng để thực thi một câu suy luận mờ thì lại cần đến một thủ tục để thực thi các luật có chứa các tân từ có trong câu truy vấn. Thủ tục này không có sẵn trong ngôn ngữ quan hệ, chính vì vậy ta phải tạo ra nó bằng ngôn ngữ lập trình. Đây là bài toán trên Oracle c RDBMS, có hai thứ ngôn ngữ để lựa chọn cho việc xây dựng module suy luận là Pro*C c và PL/SQL c . Cả hai ngôn ngữ đều có ưu và nhược điểm riêng. Cuối cùng, giải pháp máy suy luận nội hàm được lựa chọn vì nó tỏ ra có ưu điểm trong vấn đề truyền dữ liệu giữa DBMS và máy suy luận. Nếu lựa chọn trên được chấp nhận, ngôn ngữ SQL sẽ được cải thiện rất nhiều bởi lẽ dữ liệu có thể hàm chứa được các loại dữ liệu mờ hoặc nội hàm. Chú ý là trong thời điểm này chỉ mới thực hiện được những có những câu suy luận cơ bản. Có hai vấn đề có thể tiếp tục giải quyết: thứ nhất là xử lí sự không chắc chắn trong các luật suy diễn, vì máy suy luận phải thêm vào các thành phần trong khi suy luận, thứ hai là việc triển khai các câu lệnh định nghĩa dữ liệu (DDL) và thao tác dữ liệu (DML) mờ. TÀI LIỆU THAM KHẢO [1] E.F. Codd, 1970. A relational model of data for lage shared data banks. Communication of the ACM. [2] P.Bosc, M. Galibourg, and G. Hamon,1988. Fuzzy querying with sql: Extensions and implementation aspects. Fuzzy Sets and Systems, Vol. 28, pp. 333-349. [3] B. P. Buckles and F. E. Petry, 1982. A fuzzy representation of data for relational databases. Fuzzy Sets and System, Vol. 7, pp. 213-226. [4] H. Prade and C. Testemale, 1984. Gneralizing database relational algebra for the treatment of icomplete/uncertain information and vague queries. Information Sciences, Vol. 34, pp. 113-143. 26
  15. Một hướng triển khai của cơ chế cho phép suy luận trên cơ sở dữ liệu mờ [5] M. A. Vila, J. C. Cubero, J. M. Medina, and O. Pons, 1995. Logic and fuzzy relational databases: A new languge and a new definition. In P.Bosc and J.Kacprzyck editors, In Fuzzy Sets and Possibility Theory in Databases Management Systems. Physica- Velag. [6] M. Zemankova and A. Kandel, 1984. Fuzzy Relational Database – A Key to Expert Systems. Velag TUV Rheinland. [7] J.M. Medina, O. Pons, and M.A. Vila, 1994. Gefred, a generalized model of fuzzy relational databases. Information Sciences. [8] Igrancio Blanco, Juan C. Cubero, Olga Pons, and Amparo Vila, 1998. An Implementation for Fuzzy Deductive Relational Databases. Physica- Velag. [9] J.M. Medina, O. Pons, JC. Cubero, and M.A. Vila, 1997. Freddi: A fuzzy relational deductive database interface. International Journal of Intelligent Systems, Vol. 12, pp. 597-613. [10] L.A. Zadeh, 1975. The concept of a linguistic variable and its application to approxiamte reasoning. Information Sci., 8, 9:(8) 199-248, 301-307, (9) 43-80. [11] J. Grant, 1980. Incomplete information in a realtional database. Fundamenta Informaticae, Vol. 3, pp. 363-387. [12] E.F Codd, 1979. Extending the database renational model to capture more maening. ACM Transactions on Database System, Vol. 4, pp. 262-296. [13] E. F. Codd, 1986. Missing information (applicable and inapplicable) in relational databases. ACM SIGMOD Record, 15(4). [14] E. F. Codd, 1986. The twelve rulers for relational dbms. Technical Report EFC-6, San Jose, The Realtional Institute. [15] E.F. Codd, 1987. More commentary on missing information in relational databases. ACM SIGMOD recored, 16(1). [16] O. Pons, J. M. Medina, J. C. Cubero, and A. Vila, 1996. Foundations of Intelligent Systems. Chapter An Architecture for a Dedutive Fuzzy Relational Database, Springer. ABSTRACT A development of mechanism allow infering in fuzzy databases This paper presents the development of a mechanism that represents induced rules and fuzzy information stored in a relational database to build a moduce that can use to infer novel knowledge from data in tables. These induced rules can be applied in accurate data, fuzzy data or both. 27
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2