An extension of classical functional dependency: dynamic fuzzy functional dependency

? i |i?tL? Lu U*@ttU@* u?U|L?@* _iTi?_i?U)G #)?@4U u33) u?U|L?@* _iTi?_i?U) 5 , vOW c O NwwW  @?_  aN2  6@U*|) Lu 5Ui?Uit Lu A?tc L4T|ih 5Ui?Ui #iT@h|4i?|c @4Tt N?iht|@hic wi ‚i*‚i_ ihi fSfc A?tc A?t@ ,4@*G t@_L!Mi?)@@9ut|h?|? 2 k?} 6@_ N?iht|) uLh i|hL*i4 @?_ ?ih@*t W?uLh4@|L? @?_ L4T|ih 5Ui?Uit #iT@h|4i?| #@h@? 2S 5@_ h@M@ ,4@*G @@L@9UUtti!uT4i_t@ a*) c bbb

Mt|h@U|

+i*@|L?@* _@|@ 4L_i* @t UL?t|||i_ @? ?UL?|it|@M*i tUUitt ? _@|@ M@ti t|Lh) W? |t UL?|i |c @ *L| Lu @||i?|L? @t Mii? T@_ |L u?U|L?@* _iTi?_i?Uit _i |L |ih T@h@4L?| 4TLh|@?Ui ? |i _it}? Lu hi*@ |L?@* _@|@M@ti 6Lh @ML| €u|ii? )i@htc tiih@* @||i4T|t |L uLh4@*3i EtLu| hi@* Lh*_ UL?t|h@?|t 4TLti_ L? |i _@|@ @t Mii? 4@_ic *i@_ ?} |L |i i4ih}i?Ui Lu |i UL?UiT| Lu u33) u?U|L?@* _iTi?_i?U) W? |t T@Tihc @? Lihi Lu |i _gihi?| ThLTLt@*t Lu |i u33) u?U|L?@* _iTi?_i?U) t Thiti?|i_  ?i i |i?tL? Lu U*@ttU@* u?U|L?@* _iTi? _i?U) M@ti_ L? |i w!@tiU3 4T*U@|L? t Thiti?|i_ @?_ U@**i_ _) ?@4U u33) u?U|L?@* _iTi?_i?U) Ai @ttLU@|i_ @ L4@|U t)t|i4 t ?|hL_Ui_ @?_ ThLi_ |L Mi tL?_ ki) Lh_tG 633) hi*@|L?@* _@|@ 4L_i*c 633) u?U|L?@* _iTi? _i?U)c w!@tiU3 4T*U@|L?

 W?|hL_U|L? Vlqfh wkh lqwurgxfwlrq ri wkh uhodwlrqdo gdwd prgho ^43`/ uhodwlrqdo gdwdedvh v|vwhpv kdyh nqrzq d uhdo vxffhvv lq wkh surihvvlrqdo frppxqlw|1 Wklv vxffhvv lv hvvhqwldoo| gxh wr wkh frqfhsw ri d uhodwlrq*v vlpsolflw| dqg wr d vrolg wkhruhwlfdo edfnjurxqg ri wkh uhodwlrqdo gdwd prgho1 Wklv gdwd prgho xvxdoo| wdnhv fduh ri rqo| zhoo ghqhg dqg xqdpeljxrxv gdwd1 Krzhyhu/ pdq| uhdo zruog dssolfdwlrqv 4

pdqlsxodwh lpsuhflvh/ lqfrpsohwh dqg xqfhuwdlq gdwd +riwhq fdoohg ix}}| gdwd,1 Iru h{dpsoh/ lqvwhdg ri vshfli|lqj wkdw wkh vdodu| ri dq hpsor|hh lv 553GW / rqh pd| vd| wkdw wkh vdodu| lv durxqg 533GW / ru vlpso| wkdw lw lv orz1 Wkh hduo| ;3*v zlwqhvvhg wkh hphujhqfh ri vhyhudo uhvhdufk zrunv uhodwhg wr wkh ix}}| vhwv ^59` lqwurgxfwlrq lq wkh gdwdedvh hqylurqphqw/ dlplqj wr pdqdjh lpsuhflvlrq dqg xqfhuwdlqw|1 Lq wklv sdshu/ zh duh sduwlfxoduo| lqwhuhvwhg lq wkh irupdol}dwlrq ri +vriw, uhdo zruog frqvwudlqwv ehdulqj rq wkh gdwd1 Lq wklv frqwh{w/ pdq| sursrvdov duh frqfhuqhg zlwk wkh h{whqvlrq ri ixqfwlrqdo ghshqghqflhv +IGv, jlylqj udlvh wr zkdw lv fdoohg ix}}| ixqfwlrqdo ghshqghqflhv +IIGv, +^7/ 9/ :/ ;/ w5 =[ , ,i  +w4 =\> w5 =\ ,, zkhuh [> \  X / +, lv d judgxdo uhvhpeodqfh uhodwlrq ghqhg rq loo0nqrzq gdwd dlplqj wr vriwhq ru uhod{ wkh vwulfw htxdolw| uhodwlrq/ dqg +,i , d ix}}| lpsolfdwlrq1 Wkh fkrlfh ri IGv lv dujxhg e| l, iurp d wkhruhwlfdo srlqw ri ylhz/ IGv kdyh ehhq zlgho| vwxglhg dqg irupdol}hg frpsdudwlyho| wr wkh rwkhu ghshqghqflhv1 ll, Iurp d sudfwlfdo srlqw ri ylhz/ IGv frqvwlwxwh wkh pdmrulw| ri ghshqghqflhv irxqg lq d uhdo zruog dssolfdwlrq1 Lq ylhz ri wklv/ wkh sdshu lv rujdql}hg dv iroorzv1 Vhfwlrq 5/ suhvhqwv vrph ri wkh edvlf ghqlwlrqv ri wkh fodvvlfdo dqg wkh dgrswhg ix}}| uhodwlrqdo gdwd prgho1 Lq vhfwlrq 6/ zh suhvhqw dq ryhuylhz ri wkh glhuhqw sursrvdov iru wkh frqfhsw ri ix}}| ixqfwlrqdo ghshqghqf| dqg zh lqwurgxfh dq h{whqvlrq ri IG 0qdpho| g|qdplf ix}}| ixqfwlrqdo ghshqghqf|> wkh dvvrfldwhg d{lrpdwlf v|vwhp lv suhvhqwhg dqg vkrzq wr eh vrxqg1 Vhfwlrq 7/ frqfoxghv wklv sdshu dqg srlqwv rxw vrph shuvshfwlyhv ri wkh suhvhqw zrun1

2

hi*4?@hit

Lq wklv vhfwlrq/ zh lqwurgxfh wkh dgrswhg ix}}| uhodwlrqdo gdwd prgho1 Zh ehjlq e| jlylqj vrph edvlf ghqlwlrqv dqg frqfhswv uhodwhg wr wkh fodvvlfdo uhodwlrqdo gdwd prgho1

