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ờ

JOURNAL OF SCIENCE OF HNUE FIT., 2013, Vol. 58, pp. 13-27 This paper is available online at 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 1Khoa Công nghệ Thông tin, Trường Đại học Sư phạm Hà Nội 1Email: 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 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 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 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 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 Kiểu giá trị Thuộc tính dữ liệu cho kiểu giá trị mờ loại 2FT 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 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 Kiểu giá trị Thuộc tính dữ liệu cho kiểu giá trị mờ loại 2FT 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 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ẹ Bố / Mẹ Con trai / Congái John Mike Mary Mike Karl Louise Maggie Louise Mike Jake Louise Jake 19 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 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 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 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