- bài luận: 40% làm 1 người
- Thi: được mang tài liệu, 60%
CSDL suy dien (ôn phần không đệ qui)
Định giá chương trình Datalog không đệ quy
Trong phần này ta sẽ nghiên cứu chương trình Datalog không đệ quy.
Để ý rằng, nếu các quy tắc là không đệ quy thì ta có thể sắp thứ tự các nút của đồ thị phụ thuộc sao cho nếu có một cung từ pi đến pj thì i
Bước 2 : Tính quan hệ đối với chính pi bằng cách thực hiện phép chiếu lên các thuộc tính của các quan hệ trong mỗi quy tắc có đầu là pi lên trên các thành phần tương ứng đối với các biến của đầu quy tắc, sau đó lấy hợp trên tất cả các quy tắc có pi là đầu.
Thuật toán 2.1 (Thuật toán tính quan hệ cho thân quy tắc)
Vào: Cho quy tắc Datalog r và giả sử thân của quy tắc r gồm các đích con S1,...,Sn chứa các biến X1,...,Xm và
Giả sử đối với mỗi đích con Si = có một quan hệ Ri đã được tính, với là các đối số, hay là biến hay là hằng.
Ra: Một biểu thức đại số quan hệ được ký hiệu :
EVAL-RULE(r,R1,...,Rn)
được tính từ các quan hệ R1,...,Rn sẽ tạo ra một quan hệ R(X1,...,Xm) của thân quy tắc và chỉ chứa tất cả các bộ (a1,...,am) sao cho khi thay aj cho Xj (1 j m) thì tất cả các đích con S1,...,Sn đều là true.
Phương pháp : Một biểu thức đại số quan hệ được xây dựng theo các bước sau đây :
Bước 1. Đối với mỗi Si đặt Qi = .
Trong đó Vi là tập các thành phần mà mỗi biến xuất hiện trong các đối số của Si (chính xác là thành phần mà tại đó biến X xuất hiện), Fi là hội của các điều kiện sau đây :
a) Nếu tại vị trí thứ k của Si có một hằng ai thì Fi có dạng : $k = a
b) Nếu tại vị trí thứ k và h của Si đều chứa cùng một biến thì Fi có dạng : $k = $h
Bước 2. Đối với mỗi biến X không tìm thấy trong các đích con thông thường, X là biến), ta tính một biểu thức DX tạo ra quan hệ một ngôi chứa tất cả giá trị mà X có thể có và làm cho các đích con là true. Vì quy tắc là an toàn nên có một vài biến Y mà X=Y, với Y là biến bị chặn.
a) Nếu Y = a (hằng) thì DX = {a}
b) Nếu Y là biến xuất hiện như đối số thứ j của đích con thông thường Si thì DX =
Bước 3. Đặt E là nối tự nhiên của tất cả Qi được xác định ở bước 1 và DX được xác định ở bước 2. Trong phép nối này ta xem Qi như là một quan hệ mà các thuộc tính là các biến xuất hiện trong Si và xem DX là quan hệ chứa thuộc tính X.
Bước 4. Đặt EVAL-RULE(r, R1,...,Rn) = trong đó F là hội của XY đối với mỗi đích con xây dựng trong XY xuất hiện trong p1,...,pn và E là biểu thức được xác định trong bước 3. Nếu không có đích con xây dựng trong thì biểu thức đòi hỏi chính là E.
Ví dụ 2.7 Cho quy tắc r :
p(X,Y) q(a,X) r(X,Z,X) s(Y,Z)
Giả sử Q,R và S là các quan hệ tương ứng với các đích con q, r, s. Bởi vì đích con đầu tiên đòi hỏi các bộ của Q có thành phần đầu tiên là a nên ta cần xây dựng một quan hệ với thuộc tính là X và chỉ chứa các thành phần thứ hai của những bộ này, như vậy ta định nghĩa quan hệ :
T(X) =
T(X) = được xây dựng từ bước 1 của thuật toán từ đích con đầu tiên q(a,X) của quy tắc đã cho, T(X) chính là Q1 trong thuật toán.
Quan hệ R có thành phần thứ nhất và thành phần thứ ba là các biến giống nhau nên ta định nghĩa quan hệ đối với đích con này :
U(X,Z) =
U(X,Z) = là Q2 được xây dựng từ đích con thứ hai r(X,Z,X).
Q3 được xây dựng từ đích con thứ ba S(Y,Z) chính là S(Y,Z).
Do quy tắc này không có các đích con xây dựng trong nên bước 2 và bước 4 được bỏ qua. Vậy :
EVAL-RULE(r,Q,R,S) = T(X) U(X,Z) S(Y,Z) là biểu thức cuối cùng của thân quy tắc này.
Quan hệ này bao gồm các bộ (x,y,z) thỏa mãn :
1. (a,x) thuộc Q
2. (x,z,y) thuộc R và y=x
3. (y,z) thuộc S
Ví dụ 2.8 Xét quy tắc:
cousin(X,Y) parent(X,Xp) parent(Y,Yp) sibling(Xp,Yp)
Giả sử quan hệ P,S được tính đối với các vị từ parent và sibling tương ứng. Quan hệ đối với thân quy tắc này là:
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
- Thi: được mang tài liệu, 60%
CSDL suy dien (ôn phần không đệ qui)
Định giá chương trình Datalog không đệ quy
Trong phần này ta sẽ nghiên cứu chương trình Datalog không đệ quy.
Để ý rằng, nếu các quy tắc là không đệ quy thì ta có thể sắp thứ tự các nút của đồ thị phụ thuộc sao cho nếu có một cung từ pi đến pj thì i
Bước 2 : Tính quan hệ đối với chính pi bằng cách thực hiện phép chiếu lên các thuộc tính của các quan hệ trong mỗi quy tắc có đầu là pi lên trên các thành phần tương ứng đối với các biến của đầu quy tắc, sau đó lấy hợp trên tất cả các quy tắc có pi là đầu.
Thuật toán 2.1 (Thuật toán tính quan hệ cho thân quy tắc)
Vào: Cho quy tắc Datalog r và giả sử thân của quy tắc r gồm các đích con S1,...,Sn chứa các biến X1,...,Xm và
Giả sử đối với mỗi đích con Si = có một quan hệ Ri đã được tính, với là các đối số, hay là biến hay là hằng.
Ra: Một biểu thức đại số quan hệ được ký hiệu :
EVAL-RULE(r,R1,...,Rn)
được tính từ các quan hệ R1,...,Rn sẽ tạo ra một quan hệ R(X1,...,Xm) của thân quy tắc và chỉ chứa tất cả các bộ (a1,...,am) sao cho khi thay aj cho Xj (1 j m) thì tất cả các đích con S1,...,Sn đều là true.
Phương pháp : Một biểu thức đại số quan hệ được xây dựng theo các bước sau đây :
Bước 1. Đối với mỗi Si đặt Qi = .
Trong đó Vi là tập các thành phần mà mỗi biến xuất hiện trong các đối số của Si (chính xác là thành phần mà tại đó biến X xuất hiện), Fi là hội của các điều kiện sau đây :
a) Nếu tại vị trí thứ k của Si có một hằng ai thì Fi có dạng : $k = a
b) Nếu tại vị trí thứ k và h của Si đều chứa cùng một biến thì Fi có dạng : $k = $h
Bước 2. Đối với mỗi biến X không tìm thấy trong các đích con thông thường, X là biến), ta tính một biểu thức DX tạo ra quan hệ một ngôi chứa tất cả giá trị mà X có thể có và làm cho các đích con là true. Vì quy tắc là an toàn nên có một vài biến Y mà X=Y, với Y là biến bị chặn.
a) Nếu Y = a (hằng) thì DX = {a}
b) Nếu Y là biến xuất hiện như đối số thứ j của đích con thông thường Si thì DX =
Bước 3. Đặt E là nối tự nhiên của tất cả Qi được xác định ở bước 1 và DX được xác định ở bước 2. Trong phép nối này ta xem Qi như là một quan hệ mà các thuộc tính là các biến xuất hiện trong Si và xem DX là quan hệ chứa thuộc tính X.
Bước 4. Đặt EVAL-RULE(r, R1,...,Rn) = trong đó F là hội của XY đối với mỗi đích con xây dựng trong XY xuất hiện trong p1,...,pn và E là biểu thức được xác định trong bước 3. Nếu không có đích con xây dựng trong thì biểu thức đòi hỏi chính là E.
Ví dụ 2.7 Cho quy tắc r :
p(X,Y) q(a,X) r(X,Z,X) s(Y,Z)
Giả sử Q,R và S là các quan hệ tương ứng với các đích con q, r, s. Bởi vì đích con đầu tiên đòi hỏi các bộ của Q có thành phần đầu tiên là a nên ta cần xây dựng một quan hệ với thuộc tính là X và chỉ chứa các thành phần thứ hai của những bộ này, như vậy ta định nghĩa quan hệ :
T(X) =
T(X) = được xây dựng từ bước 1 của thuật toán từ đích con đầu tiên q(a,X) của quy tắc đã cho, T(X) chính là Q1 trong thuật toán.
Quan hệ R có thành phần thứ nhất và thành phần thứ ba là các biến giống nhau nên ta định nghĩa quan hệ đối với đích con này :
U(X,Z) =
U(X,Z) = là Q2 được xây dựng từ đích con thứ hai r(X,Z,X).
Q3 được xây dựng từ đích con thứ ba S(Y,Z) chính là S(Y,Z).
Do quy tắc này không có các đích con xây dựng trong nên bước 2 và bước 4 được bỏ qua. Vậy :
EVAL-RULE(r,Q,R,S) = T(X) U(X,Z) S(Y,Z) là biểu thức cuối cùng của thân quy tắc này.
Quan hệ này bao gồm các bộ (x,y,z) thỏa mãn :
1. (a,x) thuộc Q
2. (x,z,y) thuộc R và y=x
3. (y,z) thuộc S
Ví dụ 2.8 Xét quy tắc:
cousin(X,Y) parent(X,Xp) parent(Y,Yp) sibling(Xp,Yp)
Giả sử quan hệ P,S được tính đối với các vị từ parent và sibling tương ứng. Quan hệ đối với thân quy tắc này là:
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links