Tiểu luận Chương trình Datalog
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
A. GIỚI THIỆU
Chương trình Datalog là một phần quan trọng của cơ sở dữ liệu suy diễn.
Nhiều công trình nghiên cứu nhằm tìm kiếm những phương pháp ước lượng
hiệu quả đối với những truy vấn.
Tiểu luận nhằm giải quyết vấn đề là bằng cách nào để loại bỏ phần thừa
của một chương trình Datalog. Phần thừa của một chương trình là một quy tắc
thừa hoặc một nguyên tố thừa trong thân của một quy tắc. Loại bỏ một phần
thừa nhằm giảm thời gian cần thiết để lượng giá một truy vấn bởi vì nó giảm số
lượng những kết nối trong suốt quá trình lượng giá.
Một chương trình datalog thường nhận dữ liệu vào là những quan hệ đối
với vị từ EDB và trả lời là những quan hệ đối với vị từ IDB. Quy trình tối ưu
hóa yêu cầu tìm kiếm một chương trình có giá nhỏ nhất tương đương với
chương trình gốc, sao cho đối với mọi khả năng của đầu vào, chương trình gốc
và chương trình được tối ưu tính toán ra cùng một kết quả. Tiểu luận trình bày
một số khái niệm như quan hệ bao hàm, quan hệ tương đương, bao hàm đồng
dạng, tương đương đồng dạng. Trong đó, tính tương đương đồng dạng hàm
chứa tính tương đương. Để cực tiểu một chương trình trong tính tương đương
đồng dạng, ta đưa ra một thuật toán để xóa tất cả những quy tắc thừa và nguyên
tố thừa trong những quy tắc trong khi vẫn duy trì tương đương đồng dạng. Thời
gian thực hiện của thuật toán, trong trường hợp xấu nhất là theo luật số mũ của
kích cở của chương trình. Tuy nhiên nếu số lượng đối số của các vị từ hữu hạn
thì thời gian thực hiện là đa thức. Trên thực tế, thường số lượng đối số của các
vị từ không lớn nên đây là một thuật toán hiệu quả.
Tiểu luận cũng đưa ra một kỹ thuật để cực tiểu hóa chương trình Datalog
trong tính tương đương. Đây là một bài toán bất khả quyết, kỹ thuật này không
tìm thấy tất cả các phần thừa của một chương trình trong tính tương đương.
Thực ra, chương trình Datalog đã được nghiên cứu sâu và được ứng
dụng mạnh mẽ. Tiểu luận không nhằm mục đích đưa ra những vấn đề mới mà
chỉ tóm tắt và trình bày lại những tri thức mà bản thân thu nhận được thông qua
một thời gian học tập ngắn và qua tham khảo một số tài liệu.
Tiểu luận được trình bày trong ba phần. Phần 1: Đưa ra một số kiến
thức cơ sở. Phần 2: Tối ưu hóa những chương trình đề quy trong tính tương
đương đồng dạng. Phần này trình bày một thuật toán để tìm và xóa những
nguyên tố và quy tắc thừa trong khi vẫn duy trì tính tương đương đồng dạng.
Phần 3: Tối ưu hóa những chương trình đệ quy trong tính tương đương. Phần
này trình bày một thuật toán để tìm và xóa những nguyên tố và quy tắc thừa
1
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
trong khi vẫn duy trì tính tương đương, nhưng có thể không tương đương đồng
dạng.
B. NỘI DUNG
I. KIẾN THỨC CƠ SỞ
1.1-Những khái niệm về chương trình Datalog.
Định nghĩa 1.1.1 (Vị từ EDB và vị từ IDB)
-Vị từ EDB (Extensional database relation) là vị từ mà quan hệ của nó
được chứa trong cơ sở dữ liệu.
-Vị từ IDB (Intensional database relation) là vị từ được định nghĩa bởi
các quy tắc logic.
Vị từ IDB trong một chương trình P có thể xuất hiện ở đầu hoặc thân của
quy tắc. Vị từ EDB là các vị từ không xuất hiện trong đầu quy tắc mà chỉ xuất
hiện trong thân quy tắc.
Định nghĩa 1.1.2 (Nguyên tố-atom)
Nếu A1, A2,...,An là các biến hoặc hằng và p là ký hiệu vị từ thì
p(A1,A2,...,An) được gọi là một nguyên tố.
Quy ước: Các vị từ được viết bằng chữ thường, các biến được viết bằng
chữ in hoa.
Định nghĩa 1.1.3 (Vị từ xây dựng trong)
Một vị từ xây dựng trong là một vị từ so sánh số học (=, , , , >, <) với
ngữ nghĩa đã xác định.
Nếu là vị từ xây dựng trong thì ta viết XY thay cho (X,Y). Vị từ xây
dựng trong chỉ xuất hiện trong thân quy tắc.
Định nghĩa 1.1.4 (Mệnh đề Horn)
Mệnh đề Horn là một công thức bậc nhất chứa nhiều nhất một literal
dương. Có ba dạng mệnh đề Horn:
-Mệnh đề đơn vị (còn gọi là các sự kiện-fact) p
-Đích (goal) là một mệnh đề mà chỉ chứa một hoặc nhiều literal âm và
không có literal dương.
q1
q2
...
qn
qn
-Quy tắc là một công thức bậc nhất có đúng một literal dương và một
hoặc nhiều literal âm.
Ngữ nghĩa của quy tắc này là: nếu q1 q2 ... qn đều là true thì p true. p là
đầu của quy tắc, q1 q2 ... qn là thân của quy tắc
p
q1
q2
...
Định nghĩa 1.1.5 (Chương trình Datalog)
Một chương trình Datalog là một tập hữu hạn các mệnh đề Horn thỏa
mãn ba điều kiện sau:
2
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
-Không chứa đích
-Nếu chứa sự kiện với ký hiệu vị từ p thì sẽ không chứa quy tắc có đầu
quy tắc là p.
-Không chứa ký hiệu hàm.
Như vậy, ta có thể xem một chương trình Datalog là chương trình logic
không chứa ký hiệu hàm.
Ví dụ 1.1.6: Đây là một chương trình có hai quy tắc:
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z)
Trong tiểu luận ta cũng giả sử mọi biến trong đầu của quy tắc cũng phải
xuất hiện trong thân. Đối với những quy tắc có thân rỗng thì đầu quy tắc chỉ có
hằng và không có biến. Đồng thời các quy tắc luôn là những công thức an toàn.
Một quan hệ Q đối với một vị từ q là một tập các nguyên tố nền của q.
Trừ các trường hợp đã định khác, ta giả sử các quan hệ là hữu hạn. Một tập hợp
các quan hệ được xem như là một tập gồm có tất cả những nguyên tố nền của
những quan hệ này. Nếu Q1,Q2,...,Qn là các quan hệ tương ứng đối với các vị từ
q1,q2,..,qn thì <Q1,Q2,...,Qn> biểu diễn phép hợp của chúng, đó là tập hợp chứa
những nguyên tố nền của tất cả Qi. Tập <Q1,Q2,...,Qn> còn được gọi là một thể
hiện.
Định nghĩa 1.1.7 (Đồ thị phụ thuộc)
Một đồ thị liên hợp với một chương trình P được gọi là đồ thị phụ thuộc.
Trong đó một nút ứng với mỗi vị từ của chương trình, và một cung từ vị từ q
đến vị từ r khi vị từ q là trong thân của một số quy tắc và vị từ r là trong đầu
của cùng quy tắc đó.
Định nghĩa 1.1.8 (Chương trình Datalog đệ quy)
Chương trình Datalog P là đệ quy nếu đồ thị phụ thuộc của nó có một
chu trình. Một vị từ q là đệ quy trong chương trình P nếu có một đường đi từ q
đến chính nó. Vị từ đệ quy là vị từ IDB, nhưng một vị từ IDB là không nhất
thiết đệ quy.
Một quy tắc là đệ quy nếu đồ thị phụ thuộc có một chu trình bao gồm vị
từ ở đầu của quy tắc và một vị từ ở thân của quy tắc. Cụ thể, một quy tắc là đệ
quy nếu vị từ ở trong đầu của quy tắc cũng xuất hiện trong thân.
1.2-Sự tính toán của chương trình.
Dữ liệu vào của một chương trình P là một quan hệ đối với mỗi vị từ
EDB. Dữ liệu ra được tính toán bởi P là một quan hệ đối với mỗi vị từ IDB. Để
đơn giản, ta định nghĩa dữ liệu ra là DB.
3
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
Bằng cách nào để tính dữ liệu ra. Những nguyên tố nền của DB được gọi
là những sự kiện. Ban đầu, những sự kiện đó là EDB. Một quy tắc của một
chương trình nhằm để suy diễn một sự kiện mới từ một số sự kiện đã biết.
Những sự kiện được suy diễn mới này trở thành những nguyên tố nền của IDB.
Quy tắc có thể được sử dụng lại để suy diễn những sự kiện mới hơn. Một quy
tắc r được dùng để suy diễn một sự kiện mới bằng cách thế các biến của nó
bằng các hằng (thế một hằng cho tất cả sự xuất hiện của mỗi biến). Nếu với
phép thế, mỗi nguyên tố trong thân của quy tắc r trở thành một nguyên tố nền
của DB, thì hiện hành của đầu của quy tắc được thêm vào cho IDB.
Ví dụ 1.2.1: Xét chương trình của ví dụ 1.1.6
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z)
và cho EDB là tập các nguyên tố nền dưới đây {a(1,2), a(1,4), a(4,,1)}.
Ban đầu, IDB là tập rỗng. Nếu trong quy tắc thứ nhất, ta thay thế 1 vào X và 2
vào Z thì thân của quy tắc trở thành a(1,2) và nó trở thành một nguyên tố nền
của EDB. Vì vậy g(1,2) được thêm vào IDB. Hai hiện hành tương tự của quy
tắc thứ nhất là g(1,4) và g(4,1) được thêm vào IDB.
Đối với quy tắc thứ hai, ta thế 1 vào X, 4 vào Y và 1 vào Z sinh ra những
nguyên tố nền g(1,4), g(4,1) trong thân của quy tắc. Vì cả hai là đã có trong
DB, hiện hành đầu quy tắc là g(1,1) được thêm vào IDB. Tương tự, thế 4 vào X
và Z và 1 vào 1 vào Y ta được g(4,4). Cuối cùng, thế 4 vào X, 1 vào Y và 2 vào
Z, ta thu được g(4,2). Không có nguyên tố nền nào được sinh ra bởi phép thế
này nữa. Như vậy DB là: {a(1,2), a(1,4), a(4,1), g(1,2), g(1,4), g(4,1), g(1,1),
g(4,4), g(4,2)} là dữ liệu ra tính được bởi chương trình đối với EDB ở trên.
Vì ta giả sử rằng đầu vào cho một chương trình bao gồm những quan hệ
hữu hạn nên đầu ra cũng là một tập các quan hệ hữu hạn. Sự tính toán đầu ra
bằng cách lặp lại việc thế những quy tắc cho đến khi không có nguyên tố nền
nào mới được sinh ra được gọi là sự tính toán bottom-up. Đối với một chương
trình, phương pháp này thực hiện trong thời gian đa thức theo kích cở của
EDB.
Cho P là một chương trình với các vị từ EDB e1,e2,...,en và vị từ IDB
i1,i2,...,im. Cho một EDB <E1,E2,...,En> trong đó mỗi Ek là một quan hệ đối với
vị từ ek. DB được tính bởi P được biểu diễn bởi P(<E1,E2,...,En>) là một tập của
các nguyên tố nền.
Ta cũng có thể xem P là một chương trình mà đầu vào của nó là cả EDB
và IDB. Đầu ra được tính bằng cách lặp lại phép thế các quy tắc cho đến khi
không còn nguyên tố nền mới được thêm vào IDB. Rõ ràng đầu ra là một DB
4
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
mà chứa đầu vào. Khi P là một chương trình mà đầu vào của nó là cả EDB
<E1,E2,...,En> và IDB <I1,...,Im> thì đầu ra được tính bởi P được biểu diễn là
P(<E1,E2,...,En,I1,...,Im>)
Ví dụ 1.2.2: Cho P là một chương trình của ví dụ 1.1.6.
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z)
Trong ví dụ 1.2.1, khi dữ liệu vào là {a(1,2), a(1,4), a(4,,1)}, ta đã tính
được dữ liệu ra của P là O1={a(1,2), a(1,4), a(4,1), g(1,2), g(1,4), g(4,1), g(1,1),
g(4,4), g(4,2)}
Nếu cho dữ liệu vào là {a(1,2), a(1,4), g(4,,1)}, ta cũng tính được dữ liệu
ra là O2={a(1,2), a(1,4), g(1,2), g(1,4), g(4,1), g(1,1), g(4,4), g(4,2)}
Như vậy O2 = O1 - {a(4,1)}
Ta giới hạn, một chương trình P có những quy tắc với thân rỗng thì
những quy tắc này là những nguyên tố nền. Những nguyên tố nền này có trong
đầu ra của P ngay cả khi đầu vào là rỗng.
1.3-Tính tương đương, tương đương đồng dạng và những mô hình.
Định nghĩa 1.3.1 (Tính bao hàm của hai chương trình)
Cho P1 và P2 là những chương trình với cùng một tập vị từ EDB và IDB.
Chương trình P1 bao hàm chương trình P2, được viết P2 P1, nếu đối với mọi
EDB <E1,E2,...,En> thì P2(<E1,E2,...,En>) P1(<E1,E2,...,En>) (dữ liệu ra của P1
chứa dữ liệu ra của P2). Nghĩa là đối với mỗi vị từ q, quan hệ đối với q trong
DB P2(<E1,E2,...,En>) là một tập con của quan hệ đối với q trong DB
P1(<E1,E2,...,En>)
Định nghĩa 1.3.2 (Tính tương đưong của hai chương trình)
Chương trình P1 và chương trình P2 là tương đương (equivalent), ký hiệu
P2P1 nếu P2 P1 và P1 P2. Hai chương trình tương đương nếu chúng đưa ra
cùng một dữ liệu ra mỗi khi chúng được cho cùng một dữ liệu vào EDB.
Định nghĩa 1.3.3 (Tính bao hàm đồng dạng của hai chương trình)
Chương trình P1 bao hàm đồng dạng (uniformly contains) P2, ký hiệu
P2P1 nếu đối với tất cả các cặp của một EDB <E1,E2,...,En> và một IDB
<I1,I2,...,Im> ta có: P2(<E1,E2,...,En,I1,I2,...,Im>) P1(<E1,E2,...,En,I1,I2,...,Im>)
Định nghĩa 1.3.4 (Tính tương đương đồng dạng của hai chương trình)
Chương trình P1 và chương trình P2 là tương đương đồng dạng
(Uniformly equivalent), ký hiệu P2 P1 nếu P2 P1 và P1 P2. Hai chương
trình tương đương đồng dạng nếu chúng đưa ra cùng một dữ liệu ra khi chúng
5
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
được cho cùng một dữ liệu vào, trong đó dữ liệu vào có thể gồm cả những
nguyên tố nền đối với những vị từ IDB.
Mệnh đề 1.3.5: Nếu chương trình P1 bao hàm đồng dạng P2 thì P1 bao hàm P2.
Chứng minh: Nếu P2(<E1,E2,...,En,I1,I2,...,Im>) P1(<E1,E2,...,En,I1,I2,...,Im>) đối
với tất cả <E1,E2,...,En> và <I1,I2,...,Im> khi đó xét trường hợp riêng đối với
EDB <E1,E2,...,En> ta có: P2(<E1,E2,...,En,,...,) P1(<E1,E2,...,En,,...,>),
trong đó biểu thị quan hệ rỗng. Vì vậy: P2(<E1,E2,...,En>)
P1(<E1,E2,...,En>) đối với tất cả các EDB <E1,E2,...,En>. Do đó P2 P1 (ĐPCM)
Ví dụ 1.3.6: Ví dụ này nhằm chỉ ra quan hệ bao hàm là không hàm chứa quan
hệ bao hàm đồng dạng.
Cho P1 là chương trình của ví dụ 1.1.6:
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z)
và cho P2 là chương trình:
g(X,Z) a(X,Z)
g(X,Z) a(X,Y) g(Y,Z)
Cả hai chương trình tính bao đóng bắc cầu của a khi đầu vào chỉ có
những nguyên tố nền của a nghĩa là chúng là tương đương.
Hơn nữa ta thấy: P1 bao hàm đồng dạng P2, nhưng P2 không bao hàm
đồng dạng P1.
Thật vậy, giả sử dữ liệu vào là quan hệ rỗng đối với a và một số quan hệ
khác rỗng G đối với g, chẳng hạn G không là bao đóng bắc cầu của chính nó.
Thì dữ liệu ra của P2 là giống như dữ liệu vào. Trong khi đó dữ liệu ra của P1 là
bao đóng bắc cầu của G. Như vậy, quan hệ bao hàm không hàm chứa quan hệ
bao hàm đồng dạng.
Định nghĩa 1.3.7 (Mô hình)
Một DB <E1,E2,...,En,I1,I2,...,Im> là một mô hình của P nếu:
<E1,E2,...,En,I1,I2,...,Im> = P(<E1,E2,...,En,I1,I2,...,Im>). Nghĩa là không có
nguyên tố nền mới nào được sinh ra khi áp dụng chương trình P vào DB đã
cho. Đặt M(P) là tập hợp của tất cả các mô hình của P. Nó được gọi là tập hợp
M(P) đóng trong dạng giao nhau. Với một dữ liệu vào cho trước
<E1,E2,...,En,I1,I2,...,Im> thì dữ liệu ra của P là mô hình cực tiểu của P mà chứa
dữ liệu vào.
Kết quả trên hàm ý rằng hai chương trình được gọi là tương đương nếu
đối với mọi dữ liệu vào <E1,E2,...,En>, các chương trình có cùng một mô hình
6
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
cực tiểu mà chứa <E1,E2,...,En>. Chương trình P1 và chương trình P2 là tương
đương đồng dạng nếu chúng có cùng một tập mô hình, nghĩa là M(P1)=M(P2).
Mệnh đề 1.3.8: P2 P1 M(P1) M(P2)
Khi thảo luận về quan hệ bao hàm đồng dạng của hai chương trình P1 và
P2, không cần thiết chúng phải có cùng tập hợp các vị từ, quy định đầu vào là
tập bất kỳ những nguyên tố nền đối với những vị từ xuất hiện trong P1 hoặc P2.
Thậm chí có thể cho một vị từ EDB trong chương trình này là một vị từ IDB
trong chương trình kia.
Ví dụ 1.3.9: Cho P1 là chương trình của ví dụ 1.1.6:
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z)
và P2 thu được từ P1 bằng cách thêm quy tắc:
a(X,Z) a(X,Y) g(Y,Z).
Chương trình P2 chỉ có các vị từ IDB, nghĩa là có dữ liệu vào là một IDB
khác rỗng. Vì tất cả các quy tắc của P1 cũng là một quy tắc của P2, dễ dàng
kiểm tra rằng P1(d) P2(d) đối với tất cả DB d gồm có các nguyên tố nền đối
với a và g. Vì vậy, có bao hàm đồng dạng nghĩa là P1 P2
Với chương trình P1 và P2 đã cho, ta có thể xây dựng chương trình P1’ và
P2’ sao cho P2 P1 nếu và chỉ nếu P2’ P1’. Chương trình P1’ và P2’ thu được
bằng cách thêm các quy tắc có giá trị khởi động tùy ý cho vị từ IDB. Quy tắc
được thêm cho một vị từ IDB b(X1,..,Xn) là b(X1,..,Xn)b0(X1,..,Xn). Trong đó
b0 là một vị từ mà không xuất hiện ở bất kỳ quy tắc nào khác. Nếu P1 và P2 đã
có một quy tắc có dạng b(X1,..,Xn)g(X1,..,Xn), trong đó g chỉ xuất hiện ở
trong quy tắc này, thì không cần phải thêm quy tắc đối với b. Đặc biệt, nếu đối
với mọi vị từ IDB b, trong P1 và P2 đã có một quy tắc có dạng
b(X1,..,Xn)g(X1,..,Xn), trong đó g chỉ xuất hiện trong quy tắc này thì P2 P1
nếu và chỉ nếu P2 P1.
II-TỐI ƯU HÓA CHƯƠNG TRÌNH ĐỆ QUY TRONG TÍNH TƯƠNG ĐƯƠNG
ĐỒNG DẠNG.
Ta xét một kiểu tối ưu đặc biệt đó là xóa những nguyên tố thừa trong
thân của một quy tắc và xóa những quy tắc thừa trong một chương trình. Sự tối
ưu này rất hữu ích vì nó giảm số lượng các kết nối cần thiết khi tính toán dữ
liệu ra. Vấn đề tối ưu của chương trình không đệ quy đã được giải quyết. Một
chương trình gồm có những quy tắc không đệ quy có một chương trình tương
đương duy nhất với một số lượng cực tiểu các quy tắc và một số lượng cực tiểu
các nguyên tố trong thân của mỗi quy tắc. Tối ưu những chương trình đệ quy
7
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
được xem xét khó hơn. Thực tế, có thể không tồn tại thuật toán để tối ưu
chương trình đệ quy, vì sự tương đương của chương trình đệ quy là vấn đề bất
khả quyết.
Trong phần “Cực tiểu chương trình trong tính tương đương đồng dạng”
ta sẽ đưa ra một thuật toán để tìm những nguyên tố thừa trong thân quy tắc
cũng như những quy tắc thừa trong một chương trình và xóa chúng trong khi
vẫn duy trì tính tương đương đồng dạng. Kết quả cuối cùng là một chương trình
mà không còn một nguyên tố hoặc quy tắc thừa. Khác với trường hợp không đệ
quy, kết quả cuối cùng của sự tối ưu hóa này không phải là duy nhất mà nó tùy
thuộc vào thứ tự trong đó các nguyên tố và quy tắc được xem xét để xóa.
2.1-Kiểm tra tính bao hàm đồng dạng và tương đương đồng dạng.
Kiểm tra M(P1) M(P2) (và với mệnh đề 2, P2 P1) có thể thực hiện
bởi quá trình gối nhau (chase process).
Một DB d là một mô hình của P2 nếu và chỉ nếu nó là một mô hình của
mọi quy tắc r của P2. Do đó M(P1) M(P2) nếu và chỉ nếu đối với mọi quy tắc
r của P2 ta luôn có M(P1) M(r). Vì vậy, với mệnh đề 2, P2 P1 nếu và chỉ
nếu với mọi quy tắc r của P2 thì r P1 (r được xem như là một chương trình
một quy tắc).
Ta sẽ chỉ ra cách để kiểm tra r P1 (r là một quy tắc). Cho r là quy tắc
h b (h là đầu và b là thân của quy tắc, b có thể là rỗng, khi đó h là một
nguyên tố nền). Để kiểm tra r P1, ta xem nguyên tố của b như là một DB dữ
liệu vào cho P1. Những nguyên tố của b được biến đổi thành một DB bằng cách
thay thế những hằng phân biệt cho những biến của r, kết quả b trở thành một
tập các nguyên tố nền. Bao hàm đồng dạng r P1 thỏa mãn nếu và chỉ nếu
P1(b) chứa nguyên tố nền h, trong đó:
+ là một phép thế một-một mà ánh xạ mỗi biến của r vào một hằng số
phân biệt không có trong r hoặc P1
+b là tập hợp các nguyên tố nền thu được từ b bằng cách thế theo
+h là nguyên tố nền thu được từ h bằng cách thế theo
Những điều kiện ở trên hàm ý rằng nếu b là rỗng, thì r P1 đạt được
nếu và chỉ nếu r cũng là một quy tắc của P1.
Ví dụ 2.1.1: Cho P1 là chương trình của ví dụ 1.1.6
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z)
và cho P2 là chương trình:
8
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
g(X,Z) a(X,Z)
g(X,Z) a(X,Y) g(Y,Z)
Ta sẽ chỉ ra rằng P2 P1. Trước hết, các biến của P2 phải được thay thế
bởi các hằng phân biệt. Ta dùng chỉ số dưới 0 để biểu thị các hằng, biến X được
thay với một hằng là X0, biến Y được thay với một hằng Y0 và biến Z được
thay với một hằng Z0. Ta xem xét từng quy tắc của P2. Đối với quy tắc thứ nhất
r1:
g(X,Z) a(X,Z)
Hiện hành thân của r1 là DB {a(X0,Z0)}. Khi áp dụng P1 vào DB này, kết
quả là {g(X0,Z0), a(X0,Z0)}. Vì kết quả chứa hiện hành đầu của r1 nên r1P1
Xét quy tắc thứ hai r2 của P2:
g(X,Z) a(X,Y) g(Y,Z)
Hiện hành thân của r2 là {a(X0,Z0), g(X0,Z0)}. Áp dụng quy tắc thứ nhất
của P1 vào a(X0,Z0) sinh ra g(X0,Y0). Áp dụng quy tắc thứ hai sinh ra g(X0,Z0).
Như vậy, hiện hành đầu của r2 (G(X0,Z0)) có trong kết quả. Do đó r2P1.
Ta sẽ chỉ ra rằng P1 P2. Xét quy tắc thứ hai s của P1:
g(X,Z) g(X,Y) g(Y,Z)
Hiện hành thân là DB {g(X0,Y0),g(X0,Z0)}. Không có nguyên tố mới nào
được sinh ra khi P2 được áp dụng vào DB này. Vì vậy s P2, do đó P1 P2
Ví dụ 2.1.2: Cho P1 là chương trình:
g(X,Y,Z) g(X,W,Z) a(W,Y) a(W,Z) a(Z,Z) a(Z,Y)
và P2 là chương trình:
g(X,Y,Z) g(X,W,Z) a(W,Z) a(Z,Z) a(Z,Y)
Vì thân của quy tắc của chương trình P2 là một tập con của quy tắc của
P1, rõ ràng P1 P2.
Ta sẽ chỉ ra rằng P2 P1.
(1)
Hiện hành thân của quy tắc của P2 là DB {g(X0,W0,Z0), a(W0,Z0),
a(Z0,Z0), a(Z0,Y0)}. áp dụng P1 vào DB này bằng cách thay thế các biến của P1
như sau: biến X được thay bởi X0, biến W thay bởi W0 và Z và Y thay bởi Z0.
Với phép thế này, thân của quy tắc P1 trở thành một tập con của DB, vì vậy
nguyên tố nền g(X0,W0,Z0) được thêm vào DB.
áp dụng lại P1 bằng cách thay X với X0, W và Z với Z0, Y với Y0. Kết
quả g(X0,W0,Z0) là hiện hành đầu của quy tắc của P2. Vì vậy P2 P1.
(2)
Từ (1) và (2) suy ra P1P2.
2.2-Cực tiểu hóa chương trình trong tính tương đương đồng dạng
9
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
Từ thuật toán kiểm tra sự tương đương đồng dạng, ta có thể tối ưu
chương trình Datalog. Việc loại trừ những nguyên tố thừa trong thân của một
quy tắc được thực hiện như sau: Xét một quy tắc r và cho q là kết quả của việc
xóa một nguyên tố trong thân của r. Nếu q r thì quy tắc r có thể được thay
thế bởi q. Khi r được thay thế bởi q, quá trình tiếp tục xóa các nguyên tố thừa
khác trong thân của q. Nếu quy tắc kết quả là được bao hàm đồng dạng trong q
thì q được thay thế bằng quy tắc đó. Các bước được tóm tắt trong thuật toán
dưới đây:
Begin
Repeat
Đặt là một nguyên tố trong thân của r mà chưa được xem xét.
Đặt q là quy tắc thu được bằng cách xóa trong r
Nếu q r thì thay thế r bởi q
Until mỗi nguyên tố được xem xét một lần
End;
Thuật toán H1. Cực tiểu một quy tắc.
Kết quả cuối cùng là một quy tắc tương đương đồng dạng với quy tắc
gốc nhưng không tồn tại nguyên tố thừa
Để chứng minh tính đúng đắn của thuật toán, ta phải chỉ ra rằng không
nguyên tố nào phải xem xét nhiều hơn một lần. Nói cách khác, nếu một nguyên
tố là không thừa khi nó được xem xét lần thứ nhất thì việc xóa tiếp theo của
nguyên tố khác không làm cho trở thành thừa. Ta sẽ chứng minh điều này
trong phần phụ lục. Nói chung, kết quả cuối cùng của thuật toán là không duy
nhất và tùy thuộc vào thứ tự trong đó các nguyên tố được xem xét. Cuối cùng
chú ý rằng nếu q thu được từ r bằng cách xóa một nguyên tố trong thân, và
một số biến trong đầu của r xuất hiện chỉ trong thân thì q tuân theo giới hạn
ta trên những quy tắc. Rõ ràng thuật toán kiểm tra sẽ xác định rằng q r nên
không thể thừa.
10
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
Ví dụ 2.2.1: Xét chương trình P1 và P2 của ví dụ 2.1.2.
Mỗi chương trình có một quy tắc và quy tắc của chương trình P2 thu
được từ quy tắc của chương trình P1 bằng cách xóa đi nguyên tố a(W,Y). Trong
ví dụ 2.1.2, ta đã chỉ ra rằng P2 P1. Như vậy nếu ta thực hiện thuật toán H1
với quy tắc của P1 thì nó sẽ được thay thế bởi quy tắc của P2. Dễ dàng chỉ ra
rằng quy tắc của P2 không có nguyên tố thừa nào. Vì thế, thuật toán dừng với
quy tắc của P2 là một dạng tối thiểu của quy tắc của P1.
Những quy tắc thừa có thể được xóa trong một chương trình P tương tự
với sự loại bỏ những nguyên tố thừa trong thân của một quy tắc. Một quy tắc r
bị xóa trong P để thu được một chương trình P’, và nếu r P’, thì P P’ và
như vậy P’ có thể thay thế P. Để cực tiểu một chương trình P, trước hết ta cực
tiểu mỗi quy tắc bằng cách xóa đi những nguyên tố thừa của nó, và sau đó xóa
những quy tắc thừa. Tuy nhiên có thể tồn tại tình huống mà một nguyên tố
trong một số quy tắc r của P có thể không thừa nếu r được xem xét một mình,
nhưng nó bị thừa nếu xem xét trong mọi quy tắc của P.
Để cực tiểu một quy tắc r của P, ta phải sửa lại thuật toán H1 bằng cách
thay thế điều kiện q r trong lệnh “Nếu q r thì thay thế r bởi q” bằng điều
kiện q P. Thuật toán để cực tiểu một chương trình có thể viết như sau:
Begin
For mỗi quy tắc của r do
Repeat
-Đặt là một nguyên tố trong thân của r mà chưa được xem xét.
-Đặt q là quy tắc thu được bằng cách xóa trong r
-Nếu q P thì thay thế r bởi q
Until mỗi nguyên tố được xem xét một lần
Repeat
-Đặt r là một quy tắc của P mà chưa được xem xét.
-Đặt P’ là chương trình thu được bằng cách xóa r trong P
-Nếu r P’ thì thay thế P bởi P’
Untill mỗi quy tắc được xem xét một lần
End;
Thuật toán H2: Cực tiểu một chương trình P.
Trong phần phụ lục ta chứng minh rằng kết quả cuối cùng của thuật toán
không có quy tắc thừa và nguyên tố thừa. Ngoài ra ta còn chỉ ra rằng không có
quy tắc hoặc nguyên tố phải được xem xét nhiều hơn một lần. Chứng minh dựa
11
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
trên quy định mỗi quy tắc được cực tiểu và sau đó chỉ được xóa những quy tắc
thừa. Kết quả cuối cùng của thuật toán không phải là duy nhất.
III- TỐI ƯU HÓA CHƯƠNG TRÌNH ĐỆ QUY TRONG TÍNH TƯƠNG ĐƯƠNG.
Phần này mô tả một thủ tục phức tạp hơn để xóa những nguyên tố thừa
trong khi vẫn duy trì tính tương đương nhưng không tương đương đồng dạng.
Thủ tục này không phải là thuật toán đầy đủ, vì nó phải dùng một số heuristic,
như vậy nó không luôn xóa tất cả các nguyên tố thừa trong dạng tương đương.
Tuy nhiên, đây là một công cụ khá hiệu quả để tối ưu chương trình datalog.
3.1-Phụ thuộc sinh bộ
Định nghĩa 3.1.1 (Phụ thuộc sinh bộ)
Một phụ thuộc sinh bộ (Tuple-Generating Dependency-tgd) là một công
thức có dạng x’y’[1(x’)2(x’,y’)] trong đó x’ và y’ là những vectơ của
các biến và 1, 2 là sự kết hợp của những nguyên tố. Ta có thể viết một tgd
mà không có các lượng từ g(Y,Z)g(Y,W)c(W) thay vì:
Y Z W [g(Y,Z)g(Y,W)c(W)]
Định nghĩa 3.1.2 (Lượng từ phổ biến, lượng từ tồn tại)
Những biến lượng từ phổ biến (universally) là những biến xuất hiện
trong vế trái của công thức (những biến này có thể xuất hiện trong vế phải)
Những biến lượng từ tồn tại là chỉ xuất hiện ở vế phải của tgd.
Thông thường, ta nói rằng một DB d thỏa mãn một tgd t nếu đối với mọi
thể hiện của những biến lượng từ phổ biến thì điều sau đây là đúng: Nếu vế
trái của t được thế bởi thành những nguyên tố nền của d thì vế phải của t cũng
được thế thành những nguyên tố nền của d bằng cách mở rộng thành một
phép thế của tất cả các biến của t.
Ví dụ 3.1.3: Xét tgd g(X,Y) a(Y,Z) a(Z,X), và DB được sinh ra trong ví
dụ 1.2.1: {a(1,2), a(1,4), a(4,1), g(1,2), g(1,4), g(4,1), g(1,1), g(4,4), g(4,2)}.
Nếu ta thế cả X và Y bởi 4, thì hiện hành phía bên trái g(4,4) là một
nguyên tố nền của DB. Ta có thể chọn để thay thế 1 vào Z, kết quả hiện hành
bên phải gồm có các nguyên tố nền a(4,1) và a(1,4) của DB. Tuy nhiên DB
không thỏa mãn tgd vì sự thay thế 4 vào X và 2 vào Y làm biến đổi vế trái
thành một nguyên tố nền của DB, nhưng không có sự thay thế nào của Z sao
cho biến đổi vế phải thành những nguyên tố nền của DB.
tgd g(X,Y) g(X,Z) a(Z,Y) là thỏa mãn DB. Chẳng hạn: nếu X được
thay thế bởi 1 và Y được thay thế bởi 2, thì sự thay thế Z với 1 biến đổi vế phải
thành những nguyên tố nền của DB.
12
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
Cho S là một tập của những DB. Ta nói rằng chương trình P1 bao hàm
đồng dạng P2 trên S, được viết P2sP1, nếu P2(d) P1(d) đối với mọi DB dS.
Trong hầu hết các trường hợp, ta giả sử rằng S là tập tất cả DB thỏa mãn một
tập các tgd T đã cho, ta ký hiệu tập này bởi SAT(T).
Phụ thuộc sinh bộ rất quan trọng trong Datalog, vì trong nhiều trường
hợp tối ưu của một chương trình chỉ yêu cầu xem xét những DB mà thỏa mãn
một số tgd. Một trường hợp là khi EDB thỏa mãn một số ràng buộc mà có thể
được biểu diễn như là những tgd. Có thê sử dụng những ràng buộc này để tối
ưu chương trình. Ta sẽ chỉ ra cách để sử dụng những tgd một cách tổng quát
hơn. Về cơ bản, ta đưa ra một thủ tục minh chứng cho biểu diễn P2 SAT(T) P1
và phát triển một kỹ thuật dể xóa những nguyên tố thừa trong một chương trình
P bằng cách thực hiện những bước sau:
Thứ nhất: Phải chỉ ra rằng P2 SAT(T) P1 đối với một số T thích hợp,
trong đó P2 thu được từ P1 bằng cách xóa một nguyên tố trong một số quy
tắc.
Thứ hai: Phải chỉ ra rằng P2 SAT(T) P1 bao hàm P2 P1. Nếu ta chỉ ra
được cả hai thì là thừa trong P1, dù nó không thừa trong tính tương đương
đồng dạng.
Để chỉ ra P2SAT(T)P1, ta phải chỉ ra SAT(T)M(P1)M(P2), nghĩa là
mọi mô hình của P1 thỏa mãn T cũng là một mô hình của P2.
SAT(T)M(P1)M(P2) chưa thể suy ra P2SAT(T)P1. Phần tiếp theo ta sẽ mô tả
một bước thứ hai để kết luận P2 SAT(T) P1.
Để kiểm tra SAT(T)M(P1) M(P2), ta phải xét từng quy tắc r của P2
và chỉ ra rằng khi cả P1 và T được áp vào thân của r thì kết quả bao gồm đầu
của r. Áp dụng tgd của T vào một DB tương tự với áp dụng một quy tắc, vì tgd
cũng là mệnh đề Horn.
Định nghĩa 3.1.4 (tgd đầy đủ và tgd nhúng)
tgd đầy đủ (Full) là những tgd mà không có biến lượng từ tồn tại. tgd
nhúng (Embedded) là những tgd mà có một số biến lượng từ tồn tại.
Ví dụ dưới đây minh họa cho việc áp dụng một tgd đầy đủ vào một DB
(giống như áp dụng một quy tắc).
Ví dụ 3.1.5: Cho tgd đầy đủ: a(X,Y,Z) b(W,Y,V) a(X,Y,V) t(W,Y,Z).
áp dụng nó vào một DB giống như áp dụng hai quy tắc dưới đây. Mỗi quy tắc
xem vế trái của tgd là thân và một trong những nguyên tố ở về phải của tgd là
đầu.
a(X,Y,V) a(X,Y,Z) b(W,Y,V)
13
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
t(W,Y,Z) a(X,Y,Z) b(W,Y,V)
Một tgd nhúng có các biến lượng tử tồn tại vì vậy để áp dụng nó ta phải
sử dụng các hàm Slolem. Sau đây ta tiếp cận lý thuyết cơ sở dữ liệu và xem các
hàm Skolem là những giá trị null. Ta biểu thị những giá trị null là 1,...,i,...
Một tgd t được áp dụng vào một DB như sau: Giả sử rằng là một phép
thế của những biến lượng từ phổ biến của t, sao cho chỉ ra rẳng DB không vi
phạm t. Đó là, biến đổi vế trái của t thành những nguyên tố nền của DB, và
không có mở rộng nào của mà biến đổi vế phải của t thành những nguyên tố
nền của DB. Đối với mỗi biến lượng từ tồn tại của t, ta chọn một i duy nhất
(không có trong DB) và mở rộng thành một phép thế mà ánh xạ mỗi biến
lượng từ tồn tại thành giá trị rỗng tương ứng của nó. Những nguyên tố được
thay thế ở vế phải của t được thêm vào DB. Ví dụ: nếu t là tgd
g(X,Y)a(X,W)g(W,Y) và nguyên tố g(3,2) thuộc DB thì ta thêm a(3,23) và
g(23,2) (tất nhiên DB đó không chứa 23 cũng không chứa cặp nguyên tố dạng
a(3,e) và g(e,2) trong đó e là một hằng hoặc null). Những nguyên tố a(3,23) và
g(23,2) nghĩa là có một số giá trị chưa biết c sao cho a(3,c) và g(c,2) thuộc DB.
Những áp dụng kết hợp một chương trình P và một tập tgd T được biểu
thị [P,T]. Ta áp dụng [P,T] vào một DB d cho đến khi không có một nguyên tố
mới nào có thể được thêm vào DB và kết quả cuối cùng được biểu thị [P,T](d).
Rõ ràng, [P,T](d) là một mô hình của P và một DB mà thỏa mãn T. Vì việc áp
dụng của tgd có thể thêm các giá trị null mà không có trong DB, một số tập của
tgd có thể được áp dụng vào một DB khởi đầu mãi mãi. Chú ý rằng, một lần
một nguyên tố với giá trị null được thêm vào DB thì nó được xem như là một
nguyên tố nền và những giá trị null được xem như những hằng số, cho đến khi
những áp dụng của các quy tắc và các tgd được nhúng vào.
Ví dụ 3.1.6: Cho P1 là chương trình:
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z) a(Y,W)
và cho P2 là chương trình:
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z)
Dễ dàng chỉ ra rằng P1 P2. Ta sẽ chỉ ra rằng SAT(T)M(P1)M(P2),
trong đó T gồm có phụ thuộc đơn g(X,Z) a(X,W).
Những quy tắc của P2 phải được xem xét từng cái một. Ta bắt đầu với
quy tắc thứ nhất. Thân của quy tắc trở thành DB {a(X0,Z0)}. áp dụng [P1,T] vào
DB này thu được {a(X0,Z0), g(X0,Z0)} (chỉ áp dụng quy tắc thứ nhất của P1 vào
14
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
DB này). Kết quả này chứa hiện hành đầu của quy tắc thứ nhất của chương
trình P2.
Tiếp theo, xét DB {g(X0,Y0), g(Y0,Z0)} là hiện hành thân của quy tắc thứ
hai của P2. Trước hết, chỉ có thể áp dụng [P1,T] vào tgd của T. Nếu vế trái của
tgd được thay thế thành g(X0,Z0) thì phép thế này không thể mở rộng thành bất
kỳ phép thế nào mà biến đổi vế phải thành một nguyên tố nền của DB, vì vậy
a(Y0,1) được thêm vào DB. Một cách tương tự, vế trái của tgd có thể được
thay thế thành g(X0,Y0), mà kết quả là thêm a(X0,2) vào DB. Bây giờ thân của
quy tắc thứ hai của P1 có thể được thế vào g(X0,Y0), g(X0,Z0), a(X0,1), vì vậy
g(X0,Z0) được thêm vào DB, bằng cách chỉ ra rằng hiện hành đầu của quy tắc
thứ hai là thuộc kết quả. Vì vậy ta đã chỉ ra rằng SAT(T)M(P1)M(P2). Trong
phần tiếp theo, ta sẽ sử dụng sự kiện này để kết luận P2 SAT(T) P1
Việc chỉ ra P2 SAT(T) P1 là rất hữu ích, bởi vì sẽ dẫn đến P2 P1. Thật
vậy, áp dụng chương trình P1 (hoặc P2) vào một EDB giống như áp dụng P1
(hoặc P2) vào DB cơ sở (là DB gồm có dữ liệu vào và những nguyên tố nền
được sinh ra bởi những quy tắc khởi động. Một quy tắc khởi động là một quy
tắc mà thân của nó chỉ có một vị từ EDB). Vì P1 và P2 có cùng quy tắc khởi
động, chúng có cùng DB cơ sở đối với mọi EDB, và dễ dàng thấy rằng tất cả
những DB cơ sở thỏa mãn T. Vì vậy P2 SAT(T) P1 hàm ý P2P1.
Rõ ràng P2 P1 nên P2 P1. Vì vậy nó kéo theo nguyên tố a(Y,W) trong
quy tắc thứ hai của P1 là d thừa trong dạng tương đương, mặc dù nó không thừa
trong dạng tương đương đồng dạng.
3.2-Duy trì phụ thuộc sinh bộ (Preserving Tuple-Generating Dependencies)
Như đã giới thiệu, chỉ với SAT(T)M(P1)M(P2) sẽ không thể dẫn đến
P2SAT(T)P1. Nhưng nếu ta chỉ ra được P1 duy trì T, thì P2 SAT(T) P1. Ta nói
rằng P1 duy trì T nếu P1(d)SAT(T) đối với tất cả DB d SAT(T).
Không thể biết liệu có một thủ tục để chỉ ra rằng một chương trình P duy
trì một tập các tgd T. Trong phần này ta sẽ mô tả một quá trình mà có thể chỉ ra
rằng P duy trì T. Ý tưởng là nếu ta bắt đầu với một DB d SAT(T) thì mỗi lần
lặp lại trong sự tính toán bottom-up của P(d) duy trì T.
Áp dụng chương trình không đệ quy P vào một DB d nghĩa là áp dụng nó
trên những nguyên tố nền của d mà không trên những nguyên tố nền được sinh
15
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
ra từ d bởi những áp dụng trước. Khi P được áp dụng không đệ quy, ta biểu thị
nó là Pn. Rõ ràng, kết quả của việc áp dụng Pn vào một DB d, biểu thị là Pn(d) là
{h đối với một số quy tắc h b của P và phép thế , những nguyên tố của
b thuộc d}
Với định nghĩa trước, đầu ra P(d) chứa đầu vào d. Pn(d) chỉ chứa những
nguyên tố được sinh ra bằng việc áp dụng những quy tắc không đệ quy vào d
nhưng không nhất thiết chứa những nguyên tố của d.
Ví dụ 3.2.1: Cho P là một chương trình
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z)
và cho d={a(1,2),g(2,3),g(3,4)}
và Pn(d) là {g(1,2), g(2,4)}
và P(d) là {a(1,2),g(2,3),g(3,4) g(1,2), g(1,3), g(2,4), g(1,4)}
ý tưởng là để chỉ ra rằng P duy trì T bằng cách chỉ ra rằng P duy trì T
một cách không đệ quy, đó là <d,Pn(d)> SAT(T) đối với mọi d SAT(T)
(<d,Pn(d)> là sự kết hợp của d và Pn(d)). Nếu P duy trì T một cách không đệ
quy thì P duy trì T nhưng ngược lại là không đúng.
Với điều kiện là P duy trì T không đệ quy được thực hiện bởi biến đổi
của quá trình gối nhau. Quá trình này chứng minh cho sự duy trì không đệ quy
của T, nó dừng với một câu trả lời khẳng định nếu thực sự P duy trì T một cách
không đệ quy, nhưng nó có thể lặp không dừng nếu T là những tgd nhúng và
câu trả lời là phủ định. Trước khi định nghĩa một cách đầy đủ về quá trình này,
ta minh họa bằng một ví dụ đơn giản.
Ví dụ 3.2.2: Xét quy tắc đệ quy r dưới đây:
g(X,Z) g(X,Y) g(Y,Z) a(Y,W)
và cho t là tgd
g(X,Z) a(X,W)
Để chỉ ra rằng r duy trì t không đệ quy, ta sẽ thử chứng minh điều ngược
lại bằng cách xây dựng một phản ví dụ, nếu thực hiện sai thì r duy trì t không
đệ quy. Một phản ví dụ là một DB d SAT(t) sao cho <d,rn(d)> vi phạm t. DB
<d,rn(d)> vi phạm t nếu nó có một nguyên tố nền g(X0,Z0) xuất hiện một vi
phạm của t, đó là một nguyên tố nền g(X0,Z0) sao cho đối với tất cả W0, DB
<d,rn(d)> không có một nguyên tố nền nào của dạng a(X0,W0). Một nguyên tố
nền g(X0,Z0) của <d,rn(d)> mà xuất hiện một vi phạm của t phải thuộc rn(d) (nó
không thể là thuộc d, vì d SAT(t)). Như vậy ta thử xây dựng một phản ví dụ
16
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
bằng giả sử rằng g(X0,Z0) thuộc rn(d) và sau đó thêm những nguyên tố cần thiết
vào d để:
(1)- có nguyên tố g(X0,Z0) trong rn(d)
(2)- làm d thỏa mãn t
Nguyên tố g(X0,Z0) có thể thuộc rn(d) chỉ như là một kết quả của việc áp
dụng rn vào d. Bằng cách hợp g(X0,Z0) với đầu của r, ta có thể xác định những
nguyên tố nền nào phải thuộc d để sinh ra g(X0,Z0). Trong trường hợp này,
phép hợp chỉ ra rằng d phải có những nguyên tố dưới đây: g(X0,Y0), g(X0,Z0),
a(Y0,W0). Trong đó Y0, W0 là các hằng.
Vì d thỏa mãn t, có thể áp dụng tgd t vào d. áp dụng t vào g(X0,Y0) sinh
ra a(X0,1), và áp dụng nó vào g(Y0,Z0) thu được a(Y0,2). Kết quả của những
áp dụng này thuộc những nguyên tố nền mà phải là thuộc d (trái với áp dụng
của rn mà sinh ra những nguyên tố nền thuộc rn(d)). Về cơ bản, sự áp dụng của t
tương ứng với điều suy ra được hàm chứa bởi d thỏa mãn t và bằng một điều
rằng chắc chắn những nguyên tố nền được biết là thuộc d. Về nguyên tắc, tgd t
phải được áp dụng một cách lặp lại vào những nguyên tố của d (cả những
nguyên tố gốc ở trong d và những cái được thêm vào d bằng những áp dụng
trước của tgd). Trong trường hợp đặc biệt này, tgd chỉ có thể được áp dụng vào
những nguyên tố nền gốc được biết là thuộc d (nghĩa là nó được sinh ra bởi
phép hợp g(X0,Z0) với đầu của r). Kết quả những nguyên tố nền phải thuộc d
là: g(X0,Y0), g(Y0,Z0), a(Y0,W0), a(X0,1), a(Y0,2)
Trong số chúng có a(X0,1) mà được chỉ ra rằng g(X0,Z0) không xuất
hiện vi phạm của t. Như vậy, không có một phản ví dụ <d,rn(d)> và vì vậy r
duy trì t không đệ quy.
Ta có thể khái quát hóa ví dụ trên thành một P và T tùy ý. Để chứng
minh rằng P duy trì T không đệ quy, ta thực hiện đối với mỗi t T.
Đầu tiên vế trái của t được thế mỗi biến với một hằng số phân biệt mà
không thuộc P. Những nguyên tố nền của phép thế vế trái được xem xét theo
một trong hai trường hợp dưới đây:
(1)- Những nguyên tố nền của vị từ EDB trở thành một phần của d
(2)- Những nguyên tố nền của vị từ IDB trở thành một phần của Pn(d)
Đối với mỗi nguyên tố nền thuộc Pn(d), ta phải thêm vào d một số
nguyên tố mà sinh ra khi P được áp dụng không đệ quy vào d. Nói chung, có
nhiều cách để thêm những nguyên tố sinh ra . Mỗi cách được xác định bằng
một số quy tắc với đầu có thể được hợp nhất với . Như vậy, ta phải xem xét
tất cả những kết hợp có thể của việc hợp nhất những nguyên tố nền mà đã được
17
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
thêm vào Pn(d) với đầu của những quy tắc (nếu có k nguyên tố nền thuộc Pn(d)
và mỗi i có thể hợp nhất với m quy tắc, thì có mk kết hợp được xem xét). Về cơ
bản, ta phải chỉ ra rằng, đối với mỗi kết hợp có thể, không có vi phạm t. Vì vậy
xem xét một kết hợp có thể mà hợp nhất mỗi nguyên tố nền của một vị từ
IDB g (trong phép thế vế trái của t) với đầu của một số quy tắc r đối với g. Kết
quả của việc hợp nhất, những biến của r mà xuất hiện trong đầu quy tắc được
thế vào những hằng. Để biến đổi thân của r thành những nguyên tố nền, những
biến còn lại của r được thay thế bằng một hằng phân biệt mới, và những
nguyên tố nền của thân được thêm vào d. Nói tóm lại, d chứa tất cả những
nguyên tố nền mà là:
(1)- Những nguyên tố của vị từ EDB từ phép thế vế trái của tgd t hoặc
(2)- Những nguyên tố (EDB hoặc IDB) từ thân của quy tắc mà được hợp
nhất với những nguyên tố của vị từ IDB từ vế trái của t
Về phía Pn(d), nó chứa những nguyên tố của vị từ IDB từ phép thế vế trái
của t.
Trong bước thứ hai, những tgd của T được áp dụng vào d để sinh ra
nhiều nguyên tố nền hơn mà phải thuộc d. Những tgd được áp dụng lặp lại cho
đến khi không có nguyên tố nền nào có thể được sinh ra từ những cái đã có (kết
quả, d trở thành một DB thỏa mãn T)
Tiếp theo, chương trình P được áp dụng không đệ quy vào d để lấy Pn(d).
Cuối cùng, ta phải kiểm tra liệu <d,Pn(d)> thỏa mãn t. Để kiểm tra điều
đó, chỉ cần xem xét phép thế vế trái của t và kiểm tra liệu t có vi phạm trong
<d,Pn(d)>. Không xuất hiện vi phạm nếu hiện hành vế trái có thể được mở rộng
thành một hiện hành mà cũng gồm có các biến lượng từ tồn tại của t, sao cho vế
phải của t trở thành một tập con của <d,Pn(d)>. Thật ra, nó dẫn đến không cần
thiết tính toán tất cả Pn(d) mà chỉ cần xác định liệu <d,Pn(d)> chứa các nguyên
tố nền chỉ ra rằng hiện hành vế trái của t không xuất hiện vi phạm. Để biểu diễn
một cách rõ ràng ta sẽ tiếp tục dùng bước tính toán Pn(d)
Chương trình P duy trì T không đệ quy, nếu đối với tất cả tT và đối với
tất cả sự kết hợp hiện hành vế trái của t với đầu của quy tắc của P, không biểu
hiện vi phạm t.
Trong ví dụ 3.2.2, vế trái của tgd t chỉ có một nguyên tố và chỉ có một
quy tắc. Như vậy chỉ có một kết hợp để kiểm tra, và nó không xuất hiện vi
phạm. Dưới đây là thuật toán để kiểm tra P duy trì T không đệ quy.
Begin
Repeat
-Tạo d empty
18
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
-Chọn a, t T
-Cho ánh xạ những biến lượng từ phổ biến của t
vào những hằng phân biệt mà chưa thuộc P
-Thế vế trái của t theo
-Thêm những nguyên tố hiện hành của vị từ EDB vào d
Repeat
-Chọn một quy tắc đối với mỗi nguyên tố hiện hành
của một vị từ IDB
-Hợp mỗi nguyên tố với đầu của quy tắc được
chọn cho nó, và thêm hiện hành thân vào d.
-áp dụng những tgd của T vào d
-Tính Pn(d)
-Kiểm tra liệu hiện hành vế trái xuất hiện vi phạm t
trong <d,Pn(d)>
Until xuất hiện vi phạm hoặc đã kiểm tra tất cả các kết
hợp của quy tắc được chọn.
Until xuất hiện vi phạm hoặc tất cả t T đã được chọn
If xuất hiện vi phạm thì P không duy trì T một cách không đệ quy
Else P duy trì T một cách đệ quy.
End;
Thuật toán H3: Kiểm tra duy trì không đệ quy của T
Bước áp dụng T vào d có thể không dừng nếu những giá trị null mới
được đưa vào một cách lặp lại. Tuy nhiên, vẫn có thể dừng vòng lặp bên trong
với thời gian hữu hạn (đối với bất kỳ sự lựa chọn t T và bất kỳ sự lựa chọn
quy tắc đối với t) nếu t không xuất hiện vi phạm.
Để đạt được điều đó, ba bước cuối cùng của vòng lặp bên trong phải
được chèn thêm như sau: Thứ nhất, T được áp dụng vào d để sinh ra một số
nguyên tố mới mà phải thuộc d. Tiếp theo, Pn(d) được tính lại, vì giá trị của nó
có thể bị thay đổi như là một kết quả của những nguyên tố mới mà vừa được
thêm vào d. Thứ ba là để kiểm tra liệu hiện hành vế trái của t xuất hiện một vi
phạm trong <d,Pn(d)> hiện tại. Nếu không xuất hiện vi phạm thì t được duy trì
và không cần thiết để tiếp tục. Nếu còn tồn tại vi phạm thì bước trước phải
được lặp lại.
Như đã nêu, mỗi nguyên tố của một vị từ IDB, trong hiện hành vế trái
của t, được hợp với đầu của một số quy tắc. Điều này có ảnh hưởng của kiểm
tra liệu t được thỏa mãn khi những nguyên tố của những vị từ IDB trong vế trái
19
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
của nó được giới hạn là thuộc Pn(d). Trong ví dụ 3.2.2, có một nguyên tố đơn
trong vế trái của t, và như vậy t được thỏa mãn trong <d,Pn(d)> nếu:
(1)- t thoả mãn trong <d,Pn(d)> khi vế trái được giới hạn thuộc Pn(d) và
(2)- t thỏa mãn trong <d,Pn(d)> khi vế trái được giới hạn thuộc d.
(1) đã được chỉ ra trong ví dụ 3.2.2 bằng việc hợp vế trái với đầu của r.
(2) từ sự kiện d thỏa mãn t. Tuy nhiên tình huống này là không đơn giản nếu vế
trái của t có nhiều hơn một nguyên tố của một vị từ IDB. Khi đó, ta phải kiểm
tra rằng t cũng được thỏa mãn khi một số nguyên tố là thuộc Pn(d), trong khi
những nguyên tố khác là thuộc d. Như vậy ta phải xem xét nhiều kết hợp hơn.
Sự kết hợp là tất cả mà trong đó một nguyên tố của vị từ IDB trong vế trái của t
được hợp nhất với đầu của một số quy tắc hoặc được giả sử là thuộc d. Nếu một
nguyên tố được hợp với đầu của một số quy tắc thì nguyên tố trở thành một
phần của Pn(d), trong khi hiện hành thân của quy tắc trở thành một phần của d.
Ta vẫn dùng định nghĩa cũ của phép kết hợp để được xem xét nếu đối với mỗi
vị từ IDB q, ta thêm một quy tắc tầm thường có dạng: q(X1,...,Xn)
q(X1,...,Xn).
Từ đây ta giả sử rằng mỗi chương trình được tăng lên với những quy tắc
tầm thường này. Vì vậy, phép kết hợp được xem xét là giống như định nghĩa
đầu tiên, đó là phép kết hợp mỗi nguyên tố của một vị từ IDB với đầu của một
số quy tắc.
Ví dụ 3.2.3: Xét lại chương trình P1 đã cho trong ví dụ 3.1.6
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z) a(Y,W)
và và tgd t
g(X,Z) a(X,W)
Ta sẽ chỉ ra rằng P1 duy trì T={t} không đệ quy, vì vậy nó cũng duy trì
T. Kết hợp với sự kiện SAT(T) M(P1) M(P2), (được chỉ ra trong ví dụ
3.1.6) dẫn đến là P2 SAT(T) P1. Cho g(X0,Z0) là hiện hành vế trái của t. Trong
ví dụ 3.2.2, ta đã chỉ ra không xuất hiện vi phạm khi g(X0,Z0) được hợp nhất
với đầu của quy tắc thứ hai của P1. Tương tự, có thể không vi phạm khi
g(X0,Z0) được hợp nhất với quy tắc tầm thường g(X,Z) g(X,Z). Trường hợp
cuối cùng để xem xét là sự hợp nhất với quy tắc: g(X,Z) a(X,Z)
Kết quả của phép hợp nhất g(X0,Z0) với đầu của quy tắc trên, d trở thành
DB {a(X0,Z0)}. Những tgd của T không được áp dụng vào d. Tiếp theo bằng
cách áp dụng Pn vào d, ta thu được Pn (d) là {g(X0,Z0)}. Vì a(X0,Z0) thuộc
1
1
<d,Pn (d)>, t không xuất hiện vi phạm, vì vậy P1 duy trì T.
1
20
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
Ví dụ 3.2.4: Cho r là quy tắc như trong ví dụ 3.2.2:
g(X,Z) g(X,Y) g(Y,Z) a(Y,W)
và tgd là
g(X,Y) g(Y,Z) a(Y,W)
Ta sẽ chỉ ra rằng r duy trì t không đệ quy. Ta sẽ xem xét chương trình
ngay cả khi nếu nó có quy tắc tầm thường: g(X,Z) g(X,Z). Như vậy có bốn
khả năng kết hợp của sự hợp nhất của những nguyên tố trong vế trái của t với
đầu của các quy tắc. Cho g(X0,Y0) g(Y0,Z0) là hiện hành vế trái của t và xét
bốn kết hợp dưới đây:
Kết hợp thứ nhất: g(X0,Y0) hợp nhất với đầu của r. Kết quả, những
nguyên tố nền g(X0,Y1), g(Y1,Y0), a(Y1,W0) thuộc d và g(Y0,Z0) được hợp nhất
với đầu của quy tắc tầm thường và nguyên tố g(Y0,Z0) được thêm vào d
Tiếp theo, T={t} phải được áp dụng vào d và vế trái của t được thay thế
với nguyên tố nền g(Y1,Y0), g(Y0,Z0) của d.
Vì phép thế này không được mở rộng để biến đổi vế phải thành những
nguyên tố nền của d, nguyên tố nền a(Y0,1) được thêm vào d. Nguyên tố
a(Y0,1) của d cho thấy không xuất hiện vi phạm của t trong <d,rn(d)> đối với
phép kết hợp được xét.
Phép kết hợp thứ hai: g(X0,Y0) hợp nhất với đầu của quy tắc tầm thường,
nguyên tố nền g(X0,Y0) được thêm vào d và g(Y0,Z0) được hợp nhất với đầu
của r, những nguyên tố nền g(Y0,Y1), g(Y1,Z0), a(Y1,W0) được thêm vào d.
Tiếp theo, T={t} được áp dụng vào d và vế trái của t được thay thế vào
những nguyên tố nền g(X0,Y0), g(Y0,Y1) của d. Phép thế này thêm a(Y0,1) vào
d, và nguyên tố nền này chỉ ra rằng t không vi phạm trong <d,rn(d)>
Phép kết hợp thứ ba: g(X0,Y0) được hợp nhất với đầu của quy tắc r,
những nguyên tố nền g(X0,Y1), g(Y1,Y0), a(Y1,W0) được thêm vào d và
g(Y0,Z0) được hợp nhất với đầu của r, những nguyên tố nền g(Y0,Y2), g(Y2,Z0),
a(Y2,W1) được thêm vào d.
Tiếp theo T={t} được áp vào d bằng cách thế vế trái của t vào những
nguyên tố nền g(Y1,Y0), g(Y0,Y2) của d, kết quả a(Y0,1) được thêm vào d.
Nguyên tố a(Y0,1) chỉ ra rằng t không vi phạm trong <d,rn(d)> đối với phép
kết nối được xem xét.
Phép kết hợp thứ tư: Cả g(X0,Y0) và g(Y0,Z0) được hợp nhất với đầu của
quy tắc tầm thường vì vậy trở thành một phần của d. Rõ ràng, không thể có vi
phạm trong trường hợp này, vì d thõa mãn T.
Vì không có phép kết nối nào xuất hiện vi phạm nên r duy trì t
21
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
Ví dụ 3.2.5: Xét quy tắc r
g(X,Z) a(X,Y) g(Y,Z) g(Y,W) c(W)
và tgd t dưới đây
g(Y,Z) g(Y,W) c(W)
Để chỉ ra r duy trì t không đệ quy, ta thế vế trái của t với g(Y0,Z0) và hợp
nhất nó với đầu của r. Kết quả, những nguyên tố nền g(Y1,Z0), g(Y1,W0),
a(Y0,Y1), c(W0) là thuộc d
Trong trường hợp này, tgd t không thể áp dụng vào d để sinh ra những
nguyên tố mới. Nhưng khi r được áp dụng không đệ quy vào d, DB rn(d) trở
thành g(Y0,Z0), g(Y0,W0)
Để thấy g(Y0,Z0) là thuộc rn(d), ta lưu ý, nguyên tố này đã được hợp nhất
với đầu của r và hiện hành thân trở thành một phần của d. Để thấy g(Y0,W0) là
thuộc rn(d), ta thế các biến của r: X với Y0, Y với Y1, Z và W với W0.
Những nguyên tố nền g(Y0,W0) và c(W0) chỉ ra rằng <d,rn(d)> không vi
phạm t khi vế trái được thế với g(Y0,Z0). Như vậy r duy trì t.
3.3-Xác định tính tương đương (Determining Equivalence)
Phần này ta sẽ chỉ ra cách để có thể kết luận P2 P1 từ P2SAT(T)P1. Ta
sẽ sử dụng kỹ thuật này để tối ưu hóa các chương trình.
Một quy tắc r của một chương trình P là một quy tắc khởi động nếu thân
của r chỉ có những vị từ EDB. Pi là chương trình gồm có những quy tắc khởi
động của P (Pi là một chương trình không đệ quy). Cho một EDB d là dữ liệu
vào của P, ta định nghĩa Pi(d) là tập các nguyên tố nền được sinh ra bằng việc
áp dụng Pi vào d (Pi(d) không bao gồm d). DB cơ sở (preliminary) đối với một
EDB d là <d,Pi(d)>
Ví dụ 3.3.1: Cho P là chương trình
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z)
và
d={a(1,2), a(2,3), a(3,4)}
Pi(d) là {g(1,2), g(2,3), g(3,4)}
và DB cơ sở đối với d là {a(1,2), a(2,3), a(3,4), g(1,2), g(2,3), g(3,4)}.
Ví dụ dưới đây minh họa cách kết luận P2 P1 từ P2 SAT(T) P1.
Ví dụ 3.3.2: Xét lại hai chương trình của ví dụ 3.1.6
Cho P1 là chương trình:
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z) a(Y,W)
và P2 là chương trình:
22
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
g(X,Z) a(X,Z)
g(X,Z) g(X,Y) g(Y,Z)
Rõ ràng P1 P2. Trong ví dụ 3.1.6 ta đã có SAT(T) M(P1) M(P2).
Trong đó T gồm có những tgd đơn:
g(X,Z) a(X,W)
Trong ví dụ 3.2.3 ta đã chỉ ra: P1 duy trì T, kết quả, P2 SAT(T) P1. Trong
ví dụ này ta sẽ chỉ ra: P2 P1 nên P2 P1. (vì P1 P2 nên P1 P2).
Thứ nhất, ta sẽ chỉ ra rằng đối với mọi EDB d, DB cơ sở, <d,Pi(d)>, thỏa
mãn T. Trong đó Pi1 gồm có các quy tắc: g(X,Z) a(X,Z)
Về cơ bản, thuật toán H3 dùng để chỉ ra rằng <d,Pi(d)> thỏa mãn T.
Nhưng có hai thay đổi: Thứ nhất, ta không giả sử d thỏa mãn T vì vậy ta bỏ qua
bước mà những tgd của T được áp dụng vào d. Thứ hai, d là một EDB được
cho như một đầu vào của P1 do đó nó không có bất kỳ một nguyên tố nền nào
của một vị từ IDB. Vì vậy, ta không thêm vào chương trình Pi1 những quy tắc
tầm thường đối với những vị từ IDB.
Như vậy, ta bắt đầu bằng việc thế vế trái của tgd trong T, kết quả là
g(X0,Z0). Chỉ có một quy tắc trong Pi1 vì vậy chỉ có một kết hợp của sự hợp
nhất hiện hành vế trái với đầu của các quy tắc. Kết quả của phép hợp nhất này
trong d là DB {a(X0,Z0)}. Vì a(X0,Z0) được chỉ ra là thuộc <d,Pi(d)>, tgd không
xuất hiện vi phạm, vì vậy tất cả DB cơ sở của P1 thỏa mãn T.
P1 và P2 có cùng một quy tắc khởi động và kết quả những DB cơ sở của
nó giống nhau (khi được cho cùng EDB là đầu vào). Vì vậy P2 SAT(T) P1 bao
hàm P2 P1, vì tất cả những DB cơ sở thỏa mãn T.
Từ việc chỉ ra P2 P1 đã dẫn đến:
(1)-SAT(T) M(P1) M(P2).
(2)-P1 duy trì T
(3)-Đối với tất cả EDB d, chương trình P1 và P2 có cùng một DB cơ sở.
(4)-Tất cả DB cơ sở thỏa mãn T
Phần (1) có thể được chỉ ra dùng quá trình gối nhau được mô tả trong
phần “Phụ thuộc sinh bộ”. Phần (2) có thể được chỉ bằng thuật toán H3. Phần
(3) yêu cầu chỉ ra rằng Pi1 và Pi2 là tương đương. Sự tương đương của chương
trình không đệ quy giống như tương đương đồng dạng và thuật toán được mô tả
trong phần “Kiểm tra tính bao hàm và tương đương đồng dạng đã chỉ ra điều
đó. Phần (4) có thể được chỉ ra bởi thuật toán H3 với những sửa đổi như sau:
Thứ nhất, bước áp dụng những tgd của T vào d bị xóa. Thứ hai, chương trình
Pi1 không được làm tăng lên bằng những quy tắc tầm thường đối với các vị từ
IDB.
23
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
Phương pháp để chỉ ra P2 P1 có một số hạn chế dẫn đến giảm khả năng
ứng dụng của nó. Thứ nhất, không phải luôn tìm được một tập tgd T đối với cái
mà (1)-(4) đưa ra. Hơn nữa, sự kiện P2 P1 không nhất thiết hàm ý có một T
như vậy. Thứ hai, thủ tục để kiểm tra (1) hoặc (2), dừng trong thời gian hữu
hạn nếu câu trả lời là khẳng định nhưng có thể không dừng nếu câu trả lời là
phủ định. Tuy nhiên, ta tin rằng trong nhiều trường hợp thực tế tiếp cận này là
hữu ích trong việc tối ưu hóa các chương trình.
Thực ra, không cần thiết để xem xét những DB cơ sở của P1 và cho thấy
rằng chúng thỏa mãn T. Nói cách khác, những điều kiện 3 và 4 có thể được
thay thế bởi điều kiện dưới đây:
(3’)- Đối với tất cả EDB (d), DB cơ sở <d,Pi1(d)> thỏa mãn T.
Lý do: Ta biết rằng P2 SAT(T) P1 và ta muốn kết luận là P2 P1, tức là
muốn chỉ ra rằng nếu d là một EDB thì P2(d) P1(d). Vậy, cho d’ là DB cơ sở
của P1 thu được từ d (nghĩa là dd’) và giả sử rằng d’ thỏa mãn T. Vì
P2SAT(T)P1 và d’ thỏa mãn T, kéo theo P2(d’) P1(d’).
Vì chương trình Datalog là đơn điệu, nên: P2(d) P1(d).
(A)
(B)
Vì d d’, Hơn nữa, d’ là DB cơ sở thu được bằng cách áp dụng các quy
tắc khởi động của P1 vào d, vì vậy: P1(d) P1(d’)
Từ (A), (B) và (C) suy ra P2(d) P1(d).
(C)
Một chú ý khác, khi định nghĩa DB cơ sở, không cần chọn cái được sinh
bởi những quy tắc khởi động mà chỉ cần xem xét bất kỳ tập các quy tắc của P1
và áp dụng nó một số lượng lần cố định vào EDB ban đầu được cho như một
dữ liệu vào. Việc áp dụng một tập quy tắc đã cho với một số lần cố định (cả
những quy tắc đệ quy) có thể được diễn tả trong điều kiện những quy tắc không
đệ quy. Vì vậy việc kiểm tra liệu DB cơ sở thỏa mãn T có thể được thực hiện
như đã mô tả đối với DB được tạo ra bởi những quy tắc khởi động.
3.4-Tối ưu hóa trong tính tương đương (Optimizing under Equivalence)
Trong ví dụ 3.3.2, ta dã chỉ ra nguyên tố a(Y,W) thừa trong quy tắc đệ
quy của P1. Dùng thuật toán H2 không thể chỉ ra điều này vì a(Y,W) là không
thừa trong tính tương đương đồng dạng. Vấn đề là bằng cách nào để tìm ra một
tgd mà cho thấy sự thừa của a(Y,W). Trong thực tế, tiếp cận thích hợp là dùng
một số Heuristics. tgd g(X,Z)a(X,W) được dùng trong ví dụ 3.3.2 có một
thuộc tính mà dễ dàng chỉ ra: SAT(T) M(P1) M(P2)
(1)
Nhắc lại rằng T gồm có tgd trên và P2 thu được từ P1 bằng cách xóa
a(Y,W). Cụ thể, một áp dụng đơn của T vào thân của quy tắc đệ quy của P2 làm
thân đó đồng nhất với thân của quy tắc đệ quy của P1 và như vậy cho (1)
24
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
Quy tắc được tối ưu hóa trong ví dụ 3.3.2 là:
g(X,Z) g(X,Y) g(Y,Z) a(Y,W)
và tgd đã chọn cũng có thể là g(Y,Z)a(Y,W), nó gồm có những nguyên
tố xuất hiện trong thân của quy tắc trên và có các thuộc tính dưới đây:
1-Vế trái của tgd có cùng vị từ như đầu của quy tắc đang được tối ưu.
2-Nếu tgd có một biến W mà xuất hiện chỉ trong vế phải của nó thì tất cả
những nguyên tố (trong thân của quy tắc) mà chứa W là ở vế phải của tgd.
3-Tất cả những biến của tgd mà chỉ xuất hiện trong vế phải của nó là
không ở đầu của quy tắc.
Một khi một tgd được chọn, bước tiếp theo là kiểm tra liệu những
nguyên tố trong vế phải của tgd là thừa trong thân của quy tắc.
Khi tìm thấy một tgd, vẫn còn phải kiểm tra những điều kiện trong phần
trước. Một vấn đề là nó có thể không dừng. Cách để điều khiển một quá trình
tối ưu hóa mà thực hiện quá chậm đó là sử dụng thời gian tối ưu hóa một quyết
định trước của thời gian. Ví dụ dưới đây minh họa cho ý tưởng trên:
Ví dụ 3.4.1: Xét chương trình dưới đây
g(X,Z) a(X,Z) c(Z)
g(X,Z) a(X,Y) g(Y,Z) g(Y,W) c(W)
Rõ ràng một phần tử tgd để chỉ ra thừa là
g(Y,Z) g(Y,W) c(W)
mà được biểu thị bởi t. Cho P1 là chương trình gốc và cho P2 là chương
trình thu được bằng cách xóa g(Y,W) và c(W) từ thân của quy tắc đệ quy của
P1. Rõ ràng P1 P2. Ta sẽ chỉ ra P2 P1 bằng cách sau:
(1)-SAT(T) M(P1) M(P2)
(2)-P1 duy trì T
(3)-Đối với mọi EDB d, DB cơ sở <d,Pi1(d)> thỏa mãn T
Dễ dàng chỉ ra (1). Ví dụ 3.2.5 đã cho thấy quy tắc đệ quy của chương
trình P1 duy trì T. Vì T có một tgd đơn chỉ có một nguyên tố trong vế trái của
nó. (3’) và quy tắc đệ quy của P1 duy trì T hàm ý (2). Như vậy, cần phải chỉ ra
(3’). Vậy cho g(Y0,Z0) là hiện hành vế trái của tgd t. Hợp nhất nó với đầu của
quy tắc của Pi1 sinh ra DB {a(Y0,Z0), c(Z0)}. Những nguyên tố nền g(Y0,Z0) và
c(Z0) cho thấy t không vi phạm, khi vế trái của nó được thế vào g(Y0,Z0). Như
vậy, tất cả DB cơ sở thỏa mãn t. Vì vậy, ta có thể kết luận rằng những nguyên
tố g(Y,W) và c(W) thừa trong quy tắc đệ quy của P1.
C. KẾT LUẬN
25
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
Tiểu luận đã tìm hiểu một thuật toán để tối ưu hóa những chương trình
Datalog trong tính tương đương đồng dạng. Phép cực tiểu này giảm số lượng
những kết nối cần thiết để tìm tất cả các câu trả lời cho một truy vấn. Tiểu luận
cũng đã tìm hiểu một thuật toán để kiểm tra quan hệ bao hàm đồng dạng và
tương đương đồng dạng của chương trình. Tiểu luận đã tìm hiểu các vấn đề
kiểm định tính bao hàm đồng dạng khi DB thỏa mãn một số ràng buộc được
mô tả như những phụ thuộc sinh bộ. P2SAT(T)P1 hàm ý:
(1)-SAT(T) M(P1) M(P2) (2)-P1 duy trì T.
(1) được kiểm định bởi quá trình gối nhau được mô tả trong phần “Phụ
thuộc sinh bộ”. Quá trình này luôn dừng với câu trả lời đúng nếu chỉ có những
tgd đầy đủ. Nếu có cả những tgd nhúng, thì quá trình gối nhau có thể không
dừng khi (1) không đúng. Với (2), thủ tục được mô tả trong “Duy trì phụ thuộc
sinh bộ” chứng minh nó đúng trong một số trường hợp. Thủ tục đó có thể
không dừng nếu có những tgd nhúng. Một trường hợp mà (2) đúng là khi
những tgd chỉ có những vị từ EDB trên vế trái. Đặc biệt, nếu những tgd biểu
diễn những ràng buộc mà EDB thỏa mãn thì chúng chỉ có những vị từ EDB, khi
đó quá trình gối nhau có thể được dùng để chuyển một chương trình thành một
chương trình tương đương hiệu quả hơn. Tiểu luận đã đưa ra cách sử dụng thủ
tục xác định (1) và (2) để tối ưu hóa chương trình trong tính tương đương. Để
đưa ra kiểu tối ưu hóa này cần một số heuristic.
Một số vấn đề cần được tiếp tục nghiên cứu: Thứ nhất, cần mô tả dặc
điểm các trường hợp mà những thủ tục kiểm tra (1) và (2) bảo đảm dừng. Thứ
hai, biểu thị những trường hợp mà có thuật toán để tìm những tgd để chỉ ra sự
dư thừa khi một số nguyên tố thừa hoặc sự dư thừa có thể được chỉ ra nếu
những thuật toán được tìm thấy, thì nhiều heuristic phải được phát triển để tìm
những tgd mà có thể chỉ ra dư thừa.
Lời kết:
Để hoàn thành được tiểu luận này, ngoài sự nỗ lực và cố gắng của bản
thân, tác giả đã nhận được sự giúp đỡ qúy báu của Quý Thầy TS Trương Công
Tuấn. Là một học viên chuyên ngành Tin học và dù rất tâm đắc với đề tài đang
nghiên cứu nhưng với thời gian có hạn và khối lượng kiến thức của bản thân
còn ít ỏi nên chắc chắn tiểu luận không tránh khỏi những hạn chế trong việc
tiếp cận, nghiên cứu và trình bày. Tôi xin kính trọng cảm ơn sự giúp đỡ quý
báu của Quý Thầy và mong được đón nhận từ Quý Thầy sự góp ý để bản thân
tôi có được hiểu biết đúng hơn đối với vấn đề đang nghiên cứu đồng thời mong
được sự lượng thứ cho những sơ suất trong tiểu luận này.
26
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
PHỤ LỤC
1-Tính đúng đắn của kiểm tra sự bao hàm đồng dạng
Trước hết ta chứng minh hai bổ đề về mối quan hệ giữa tính bao hàm
đồng dạng của hai chương trình và tính bao hàm của những tập mô hình của
chúng.
Cho S là một tập các DB, S có thể là tập bất kỳ và không nhất thiết tập
những DB mà thỏa mãn một số tập T của tgd. Đối với một chương trình P, tập
P(S) gồm có tất cả dữ liệu ra đối với dữ liệu vào trong S, P(S)={P(d) | dS}.
M(P) là tập tất cả các mô hình của P.
Bổ đề 1: P2 S P1 S M(P1) M(P2)
Chứng minh:
Giả sử P2 S P1. Đặt d S M(P1).
Ta chứng minh d P2(d) P1(d) = d là đúng
(1)
Thật vậy:
Vì dữ liệu ra luôn chứa dữ liệu vào của nó nên d P2(d).
Vì P2 S P1 và d S nên P2(d) P1(d).
Vì d M(P1) nên đẳng thức thoa mãn. Vậy (1) cho ta: d M(P2).
Bổ đề 2: P1(S) M(P1) M(P2) P2 S P1
Chứng minh: Giả sử P1(S) M(P1) M(P2), và cho d S là một dữ liệu vào
của P2 (d không nhất thiết là mô hình của P2). Đặt d1=P1(d) và d2=P2(d).
Ta phải chứng minh d2 d1.
Thật vậy:
Vì d1 P1(S) M(P1) kéo theo d1 M(P2).
Vì d2 là mô hình cực tiểu của P2 mà chứa d và d1 cũng là mô hình của P2
mà chứa d. Vì vậy d2 d1,
Hai bổ đề trên dẫn đến hệ quả sau:
Hệ quả 1: Cho P1 là một chương trình và S là một tập các DB sao cho P1(S)S
khí đó: P2 S P1 S M(P1) M(P2)
Chú ý rằng nếu S là tập hợp của tất cả DB thỏa mãn những tgd của một
số T, nghĩa là S=SAT(T) thì P1(S) S nghĩa là P1 duy trì T.
Rõ ràng SAT(T)M(P1)M(P2) nếu và chỉ nếu SAT(T)M(P1)M(r)
đối với mọi quy tắc r của P2, bởi vì một DB là một mô hình của P2 nếu và chỉ
nếu nó là một mô hình của mỗi quy tắc r của P2. Quá trình gối nhau, được mô
tả trong phần “Phụ thuộc sinh bộ”, kiểm tra SAT(T) M(P1) M(r) và định lý
dưới đây chứng minh tính đúng đắn của nó. Để thực hiện quá trình này, thân
27
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
của r phải được xem như là một DB, và điều này được thực hiện bằng cách thế
những biến của r với những hằng phân biệt mà chưa có trong r hoặc P, theo
một số phép thế . Áp dụng kết hợp của một chương trình P và một tập các tgd
của T, được biểu thị bởi [P,T]
Định lý 1: Cho r là quy tắc hb, và cho là một ánh xạ một-một của các biến
của r vào các hằng mà chưa xuất hiện trong r hoặc P. Khi đó: h[P,T](b)
SAT(T)M(P)M(r)
Chứng minh: Ý tưởng:
Thứ nhất ta giả sử rằng SAT(T)M(P) M(r) và sẽ chỉ ra rằng
h[P,T](b). Vì thế, xem xét những DB b và [P,T](b). Rõ ràng,
[P,T](b)SAT(T)M(P), vì [P,T](b) được định nghĩa là DB thu được từ b
bằng cách áp dụng những quy tắc của P và các tgd của T cho đến khi không có
quy tắc hoặc tgd có thể được áp dụng thêm nữa. Vì vậy [P,T](b) M(r), bởi
vì ta giả sử SAT(T) M(P) M(r).
Bây giờ ta sẽ chỉ ra rằng [P,T](b) M(r) hàm ý h [P,T](b). Theo
định nghĩa, DB [P,T](b) chứa b. Nếu ta áp dụng r vào b, rõ ràng hr(b),
vì khi thân của r được thế theo , nó trở thành b và vì vậy h là thuộc dữ liệu
ra. Nhưng [P,T](b) được giả sử là một mô hình của r, vì vậy áp dụng r vào
[P,T](b) không thể sinh ra nguyên tố mới nào. Vì vậy h [P,T](b), vì áp
dụng r vào b sinh ra h.
Ta sẽ chứng minh chiều ngược lại. Giả sử h [P,T](b), ta sẽ chỉ ra
SAT(T) M(P) M(r). Vậy, cho d là DB bất kỳ trong SAT(T)M(P). Ta
phải chỉ ra d M(r).
Theo trực quan, chứng minh bằng cách chỉ ra rằng bất kỳ sự áp dụng nào
của r vào d cũng có thể được mô phỏng bởi một chuỗi của những áp dụng của
[P,T], và vì việc áp dụng [T,P] vào d không sinh ra nguyên tố mới, vậy thực
hiện áp dụng của r. Ta xét một phép thế tùy ý q mà thay thế thân của r thành
những nguyên tố nền của d. Để hoàn thành chứng minh, ta phải chỉ ra hq cũng
thuộc d. Nhưng h [P,T](b) và vì vậy có một chuỗi các phép thế 1, 2,...,
n mà chỉ ra h [P,T](b), đó là, đối với mỗi i có một quy tắc của P hoặc
một tgd của T, sao cho khi quy tắc hoặc tgd được thế theo i, một nguyên tố
mới được sinh ra, và sự áp dụng cuối cùng (đối với n) sinh ra h. Như vậy, nó
kéo theo rằng q-11,..., q-1n là một chuỗi phép thế mà [P,T](d) chứa
hq. Nhưng d SAT(T) M(P) hàm ý d= [P,T](d) và vì vậy hq thuộc d
28
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
Nếu quy tắc r có thân rỗng (nên đầu của nó là một nguyên tố nền), thì
dịnh lý 1 hàm ý SAT(T) M(P) M(r) nếu và chỉ nếu r là một quy tắc của P.
Chú ý, nếu T có các tgd nhúng, thì DB [P,T](b) có thể là vô hạn, vì vậy không
có giới hạn trên thời gian để chỉ ra [P,T](b) chứa h (Mặc dù h sẽ được tìm
ra trong một thời gian hữu hạn nếu nó là thực sự thuộc [P,T](b)). Hơn nữa,
nếu [P,T](b) không chứa h, thì có thể không xác định được sự kiện này chỉ
bằng tính toán [P,T](b), vì sự tính toán có thể là vô hạn. Chú ý, nếu [P,T](b)
không chứa h, thì có thể là chỉ những DB d là vô hạn sao cho
dSAT(T)M(P) và dM(r). Nói cách khác, nếu T gồm có những tgd nhúng,
thì chiều trong định lý 1 được cho là đúng mà tập tất cả các DB có thể bao
gồm cả DB hữu hạn và vô hạn. Rõ ràng, nếu không có tgd nào thì ta có hệ quả
quan trọng dưới đây cho định lý 1. Hệ quả này là đúng khi chỉ những DB hữu
hạn được xem xét, và nó cho thấy sự đúng đắn của thuật toán để kiểm định
quan hệ bao hàm đồng dạng. Thuật toán này luôn luôn dừng.
Hệ quả 2: Cho r là một quy tắc với đầu là h và thân là b, và cho là một ánh
xạ một-một của các biến vào các hằng mà chưa xuất hiện trong r hoặc P. Khi
đó h P(b) M(P) M(r)
2. Tính đúng đắn của kiểm tra sự duy trì không đệ quy của những tgd
Thủ tục được mô tả trong “Duy trì phụ thuộc sinh bộ” để kiểm tra liệu
một chương trình P duy trì không đệ quy một tập T các tgd cũng dựa trên sự
gối nhau. Có thể nói rằng nếu thủ tục hoặc xác định P không duy trì không đệ
quy một số t T hoặc không dừng, thì nó xây dựng một DB d sao cho d thỏa
mãn T và <d,Pn(d)> vi phạm t. Chú ý, thủ tục có thể không dừng chỉ nếu T có
những tgd nhúng, và trong trường hợp này ví dụ phản chứng d là vô hạn. Nếu
thủ tục xác định P duy trì T không đệ quy, thì nó thực hiện bằng cách xây dựng
đối với mỗi khả năng vi phạm của một số t T, một DB hợp với quy tắc tiêu
chuẩn trong đó không tồn tại vi phạm, và DB hợp với quy tắc tiêu chuẩn đó có
thể được ánh xạ đồng cấu vào bất kỳ DB khác mà có thể biểu hiện một số vi
phạm. Như vậy, có thể không vi phạm.
3. Tính đúng đắn của thuật toán để cực tiểu hóa chương trình
Định lý 2: Thuật toán để cực tiểu những chương trình trong dạng tương đương
đồng dạng là đúng
Chứng minh: Ta phải chỉ ra rằng không có nguyên tố hoặc quy tắc đã được xem
xét nhiều hơn một lần. Vậy, cho P là chương trình cuối cùng được sinh ra bởi
thuật toán. Ta phải chỉ ra rằng P không có nguyên tố và quy tắc thừa. Trước
hết ta chỉ ra P không có quy tắc thừa.
29
TiÓu luËn kÕt thóc m«n häc: Ch-¬ng tr×nh Datalog
Giả sử rằng một số quy tắc r thừa trong P. Gọi P là chương trình tại thời
điểm bắt đầu của quá trình lặp trong đó quy tắc r được xem xét để xóa bỏ. Đặt
P’ và P’ là chương trình tương ứng P và P khi r bị xóa. Rõ ràng, P và P là
tương đương đồng dạng, vì thuật toán xóa trong khi vẫn duy trì tính tương
đương đồng dạng. Vì r chưa được xóa một cách vĩnh cửu, r P’. Đặt h và b là
đầu và thân tương ứng của quy tắc r, và đặt là ánh xạ một-một của các biến
của r vào các hằng chưa có trong r hoặc P. Ta có hP’(b), vì r P’, và ta
cũng có h P’(b), vì r là thừa trong P. Nhưng nó mâu thuẫn với P’(b)
P’(b) (Vì mọi quy tắc của P’ cũng là một quy tắc của P’. Ta đã xóa những
nguyên tố thừa trước khi xóa những quy tắc thừa, vì vậy một quy tắc xuất hiện
trong P có chính xác cùng một thân cũng ở trong P; Nếu một số quy tắc đã
xuất hiện trong P với một số nguyên tố đã xóa từ thân của nó được so sánh với
P, nó sẽ không thể suy ra P’(b) P’(b)). Như vậy, ta đã chỉ ra rằng P
không có quy tắc thừa.
Tiếp theo ta chỉ ra P không có nguyên tố thừa. Giả sử một số quy tắc r
của P có một nguyên tố thừa trong thân của nó. Gọi P là chương trình tại
thời điểm bắt đầu của quá trình lặp trong đó được xem xét để xóa. Đặt h là
đầu của quy tắc r, đặt b và b là thân của nó trong P và P (mọi nguyên tố của
b cũng là của b). Thân của b’ và của b’ thu được từ b và b bằng cách xóa đi
. Đặt là một ánh xạ một-một của tất cả các biến của r vào các hằng mà chưa
có trong r hoặc P. Vì chưa bị xóa vĩnh cửu, h P(b’). Vì thừa trong P,
kéo theo h P(b’), vì b’ b’, và chương trình Datalog là đơn điệu, đó
là thêm nhiều nguyên tố vào dữ liệu vào mà không xóa bất kỳ nguyên tố nào
của dữ liệu ra. Như vậy ta cũng đã chỉ ra rằng P không chứa nguyên tố thừa.
30
Tải về để xem bản đầy đủ
32 trang
20/07/2025
860
Bạn đang xem 30 trang mẫu của tài liệu "Tiểu luận Chương trình Datalog", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- tieu_luan_chuong_trinh_datalog.doc
