I n d on e s i an   Jo u r n al   o El e c t r i c al   En gi n e e r i n g   an d   C o m p u te r   S c i e n c e   V o l .   18 ,   N o .   3 J u n e   20 20 ,   pp .   1596 ~ 1606   IS S N :   2502 - 4752 ,   D O I :   10. 1 1591 / i j e e c s . v 1 8 .i 3 . pp 159 6 - 1606             15 96       Jou r n al   h o m e pa ge ht t p: / / i j e e c s . i a e s c or e . c om   OR D - GA P:   a   h y b r i d - b a sed   l a b e l i n g   schem e s to   su p p o r t   X M L   d y n a m i c   u p d a t e s       A i s yah   A m i n ,   S u - C h e n H aw ,   S am i n i   S u b r am an i am   F a c ul t y   o f   C o m put i ng   a nd   I nf o r m a t i c s ,   M u l t i m e d i a   U n i v e r s i t y ,   M a l a y s i a       A r ti c l e   I n fo     A B S TR A C T   Ar t i c l e   h i s t or y :   R e c e i v e S e 13,   2 019   R e v i s e D e c   14,   2019   A c c e pt e D e c   30,   2 019       e X t e n s i bl e   M a r kup  L a ng ua g e   ( X M L )   ha s   be e w i de l y   us e a s   t he   s t a n da r d   f o r   da t a   e xc ha ng e   s t a nda r o v e r   t he   I nt e r ne t .   W i t t he   f a s t   g r o w i ng   r a t e   o f   da t a ,   e s p e c i a l l y   w i t h i g upda t e s ,   i t   i s   c r uc i a l   t o   e n s ur e   t ha t   t he   X M L   i s   a b l e   t o   c o pe   w i t f r e qu e n t   c ha ng e s   w i t v e r y   l e a s t   e f f e c t   o t he   e xi s t i ng   s t r uc t ur e .   T he r e f o r e ,   i t h i s   p a pe r ,   w e   i nv e s t i g a t e   o t h e   e x i s t i ng   l a be l i ng   s c he m e s   a n m a ppi ng   a ppr o a c he s   t o   g a ug e   a   be t t e r   und e r s t a nd i ng   i t e r m s   o f   t he   r o bus t ne s s   o f   t h e   l a b e l i ng   s c he m e s   a nd  t h e   i m po r t a nc e   o f   t he   m a pp i ng   s c he m e s .   N e x t ,   w e   p r o po s e   O R D - G A P   l a be l i ng   s c he m e s   t o   i d e nt i f y   t he   s t r uc t ur a l   r e l a t i o ns h i a m o ng   X M L   no de s   a nd   y e t ,   i t   i s   p e r s i s t e nt   t o   r e - l a b e l i ng   w he ne w   no de s   a r e   i ns e r t e d .   S ubs e qu e nt l y ,   a   m a ppi ng   s c he m e   i s   pr o po s e t o   t r a n s f o r m   X M L   i nt o   R e l a t i o na l   D a t a ba s e   ( R D B ) .   P r e l i m i n a r y   e xpe r i m e nt a l   e v a l ua t i o de m o ns t r a t e t h a t   t he   p r o po s e a pp r o a c a c hi e v e   66%   be t t e r   a s   c o m pa r e t o   O R D P A T H ,   a nd  56 %   b e t t e r   a s   c o m pa r e t o   M E   l a b e l i ng   i t e r m s   o f   da t a   l o a di ng   t i m e   Ke y w or ds :   D y n a m i c   upd a t e s   L a b e l i n g   s c h e m e   M a ppi ng  a pp r o a c h   S t ruc t u r a l   r e l a t i o n s h i p   X M L   da t a b a s e   C opy r i gh t   ©   2020   I n s t i t ut e   o f   A dv anc e E ng i ne e r i ng   and   S c i e nc e .     A l l   r i gh t s   r e s e r v e d .   Cor r e s pon di n g   Au t h or :   Su - C h e n g   H a w ,     F a c ul t y   of   Co m put i n g   a n d   I n f o r m a t i c s ,     M ul t i m e di a   U ni v e r s i t y ,   M a l a y s i a .     E m a i l :   s uc h e n g @ m m u . e du. m y       1.   I N TR O D U C TI O N   E xt e n s i b l e   M a r ku L a n g ua ge   (X M L ha s   a r i s e n   a s   t h e   s t a n d a r f o r   d a t a   e xc ha n ge   o v e r   t h e   I nt e rn e t   due   t o   t h e   f a c t   t ha t   i t   i s   e a s i l y   r e a da b l e   by   h u m a a n d   m a c hi n e ,   a s   i t   us e s   n a t u ra l   l a ngua ge   f o r   m a rkup   e xpr e s s i o n .   A l t e rna t i v e l y ,   Re l a t i o na l   D a t a b a s e   (R D B i s   c o m m o n l y   be i n us e a s   b a c k - e n i n   v a ri o us   i n dus t ri e s .   N e ve r t h e l e s s ,   due   t o   t h e   da t a   i s   p r o c e s s   i n de pe nde n t l y   of  i t s   c o n t e xt ,   R D B   c o ul n o t   f ul f i l l   t h e   m a r ke t   de m a nd.   A s   s uc h ,   i t   i s   e s s e n t i a l   t o   ha v e   a   go o m a ppe f o r   s t o ri n a n d   r e t r i e v i ng  X M L   s t r uc t u r e   (hi e ra r c h i c a l   m o de l i n t o   R D B   (t a b l e s   w i t h   r o w s   a n d   c o l um ns [1].   T h e   ke y   c r i t e r i o f o r   a   go o m a ppe i s   t e n s u r e   t ha t   t h e   f o u r   m a i s t r uc t u r a l   r e l a t i o n s h i ps ,   i . e . ,   A n c e s t o r - D e s c e n da n t   (A - D ) ,   P a r e nt - C hi l (P - C),   s i b l i ng  a n o rde r   a r e   pr e s e r v e [2,   3] .   I n   o r de r   t o   do   s o ,   a   goo a n e f fe c t i ve   l a b e l i n s c h e m e   e m pl oy e o n   t h e   n o de   (a l s o   k n o w n   a s   n o de   i n de xi ng)  i s   e s s e n t i a l   [4 ,   5] .     T h e r e   a r e   n um b e r s   o f   r e s e a r c h e s   do n e   o n   l a b e l i n s c h e m e   [6 - 9].   I n   t hi s   pa pe r ,   w e   a na l y z e   s o m e   r e c e n t   l a b e l i n g   s c h e m e s ,   w i t h   f o c us   o n   t h e   s uppo r t   du ri n d y n a m i c   upd a t e s   (i n s e r t i o n   o pe ra t i o n ) .   T h e   m a i t y p e s   of   i n s e rt i o n   h a p pe n:   (i l e f t - m o s t   i n s e r t i o n,   (i i ri g h t - m o s t   i n s e r t i o n ,   a n ( i i i i n - b e t w e e n     i n s e r t i o n   [7 ,   8,   10].   N e v e r t h e l e s s ,   m o s t   of  t h e   c urr e n t   a pp r o a c h e s   s t i l l   e xh i b i t   t h e   n e e ds   of   r e - l a b e l i ng  w h e n   t h e   r e s e r v e l a b e l   ha s   b e e n   us e up.   O n   t h e   o t h e r   ha n d ,   m a ppi n p l a y s   a   r o l e   t o   de t e r m i n e   h o w   e f fe c t i ve   a   X M L   da t a b a s e   h a s   b e e n   t ra n s f o r m e i n t o   R D B .   E xc e s s i ve   t a b l e s   a f t e r   t h e   m a pp i n p r o c e s s   w i l l   r e s ul t e i e xc e s s i ve   j o i n s ;   w h i l e   t o o   m a n y   i n f o r m a t i o n   s t o r e i n   a   s i ngl e   t a b l e   m a y   n o t   b e   t h e   go o s o l ut i o n   a s     w e l l   [11] .   T h us ,   i t   i s   e s s e n t i a l   t o   p r o po s e   a   n e w   l a b e l i n g   a n d   m a pp i n s c h e m e   t o   e n s u r e   (i n o   l o s s   of  i n f o r m a t i o n   w h e n   t ra n s f o r m i ng  f r o m   X M L   t o   RD B   s t o r a ge ,   (i i a v o i r e - l a b e l i n i f   dy n a m i c   upd a t e s   h a ppe n,   (i i i f a s t   que r y   r e t ri e v a l .   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       O R D - G A P a   h y br i d - bas e d   l a be l i ng   s c h e m e s   t o   s uppor t   X M L   dy nam i c   upd at e s   ( A i s y a A m i n )   1597   T h e   s ub s e que n t   s e c t i o n s   a r e   o r ga ni z e a s   f o l l ow s .   S e c t i on   r e v i e w s   t h e   l a b e l i n s c h e m e s   a n d   m a pp i n s c h e m e s .   I n   a d di t i o n,   t h i s   pa pe r   a l s o   s um m a r i z e s   a nd  di s c us s e s   o n   t h e   a dv a nt a ge s   a n di s a dv a n t a ge s   of   t h e s e   s c h e m e s .   T hr o ug h o ut   t h e   r e v i e w ,   S i gm o dR e c o r da t a s e t   i s   us e a s   a n   e x a m p l e .   T h e   pa rt i a l   v i e w   o S i gm o dR e c o r D a t a s e t   i s   de pi c t e i n   F i g u r e   1.   S e c t i o n   pro pos e s   o ur   p r o po s e a ppr o a c h   na m e l y   a s   O R D - G A P   l a b e l i n g   s c h e m e s   w hi c s uppo rt   dy n a m i c   upd a t e s   o X M L   da t a b a s e s .       2.   LI TER A TU R R EV I EW     2 . 1 .      R e v i e w   o n   Ex i s ti n g   Lab e l i n g   S c h e m e s   L a b e l i n s c h e m e s   c a n   b e   b r o a dl y   gr o upe i n t o   r e gi o n   e n c o di n g ,   m u l t i pl i c a t i v e ,   pr e f i x - b a s e d,   a n d   h y b r i d - b a s e [3].   A   r e gi o n - b a s e l a b e l i n s c h e m e   u t i l i z e   t he   t r e e   t r a v e r s a l   na v i ga t i o t o   a s s i g l a b e l   o n   t h e   n o de s   t o   pr e s e r v e   t h e   o r de r i ng  w h i l e   e n s u ri n t h e   s t ruc t u ra l   r e l a t i o n s h i ps   a r e   p r e s e r v e d .   A   p r e f i x - b a s e d   l a b e l i n s c h e m e s   [3,   1 2 ,   13]  i s   us ua l l y   t h e   m o s t   s i m pl e   s c h e m e   a s   i t   di r e c t l y   e n c o de   a   n o de ’s   pa r e n t   l a b e l   a s   t h e   p r e f i o f   i t s   l a b e l .   O n   t h e   o t h e r   ha n d ,   m ul t i p l i c a t i v e   l a b e l i n g   s c h e m e   us u a l l y   a s s i g n   l a b e l   b a s e o n   s o m e   a r i t hm e t i c   c o m put a t i o n   t o   i de nt i f y   t h e   s t r uc t u ra l   r e l a t i o n s hi ps   a m o n n o de s .   A   h y b r i l a b e l i n s c h e m e ,   h o w e ve r ,   i s   c o m po s e d   of  s o m e   c o m b i n a t i o n s   o e xi s t i n s c he m e   gr o upi n t o   b a l a n c e   b e t w e e n   o n e   w e a kn e s s   w i t t h e   s t r e n g t o f   t h e   o t h e r   g r o up   [14] .           F i gu r e   1 .   A   S a m pl e   o f   S i gm o dR e c o r X M L   do c um e nt       V - Co n t a i nm e nt   [7]   i s   a   r e gi o e n c o di n l a b e l i n s c h e m e ,   w hi c h   i s   b a s e o n   c o n t a i nm e nt   l a b e l   [15] .   P r i m a ri l y ,   t h e   l a b e l i n s t r uc t u r e   c o n t a i n s   (s t a r t V ,   e ndV ,   l e ve l ),   w h e r e   by   s t a rt V ,   e n dV   a r e   t w o   v e c t o r s   r e p r e s e n t i n t h e   o n e - t i m e   a s s i g nm e n t   o f   i n i t i a l   l a b e l i n p r e / p o s t   l a b e l i n s c h e m e ,   a n l e v e l   de n o t e s   t h e   de pt h   f r o m   t h e   r o o t   n o de   t o   c urr e n t   n o de .   T h e   i ni t i a l   l a b e l i n s c he m e s   a r e   a s s i g n e b a s e o n   de pt h - f i r s t   t ra v e r s a l .   S ub s e que n t l y ,   t o   s upp o r t   dy n a m i c   upda t e s ,   t h e y   pr o p o s e s o m e   a l go r i t hm s   t o   a c c o m m o da t e   t h e   i n s e r t i o n   i t h e   l e f t - m o s t ,   r i g ht - m o s t   a n i n - b e t w e e n   n o de s .   T h e   i n s e rt i o n   i s   po s s i b l e   i t h e   s t a r t   a n e nd  a r e   b e t w e e n   t h e   ra n ge   o f   t h e   p r e v i o us   a nd  f o l l ow i n g   s i b l i n gs .   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   18 ,   N o .   3 J u n e   20 2 :     1 5 9 6   -   1 6 0 6   1598   M ul t i pl i c a t i v e   l a b e l i n (M E us e s   m ul t i pl i c a t i o n   o pe r a t i o n   o n   o dd  n u m b e r s   t o   l a b e l   t h e   X M L   t r e e .   It   c o n s i s t s   of   (l e v e l ,   [s e l f l a be l ,   o r di na l ] ),   w h e r e   by   l e ve l   r e pr e s e nt   t h e   n o de   de pt h   o f   t h e   t r e e ,   s e l f l a b e l   i s   c o m put e a s   pa r e n t   *o r d i n a l   (p a r e n t   i s   t h e   s e l f L a b e l   of   pa r e nt   n o de ,   a n d   o r d i n a l   i s   t h e   po s i t i o o f   t h e   c urr e n t   n o de   w i t h i n   i t s   s i b l i n g )”   [8] .   T h e   r o o t   n o de   s t a rt s   a s   1.   T h e   f o r m ul a   2 n + w a s   a ppl i e t o   ge n e r a t e   o dd   n u m b e r s ,   w h e r e   r e pr e s e nt   t h e   po s i t i o o f   a   n o de .   I a d di t i o n ,   t h e y   a l s o   o ut l i n e s o m e   f o r m ul a s   t o   c a l c ul a t e   n e w   l a b e l   f o r   l e f t - m o s t ,   r i g ht - m o s t   a n d   i n - b e t w e e n   i n s e r t i o n   w i t h o ut   a n y   r e l a b e l i n g   i n c u rr e d .   L e v e l - b a s e l a b e l i n s c h e m e   (L L S i s   a   h y b r i l a b e l i n s c he m e   b a s e o n   i n t e r v a l   a n p r e f i x - b a s e d   l a b e l i n s c h e m e   [16] .   L L S   l a b e l i n s t r uc t u r e   a r e   a s s i g n e d   a s   < d. p . s >   w h e r e by   de n o t e   t h e   de p t h   o f   l e ve l ,   (i n di c a t e   a s   P e r L i s   t h e   num b e r   o f   n o de   a c r o s s   l e ve l ,   a nd  s   i s   t h e   i n s t a n c e   s e r i a l   n u m b e r   t ha t   r e c o gn i z e   n o de s   b e t w e e n   t h e   s a m e   n o de   f r o m   t h e   s a m e   c l a s s .   If   a n   i n s e rt i o h a p pe n,   t h e   r e - l a b e l i n o f   n o de s   o n l y   e ff e c t   o n   t h e   n o de   l a b e l   o f   t h e   s ub s e que n t   i n s e r t e d   n o de s   a s   s h o w n   i n   F i gu r e   2 .             F i gu r e   2 .   L L S   L a b e l i ng  S c h e m e   o f   d y n a m i c   upd a t e s       D y n a m i c   P r e f i x - b a s e L a be l i n g   S c h e m e   (D P L S [1 3]  i s   a e xa m pl e   o f   pr e f i x - b a s e l a b e l i ng  by   e xt e n di ng  o D e w e y   e n c o di n s c h e m e   [17] .   T h i s   a pp r o a c h   ha s   t w o   s t a ge s ,   w h e r e by   t h e   f i r s t   s t a ge   i n c l ude s   c o n s t r uc t i n t h e   i n i t i a l   D P L S   l a b e l i n b a s e o n   D e w e y   s c h e m e ,   f o l l ow e by   t h e   n e xt   s t a ge   i s   t o   h a n d l e   a n y   upda t e s .   S i m i l a rl y ,   t h i s   a pp r o a c h   s up po r t s   t hr e e   t y pe s   of   i n s e rt i o n:   l e f t - m o s t ,   i n - b e t w e e n   a n d   ri g h t - m o s t .   F &   M e n [18]  p r o po s e T r i p l e - c o de ,   w h i c h   c o n s i s t s   o f   < s t a rt ,   e n d ,   pa r e nt - i d > .   T h e i r   a pp r o a c h   a do pt e t h e   i n t e r v a l - b a s e l a b e l i n s c h e m e   by   r e pl a c i ng  t he   ‘l e ve l ’  t a w i t h   n o de ’s   ‘pa r e nt - i d’,   m a ki n i t   s i m pl e   t o   o b t a i n   P - a n s i b l i ng  r e l a t i o n s hi ps .   H e   [ 19]  pr o p o s e pr e f i x - b a s e s c h e m e   us i n f ra c t i o n s ,   w h i c h   h e   n a m e i t   a s   D P E S F   E n c o di ng.   T h i s   l a b e l i n s c h e m e   i s   i n   N um b e r - C ha r a c t e r   f o r m a t   b a s e o n   t h e   m a pp i n g   r u l e s   a s   fo l l ow s :   t o   m a e a c h   di gi t   =   { 0, 1 , 2 , 3, 4, 5 , 6 , 7 , 8, 9}   i n   t h e   n um e r a t o r   t o   a   m a t c h i n c h a ra c t e r   ={ , , , , , , , , , } .   A s   s uc h,   l a b e l   w i t (1251 4)  i s   e xp r e s s e a s   14 .     M o r e   r e c e n t l y ,   G o pi n a t ha n   &   A s a w a   [20]  p r o po s e a n   e xt e n de D e w e y   l a b e l i n s c h e m e ,   w hi c co n s i s t s   of   [pr e f i x. o r di na l l a b e l   t o   s uppo r t   Co n t e n t   a n S t ru c t ur e   Q ue r y   (CA S e ff e c t i v e l y .   In   a ddi t i o n,   t h e y   a l s o   p r o po s e n e w   pa t b a s e i n de xi ng  na m e l y ,   pa t i nde (p_i n de x)  a n d   pa t h   c o m b i n e d   i n de (pc _i n de x) .   T h e s e   i n de xe s   w e r e   c o n s t r uc t e d   us i n g   B + T r e e   a nd  H a s h M a p   r e s pe c t i v e l y .     A hn  e t   a l .   [21]   p r o po s e t o   i m pl e m e n t   r e pe t i t i v e   pr i m e   n u m b e r   [22 l a b e l i n i n   a   M a R e duc e - b a s e d   a l go ri t hm   t o   o ve r c o m e   t h e   p r o b l e m   of   m e m o r y   i n s uf f i c i e n t   s h o ul a   m a s s i v e   X M L   da t a   i s   l o a de i n   a   s i n g l e   m a c h i n e .   B e i n i pa ra l l e l   e n v i r o nm e n t ,   t hi s   a l l o w s   m ul t i pl e   m a c hi n e s   t o   c o m put e   l a b e l s   i n de pe n de nt l y .   In  a n o t h e r   r e s e a r c h   w o r k,   M o h a m m e e t   a l .   [23]  i n d i c a t e t ha t   s e l e c t i v i t y   e s t i m a t i o n   i s   c r uc i a l   t o   s uppo r t   s e v e r a l   t y p e s   o f   X M L   que r y ,   e s pe c i a l l y   t h o s e   t h a t   c o nt a i n s   w i l dc a r ds   o r   l o gi c a l   o pe ra t o r s .   T h e y   pr o po s e d   c o m b i n i ng  p r i m e   n u m b e r   l a b e l i n g   a n d   s y n o ps i s   m o de l i ng  f o a n s w e r i n g   t h e s e   que r i e s .     2 . 2 .      R e v i e w   o n   Ex i s ti n g   M ap p i n S c h e m e s     M a ppi n s c h e m e s   a r e   e s s e n t i a l   t o   t ra n s f o r m   X M L   i n t o   r e l a t i o n a l   s t o ra ge .   T h e s e   s c h e m e s   c a n   b e   gr o upe i n t o   pa t h - b a s e d,   e dge - b a s e a n n o de - b a s e t e c h ni que .   Z h e t   a l .   [11]  p r o po s e M i n i - X M L ,   w h i c h   i s   a   pa t h - b a s e m a pp i n s c h e m e .   S t r uc t u ra l   r e l a t i o n s   of   M i ni - X M L   c o n s i s t   o ( L e v e l , [P - pa t h Id ,   S - o r de r]),   w h e r e   L e v e l   i n di c a t e s   t h e   de pt h   o f   t h e   c urr e nt   n o d e ,   P - pa t h I i s   t h e   pa t h   i o f   di r e c t   pa r e n t   n o de ,   a n S - o rde i s   t h e   po s i t i o n   o f   c ur r e nt   l e a f   n o de   i n   di r e c t   n o de .   R oo t   l a b e l   i s   (0, [0, 1] ).   A f t e r   t h e   m a pp i n p r o c e s s ,   t h e r e   a r e   t w o   m a ppi ng  t a b l e s   n a m e l y   P a t hT a b l e   a nd  L e a f T a b l e .   T h e   P a t h T a b l e   a s   s h o w n   i n   T a b l e   1 ,   i s   us e t o   ke e p   a l l   pa t h   i n f o rm a t i o n   o f   i nn e r   n o de s ,   w h i l e   t h e   L e a f T a b l e   a s   s h o w n   i n   T a b l e   2 ,   i s   us e t o   ke e l e a f   n o de s   i n f o r m a t i o n.   T h e   a u t h o r s   c o m pa r e t h e   pe r f o r m a n c e   of   M i n i - X M L   a ga i n s t   s - X M L   (c i t a t i o n ),   w h i c h   i ndi c a t e d   t h a t   M i ni - X M L   h a s   b e t t e pe r f o r m a n c e   a n b e t t e s t o ra ge   s pa c e   a s   w e l l   a s   m o r e   s c a l a b l e   t o   s uppo r t   h uge   X M L   da t a .       Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       O R D - G A P a   h y br i d - bas e d   l a be l i ng   s c h e m e s   t o   s uppor t   X M L   dy nam i c   upd at e s   ( A i s y a A m i n )   1599   T a b l e   1 .   P a rt i a l   V i e w   o f   P a t hT a b l e         T a b l e   2 .   P a rt i a l   V i e w   o f   L e a f T a b l e         In   a n o t h e r   a p p r o a c h,   Q t a i s h   a n A hm a [24]   p r o po s e X A n c e s t o r ,   w hi c i s   a l s o   a   p a t h - ba s e m a pp i n t e c hni que .   X A n c e s t o r   c o n t a i n s   o f   X t o D B ,   w h i c h   i s   a   m a ppi ng  a l go r i t hm ,   a n X t o S Q L ,   w h i c h   i s   a   que r y   r e t r i e v a l   a l go ri t hm   a n d   F i xe R D B ,   w h i c i s   a n   i n t e g ra t e s o l ut i o n .   T h e   b e a ut y   of   X A n c e s t o r   a pp r o a c i s   m a pp i n o f   X M L   n o de   i n t o   R D B   w i t h o ut   h a v i n g   t h e   n e e ds   t o   m a t h e   e nt i r e   do c um e n t .   T h i s   m e a n s   t h a t   o n l y   a n c e s t o r   pa t h   w i l l   b e   m a i nt o   R D w h e r e a s ,   t h e   w h o l e   doc um e n t s   t h a t   c o n s i s t   o l e a f - n o de   a n i nn e r - n o de s   w i l l   b e   i gn o r e d.   T hus ,   i t   r e duc e s   t h e   s t o ra ge   s pa c e .   T h e   a l go r i t hm   o f   X A n c e s t o r   h e l ps   t o   ke e t h e   P - a n A - D   r e l a t i o n s hi ps   i n   t ra n s l a t i n S Q L   que r i e s .   F i gu r e   i l l us t ra t e s   i n   t h e   a r c hi t e c t u r e   of   X A n c e s t o r .   A n c e s t o r _P a t h   o f   X A n c e s t o r   S c h e m e   a n L e a f _N o de   of   X A n c e s t o r   S c h e m e   a s   s h o w n   i T a b l e   a n d   4 .             F i gu r e   3 .   X A n c e s t o r   m a ppi n g   a pp r o a c [20 ]     Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   18 ,   N o .   3 J u n e   20 2 :     1 5 9 6   -   1 6 0 6   1600   T a b l e   3 .   A n c e s t o r _P a t h   o f   X A n c e s t o r   S c h e m e         T a b l e   4 .   L e a f _N o de   o f   X A n c e s t o r   S c h e m e         3.   R ES EA R C H   M ET H O D O L O G Y     3 . 1    Th e   A r c h i te c tu r e   D i agr am   T h e r e   f ra m e w o r c o n s i s t s   of   t hr e e   m a i n   c o m po n e n t s :   X M L   P a r s e r,   X M L   E n c o de r ,   a nd  X M L   M a ppe r   a s   s h o w n   i n   F i gu r e   4 .   F i r s t l y ,   t h e   up l o a de X M L   do c um e n t   w i l l   u n de r go   X M L   P a r s e r   f o r   w e l l - fo r m e d n e s s   c h e c ki n g,   a n d   ge t   v a l i da t e b e f o r e   da t a   e xc h a nge   t a ke   pl a c e .   W e   e m pl oy e t h e   S i m p l e   A P f o r   X M L   (S A X pa r s e r   f o r   t h i s .   I n   X M L   E n c o de r ,   X M L   do c um e n t s   a r e   e n c o de a s   a   s e t   o f   s t r e a m s   l a b e l e w i t o ur   pr o po s e l a b e l i n s c h e m e   (de s c r i b e   i n   t h e   n e xt   s e c t i o n ).   In   X M L   M a ppe r,   t h e   X M L   da t a   i s   m a ppe i nt o   R D B .         F i gu r e   4 .   T h e   P r o po s e A r c hi t e c t u r e       3 . 2    P r o p o s e d   Lab e l i n S c h e m e   i n   X M L   En c o n d e r   T h e   l a b e l i n s c h e m e   i s   na m e d   a s   O R D - G A P ,   w h i c h   c om e s   a f t e r   t h e   a pp r o a c h   O R D P A T H   b y   r e s e r v i n g a f o r   f ut u r e   i n s e rt i o n.   T h e   i n i t i a l   l a b e l i n o O R D - G A P   i s   c o m put e b a s e o n   de pt h - f i r s t   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       O R D - G A P a   h y br i d - bas e d   l a be l i ng   s c h e m e s   t o   s uppor t   X M L   dy nam i c   upd at e s   ( A i s y a A m i n )   1601   t r a v e r s a l   i a   f o r m   o f   a   (s - e )l ,   w h e r e   s   a n e   a r e   t h e   s t a r t   a nd  e n o f   t h e   ra n ge ,   a n d   l   r e p r e s e n t s   t h e   l e v e l   of   t h e   n o de .   T h e   s   a nd  e   a r e   c o m put e d   b a s e o n   t h e   g a p ,   w hi c i s   r e s ul t   o f   Σ (m a xf a n - o ut   +   m a xde pt h).   F i gu r e   5   s h o w s   t h e   p a r t i a l   o f   S i gm o dR e c o r da t a s e t   a nn o t a t e w i t h   O R D - G A P .   F i r s t l y ,   t h e   g a m us t   b e   c a l c ul a t e d .   I t h i s   s a m pl e ,   t h e   t r e e   h a s   t h e   l a r ge s t   f a n - o ut   ( m a xf a n - o ut o f   a n de e pe s t   l e v e l   (m a xde pt h o f   6.   A s   s uc h,   t h e   ga i s   1 0.     T h e   r o o t   n o de   b e gi n s   w i t h   (f o r   t h e   s ).   S ub s e que n t l y ,   t h e   t r e e   w i l l   b e   a nn o t a t e b a s e o n   de pt h - f i r s t   t r a v e r s a l .   A s   s uc h,   t h e   s   f o r   t h e   s uc c e e di n n o de ,   ‘i s s ue ’,   w i l l   b e   a s s i g n e w i t h   t h e   p r e v i o us   n o de ’s   s   a dde d   w i t h   t h e   g a (i n   t h i s   c a s e ,   i t   i s   1 + 10) .   T hi s   i s   f o l l ow e by   vo l um e ’,   w h i c h   w i l l   b e   a s s i gn e a s   2 (11+ 10)  f o r   t h e   s   l a b e l .   O n c e   a   l e a f   ha s   b e e n   r e a c h e d,   t h e   e   w i l l   t h e n   b e   g e n e ra t e by   a ddi n g   t h e   p r e v i o u s   r u nni n num b e r   of   s   w i t h   t h e   ga p.   F o r   e xa m pl e ,   t a ke   a   l o o i n t o   t h e   f i r s t   l e a f   n o de   r e a c h e d.   T hi s   n o de   h a s   t h e   s   l a b e l   of   31,   t h us ,   t h e   e   l a b e l   c o m put e w i l l   b e   41.   Co n v e r s e l y ,   i f   t h e   n o de   i s   n o t   a   l e a f   n o de ,   i t ’s   e   l a b e l   w i l l   b e   c o m put e by   a ddi ng  t h e   e   l a b e l   o f   t h e   ri g h t m o s t   c h i l w i t t h e   ga p   b a s e o t h e   de pt h - f i r s t   t r a v e r s a l .             F i gu r e   5 .   T h e   i ni t i a l   l a b e l i n g   o f   O R D - G A P       F i gu r e   s h o w s   t h e   ps e udo c o de s   fo r   O R D - G A P .   F i gur e   6(a )   o ut l i n e s   t h e   G e t G a f un c t i o n .   I t   s h o w s   h o w   t h e   ga p”   i s   c a l c ul a t e d.   T h e   a l go r i t hm   t a ke s   a   n o de   a nd  t h e   n e xt   l e v e l   of   t h e   c urr e nt   n o de   a s   i n pu t .   By   t r a v e r s i n t h e   e nt i r e   c hi l u n de r   t h e   pa rt i c ul a r   n o de ,   i t   w i l l   b e   a b l e   t o   c o un t   t h e   m a xi m u m   n u m b e r   o c h i l d ,   w h i c h   w i l l   t h e n   b e   c o m put e a s   t h e   m a x i m um   f a n - o ut .   S i m i l a r l y ,   t h e   m a xi m um   l e v e l   w i l l   b e   c o m put e a s   t h e   m a x i m u m   de pt o f   t h e   t r e e .     F i gu r e   6(b s h o w s   t h e   A s s i g n L a b e l   f un c t i o n.   B a s e o n   t h e   ga p”   c a l c ul a t e f r o m   G e t G a p   f un c t i o de s c r i b e e a r l i e r ,   t h e   a l go ri t hm   h a s   t h e   p a r e nt   n o de ,   t h e   c urr e nt   ra n ge ,   a n t h e   c urr e nt   l e v e l   a s   t h e   i n pu t .   T h e n,   i t   w i l l   a s s i g n   t h e   s t a rt   o f   t h e   l a b e l   a s   t h e   c urr e nt   r a nge ,   a s   w e l l   a s   t h e   c urr e nt   l e v e l .   B a s e o n   de pt h - f i r s t     ( 1     8 1 1 )   0 ( 1 1 - 6 4 1 )   1 ( 2 1 - 5 1 )   2 ( 6 6 1 - 6 9 1 )   2 ( 6 5 1 - 8 0 1 )   1 ( 6 1 - 9 1 )   2 ( 1 0 1 - 6 3 1 )   2 ( 7 0 1 - 7 3 1 )   2 ( 7 4 1 - 7 9 1 )   2 ( 1 1 1 - 3 4 1 )   3 ( 1 2 1 - 1 5 1 )   4 ( 1 6 1 - 1 9 1 )   4 ( 2 0 1 - 2 3 1 )   4 ( 2 4 1 - 3 3 1 )   4 ( 3 5 1 - 6 2 1 )   3 ( 3 6 1 - 3 9 1 )   4 ( 4 0 1 - 4 3 1 )   4 ( 4 4 1 - 4 7 1 )   4 ( 4 8 1 - 6 1 1 )   4 ( 2 5 1 - 2 8 1 )   5 ( 2 9 1 - 3 2 1 )   5 ( 5 3 1 - 5 6 1 )   5 ( 5 7 1 - 6 0 1 )   5 ( 7 5 1 - 7 6 1 )   3 ( 7 7 1 - 7 8 1 )   3 ( 4 9 1 - 5 2 1 )   5 1 1 ( 3 1 - 4 1 )   3 1 ( 7 1 - 8 1 )   3 1 1 1 ( 7 1 1 - 7 2 1 )   3 ( 6 7 1 - 6 8 1 )   3 S i g m o d R e c o r d A r c h i t e c t u r e   o f   F u t u r e   D a t a b a s e   S y s t e m s 3 0 4 4 L a w r e n c e   A . R o w e M i c h a e l   S t o n e b r a k e r E r r o r   i n   P r o c e s s   s y n c h r o n i z a t i o n   i n   D a t a b a s e   S y s t e m P h i l i p   A . B e r s t e i n M a r c o   A . C a s a n o v a N a t h a n   G o o d m a n 9 2 9 ( 1 3 1 - 1 4 1 )   5 ( 1 7 1 - 1 8 1 )   5 ( 2 1 1 - 2 2 1 )   5 ( 3 7 1 - 3 8 1 )   5 ( 4 1 1 - 4 2 1 )   5 ( 4 5 1 - 4 6 1 )   5 ( 2 6 1 - 2 7 1 )   6 ( 3 0 1 - 3 1 1 )   6 ( 5 0 1 - 5 1 1 )   6 ( 5 4 1 - 5 5 1 )   6 ( 5 8 1 - 5 9 1 )   6 i s s u e i s s u e v o l u m e v o l u m e n u m b e r n u m b e r a r t i c l e s a r t i c l e s a r t i c l e a r t i c l e a r t i c l e a r t i c l e a u t h o r a u t h o r a u t h o r a u t h o r a u t h o r t i t l e t i t l e i n i t P a g e i n i t P a g e e n d P a g e e n d P a g e a u t h o r s a u t h o r s Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   18 ,   N o .   3 J u n e   20 2 :     1 5 9 6   -   1 6 0 6   1602   t r a v e r s a l ,   i t   w i l l   f i r s t   t r a v e r s e   t h e   c h i l n o de s ,   a nd  a s s i g n   e a c h   n o de   w i t h   t h e   s t a rt   a n l e v e l   (s e e   L i n e   10) .   W h e n   t h e   l e a f   n o de   i s   r e a c h e d ,   i t   w i l l   t h e a s s i g t h e   e n d   (w hi c i s   t h e   s um   o f   s t a rt   a n g a p” ) .   T hi s   p r o c e s s   r e pe a t s   u n t i l   e a c h   n o de   i s   l a b e l l e d.                       (a )   (b )     F i gu r e   6 .   A l go r i t hm   f o r   ( a )   F u n c t i o A s s i g n L a b e l   (b F u n c t i o n   G e t G a p       3 . 3    P r o p o s e d   M ap p i n g   S c h e m e   i n   X M L   M ap p e r   W h i l e   a s s i g ni n t h e   O R D - G A P   l a b e l i n g,   t h e   X M L   t r e e   i s   m a ppe i n t o   R D B .   T a b l e   a n T a b l e   de pi c t   t h e   m a ppe r e s ul t .   B a s i c a l l y ,   t h e   i T a b l e   a nd  t T a b l e   a re   c o n s t r uc t e t o   s t o r e   t h e   i nt e rna l   n o de   a n t e xt   n o de   r e s pe c t i v e l y .       T a b l e   5 .   i T a b l e   ( P a r e n t   T a b l e )   S t a rt     E n d     L e v e l     P s t a rt   V a l u e   251   281   5   241   a u t h o r   291   321   5   241   a u t h o r   491   521   5   481   a u t h o r   531   561   5   481   a u t h o r   571   601   5   481   a u t h o r   121   151   4   111   t i t l e   161   191   4   111   i n i t P a g e   201   231   4   111   e n d P a g e   241   331   4   111   a u t h o r s   361   391   4   351   t i t l e   401   431   4   351   i n i t P a g e   441   471   4   351   e n d P a g e   481   611   4   351   a u t h o r s   111   341   3   101   a rt i c l e     351   621   3   101   a rt i c l e     751   761   3   741   a rt i c l e     771   781   3   741   a rt i c l e     21   51   2   11   v o l u m e   61   91   2   11   n u m b e r   101   631   2   11   a rt i c l e s     661   691   2   651   v o l u m e   701   731   2   651   n u m b e r   741   791   2   651   a rt i c l e s   11   641   1   1   i s s u e     65   801   1   1   i s s u e   1   811   0   -   S i g m o d R e c o r d   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       O R D - G A P a   h y br i d - bas e d   l a be l i ng   s c h e m e s   t o   s uppor t   X M L   dy nam i c   upd at e s   ( A i s y a A m i n )   1603   T h e   A - D   r e l a t i o n s hi i s   de t e r m i n e w i t t h e   f o l l o w i n f o r m u l a :     1.   i f ( A ( s )   <   D ( s )   <   A ( e )) .     Ex am p l e   1 :   L e t   n o de b e   vo l um e   (21 - 51 )2  a n n o de b e   S i gm o dR e c o r (1 - 811)0 ,   (S i gm o dR e c o r (1)  <   v o l um e   (21)   <   S i g m o dR e c o r (811) ).   A s   s uc h ,   n o de a n d   n o de h a s   A - D   r e l a t i o n s h i p.         T a b l e   6 .   t T a b l e   (C h i l T a b l e )   S t a rt     E n d     L e v e l     P s t a rt   V a l u e     261     271     6     251     L a w r e n c e   A . R o w e   301   311   6   291   M i c h a e l   S t o n e b ra k e r   501   511   6   491   P h i l i p   A . Be r s t e i n   541   551   6   531   M a rc o   A . Ca s a n o v a   581   591   6   571   N a t h a n   G o o d m a n   131   141   5   121   A r c h i t e c t u r e   o f   F u t u re   D a t a b a s e   S y s t e m s   171   181   5   161   30   211   221   5   201   44   371   381   5   361   E rro r   i n   P ro c e s s   s y n c h r o n i z a t i o n   i n   D a t a b a s e   S y s t e m   411   421   5   401   9   451   461   5   441   29   31   41   3   21   11   71   81   3   61   1   671   681   3   661   11   711   721   3   701   3       T h e   p r o po s e a ppr o a c s uppo rt s   a l l   s t ruc t u ra l   r e l a t i o n s h i ps   w h i c a r e   P - C ,   A - D ,   a nd  s i b l i ng.     T h e   P - C   r e l a t i o n s hi i s   de t e rm i n e w i t t h e   f o l l ow i n g   f o r m u l a :     2.   i f   ( P (s )   <   C( s )   <   P ( e )   )   and  ( C( l e v e l )     P ( l e v e l )   =   1)     3.   P s t ar t   f or   C   = =   S t ar t   f or   P   ( Mappi n S c h e m e )     T h e   f i r s t   c ri t e r i a   i s   t h e   ra n ge ,   w hi c h   i s   s i m i l a r   t o   t h e   c ri t e ri a   f o r   A - D   r e l a t i o n s hi p .   H ow e ve r ,   i t   i s   e s s e n t i a l   t o   c h e c fo r   t h e   l e v e l   d i ff e r e n c e   be t w e e n   t h e   t w o   n o de s ;   i f   t h e   di f f e r e n c e   i s   1,   t h e n,   t h e   t w o   n o de s   a r e   h a v i n g   P - C   r e l a t i o n s hi p .   I t   c a a l s o   b e   de t e r m i n e e a s i l y   f r o m   t h e   t a b l e   by   us i ng  P S t a r t   v a l ue .     Ex am p l e   2 :   L e t   n o de be   vo l um e   (21 - 51)2  a n n o de b e   i s s ue   (11 - 641)1 ,   (i s s ue   ( 11)  <   v o l um e   (21)  <   i s s ue   (641)   a n v o l um e   (2) - a r t i c l e (1)= 1) .   A s   s uc h ,   n o de a n d   n o de h a s   P - C   r e l a t i o n s hi p.     T o   de t e r m i n e   f o r   t h e   s i b l i n r e l a t i o n s h i p ,   i f   t h e   nod e s   hav e   t he   s am e   P St ar t ,   t he y   ar e   ha v i n s i bl i ng   r e l at i ons hi p   Ex am p l e   3:   L e t   n o de be   vo l um e   (661 - 691) a n n o de b e   n u m b e r (701 - 7 31)2 .   F r o m   i T a b l e ,   b o t h   ha v e   P S t a r t   ‘651’ .   A s   s uc h ,   n o de i s   a   s i b l i n g   o f   n o de 2.       3 . 4    S u p p o r f o r   D yn am i c   U p d at e s   T h e   d y n a m i c   upda t e s   a r e   s uppo r t e i n   t h e   p r o po s e a ppr o a c h e a s   t h e r e   i s   n o   r e - l a b e l i n r e qu i r e d.   Fo r   t h e   upda t e s   due   t o   i n s e r t i o n,   w e   a ppl y   t h e   O R D P A T H   l a b e l i n s c h e m e .   I n s e r t i o n   c o n s i s t s   o f   i n s e r t i n g   b e t w e e n   t h e   n o de s ,   i n s e r t   i nt o   t h e   r i g h t - m o s t   a n l e f t - m o s t   no de s .   F o r   i n s e r t i o n   i n v o l v e i n   i n - b e t w e e n   n o de s   a n i n s e r t i o n   i n t o   t h e   r i g h t - m o s t   n o de s ,   t h e   e   v a l ue   o n   t h e   l e f t   s i b l i n w i l l   b e   us e a s   t h e   p r e f i t o   t h e   O R D P A T H   l a b e l .   S i m i l a rl y ,   i n s e rt i o i nt o   t h e   l e f t - m o s t   r e qu i r e s   t h e   l e f t - m o s t   s i b l i n s   v a l ue .     F i gu r e   s h o w s   t h e   e xa m pl e   o f   t h e   t hr e e   t y p e s   o f   i n s e r t i o n.   T h e   do t t e l i n e s   a n do t t e c i r c l e s   i n di c a t e   t h e   i n s e r t i o n   o f   n o de s .   A s   s h ow n   i n   F i gu r e   7,   t h e   l e f t - m o s t   i n s e rt i o n   o f   a   s u b t r e e   o n   t h e   s e c o n l e ve l ,   w i l l   p r o duc e   a   l a b e l   of   (21. 1)2,   f o l l o w e by   i t s   c h i l w i t h   l a b e l   (21. 1 . 1)3 ,   a n de s c e n da nt   w i t h   l a b e l   (21. 1 . 1 . 1)4  r e s pe c t i v e l y .   F o r   t h e   r i g ht m o s t   i n s e rt i o n,   t h e   s   v a l ue   i s   (791 . 1)2  a s   i t   us e s   t h e   e   v a l ue s   o n     t h e   l e f t   s i b l i n g .   M e a n w hi l e ,   f o r   t h e   i n s e rt i o n   i n - b e t w e e n   n o de s ,   i t   us e s   t h e   e   v a l ue   o t h e   l e f t   n o de   (641. 1)2 ,   fo l l ow e d   by   i t s   t w o   c h i l d r e n   w i t h   l a b e l   (641. 1 . 1)2  a n (6 41. 1. 2) 2.   I n   a   w a y ,   t h e   s t r uc t u r e   o f   t h e   l a b e l   r e m a i n s ,   a n t h e   r e t ri e v a l   o f   r e l a t i o b e t w e e n   n o de s   s t i l l   w o r ks   w i t t h e   i n s e rt i o n   n o de .         Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   18 ,   N o .   3 J u n e   20 2 :     1 5 9 6   -   1 6 0 6   1604       F i gu r e   7 .   T h e   p r o po s e a pp r o a c l a b e l i ng  s c h e m e   f o r   i n s e r t i o n       4.   EX P ER I M EN TA EV A LU A TI O N S   A N D   P R ELI M I N A R Y   R ES U LTS   In   t h i s   s e c t i o n,   t h e   pe r f o r m a n c e   of   t h e   p r o po s e a ppr o a c h   w a s   c o m pa r e t o   o t h e a pp r o a c h e s   us i n g   t h e   da t a s e t   o b t a i n e f r o m   U n i v e r s i t y   of   W a s h i ngt o r e po s i t o r y   [25]  a s   t h i s   i s   t h e   s t a nda r d   da t a s e t s   f o r   b e n c h m a r ki ng.   F o t h e   p r e l i m i na r y   e v a l ua t i o n ,   w e   h a v e   o n l y   c o n duc t e e xpe r i m e nt a l   b a s e o n   s t o r i ng  t i m e ,   i . e . ,   t h e   da t a   l o a di ng  t i m e .   T h e   o t h e r   e v a l ua t i o n   o n   t h e   q ue r y   r e s p o n s e   t i m e   w i l l   b e   c a rr i e o ut   i n   o ur     f ut ur e   w o r k.     T a b l e   s h o w s   t h e   de t a i l s   o f   Y a h o o . xm l ,   S i gm o dR e c o r d. x m l   a n D b l p. x m l   da t a s e t s .   T h e   e xpe r i m e n t   w a s   pe r fo r m e o n   a   3. 4 G H z   In t e l   (R Co r e (T M i 7 - 3 770  C P U ,   w i t h   8. 00  G B   R A M   o n   a   W i n do w s   7   H o m e   P r e m i um .   I n   o r de r   t o   o b t a i n   a   b e t t e r   c o n s i s t e n c y ,   t h e   e v a l ua t i o n s   w e r e   e xe c ut e fo r   t hr e e   t i m e s   o n   e a c h   t e s t   c a s e .   T h e   r e s ul t s   o b t a i n e a r e   t h e n   c o m put e a s   t h e   a v e r a ge   o f   t h e s e   t h r e e   c o n s e c ut i ve   r un s .   T a b l e   s h o w s   t h e   i n s e r t i o n   r e s u l t   o n   t h e   t hr e e   s e l e c t e da t a s e t s .     F r o m   t h e   r e s ul t ,   i t   i s   o b s e r v e t ha t   ge n e ra l l y   O R D - G A P   o ut pe r f o r m e t h e   r e s t   o f   t h e   a p p r o a c h e s   i t e rm s   o f   t h e   da t a   l o a di ng  t i m e   by   66%  b e t t e r   a s   c o m pa r e t o   O R D P A T H ,   a n 56%   b e t t e r   a s   c o m pa r e t o   M E   l a b e l i n g.   T hi s   i s   due   t o   t h e   r e a s o n   t h a t   i nt e ge c o m put a t i o n   i s   f a s t e r   a s   c o m pa r e t o   s t r i ng  (O R D P A T H ).   M E   l a b e l i n i s   a l s o   i nt e ge r - b a s e d,   y e t ,   i t   i s   s l o w e r   a s   m u l t i pl i c a t i o n   c a l c ul a t i o i s   n e e de t o   c o m put e   t h e   l a b e l .         T a b l e   7 .   D e s c r i pt i o n   o f   X M L   D a t a s e t s   F i l e n a m e   D e s c r i p t i o n   S i z e   E l e m e n t s   A t t r i b u t e s   M a x - D e p t h   A v g - d e p t h   Y a h o o   . x m l   Y a h o o   a u c t i o n   d a t a   2 4 K B   342   0   5   3 . 7 6 6 0 8   S i g m o d R e c o r d . x m l   S I G M O D   R e c o r d   i n   X M L   4 6 7 K B   11526   3737   6   5 . 1 4 1 0 7   D b l p . x m l   D B L P   B i b l i o g r a p hy   1 2 7 M B   3 3 3 2 1 3 0   4 0 4 2 7 6   6   2 . 9 0 2 2 8       T a b l e   8 .   L o a di n g   T i m e   o f   t h e   A pp r o a c h e s   D a t a s e t   M E   L a b e l i n g   ( m s )   O RD P A T H   ( m s )   O RD - G A P   (m s   Y a h o o . x m l   (2 4 K B)   829   967   432   S i g m o d R e c o r d . x m l   (4 6 7 K B)   1 5 2 4 1   2 0 5 8 1   6224   D b l p . x m l   (1 2 7 M B)   4 6 7 9 8 9 2   6 5 5 1 5 5 4   1 8 0 2 5 5 3       ( 1     8 1 1 )   0 ( 1 1 - 6 4 1 )   1 ( 2 1 - 5 1 )   2 ( 6 6 1 - 6 9 1 )   2 ( 6 5 1 - 8 0 1 )   1 ( 6 1 - 9 1 )   2 ( 1 0 1 - 6 3 1 )   2 ( 7 0 1 - 7 3 1 )   2 ( 7 4 1 - 7 9 1 )   2 ( 1 1 1 - 3 4 1 )   3 ( 1 2 1 - 1 5 1 )   4 ( 1 6 1 - 1 9 1 )   4 ( 2 0 1 - 2 3 1 )   4 ( 2 4 1 - 3 3 1 )   4 ( 3 5 1 - 6 2 1 )   3 ( 3 6 1 - 3 9 1 )   4 ( 4 0 1 - 4 3 1 )   4 ( 4 4 1 - 4 7 1 )   4 ( 4 8 1 - 6 1 1 )   4 ( 2 5 1 - 2 8 1 )   5 ( 2 9 1 - 3 2 1 )   5 ( 5 3 1 - 5 6 1 )   5 ( 5 7 1 - 6 0 1 )   5 ( 7 5 1 - 7 6 1 )   3 ( 7 7 1 - 7 8 1 )   3 ( 4 9 1 - 5 2 1 )   5 1 1 ( 3 1 - 4 1 )   3 1 ( 7 1 - 8 1 )   3 1 1 1 ( 7 1 1 - 7 2 1 )   3 ( 6 7 1 - 6 8 1 )   3 S i g m o d R e c o r d A r c h i t e c t u r e   o f   F u t u r e   D a t a b a s e   S y s t e m s 3 0 4 4 L a w r e n c e   A . R o w e M i c h a e l   S t o n e b r a k e r E r r o r   i n   P r o c e s s   s y n c h r o n i z a t i o n   i n   D a t a b a s e   S y s t e m P h i l i p   A . B e r s t e i n M a r c o   A . C a s a n o v a N a t h a n   G o o d m a n 9 2 9 ( 1 3 1 - 1 4 1 )   5 ( 1 7 1 - 1 8 1 )   5 ( 2 1 1 - 2 2 1 )   5 ( 3 7 1 - 3 8 1 )   5 ( 4 1 1 - 4 2 1 )   5 ( 4 5 1 - 4 6 1 )   5 ( 2 6 1 - 2 7 1 )   6 ( 3 0 1 - 3 1 1 )   6 ( 5 0 1 - 5 1 1 )   6 ( 5 4 1 - 5 5 1 )   6 ( 5 8 1 - 5 9 1 )   6 i s s u e i s s u e v o l u m e v o l u m e n u m b e r n u m b e r a r t i c l e s a r t i c l e s a r t i c l e a r t i c l e a r t i c l e a r t i c l e a u t h o r a u t h o r a u t h o r a u t h o r a u t h o r t i t l e t i t l e i n i t P a g e i n i t P a g e e n d P a g e e n d P a g e a u t h o r s a u t h o r s 2 1 . 1 ( 2 1 . 1 . 1 ) 3 ( 2 1 . 1 . 1 . 1 ) 4 7 9 1 . 1 ( 7 9 1 . 1 . 1 ) 3 ( 7 9 1 . 1 . 1 . 1 ) 4 6 4 1 . 1 ( 6 4 1 . 1 )   2 ( 6 4 1 . 1 . 2 )   2 ( 6 4 1 . 1 . 1 )   3 ( 6 4 1 . 1 . 1 . 2 )   3 Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       O R D - G A P a   h y br i d - bas e d   l a be l i ng   s c h e m e s   t o   s uppor t   X M L   dy nam i c   upd at e s   ( A i s y a A m i n )   1605   5.   C O N C LU S I O N   A N D   F U TU R W O R K S   In  t hi s   pa pe r,   w e   h a v e   r e v i e w e s o m e   e xi s t i n w o r ks   o n   l a b e l i ng  a nd  m a pp i n s c h e m e s .   S ub s e que n t l y ,   w e   h a v e   p r o po s e o ur   l a b e l i n s c h e m e   na m e d   O R D - G A P ,   w h i c h   i s   pe r s i s t e n t   t o   r e - l a b e l i n g ,   a s   t h i s   a pp r o a c h   e xt e n t h e   O R D P A T H   l a b e l i ng  t o   c a t e f o r   a n y   d y n a m i c   upd a t e s .   I n   a dd i t i o n ,   p r e l i m i na r y   e xpe r i m e nt a l   e v a l ua t i o n   ha s   s h o w n   t h a t   O R D - G A P   w o r ks   w e l l   t o   t r a n s f o r m   X M L   i nt o   R D s t o r a ge   i n   t e r m s   of   t h e   l o a di n t i m e .   I n   o u r   f ut u r e   w o r ks ,   w e   w i l l   f ur t h e r   e xp e r i m e nt   w i t h   o t h e r   t y pe s   of  da t a s e t s   (i n   t e rm s   of  s i z e ,   s t r uc t u r e   o f   t h e   da t a s e t ,   t h e   de pt h   l e v e l ,   a nd  s o   o n ).   I n   a ddi t i o n,   t h e   ke y   c r i t e r i o n s   f o r   goo da t a b a s e   a r e ,   i t   s h o ul b e   a b l e   t o   s upp o r t   s t o r a ge   a nd  r e t r i e v a l   e f f i c i e n t l y .   T h us ,   w e   w i l l   a l s o   e v a l ua t e   t h e   t i m e   t a ke n   t r e t ri e v e   v a r i o us   t y pe s   of   s i m pl e   a n d   c o m pl e que r i e s .         A C K N O WL ED G E M EN TS     T h i s   w o r i s   s up po r t e d   by   t h e   f u n di ng  o f   T M   R & D   f r o m   t h e   T e l e ko m   M a l a y s i a ,   M a l a y s i a .         R EF ER EN C ES     [ 1]   K .   S c hw e i ns b e r g ,   a nd  L .   W e g ne r ,   " A dv a nt a g e s   o f   c o m pl e S Q L   t y pe s   i s t o r i ng   X M L   do c um e nt s " ,   F ut ur e   G e n e r at i on   C om p ut e r   Sy s t e m s ,   2 016   ( i n   pr e s s ) .     [ 2]   G . Z .   Q a da h ,   " I nde xi ng   t e c hni q ue s   f o r   p r o c e s s i ng   g e ne r a l i z e X M L   do c um e nt s " ,   C om p ut e r   S t an dar ds   &   I nt e r f ac e s v o l .   49,   p p.   34 - 43 ,   201 7.     [ 3]   S . C .   H a w ,   a nd  C . S .   L e e ,   " N o de   L a be l i ng   S c he m e s   i X M L   Q ue r y   O pt i m i z a t i o n:   A   S ur v e y   a nd  O pe D i s c us s i o n" ,   I E T E   T e c hni c a l   R e v i e w ,   v o l .   26   ( 2 ) ,   pp.   8 9 - 101,   2 009 .   [ 4]   N .   F e r r o ,   a nd  G .   S i l v e l l o ,   " D e s c e nd a n t s ,   a nc e s t o r s ,   c hi l d r e a nd  pa r e n t :   A   s e t - ba s e a p pr o a c t o   e f f i c i e nt l y   a ddr e s s   X P a t h   p r i m i t i v e s " ,   I nf o r m a t i o P r oc e s s i n &   M ana ge m e nt v o l .   52 ( 3) ,   p p.   39 9 - 429,   2 016 .     [ 5]   J . K o pke ,   " A nno t a t i o p a t h s   f o r   m a t c hi ng   X M L - S c he m a s " ,   D a t a   &   K now l e dge   E ngi ne e r i n g ,   20 17  ( i pr e s s ) .     [ 6]   E .   B a r r o s ,   e t   a l . ,   " L C A - ba s e a l g o r i t hm s   f o r   e f f i c i e n t l y   pr o c e s s i ng   m ul t i p l e   ke y w o r que r i e s   o v e r   X M L   s t r e a m s " ,   D at a   &   K no w l e dge   E ngi ne e r i n g ,   v o l .   103 ,   pp. 1 - 18,   20 16 .     [ 7]   Z .   Q i n ,   e t   al . ,   " E f f i c i e nt   X M L   que r y   a nd  upda t e   p r o c e s s i ng   us i n g   a   n ov e l   pr i m e - b a s e m i dd l e   f r a c t i o l a be l i ng   s c he m e " ,   C hi na  C om m un i c a t i ons ,   v o l .   14 ( 3 ) ,   pp .   14 5 - 157,   2 017 .     [ 8]   S .   S ub r a m a n i a m ,   a nd  S . C .   H a w ,   " M E   L a b e l i ng :   A   R o bus t   H y br i S c he m e   f o r   D y na m i c   U pda t e   i X M L   D a t a b a s e s " ,   I E E E   I n t e r na t i o na l   S y m po s i um   on   T e l e c om m u ni c at i on   T e c hnol o gi e s ,   2014 .     [ 9]   J .   L i u,   e t   al . ,   E f f i c i e nt   l a be l i ng   s c he m e   f o r   d y na m i c   X M L   t r e e s , .   I nf o r m a t i o Sc i e nc e s ,   v o l .   221,     pp.   33 8 - 354,   2 01 3 .     [ 10]   P .   F r a i g ni a ud ,   a nd  A .   K o r m a n .   " A O pt i m a l   A nc e s t r y   L a be l i ng   S c he m e   w i t A ppl i c a t i o ns   t o   X M L   T r e e s   a nd   U ni v e r s a l   P o s e t s " ,   J our n al   o f   t he   A C M ,   v o l . 6 ( 1) ,   pp .   6: 1 - 6 : 30,   20 16.     [ 11]   H .   Z hu ,   e t   al . ,   " M i n i - X M L :   A e f f i c i e nt   m a pp i ng  ap pr o ac be t w e e X M L   and  r e l at i ona l   da t ab as e " ,   I E E E / A C I S   16t h   I nt e r n a t i o na l   C o nf e r e nc e   o C o m put e r   a n I nf o r m a t i o S c i e nc e 201 7   [ 12]   T . A .   G ha l e b,   a n S . M o ha m m e d,   " A   D y na m i c   L a be l i ng   S c he m e   B a s e o L og i c a l   O pe r a t o r s :   A   S uppo r t   f o r   O r de r - S e ns i t i v e   X M L   U pda t e s " ,   P r oc e di a   C om pu t e r   Sc i e nc e v o l .   57 ,   pp.   1211 - 121 8,   20 15.     [ 13]   J .   L i u ,   a nd  X . X .   Z ha ng .   " D y na m i c   l a be l i ng   s c he m e   f o r   X M L   upda t e s " ,   K n ow l e dge - B as e Sy s t e m s ,   v o l .   106 ,     pp.   13 5 - 149,   2 016 .     [ 14]   S . C .   H a w ,   a nd  A .   A m i n,   " N o de   I nde xi ng   i X M L   Q ue r y   O pt i m i z a t i o n:   A   R e v i e w " ,   I nd i an  J our na l   of   Sc i e nc e   and  T e c hnol o gy ,   v o l .   8( 32) ,   pp .   1 - 9,   201 5.     [ 15]   C .   Z h a ng ,   e t   a l . ,   " O s u ppo r t i ng  c on t a i nm e nt   que r i e s   i R D B   m an age m e nt   s y s t e m s " ,   A C M   S I G M O D   I nt e r na t i o na l   C o nf e r e nc e   o M a n a g e m e nt   o f   D a t a ,   pp .   425 - 43 6,   20 01.     [ 16]   S .   M o ha m m a d,   a n P .   M a r t i n ,   " L L S :   L e v e l - b as e s   L abe l i ng  S c he m e   f o r   X M L   D a t ab as e s " ,   C o nf e r e nc e   o f   t he   C e n t e r   f o r   A d v a nc e S t udi e s   o C o l l a bo r a t i v e   R e s e a r c h 2010 ,   pp .   115 - 12 7.     [ 17]   I .   T a t a r i no v ,   e t   a l . ,   " S t o r i ng   a nd   Q ue r y i ng   O r de r e d   X M L   u s i ng   a   R D B   S y s t e m " ,   A C M   SI G M O D ,   p p.   20 4 - 15,   20 02 .   [ 18]   L .   F u,   a nd  X ,   M e ng ,   " T r i p l e   C ode :   A n   E f f i c i e n t   L abe l i n Sc he m e   f or   Q ue r y   A ns w e r i ng  i X M L   D at a " ,   W e b   I n f o r m a t i o S y s t e m   a n A ppl i c a t i o C o nf e r e nc e ,   pp.   4 2 - 47,   20 13.     [ 19]   Y .   H e ,   " A   N ov e l   E nc od i ng  Sc he m e   f or   X M L   D oc um e nt   U pda t e - s up por t i n g " ,   I nt e r na t i o na l   C o nf e r e nc e   o A dv a nc e s   i M e c ha ni c a l   E ng i ne e r i ng   a nd   I ndus t r i a l   I nf o r m a t i c s ,   pp .   1 844 - 18 49,   20 15.     [ 20]   D .   G o pi na t h a n,   a nd   K .   A s a w a ,   " N e w   P a t B a s e I nde S t r uc t ur e   f o r   P r o c e s s i ng   C A S   Q ue r i e s   o v e r     X M L   D a t a ba s e " ,   J o ur n al   o f   C om pu t i n and   I n f o r m at i o T e c h nol og y ,   v o l .   25 ( 3 ) ,   pp .   21 1 - 225,   2 017 .     [ 21]   J .   A hn,   e t   a l . , " A   d y na m i c   a nd  pa r a l l e l   a ppr o a c f o r   r e pe t i t i v e   p r i m e   l a b e l i ng   o f   X M L   w i t M a pR e d uc e " ,   T he   J our nal   o f   Supe r c om pu t i n g ,   v o l .   73( 2) ,   pp.   8 10 - 836 ,   2017 .     [ 22]   D . H .   S un ,   a nd  S . C .   H w a ng ,   " A   l a be l i ng   m e t ho ds   f o r   ke y w o r s e a r c o v e r   l a r g e   X M L   doc um e nt s " ,   J our n al   o f   K I I SE ,   v o l .   41 ( 9 ) ,   p p.   69 9 - 706,   2 014 .     [ 23]   S .   M o ha m m e d ,   A . F .   B a r r a da h ,   E . M .   E l - A l f y ,   " S e l e c t i v i t y   e s t i m a t i o o f   e xt e nde X M L   que r y   t r e e   pa t t e r n s   b a s e o pr i m e   num be r   l a be l i ng   a nd  s y no ps i s   m o de l i ng " ,   S i m ul at i on   M ode l l i n P r ac t i c e   and  T he or y ,   v o l .   6 4 ,     pp.   30 - 42 ,   201 6.   [ 24]   A .   Q t a i s h ,   a nd  K .   A hm a d,   " X A n c e s t o r :   A n   e f f i c i e nt   m a ppi ng   a ppr o a c f o r   s t o r i ng   a nd  que r y i ng   X M L   doc um e nt s   i n   r e l a t i o na l   d a t a ba s e   us i ng   p a t h - b a s e t e c hn i que " ,   K now l e dge - B as e Sy s t e m s ,   v o l .   11 4,   pp .   167 - 19 2,   20 16 .     [ 25]   U W ,   20 18.   h t t p: / / w w w . c s . w a s h i ng t o n. e du/ r e s e a r c h/ xm l da t a s e t s / w w w / r e po s i t o r y . ht m l     Evaluation Warning : The document was created with Spire.PDF for Python.