Tiểu luận 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 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 q là vị từ xây dựng trong thì ta viết XqY thay cho q(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 -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. p q1 q2 ...qn 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 Đị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: -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ì 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 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. 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 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() 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 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 và IDB thì đầu ra được tính bởi P được biểu diễn là P() 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 thì P2() Í P1() (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() là một tập con của quan hệ đối với q trong DB P1() Đị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 P2ºP1 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 P2ͲP1 nếu đối với tất cả các cặp của một EDB và một IDB ta có: P2() Í P1() Đị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 đượ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() Í P1() đối với tất cả và khi đó xét trường hợp riêng đối với EDB ta có: P2(), trong đó ặ biểu thị quan hệ rỗng. Vì vậy: P2() Í P1() đối với tất cả các EDB . 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 là một mô hình của P nếu: = P(). 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 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 , các chương trình có cùng một mô hình cực tiểu mà chứa . 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 đượ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(bq) chứa nguyên tố nền hq, trong đó: +q 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 +bq là tập hợp các nguyên tố nền thu được từ b bằng cách thế theo q +hq là nguyên tố nền thu được từ h bằng cách thế theo q 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: 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 r1ͲP1 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 đó r2ͲP1. 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. (1) Ta sẽ chỉ ra rằng P2 Ͳ P1. 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 P1ºP2. 2.2-Cực tiểu hóa chương trình trong tính tương đương đồng dạng 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 a 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 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ố a 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 a 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 n