뗚 3 1 뻭 뗚15웚볆 쯣 믺 릤 돌 2005쓪8퓂 V o l. 3 1 1 5 Computer Engineering August 2005 믹 뷰 쿮 쒿 싛컄 컄헂뇠뫅10003428(2005)19005903컄쿗뇪쪶싫A 뮶믡 훐춼럖샠뫅TP311 탅쾢췸룱뗄탩쓢쫓춼캬뮤 뷰 펭1랮붨욽2 (1.훐맺뿆톧풺볆쯣벼쫵퇐뺿쯹죭볾퇐뺿쫒놱뺩 1000802.훐맺뿆톧풺볆쯣벼쫵퇐뺿쯹놱뺩100080) 햪 튪퓚탅쾢췸룱풴뗄닣듎쒣탍[2]훐탩쓢쫓춼닣횱뷓랴펳탐튵폃뮧뗄풴럃컊탨쟳탩쓢쫓춼닣떽싟벭풴닣펳짤뗄헽좷탔쫇쪹폃탩쓢쫓춼뷸탐탅쾢췸룱풴럃컊뗄믹뒡튵컱싟벭뗄뇤뮯뿉쓜틽웰싟벭풴닣풪쫽뻝뗄뇤뮯떼훂탩쓢쫓춼떽싟벭풴뗄펳짤쪧킧폃뮧쪹폃탩쓢쫓춼컞램뗃떽풤웚뗄뷡맻룃컄쳖싛쇋싟벭풴닣풪쫽뻝랢짺뇤뮯뗄룷훖쟩뿶늢쳡돶쇋쿠펦뗄탩쓢쫓춼뗷헻랽램틔캬뮤탩쓢쫓춼닣풪쫽뻝뗄폐킧탔 맘볼듊탅쾢췸룱탩쓢쫓춼캬뮤펳짤 Virtual View Maintenance of Information Grid JIN Ying1, FAN Jianping2 ( Division, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080; of Computing Technology, Chinese Academy of Sciences, Beijing 100080) Abstract In the layered resource space model of information grid, the virtual view layer directly reflects industrial users’ request of resource access. To access resources using virtual views, users must guarantee the validity of mappings between the metadata of virtual view layer and logical resource layer. Unfortunately, evolution of the metadata of logical resource layer may invalidate such mappings, and users can not get expected results by using virtual views. This paper discusses different types of the resource layer changes. Then it proposes adapting algorithms to preservethe affected virtual views. Key wordsInformation grid; Virtual view maintenance; Mapping 탅쾢췸룱샻폃췸룱벼쫵쪵쿖탅쾢뗄릲쿭맜샭뫍쳡릩탅훂탩쓢쫓춼뚨틥쪧킧뗄뢴퓓뇤뮯늢틔쫓춼뫏램탔뫍뷡맻벯쾢럾컱훷튪뷢뻶럖늼뗄틬릹뗄탅쾢풴횮볤뮥솪뫍뮥닙ퟷ헽좷탔캪쒿뇪쳡돶쇋헫뛔룷훖뇤뮯뗄뗷헻쯣램 컊쳢틔싺ퟣ웳튵헾뢮늿쏅뗈ퟩ횯탅쾢릲쿭뗄탨쟳캪룼1탅쾢췸룱풴뿕볤쒣탍 뫃뗘횧돖췸룱펦폃뛔풴럃컊뗄춸쏷탔쒿뇪탅쾢췸룱퇐뺿탅쾢풴뿕볤쒣탍내탅쾢풴뗄컯샭쳘헷싟벭쳘헷헟퓚맘쾵쫽뻝뿢돩쿳닣듎뫍횯얮탇췸룱풴뿕볤쒣탍[1]뗄샭폃뮧쪹폃쳘탔붫탅쾢풴뿕볤럖캪컯샭풴닣싟벭풴닣싛믹뒡짏뛔탅쾢풴내웤컯샭쳘헷싟벭쳘헷폃뮧쪹폃뫍탩쓢쫓춼닣[2]죧춼1쯹쪾 쳘탔뗈뷸탐쇋늻춬닣듎뗄돩쿳붫풴뿕볤럖캪컯샭풴닣 싟벭풴닣뫍탩쓢쫓춼닣릹붨쇋뻟폐닣듎뷡릹뗄탅쾢풴 탩쓢쫓춼닣뿕볤쒣탍탩쓢쫓춼닣캻폚탅쾢풴뿕볤ퟮ짏닣붨솢퓚싟 벭풴닣횮짏췸룱풴뗄폃뮧춨맽뛔싟벭풴닣뗄뛔쿳뷸 싟벭탐ퟩ뫏즸톡퓋쯣탎돉탩쓢쫓춼닣튵컱싟벭뇤뮯틽웰뗄 풴닣싟벭닣풪쫽뻝뇤뮯뿉쓜믡쪹뗃탩쓢풴닣떽싟벭풴닣뗄펳 짤쪧킧듓뛸떼훂쪹폃탩쓢쫓춼뗄탅쾢럃컊컞램뷸탐틲듋 듦 뒢쾵 춳 1듦뒢쾵 춳 2듦뒢쾵춳n 탅쾢췸룱퓚뚨틥쇋헽좷폐킧뗄탩쓢쫓춼닣풪쫽뻝횮뫳뮹뇘컯샭풴닣 탫룹뻝싟벭풴닣뇤뮯뷸탐쿠펦뗄뗷헻돆탩쓢쫓춼뗄캬뮤 탩쓢쫓춼탩쓢쫓춼뛔튵컱뛔쿳뫍탩 쓢쫓춼뗄틽폃헫뛔뗗닣탅쾢풴쓜솦뇤뮯떼훂뗄쫓춼뚨틥뗷헻컊쳢 튵컱뛔쿳튵컱뛔쿳볤맘솪 Amy Nica뗈퓚EVEEvolvable – View - 쫽뻝쪵쳥벯튵컱뛔쿳떽쫽뻝벯뗄펳짤 맘쾵Environment쾵춳훐쳡돶쇋쫓춼춬늽View Synchronization 뗄룅쓮[3]쪹폃튻훖삩햹뗄SQL폯퇔뷸탐쫓춼뚨틥쳡돶쇋춼1 탅쾢췸룱풴돩쿳닣듎벰펳짤맘쾵 헫뛔룷훖샠탍뇤뮯뗄쫓춼뗷헻쯣램탅쾢췸룱싟벭풴닣평폚좱랦EVE쾵춳뗄탅쾢풴쏨쫶훐뗄폯틥풼쫸믹폚폯틥풼쫸믹뷰쿮쒿맺볒뷜돶쟠쓪뿆톧믹뷰훺쿮쒿69925205맺볒863뗄쳦뮻닟싔쓑틔쪩탐춬쪱EVE쾵춳훷튪맘힢떥룶맘쾵뗄볆뮮믹뷰훺쿮쒿2002AA104310훐맺뿆톧풺몣췢뷜돶쟠쓪톧뇤뮯뫶싔쇋짦벰뛠룶맘쾵뗄뢴퓓뇤뮯쟩뿶뗄뒦샭뛸듓풪헟믹뷰훺쿮쒿20014010횣훝쳺슷뻖2003뿆톧벼쫵랢햹볆뮮믹뷰훺쿮쒿03s08 쫽뻝캬뮤뗄뷇뛈뾴헢킩뢴퓓뇤뮯늢늻뗈춬폚볲떥뇤뮯뗄쮳ퟷ헟볲뷩뷰 펭(1976—)얮쮶쪿짺훷퇐랽쿲쫽뻝벯돉뫍탅탲랢짺 쾢췸룱랮붨욽퇐뺿풱늩떼 뛔EVE쾵춳쳡돶뗄뇤뮯샠탍뷸탐쇋삩돤퓶볓쇋뿉쓜떼뚨룥죕웚2004-06-27 E-mailjinying@ 59
탅쾢췸룱컯샭닣붨쒣뗄훷튪뛔쿳쫇췸룱훐닺짺놣듦뫍쫴탔뗄탂튵컱뛔쿳CC뻟폐A뫍B훐쯹폐뗄럇훷쫴탔튵맜샭탅쾢뗄듦뒢쾵춳죧쫽뻝뿢맜샭쾵춳펦폃쾵춳컄볾컱뛔쿳A뫍B놻즾돽 쾵춳Web햾뗣틔벰듦뒢쾵춳훐쳡릩탅쾢뗄룷훖쫽뻝쪵쳥뗄C(K*, a, b) = {k,x,y|<k,x>∈A∨<k,y>∈B} 벯뫏 (8)튵컱뛔쿳닰럖 탅쾢췸룱퓚컯샭닣뗄믹뒡짏돩쿳돶싟벭풴닣내헕튵Decompose C(K*, a, b) 컱쇬폲뗄맦랶뫍탨튪뛔쫽뻝쪵쳥뗄싟벭쳘헷뫍늻춬쫽뻝쪵쳥Into A(K*, a), B(K*, b) 볤뗄싟벭맘쾵뷸탐돩쿳쫽뻝쪵쳥퓚싟벭닣뗄돩쿳탎쪽돆캪냑튵컱뛔쿳C닰럖돉탂튵컱뛔쿳A뫍BA뫍B뻟폐폫튵컱뛔쿳C쿠춬뗄훷쫴탔럖뇰놣쇴쇋C뗄튻늿럖럇훷쫴탔튵컱뛔 뛔폚쳘뚨폃뮧뛸퇔쯻쏇횻맘탄헻룶췸룱탅쾢훐뗄튻늿쿳C놻즾돽 럖쓚죝늢쟒듳뛠쫽쟩뿶쿂쯻쏇룼맘탄뺭맽ퟩ뫏볓릤뗄쓚죝A(K*, a) ={k,x|∃y,<k,x,y>∈C} 틲듋싟벭닣뗄쓚죝뛔폚쯻쏇뛸퇔죔좻쿔뗃뢴퓓뛸쎻폐헫뛔B(K*, b) ={k,y|∃x,<k,x,y>∈C} 탔탅쾢췸룱탩쓢쫓춼닣뗄탎돉헽쫇캪쇋뷢뻶헢튻컊쳢캪C(K*, a, b) ={k,x,y|<k,x>∈A∧<k,y>∈B} ퟮ훕폃뮧쳡릩룼캪폐킧뗄ퟩ뫏탅쾢(9)튵컱뛔쿳죚뫏 춨맽뛔튵컱뛔쿳뗄틽폃탩쓢쫓춼뫍싟벭풴풪쫽뻝볤Merge A(K*, a), B(K*, a) 듦퓚ퟅ떥쿲뗄펳짤맘쾵ퟷ캪놻틽폃뗄뛔쿳싟벭풴닣뗄Into C(K*, a) 뇤뮯뿉쓜믡펰쿬떽헢훖펳짤뗄폐킧탔뷸뛸펰쿬떽탅쾢췸룱뻟폐쿠춬쫴탔뗄튵컱뛔쿳A뫍B죚뫏돉춬퇹뷡릹뗄튵컱풴뗄럃컊뛔쿳CC냼몬A뫍B훐쯹폐풪ퟩ튵컱뛔쿳A뫍B놻즾돽 C(K*, a) = {k,x|<k,x>∈A∨<k,x>∈B} 2탩쓢쫓춼캬뮤 (10)튵컱뛔쿳럖뛎 캪샭뷢탩쓢쫓춼뗄캬뮤컒쏇쫗쿈쳖싛틽웰탩쓢쫓춼캬뮤뗄풭틲벴싟벭풴닣뗄뇤뮯샠탍좻뫳헫뛔헢킩뇤뮯샠Partition C(K*, a) 탍쳡돶뗷헻쯣램Into A(K*, a): a=’value1’; Else B(K*, a); 싟벭풴닣풪쫽뻝뗄뇤뮯 냑튵컱뛔쿳C럖돉솽룶춬퇹뷡릹뗄튵컱뛔쿳A뫍BA싟벭풴닣뚨틥캪튻ퟩ튵컱뛔쿳뗄벯뫏컒쏇쪹폃볇뫅훐냼몬C훐풭폐뗄럻뫏쳵볾a=’value1’뗄풪ퟩB훐냼몬웤R***(k1,k2,L,kn,f1,f2,L,fm)뇭쪾튵컱뛔쿳R웤훐쯻풪ퟩ튵컱뛔쿳C놻즾돽 k***1,k2,L,k쫇훷쫴탔n>0nf1,f2,L,f캪럇훷쫴탔m >= mA(K*, a) = {k,x|<k,x>∈C∧x='vlaue1'} 0볲볇캪RK*, F퓚탩쓢쫓춼뗄뚨틥훐쪹폃떽뗄싟벭B(K*, a) = {k,x|<k,x>∈C∧¬(x='value1')} 풴닣풪쫽뻝냼삨튵컱뛔쿳뗄쏻돆뫍튵컱뛔쿳뗄쫴탔쏻돆C(K*, a) = {k,x|<k,x>∈A∨<k,x>∈B} 쫗쿈쇐돶싟벭풴닣뗄볲떥뇤뮯샠탍(11)럇훷쫴탔틆뚯 Move a (1)튵컱뛔쿳즾돽 Delete_Obj AFrom A(K*, a) 즾돽쏻캪A뗄튵컱뛔쿳To B(K*, b) 럇훷쫴탔틆뚯쎻폐뒴붨탂뗄튵컱뛔쿳뛸쫇냑A(K*, a)(2)튵컱뛔쿳퓶볓 Add_Obj A(K*, F)뇤돉쇋A’(K*)B(K*,b)뇤돉쇋B’(K*, b, a) 퓶볓튵컱뛔쿳A(K*, F)A’(K*) = {k|<k>∈A} B’(K*, b, a) = (3)럇훷쫴탔즾돽 {k,y,x|<k,y>∈B∧((∃z,<k,z>∈A)→(z=x))}Delete_Attr a From A 듓튵컱뛔쿳A훐즾돽럇훷쫴탔(12)럇훷쫴탔ퟩ뫏 a Compose (4)럇훷쫴탔퓶볓 From , Add_Attr a Into A 튵컱뛔쿳A퓶볓튻룶쫴탔With = f(, ) a 튵컱뛔쿳A훐뗄쫴탔a1뫍a2춨맽몯쫽f뗃떽탂쫴탔a3(5)튵컱뛔쿳룼쏻 뻉쫴탔뫍놻즾돽 Rename_obj A As B 붫쏻캪A뗄튵컱뛔쿳룼쏻캪A’(K*,a3)={k,x|∃y,z,<k,y,z>∈A∧x=f(y,z)} B (13)럇훷쫴탔닰럖 (6)쫴탔룼쏻 Decompose Rename_Attr a1 In A As a2 붫쏻캪A 뗄튵컱뛔쿳훐뗄쫴탔Into , a1룼쏻캪a2 헢킩뚼쫇퓚튻룶튵컱뛔쿳뚨틥쓚뗄뇤뮯싟벭풴닣풪With = f(, ) 쫽뻝뗄뗷헻늢늻뻖쿞폚떥룶튵컱뛔쿳쓚뢴퓓뗄뗷헻뿉쓜믡튵컱뛔쿳A뗄쫴탔a1놻닰럖돉솽룶탂쫴탔a2뫍a3닰짦벰떽뛠룶튵컱뛔쿳틲듋폖퓶볓쇋짦벰떽뛠룶튵컱뛔쿳럖뗃떽뗄쫴탔횵싺ퟣf(a2, a3) = a1쫴탔a1놻즾돽 뗄뇤뮯샠탍A(K*,a1)={k,x|∃y,z,<k,y,z>∈A'∧x=f(y,z)} 탩쓢쫓춼뗷헻 (7)튵컱뛔쿳ퟩ뫏 펰쿬쫓춼뚨틥뗄싟벭풴닣뇤뮯쫇탩쓢쫓춼뗷헻맘힢뗄Compose C(K*, a, b) 붹뗣뿉틔뛔쫜떽펰쿬뗄쫓춼뷸탐뗷헻놣돖뇤뮯잰뫳쫓춼From A(K*, a), B(K*,b) 튵컱뛔쿳A뫍B폐쿠춬뗄훷쫴탔ퟩ뫏돉캪뻟폐춬퇹훷뷡릹뗄컈뚨 60
컒쏇쳖싛SPJ뷡릹뗄쫓춼뚨틥쪹폃뇭쪾쫓춼 if(A in ) { v쪹폃뗄튵컱뛔쿳벯뫏뇭쪾튵컱뛔쿳쫴탔춶펰뗄 = - {A}{B}; 쇐뇭뇭쪾쫓춼쪹폃뗄톡퓱쳵볾 for (훐뗄쎿룶쫴탔) 쇭췢평폚튵컱뛔쿳퓶볓뫍럇훷쫴탔퓶볓뗄뇤뮯쟩뿶늻 if (R == A) 붫쳦뮻돉; 펰쿬탩쓢쫓춼닣퓚듋늻ퟶ쳖싛튵컱뛔쿳즾돽럇훷쫴탔즾돽뫍럇훷쫴탔ퟩ뫏뇤뮯쟩뿶쿂쫜펰쿬뗄탩쓢쫓춼컞램듯 for (훐뗄쎿룶쫴탔) 떽뗷헻잰뫳쫓춼뷡릹컈뚨뗄튪쟳튲늻퓚쯣램훐뒦샭 if (R == A) 붫쳦뮻돉; } 뛔탩쓢쫓춼닣훐뗄쎿룶쫓춼v쾵춳룹뻝탨튪뒦샭뗄늻 return v; //략믘쳦뮻뗷헻뫳뗄쫓춼 } 춬뇤뮯쟩뿶뷸탐쿠펦뗄뒦샭function replace_attr(A, a, B, b) {/*붫튵컱뛔쿳A뗄쫴탔a쳦뮻캪 튵컱뛔쿳B뗄쫴탔b*/ rename_obj(A, B) {/*튵컱뛔쿳A룼쏻캪B*/ result = false; replace_obj(A, B); //뗷폃튵컱뛔쿳쳦뮻몯쫽 } rename_attr(A, a1, a2) {/*튵컱뛔쿳A뗄쫴탔 if (A in ){ a1룼쏻캪a2*/ for (훐뗄쎿룶쫴탔) { replace_attr(A, a1, A, a2); //뗷폃쫴탔쳦뮻몯쫽 } if ((R==A) AND (attr==a)){ decompose_obj(C, k, A, a, B, b) {/*튵컱뛔쿳C럖뷢캪뻟폐쿠춬훷쫴탔k뗄튵컱뛔쿳A뫍붫쳦뮻돉; B*/ result = true; } if (C in ) { } replace_attr(C, a, A, a); for (훐뗄쎿룶쫴탔){ replace_attr(C, k, A, k); if ((R==A) AND (attr==a)){ replace_attr(C, b, B, b);//쳦뮻v틽폃뗄C뗄쫴탔 붫쳦뮻돉; = - {C} {A, B}; //뗷헻쫓춼틽폃뗄튵컱뛔쿳벯뫏result = true; } } = + “ AND = ”; } } } return result; //략믘횵횸쪾쫇럱폐쫴탔쳦뮻랢짺 } partition_obj(C, A, B) {/*튵컱뛔쿳C럖뛎*/ 듓짏쏦뗄쯣램쏨쫶훐뿉틔뾴떽쯣램뛔폚쫓춼v뗄춶펰 if (C in ) { 쫴탔쇐뇭훐뗄쫴탔쯹폐닙ퟷ뚼쫇쳦뮻뒦샭쎻폐즾돽믲헟퓶 temp = v; v1 = replace_obj(C, A); 볓뗄닙ퟷ틲뛸뿉틔놣횤뗷헻잰뫳쫓춼뷡릹뗄컈뚨탔떫쫇 v = temp; v1 = replace_obj(C, B); 듋쯣램늢늻쓜놣횤퓚쎿훖뇤뮯쟩뿶쿂뗷헻잰뫳쫓춼쓚뗄쫽 v = v1 UNION v2; } 뻝벯뫏뚼놣돖늻뇤 } 3ퟜ뷡 decompose_attr(A, a, f(, )) {/*튵컱뛔쿳A뗄럇훷쫴탔a퓚탅쾢췸룱닣듎뮯풪쫽뻝뷡릹쒣탍훐탩쓢쫓춼닣뫍싟닰럖*/ 벭풴닣횮볤듦퓚떥쿲펳짤헢훖펳짤뗄폐킧탔쫇탩쓢쫓춼 replace_attr(A, a, A, f(, ));} 헽좷럖뷢캪싟벭풴뗄믹놾놣횤싟벭풴닣풪쫽뻝뗄뇤뮯compose_obj(A, B, C) {/*튵컱뛔쿳A뫍Bퟩ뫏캪C*/ 뿉쓜펰쿬헢훖펳짤뗄폐킧탔쪹폃뮧붨솢뗄쫓춼컞램쪹폃믲 replace_obj(A, C); 늻쓜뗃떽웚췻뗄뷡맻 replace_obj(B, C); 놾컄퓚EVE쾵춳뗄쫓춼춬늽쮼쿫뗄믹뒡짏쳖싛쇋룼뢴}퓓뗄싟벭풴뇤뮯쟩뿶뛔폚뿉뗷헻뗄쟩뿶쳡돶쇋쿠펦뗄 merge_obj(A, B, C) {/*튵컱뛔쿳A뫍B죚뫏캪C*/뗷헻쯣램틔놣횤뗷헻뫳쫓춼뗄뫏램탔헢훖믹폚뢴퓓싟벭 풴뇤뮯쟩뿶뗄뗷헻쯣램퓶잿쇋탩쓢쫓춼닣쫊펦뗗닣풪쫽뻝 //춬튵컱뛔쿳ퟩ뫏compose_obj(A, B, C) } move_attr(A, a, B, k) {/*튵컱뛔쿳A뗄럇훷쫴탔a틆뚯훁튵컱뛔뇤뮯뗄쓜솦복짙싟벭풴닣풪쫽뻝뇤뮯뗄펰쿬쳡룟쇋쾵쿳B*/춳뗄ퟔ컒뗷헻쓜솦 if (A in ) { 닎뾼컄쿗 result = replace_attr(A, a, B, a); 1 샮 캰탬횾캰. 튻훖췸룱풴뿕볤쒣탍벰웤펦폃. 볆쯣믺퇐뺿폫 if (result) { 랢햹, 2003, 40(12)1756-1762 = {B}; 2 쇎뮪쏷, 돌늮폰, 쇵탂훜뗈. 탅쾢췸룱훐풪쫽뻝닣듎뮯뷡릹쒣탍 =+“ AND =”; 뗄퇐뺿뫍펦폃. 볆쯣믺퇐뺿폫랢햹,2003,40(12)1694-1699 }//죴쎻폐쳦뮻퓲컞탫뗷헻 } 3 Rundensteiner E A, Lee A J, Nica A. On Preserving Views in } Evolving Environments. In: Proc. 4th KRDB Workshop (Knowledge 놻뗷폃몯쫽쮵쏷 Represen- tation Meets Data Bases), Athens, 1997function replace_obj(A, B) {/*붫튵컱뛔쿳A쳦뮻캪B*/ 61
