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

doc31 trang | Chia sẻ: lvcdongnoi | Ngày: 02/07/2013 | Lượt xem: 1906 | Lượt tải: 2download
Bạn đang xem nội dung tài liệu Tiểu luận Chương trình Datalog, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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

Các file đính kèm theo tài liệu này:

  • docDownload- Tiểu luận cao học- Chương trình Datalog.doc
Luận văn liên quan