Tiểu luận Tìm hiểu 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 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ố a trong thân, và một số biến trong đầu của r xuất hiện chỉ trong thân a 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 a không thể thừa. 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 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 Ͳ 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 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’[Y1(x’)đY2(x’,y’)] trong đó x’ và y’ là những vectơ của các biến và Y1, Y2 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 q 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 q 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 q 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. 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 P2ͲsP1, nếu P2(d) Í P1(d) đối với mọi DB dẻS. 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ố a 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ì a là thừa trong P1, dù nó không thừa trong tính tương đương đồng dạng. Để chỉ ra P2ͲSAT(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 P2ͲSAT(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) 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à d1,...,di,... Một tgd t được áp dụng vào một DB như sau: Giả sử rằng q là một phép thế của những biến lượng từ phổ biến của t, sao cho q chỉ ra rẳng DB không vi phạm t. Đó là, q 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 q 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 di duy nhất (không có trong DB) và mở rộng q 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,d23) và g(d23,2) (tất nhiên DB đó không chứa d23 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,d23) và g(d23,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 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,d1) đượ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,d2) 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,d1), 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 ý P2ÍP1. 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 P2ͲSAT(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 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à {hq | đối với một số quy tắc h ơ b của P và phép thế q, những nguyên tố của bq 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à ẻ SAT(T) đối với mọi d ẻ SAT(T) ( 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 vi phạm t. DB 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 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 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ụ 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,d1), và áp dụng nó vào g(Y0,Z0) thu được a(Y0,d2). 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,d1), a(Y0,d2) Trong số chúng có a(X0,d1) 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ụ 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 a thuộc Pn(d), ta phải thêm vào d một số nguyên tố mà sinh ra a 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 a. 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 a. 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 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 a 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 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 . 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 . 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 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ả tẻT 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 -Chọn a, t ẻ T -Cho q á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 q -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 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 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 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 nếu: (1)- t thoả mãn trong khi vế trái được giới hạn thuộc Pn(d) và (2)- t thỏa mãn trong 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 Pn1 vào d, ta thu được Pn1(d) là {g(X0,Z0)}. Vì a(X0,Z0) thuộc , t không xuất hiện vi phạm, vì vậy P1 duy trì T. 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,d1) được thêm vào d. Nguyên tố a(Y0,d1) của d cho thấy không xuất hiện vi phạm của t trong đố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,d1) vào d, và nguyên tố nền này chỉ ra rằng t không vi phạm trong 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,d1) được thêm vào d. Nguyên tố a(Y0,d1) chỉ ra rằng t không vi phạm trong đố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 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 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ừ P2ͲSAT(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à 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: 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ở, , 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 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 , 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. 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ở 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à dÍd’) và giả sử rằng d’ thỏa mãn T. Vì P2ͲSAT(T)P1 và d’ thỏa mãn T, kéo theo P2(d’) Í P1(d’). (A) Vì chương trình Datalog là đơn điệu, nên: P2(d) Í P1(d). (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’) (C) Từ (A), (B) và (C) suy ra P2(d) Í P1(d). 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) 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ở 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 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ộ. P2ͲSAT(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. 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) | dẻS}. 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 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ế q. á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 hơb, và cho q 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 đó: hqẻ[P,T](bq) Û 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 hqẻ[P,T](bq). Vì thế, xem xét những DB bq và [P,T](bq). Rõ ràng, [P,T](bq)ẻSAT(T)ầM(P), vì [P,T](bq) được định nghĩa là DB thu được từ bq 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](bq) ẻ 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](bq) ẻ M(r) hàm ý hq ẻ [P,T](bq). Theo định nghĩa, DB [P,T](bq) chứa bq. Nếu ta áp dụng r vào bq, rõ ràng hqẻr(bq), vì khi thân của r được thế theo q, nó trở thành bq và vì vậy hq là thuộc dữ liệu ra. Nhưng [P,T](bq) được giả sử là một mô hình của r, vì vậy áp dụng r vào [P,T](bq) không thể sinh ra nguyên tố mới nào. Vì vậy hq ẻ [P,T](bq), vì áp dụng r vào bq sinh ra hq. Ta sẽ chứng minh chiều ngược lại. Giả sử hq ẻ [P,T](bq), 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 hq ẻ [P,T](bq) và vì vậy có một chuỗi các phép thế j1, j2,..., jn mà chỉ ra hq ẻ [P,T](bq), đó 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 ji, một nguyên tố mới được sinh ra, và sự áp dụng cuối cùng (đối với jn) sinh ra hq. Như vậy, nó kéo theo rằng qoq-1oj1,..., qoq-1ojn 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 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](bq) 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](bq) chứa hq (Mặc dù hq 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](bq)). Hơn nữa, nếu [P,T](bq) không chứa hq, thì có thể không xác định được sự kiện này chỉ bằng tính toán [P,T](bq), vì sự tính toán có thể là vô hạn. Chú ý, nếu [P,T](bq) không chứa hq, thì có thể là chỉ những DB d là vô hạn sao cho dẻSAT(T)ầM(P) và dẽM(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 q 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 đó hq ẻ P(bq) Û 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à 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. 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 q 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ó hqẽP’(bq), vì r Ú² P’, và ta cũng có hq ẻ P’Ư(bq), vì r là thừa trong PƯ. Nhưng nó mâu thuẫn với P’Ư(bq) Í P’(bq) (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’Ư(bq) Í P’(bq)). 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ố a 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 đó a đượ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 a. Đặt q 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ì a chưa bị xóa vĩnh cửu, hq ẽ P(b’q). Vì a thừa trong PƯ, kéo theo hq ẻ PƯ(b’Ưq), vì b’Ưq Í b’q, 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. Tài liệu tham khảo 1- Trương Công Tuấn-Bài giảng chương trình Datalog-2005 2- Yehoshua Sagiv-Optimizing Datalog Programs. 3- Jeffrey D. Ullman, Trần Đức Quang (dịch)-Nguyên lý các hệ cơ sở dữ liệu và cơ sở tri thức, Tập 1-NXB TK-1998 4- S.Ceri G. Gottlob L. Tanca-Logic Programming and Databases-1989 Mục lục Nội dung Trang Giới thiệu ..................................................................................................................................................... 1 Nội dung ....................................................................................................................................................... 2 I-Kiến thức cơ sở............................................................................................................................... 2 1.1 Những khái niệm về chương trình Datalog............................................. 2 1.2 Sự tính toán của chương trình................................................................................. 3 1.3 Tính tương đương, tương đương đồng dạng và những mô hình. 5 II-Tối ưu hóa chương trình trong tính tương đương đồng dạng................. 7 2.1 Kiểm tra tính bao hàm đồng dạng và tương đương đồng dạng...... 8 2.2 Cực tiểu hóa chương trình trong tính tương đương đồng dạng....... 9 III-Tối ưu hóa chương trình đệ quy trong tính tương đương......................... 11 3.1 Phụ thuộc sinh bộ.............................................................................................................................. 11 3.2 Duy trì phụ thuộc sinh bộ......................................................................................................... 15 3.3 Xác định tính tương đương...................................................................................................... 21 3.4 Tối ưu hóa trong tính tương đương................................................................................ 23 Kết luận...................................................................................................................................................................... 25 Phụ lục......................................................................................................................................................................... 26 Tài liệu tham khảo......................................................................................................................................... 30