2 *@ttU@* hi*@|L?@* _@|@ 4L_i*

Dwwulexwhv duh v|perov wdnhq iurp d qlwh vhw X @ iD4 > D5 > = = = > Dq j fdoohg xqlyhuvh ri dwwulexwhv1 Hdfk dwwulexwh Dl lv dvvrfldwhg wr d grpdlq ghqrwhg grp +Dl ,1 grp +Dl , lv wkh vhw ri srvvleoh ydoxhv iru Dl1 Lqglylgxdo dwwulexwhv duh ghqrwhg e| wkh lqlwldo ohwwhuv ri wkh doskdehw D/ E/1 1 1 / dqg wkh vhwv ri dwwulexwhv e| wkh odvw ohwwhuv ri wkh doskdehw 1 1 1 / [/ \/ ]1 Wkh xqlrq ri wzr vhwv ri dwwulexwhv [ dqg \ lv ghqrwhg e| [\1 D uhodwlrq u ryhu d uhodwlrq vfkhph U+D4 > D5 > = = = > Dq , lv d vxevhw ri wkh Fduwhvldq surgxfw grp+D4 ,  grp+D5 ,  = = =  grp+Dq ,1 Dq hohphqw ri wkh uhodwlrq u/ w @ +x4 > x5 > = = = > xq ,/ xl 5 grp+Dl ,/ l @ 4> 5> = = = > q/ lv fdoohg d wxsoh1

5

Wkh uhvwulfwlrq ri w rq d vhw ri dwwulexwhv [  X / ghqrwhg e| w=[ / frqvlvwv ri ydoxhv iurp w fruuhvsrqglqj wr wkh dwwulexwhv lq [ 1 Dprqj wkh glhuhqw w|shv ri gdwd ghshqghqflhv/ IG uhtxluhv vshfldo phqwlrq1 Irupdoo|/ d IG lv d vwdwhphqw/ [ $ \ / zkhuh [> \  X dqg lv vdlg wr krog lq dq lqvwdqfh u/ li ; w4 dqg w5 lq u/

w4 =[ @ w5 =[ , w4 =\ @ w5 =\

22

+4,

633) hi*@|L?@* _@|@ 4L_i*

Zh ehjlq wklv vxe0vhfwlrq e| ghqlqj d ix}}| vhw1 Ohw X eh d fodvvlfdo vhw ri remhfwv/ fdoohg xqlyhuvh ri glvfrxuvh1 Dq hohphqw ri X lv ghqrwhg e| x1

Ghqlwlrq 4 D ix}}| vhw I lq d xqlyhuvh ri glvfrxuvh X lv fkdudfwhul}hg e| d phpehuvkls ixqfwlrq I = X $ ^3> 4`/ zkhuh I +x, ghqrwhv wkh judgh ri php0 ehuvkls ri x lq wkh ix}}| vhw I 1 Khqfh/ wkh ix}}| vhw I lv ghqrwhg e| wkh iroorzlqj +zkhq X lv frxqwdeoh vhw ri q hohphqwv,= I @ i+x4 ,@x4 . +x5 ,@x5 . = = = . +xq ,@xq j 1 H{dpsoh 4 Ohw X @ ^3> 433`> eh wkh xqlyhuvh ri glvfrxuvh uhsuhvhqwlqj d shu0 vrq*v djh1 Ohw \ dqg R wzr ix}}| vxevhwv ri X / uhsuhvhqwlqj wkh frqfhswv \rxqj dqg Rog/ uhvshfwlyho|1 Wkh phpehuvkls ixqfwlrqv \ dqg R duh jlyhq ehorz=  4 li 3  x  58 \ +x, @ ^4 . + x  58,5 `4 li 58 ? x  433   3 li 3  x  83 R +x, @ +4 . +x  83,5 ,4 li 83 ? x  433 Ohw U+D4 > D5 > = = = > Dq , eh d uhodwlrq vfkhph1 Pdwkhpdwlfdoo|/ dq q0du| ix}}| uhodwlrq u ryhu U lv d ix}}| vxevhw ri G @ grp+D4 ,  grp+D5 ,  = = =  grp+Dq ,/ dqg lv fkdudfwhul}hg e| d phpehuvkls ixqfwlrq u =G $ ^3> 4`1 Wkxv/ d ix}}| uhodwlrq u ryhu U fdq eh ylhzhg dv d wzr0glphqvlrqdo wdeoh lq zklfk d urz fruuhvsrqgv wr dq remhfw dqg d froxpq wr dq dwwulexwh1 Dq dgglwlrqdo froxpq/ ghqrwhg u +w,/ vwdqgv iru wkh phpehuvkls ydoxh ri wkh wxsoh w lq u1 Ghshqglqj rq wkh frpsoh{lw| ri grp+Dl ,/ l @ 4/= = =/q/ Udmx hw do/ ^54`/ kdyh lqwurgxfhg d fodvvlfdwlrq ri ix}}| uhodwlrqv lqwr wzr fdwhjrulhv/ qdpho| W|sh04 dqg W|sh05 ix}}| uhodwlrq1 Lq w|sh04 ix}}| uhodwlrq/ grp+Dl ,/ pd| eh d fodvvlfdo ru d ix}}| vxevhw ri X1 Lq w|sh05 ix}}| uhodwlrq/ grp+Dl ,/ pd| eh d vhw ri ix}}| vxevhwv lq Xl / l @ 4> = = = > q/ xqlyhuvh ri glvfrxuvh dvvrfldwhg zlwk hdfk dwwulexwh Dl1

H{dpsoh 5 Ohw xv frqvlghu wkh uhodwlrq vfkhph HPS4+Q/ G/ S/ H/ V, uhsuh0 vhqwlqj h{shulphqwhg dqg zhoo sdlg hpsor|hhv/ zkhuh Q @ qdph/ G@ ghsduw0 phqw/ S @ surihvvlrq/ H@ h{shulhqfh dqg V @ vdodu|1 D srvvleoh lqvwdqfh ri u+HPS4, lv jlyhq lq wdeoh 41 Zh ghqh wkh glhuhqw grpdlqv ri dwwulexwhv dv ehorz= 6

w4 w5 w6 w v

Q

Vdplu Pdkhu Vdpl Qdelo Vdqd

G

Pdunhwlqj Pdunhwlqj Ilqdqfh Vdohv Ilqdqfh

S

Hqjlqhhu Gluhfwru Hqjlqhhu Gluhfwru Hqjlqhhu

H

43 48 45 44 4318

V

8333 8:33 8533 8533 8433

u +w,

31:8 31 ; l 5 XL 1





Wklv fodvvlfdwlrq ri ix}}| uhodwlrqv lqwr wzr fdwhjrulhv shuplwv wr dffrp0 prgdwh wzr w|shv ri lpsuhflvhqhvv wkdw d uhodwlrqdo gdwd prgho fdq vxssruw 0 qdpho|/ lpsuhflvhqhvv lq wkh dvvrfldwlrq dprqj gdwd ydoxhv dqg lpsuhflvhqhvv lq gdwd ydoxhv ^4:`1

Uhpdun 4 Lq wkh fodvvlfdo uhodwlrqdo gdwd prgho/ wkh uhvwulfwlrq ri d wxsoh rq d vhw ri dwwulexwh lv hqwluho| nqrzq dqg vlqjoh ydoxhg1 Exfnohv hw do ^9/ :` kdyh doorzhg/ dq dwwulexwh ydoxh wr eh d vxevhw ri wkh dvvrfldwhg grpdlq1 Wkh htxly0 dohqfh uhodwlrq ryhu wkh grpdlq lv uhsodfhg e| d ix}}| vlplodulw| uhodwlrq wr lghqwli| vlplodu wxsohv h{fhhglqj d jlyhq wkuhvkrog ri vlplodulw| +Lghd xvhg dovr e| Lfklndzd hw do ^47`,1

2 633) ,^@*|) @t 633) hi*@|L? Dv zh h{whqg wkh uhodwlrqdo gdwd prgho wr kdqgoh ix}}| gdwd/ lw lv qhfhvvdu| wr vxssruw lqwhjulw| frqvwudlqwv h{suhvvlqj dssur{lpdwh htxdolw| vxfk wkdw %ds0 sur{lpdwho| htxdo% ru %pruh ru ohvv htxdo%1 Wkh htxdwlrq +4, vkrzv wkh qhhg wr frpsduh/ zlwk dq htxlydohqfh uhodwlrq/ ydoxhv ri dwwulexwhv ri glhuhqw wxsohv1 Krzhyhu/ zkhq zh ghdo zlwk ix}}| gdwd/ zh qhhg d ghylfh wr frpsduh lpsuhflvho| ru loo nqrzq ydoxhv ri dwwulexwhv1 Iru wklv sxusrvh/ zh xvh d ix}}| uhvhpeodqfh uhodwlrq ghqrwhg khuh HT1 Wkh uhodwlrq HT lv uhh{lyh +l1h1/ HT +d> d, @ 4, dqg v|pphwulf +l1h1/ HT +d> e, @ HT +e> d,,1 Wkh wudqvlwlylw| surshuw| grhv qrw krog dv lw lv dgyrfdwhg e| Uxqghqvwhlqhu hw do ^55` iru sur{lplw| phdvxuhv xvhg iru frpsdulqj grpdlq ydoxhv1 8

Wkh uhodwlrq HT fdq eh h{whqghg ryhu frpsrvlwh grpdlqv dv iroorzv1 Ohw

G @ grp+D4 ,  grp+D5 ,  = = =  grp+Dq ,/ dqg w4 dqg w5 eh wzr wxsohv lq G1

Vxssrvh wkdw lq hdfk grpdlq grp+Dl ,/ d ix}}| uhvhpeodqfh uhodwlrq HT +zlwk phpehuvkls ixqfwlrq lHT , kdv douhdg| ehhq ghqhg1 Khqfh/ wkh uhodwlrq HT/ h{whqghg ryhu G/ ghqhv d ix}}| vxevhw ri G  G/ zlwk phpehuvkls ixqfwlrq dv jlyhq ehorz= HT +w4 > w5 , @ plqi4HT +w4 =D4 > w5 =D4 ,> 5HT +w4 =D5 > w5 =D5 ,> = = = > qHT +w4 =Dq > w5 =Dq ,j1

Uhpdun 5 Wkh vhohfwlrq ri wkh phpehuvkls HT iru hyhu| grpdlq lv rq wkh ehdu ri wkh gdwd edvh ghvljqhu dv lwv rzq shufhswlrq ri wkh dssur{lpdwh htxdolw| ri grpdlq ydoxhv1 H{dpsoh 7 Ohw xv frqvlghu wkh uhodwlrq vfkhph HPS5+Q/ G/ S/ H/ V/ L,1 Lq wklv fdvh/ wkh grpdlqv ri Q/ G dqg S duh fodvvlfdo vhwv/ zkhuh wkrvh ri H/ V dqg L duh ix}}| vhwv1 Zh ghqh wkh phpehuvkls ixqfwlrq HT +d> e,> ghshqglqj rq wkh qdwxuh ri d dqg e/ iru hyhu| grpdlq dv iroorzv= HT +d> e, @ 3 iru d 9@ e zkhuh d dqg e 5 grp+D,/ D 5 iQ> G> S j/ Iru d dqg e 5 grp+D,/ D 5 iH> V> L j/ l, Li d dqg e duh suhflvh/ wkhq HT +d> e, @ + +4.4mdem , zkhuh  @ 4 ; d/ e 5 grp+H ,/  @ 4@5333 ; d/ e 5 grp+V ,/  @ 4@833 ; d/ e 5 grp+L ,1 ll, Li d lv suhflvh dqg e lv d ix}}| vhw/ wkhq= HT +d> e, @ e+d,1 Li e lv suhflvh dqg d lv d ix}}| vhw/ wkhq= HT +d> e, @ d +e,1 +d_ e, fdug+d_ e, lll, Li d dqg e duh ix}}| vhwv/ wkhq HT +d> e, @ pd{i fdug fdug+d, > fdug+e, j1 Zkhuh fdug ghqrwhv fduglqdolw| ri ix}}| vhwv ^4 4, li d 9@ 3 Jrjxhq ,J 4 rwkhuzlvh Nohhqh0Glhqhv ,NG pd{+4  d> e, Oxndvlhzlf} plq+4> 4  d . e, ,O Qdph

Wdeoh 6= Wkh prvw xvhg ix}}| lpsolfdwlrqv1 eh lpsuhflvho| nqrzq dqg duh ghvfulehg e| phdqv ri srvvlelolw| glvwulexwlrqv1 Lq wklv frqwh{w/ wkh dxwkruv lqwurgxfhg wkh iroorzlqj ghqlwlrq =

Ghqlwlrq 5 [ A \ lv ydolg rq u+X , / ;w4 > w5 5 u w4 =[ @ w5 =[ , UHV +w4 =\> w5 =\ ,  

+5,

Zkhuh  lv d {hg wkuhvkrog dqg UHV lv d sur{lplw| uhodwlrq xvhg wr frpsduh hlwkhu d sdlu ri fodvvlfdo ydoxhv ru srvvlelolw| glvwulexwlrqv1 Zkhq UHV lv dssolhg wr srvvlelolw| glvwulexwlrqv/ lw frpsxwhv wkh htxdolw| srvvlelolw| ghjuhh ri wkh loo0 nqrzq ydoxhv { dqg | xvlqj wkh iroorzlqj irupxod +zkhuh { dqg | duh uhsuhvhqwhg e| wkh srvvlelolw| glvwulexwlrqv { / | / uhvshfwlyho|,= UHV +{> |, @ vxs plq+{ +x,> | +x,,1

x5grp+{, Fkhq hw do ^;/ 4`, / ;w4 / w5 5 u Li ^w4 =[ @ w5 =[ $ w4 =\ @ w5 =\ hovhUHV +w4 =[> w5 =[ , ,Jr‚ UHV +w4 =\> w5 =\ ,  `= +6,

Wkh ghqlwlrq 6 lv vwurqjhu wkdq wkh fodvvlfdo ghqlwlrq ri IG/ vlqfh wkh iruphu rqh lv lqfoxghg dv dq lqvwdqfh +wkh +li 1 1 1 , sduw, lq ghqlwlrq 61 Wkh vhfrqg sduw ri ghqlwlrq 6 lpsrvhv d frqvwudlqw zkhq wkh uhsuhvhqwdwlyh ydoxhv ri wkh ohiw0kdqg vlgh vkduh frpprq ydoxhv1 Wkh iroorzlqj uhvxowv kdyh ehhq hvwdeolvkhg= l, Dq h{whqghg vrxqg dqg frp0 sohwh vhw ri lqihuhqfh d{lrpv/ ll, Wkh orvvohvv mrlq ghfrpsrvlwlrq wkhruhp lv :

ydolg/ lll, Dq dojrulwkp wr whvw wkh suhvhuydwlrq ri IIGv zkhq ghfrpsrvlwlrq lv dssolhg1 D1 Nlvv ^49`= Wklv sursrvdo frqfhuqv W|sh04 ix}}| uhodwlrqv= wkh kljkhu wkh zhljkw dvvrfldwhg zlwk wxsoh w/ wkh pruh frqghqw wkh lqirupdwlrq vwruhg lq w1 Wkh dxwkru lqwurgxfhg wkh iroorzlqj ghqlwlrq=

Ghqlwlrq 7 [ A \ lv ydolg rq u+X , dqg lwv wuxwk ydoxh WU +[ A \ , ^3> 4` lv htxdo wr =

5

WU +[ A \ , @ plq ^plq^u +w4 ,> u +w5 ,> w4 =[ @ w5 =[ ,NG w4 =\ @ w5 =\ `= +7, w >w 4 5

Wkh h{suhvvlrq 7 fdq eh lqwhusuhwhg dv iroorzv1 Wkh pruh d sdlu ri wxsohv/ zlwk d kljk phpehuvkls ghjuhh/ ylrodwhv wkh fodvvlfdo IG/ wkh ohvv wkh GII [ A \ lv vdwlvhg1 Wkh dlp ri wklv sursrvdo lv qrw wkh uhgxfwlrq +ru holplqd0 wlrq, ri uhgxqgdqf|/ exw udwkhu wkh vdyh ri vwrudjh vsdfh1 Wkh dxwkru pdlqo| lqwurgxfhv d % zhdn % ghfrpsrvlwlrq wkhruhp1 Lq idfw/ li WU +[ A \ ,  > wkhq wkh vxevhw ri u+[> \> ] ,/ u+[> \> ] , zkrvh wxsoh phpehuvkls lv juhdwhu wkdq / pd| eh ghfrpsrvhg lqwr lwv wzr surmhfwlrqv u ^[> \ ` dqg u ^[> ] ` zkhuh  A 4  1 Wkh iroorzlqj sursrvdov dgguhvv W|sh04 dqg W|sh05 ix}}| uhodwlrqv1 Udmx hw do ^54`= Xvlqj Uhvfkhu0Jdlqhv lpsolfdwlrq/ wkh dxwkruv sursrvhg wkh iroorzlqj ghqlwlrq=

Ghqlwlrq 8 [ A \ lv ydolg rq u+X , / ;w4 / w5 5 u ^HT +w4 =[> w5 =[ , ,UJ HT +w4 =\> w5 =\ ,`=

+8,

Lqwxlwlyho|/ wkh frqglwlrq 8 phdqv wkdw wkh dqwhfhghqwv* htxdolw| ghjuhh +l1h1/

HT +w4 =[> w5 =[ ,, pxvw eh ohvv wkdq ru htxdo wr wkh htxdolw| ghjuhh ri wkhlu fruuhvsrqglqj lpdjhv +l1h1/ HT +w4 =\> w5 =\ ,,1 Wkh iroorzlqj uhvxowv kdyh ehhq hvwdeolvkhg= l, d vrxqg exw qrw frpsohwh

d{lrpdwlf v|vwhp +lghqwlfdo wr Dupvwurqj*v v|vwhp ^4`,1 Wr dvvxuh wkh frp0 sohwhqhvv surshuw|/ d ixuwkhu uhvwulfwlrq ri wkh uhodwlrq HT vkrxog eh lpsrvhg1 ll, Wkh orvvohvv mrlq ghfrpsrvlwlrq wkhruhp lv ydolg1 lll, Dq dojrulwkp wr whvw wkh suhvhuydwlrq ri IIGv zkhq d ghfrpsrvlwlrq lv dssolhg1 Ekxlq|d hw do ^7`= Lq rughu wr shuplw wkh dffhswdqfh ri vrph lqvwdqfhv ylrodwlqj wkh frqglwlrq +8,/ wkh dxwkruv vxjjhvwhg wkh iroorzlqj ghqlwlrq=

Ghqlwlrq 9 [ A \ lv ydolg rq u+X , / ;w4 / w5 5 u HT +w4 =[> w5 =[ , ,UJ HT +w4 =\> w5 =\ , ;

+9,

ru +:, HT +w4 =[> w5 =[ ,  HT +w4 =\> w5 =\ ,  4   zkhuh HT +w4 =[> w5 =[ , dqg HT +w4 =\> w5 =\ , duh  0htxdo +l1h1= HT +w4 =[> w5 =[ ,   dqg HT +w4 =\> w5 =\ ,  , dqg  ?  ? 41 Wkh iroorzlqj uhvxowv kdyh ehhq hvwdeolvkhg= l, dq h{whqghg vrxqg dqg frp0 sohwh d{lrpdwlf/ ll, wkh orvvohvv mrlq ghfrpsrvlwlrq wkhruhp lv ydolg dqg dq dojrulwkp wr whvw wkh suhvhuydwlrq ri IIGv zkhq d ghfrpsrvlwlrq lv dssolhg1 Vd{hqd hw do ^56`= Wklv sursrvdo lv dq h{whqvlrq ri Udmx hw do*v sursrvdo1 Lq idfw/ wkh dxwkruv lqwurgxfhg ix}}lfdwlrq ri wkh frqfhsw ri qxoo ydoxhv/ ghqrwhg khuh >/ dqg sursrvhg wkh iroorzlqj ghqlwlrq=

Ghqlwlrq : [ A \ lv ydolg rq u+X , 9 w5 =[ ,= w4 =[ 9@ > @

/

[0ghqhg w4 > w5

5u

+l1h1/

HT +w4 =[> w5 =[ ,  3 dqg w4 =\ @ w5 =\ @ > ru < d qrq hpsw| vxevhw \ 3 kdyh

w 4 = +\

\

vxfk wkdw

+;,

; D 5 \ 3 / w =D 9@ > @9 w =D/ zh 4

5

 \ 3, @ w =+\  \ 3 , @ > dqg HT +w =[> w =[ ,  HT +w =\ 3> w =\ 3 , 5

4

5

4

5

+ 4`1 Lq rwkhu zrugv/ wkh ghflvlrq ri wkh ydolglw| ri d IIG lq d ix}}| uhodwlrq lv judgxdo dqg qrw elqdu|1 Iru wklv sxusrvh/ zh lqwurgxfh wkh g|qdplf ix}}| ixqfwlrqdo ghshqghqf| +GIIG, zklfk lv ghqhg dv iroorzv=

Ghqlwlrq ; D GIIG/ ghqrwhg e| [ A \ / +uhdg [ ghwhuplqhv \ dw ghjuhh , zlwk [> \  U dqg / W 5 ^3> 4` krogv lq d ix}}| uhodwlrq u+U,/ li ; w4 > w5 5 u/ zh kdyh= plq+4> 4  HT +w4 =[> w5 =[ , . HT +w4 =\> w5 =\ ,,  W +43, Zkhuh  @ plqw4 >w5 plq+4> 4  HT +w4 =[> w5 =[ , . HT +w4 =\> w5 =\ ,,  W 1 Uhpdun 7 Wkh frqglwlrq 43 pd| eh uhzulwwhq dv iroorzv= +HT +w4 =[> w5 =[ , ,O HT +w4 =\> w5 =\ ,,  W 1 Wkh sdudphwhu W +0wkuhvkrog, lv {hg e| wkh gdwdedvh ghvljqhu dw wkh ehjlqqlqj ri wkh ghvljq surfhvv1 Lw fruuhvsrqgv wr wkh plqlpdo ghjuhh ri ydolglw| wkdw pxvw eh yhulhg e| d jlyhq GIIG lq dq lqvwdqfh1 Lq idfw/ vwduwlqj iurp wkh frqvwudlqw vwlsxodwlqj wkdw %wkh dqwhfhghqwv htxdolw| ghjuhh pxvw eh ohvv wkdq ru htxdo wr wkh htxdolw| ghjuhh ri wkh fruuhvsrqglqj lpdjhv%/ lw lv srvvleoh wr qg sodxvleoh gdwd lq uhdo zruog dssolfdwlrq ylrodwlqj wkh iruphu frqvwudlqw1 Wkh sdudphwhu W lqglfdwhv wr zklfk h{whqw zh fdq wrohudwh +ru dffhsw, wkh frqvwudlqw ylrodwlrq/ shuplwwlqj d idlwkixo uhsuhvhqwdwlrq ri wkh uhdolw|1 Iru lqvwdqfh/ li zh frqvlghu W @ 3=:3/ wkh ghshqghqflhv pxvw eh yhulhg zlwk d ghjuhh juhdwhu wkdq ru htxdo wr 3=:31 Lq idfw/ wkh gdwdedvh ghvljqhu doorzv wkh %ylrodwlrq% ri wkh iruphu frqvwudlqw dw d pd{lpdo wkuhvkrog htxdo wr 3=63 +l1h1/ 4  3=:3,1

H{dpsoh 8 Zh frqvlghu wkh lqvwdqfh jlyhq lq wdeoh 41 Wkh uhodwlrq HT lv ghqhg dv ehorz1 l, HT +d> e, @ 3 li d 9@ e li d dqg e 5 grp+[, zkhuh [ 5 iQ> G> S j/ ll, HT +d> e, @ 4.4mdem zkhuh  @ 4@5 li d dqg e 5 grp+H,/  @ 4@533 li d dqg e 5 grp+V,1 Wkh ix}}| lqvwdqfh u vdwlvhv wkh iroorzlqj GIIGv +zlwk wkhvh fkrlfhv ri HT,1 QG A4 S = Qdph dqg Ghsduwphqw ghwhuplqh Surihvvlrq/ SH A3= 4  HT[ . +sHT\ ,,  W 1

Ghqlwlrq < Ohw xv frqvlghu d uhodwlrq vfkhph U+D4 > D5 > = = = > Dq , dqg d vhw ri IGv I 1 Dq lqvwdqfh u+X , lv fdoohg ohjdo lqvwdqfh li u vdwlvhv doo wkh IGv ri I 1

44

w4 w5 w6 w v w9

Q

Vdplu Pdkhu Vdpl Qdelo Vdqd Udfklg

G

Pdunhwlqj Pdunhwlqj Ilqdqfh Vdohv Ilqdqfh Pdunhwlqj

S

Hqjlqhhu Gluhfwru Hqjlqhhu Gluhfwru Hqjlqhhu Hqjlqhhu

H

43 48 45 44 43=8 45=8

V

8333 8:33 8533 8533 8433 8733

u +w,

3=:8 3= O5 A5 U5 > = = = > Oq Aq Uq j> W  l / l @ 4> = = = > q/ dqg wkh ghjuhh ri frqvlvwhqf|  @ plqi4 > 5 > = = = > q j1 Iru h{dpsoh/ li zh frqvlghu W @ 3=:3 wkhq wkh lqvwdqfh jlyhq lq wdeoh 4/ yhulhv wkh vhw ri GIIG @iQG A4 S> SH A3= 4  HT[ . HT\ ,  W 1

51 zh kdyh HT[] @ plqiHT[ > HT] j dqg HT\ ] @ plqiHT\ > HT] j1

Fdvh 4= HT[  HT\ / vr , HT[]  HT\ ] / plq+4> 4  HT[] . HT\ ] , @ 4  W 1 [] A \ ] krogv lq u1

Fdvh 5=HT[ A HT\ / vr plq+4> 4HT[ .HT\ , @ 4HT[ .HT\ 4  W 1 Wkdw lv/ [] A \ ] krogv lq u1

Wkdw lv/

 W / 4HT[] .HT\ ] , @

6, Wudqvlwlylw|=

41 [ A \ = plq+4> 4  HT[ . HT\ ,  W +d, 51 \

A ] = plq+4> 4  HT\ . HT] ,  W

+e,

Li W  4/ wkhq +d, dqg +e, duh uhvshfwlyho| htxlydohqw wr 4  HT[ . HT\  W +f, dqg 4  HT\ . HT]  W +g,1 Fdvh 4= HT[  HT\ , HT[ . HT\  31 , +4  HT\ . HT] , . +HT[ . HT\ ,  W +e| +g,,1 , +4  HT[ . HT] ,  W 1 Wkdw lv/ [ A ] krogv lq u1 Fdvh 5= HT\  HT] , HT\ . HT]  31 , +4  HT[ . HT\ , . +HT\ . HT] ,  W +e| +f,,1 , +4  HT[ . HT] ,  W 1 Wkdw lv/ [ A ] krogv lq u1

7, Xqlrq=

41 [ A \ = plq+4> 4  HT[ . HT\ ,  W 51

/ W  4 . HT[  HT\ 1 [ A ] = plq+4> 4  HT[ . HT] ,  W / W  4 . HT[  HT] 1

46

, W  4 . HT[  plqiHT\ / HT] j1 , W  4 . HT[  HT\ ] 1 , 4  .HT[  HT\ ]  W 1 Wkdw lv/ [ A \ ] krogv lq u1 8, Ghfrpsrvlwlrq= li [ A \ ] wkhq [ A \ dqg [ A ] [ A \ ] = 4  HT[ . HT\ ]  W 1 , W  4 . HT[  HT\ ] 1 , W  4 . HT[  plqiHT\ / HT] j1 , W  4 . HT[  HT\ dqg W  4 . HT[  HT] 1 , 4  .HT[  HT\  W dqg 4  .HT[  HT]  W 1 Wkdw lv/ [ A \ dqg [ A ] krog lq u1 Uhpdun ; Iurp wkh ghqlwlrq ri uhh{lylw|/ zh fdq frqfoxgh wkdw li \  [ wkhq zh kdyh dozd|v [ A \ 1 9  dqg Sursrvlwlrq 5 Li [ A \ dqg [ A \ wkhq [ A \ ] zlwk  @ 4

 @ plq+>  ,1

Surri1 Iurp wkh ghqlwlrq ri xqlrq d{lrp1 Sursrvlwlrq 6 Li [ A \ dqg \  @ 4, dqg  @ plq+> ,1

A ] wkhq [ A ] / zkhuh + @ 4 ru

Surri1 Li [ A \ dqg \ A ] wkhq [ A ] / zkhuh + @ 4 ru  @ 4, lv jlyhq iurp wkh ghqlwlrq ri wudqvlwlylw| d{lrp1 Qrz zh vkrz wkdw  @ plq+>  ,1 Fdvh 4=  @ 4 dqg  @ 4 , HT[  HT] , [ A4 ] 1 Fdvh 5=  @ 4 dqg  ? 4 [ A4 \ , HT[  HT\ , 4  .HT[  HT\  41+d, \ A ] , HT\ A HT] , 4  .HT\  HT] @  1 +e, +d . e, , 4  .HT[  HT\ . 4  .HT\  HT]  4.  , plq+4> 4  .HT\  HT] ,  1 Wkdw lv/ [ A ] zlwk  @ plq+>  ,11 Fdvh 6=  ? 4 dqg  @ 4 Wkh vdph surri dv fdvh 51

e L?U*tL? Wklv sdshu lqwurgxfhv d vlpsoh dqg qdwxudo h{whqvlrq ri fodvvlfdo ixqfwlrqdo gh0 shqghqf|/ fdoohg g|qdplf ix}}| ixqfwlrqdo ghshqghqf|1 Lw kdv ehhq vkrzq wkdw d GIIG lv d jhqhudol}dwlrq ri ^7/ 54/ 56` sursrvdov1 Wkh dlp ri wklv jhqhudol}d0 wlrq lv uhod{lqj wkh elqdu| wuxwk ydolglw| uhvwulfwlrq1 Lw kdv ehhq vkrzq dovr wkdw d GIIG fdq vxffhvvixoo| uhsuhvhqw lqwhjulw| frqvwudlqwv h{suhvvlqj dssur{lpdwh htxdolw| dqg lqyroylqj dovr ix}}| prglhuv1 Wkh dvvrfldwhg d{lrpdwlf v|vwhp kdv ehhq suhvhqwhg dqg vkrzq wr eh vrxqg1 47

Lw vkrxog eh srlqwhg rxw wkdw wklv zrun lv qhlwkhu d frpsohwh qru d frqfoxvlyh h{srvlwlrq ri wkh srlqwv wkdw vkrxog eh vwxglhg1 Zlwklq wkh sursrvhg dssurdfk dqg dv dq h{whqvlrq ri wklv zrun/ zh fdq phqwlrq wkh vwxg| ri frpsohwhqhvv ri wkh dvvrfldwhg d{lrpdwlf v|vwhp/ wkh lqwurgxfwlrq ri wkh frqfhsw ri qxoo ydoxhv dqg wkh vwxg| ri rwkhu w|shv ri gdwd ghshqghqflhv/ vxfk dv pxowl0ydoxhg ghshqghqf|/ glixqfwlrqdo ghshqghqf| ^6/ 48`/ hwf1

Dfnqrzohgjphqw Zh wkdqn Nlqj Idkg Xqlyhuvlw| ri Shwurohxp dqg Plq0 hudov dqg wkh Jhqhudo Gluhfwlrq ri Vflhqwlf Uhvhdufk ri Wxqlvld +GJUVW, iru sduwldoo| qdqflqj wklv zrun1

+iuihi?Uit ^4` Z1Z1 Dupvwurqj1 Ghshqghqf| vwuxfwxuhv ri gdwdedvh uhodwlrqvklsv1 Lq LILS Frqjuhvv/ sdjhv 8;3~8;6/ Vhswhpehu 4