I n t e r n a t i o n a l   J o u r n a l   o f   E l e c t r i c a l   a n d   C o m p u t e r   E n g i n e e r i n g   ( I J E C E )   V o l . 2 ,   N o . 2 ,   A p r i l   2 0 1 2 ,   p p .   2 3 9 ~ 2 4 6   I S S N :   2 0 8 8 - 8 7 0 8             2 3 9       J o u r n a l   h o m e p a g e :   h t t p : / / i a e s j o u r n a l . c o m / o n l i n e / i n d e x . p h p / I J E C E   B r i d g i n g   X M L   a n d   R e l a t i o n a l   D a t a b a s e s :   A n   E f f e c t i v e   M a p p i n g   S c h e m e   b a s e d   o n   P e r s i s t e n t       S a m i n i   S u b r a m a n i a m ,   S u - C h e n g   H a w ,   P o o   K u a n   H o o n g   F a c u l t y   o f   I n f o r m a t i o n   T e c h n o l o g y ,   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 t i c l e   I n f o     A B S T R A C T   A r t i c l e   h i s t o r y :   R e c e i v e d   D e c   1 4 th ,   2 0 1 1   R e v i s e d   M a r   1 s t ,   2 0 1 2   A c c e p t e d   M a r 2 6 th ,   2 0 1 2       X M L   h a s   e m e r g e d   a s   t h e   l e a d i n g   m e d i u m   f o r   d a t a   t r a n s f e r   o v e r   t h e   W o r l d   W i d e   W e b .   A t   t h e   p r e s e n t   d a y s ,   r e l a t i o n a l   d a t a b a s e   i s   s t i l l   w i d e l y   u s e d   a s   t h e   b a c k - e n d   d a t a b a s e   i n   m o s t   o r g a n i z a t i o n s .   S i n c e   t h e r e   i s   m i s m a t c h   i n   t h e s e   t w o   s t r u c t u r e s ,   a n   e f f e c t i v e   m a p p i n g   s c h e m e   i s   d e f i n i t e l y   e s s e n t i a l   t h a t   p r o v i d e s   s e a m l e s s   i n t e g r a t i o n   w i t h   r e l a t i o n a l   d a t a b a s e s .   O n   t h e   o t h e r   h a n d ,   a n   i m m u t a b l e   l a b e l i n g   s c h e m e   i s   c e r t a i n l y   s i g n i f i c a n t   t o   d e n t i f y   t h e   X M L   n o d e s   u n i q u e l y   a s   w e l l   a s   s u p p o r t s   d y n a m i c   u p d a t e   w i t h o u t   h a v i n g   t h e   e x i s t i n g   l a b e l s   t o   b e   r e - l a b e l e d   w h e n   t h e r e   i s   a n   o c c u r a n c e   o f   d y n a m i c   u p d a t e .   A s   s u c h ,   i n   t h i s   p a p e r ,   w e   p r o p o s e   s - X M L   b y   a d o p t i n g   t h e   P e r s i s t e n t   L a b e l i n g   s c h e m e   a s   t h e   a n n o t a t i o n   s c h e m e   t o   e n s u r e   s e a m l e s s   i n t e g r a t i o n   w i t h   r e l a t i o n a l   d a t a b a s e   a n d   a b l e   t o   s u p p o r t   u p d a t e s   w i t h o u t   t h e   n e e d   t o   r e - c o n s t r u c t   t h e   e x i s t i n g   l a b e l s .   W e   c o n d u c t   e x p e r i m e n t s   t o   s h o w   t h a t   s - X M L   p e r f o r m s   b e t t e r   i n   t e r m s   o f   m a p p i n g   t h e   X M L   n o d e s   t o   r e l a t i o n a l   d a t a b a s e s ,   q u e r y   r e t r i e v a l   a n d   d y n a m i c   u p d a t e   c o m p a r e d   t o   t h e   e x i s t i n g   a p p r o a c h e s .   K e y w o r d :   L a b e l i n g   s c h e m e s   M a p p i n g   s c h e m e   P e r s i s t e n t   l a b e l i n g   Q u e r y   p r o c e s s i n g   R e l a t i o n a l   d a t a b a s e s         Co p y r i g h t   ©   2 0 1 2   I n s i t u t e   o f   A d v a n c e d   E n g i n e e e r i n g   a n d   S c i e n c e .     A l l   r i g h t s   r e s e r v e d .   C o r r e s p o n d i n g   A u t h o r :   S a m i n i   S u b r a m a n i a m ,     F a c u l t y   o f   I n f o r m a t i o n   T e c h n o l o g y ,     M u l t i m e d i a   U n i v e r s i t y ,   6 3 1 0 0   C y b e r j a y a ,   M a l a y s i a   E m a i l :   t s 4 2 0 0 3 @ y a h o o . c o m       1 .   I N T R O D U C T I O N   X M L   h a s   e m e r g e d   a s   a   g e n e r i c   m a r k u p   l a n g u a g e   f o r   d o c u m e n t s   a s   w e l l   a s   t h e   d e   f a c t o   s t a n d a r d   f o r   d a t a   e x c h a n g e   o v e r   t h e   W o r l d   W i d e   W e b .   T h e r e   a r e   m a n y   d i f f e r e n t   t y p e s   o f   X M L   d a t a   f o u n d   i n   t o d a y s   d o c u m e n t   r e p o s i t o r i e s ,   d i g i t a l   l i b r a r i e s   a n d   o n   t h e   w e b ,   w h i c h   r a n g e   f r o m   s i m p l e   f l a t   t e x t   w i t h   l i t t l e   m e a n i n g f u l   s t r u c t u r e   t o   b e   q u e r i e d   t o   o v e r   t r u l y   s e m i s t r u c t u r e d   d a t a   w i t h   a   r i c h   a n d   o f t e n   i r r e g u l a r   s t r u c t u r e .   F o r   e x a m p l e ,   a   b u s i n e s s   c a n   e a s i l y   m o d e l   c o m p l e x   s t r u c t u r e s   s u c h   a s   i n v o i c e ,   o r d e r s   a n d   i n v e n t o r y   s y s t e m   i n   X M L   f o r m a t .   I n   a d d i t i o n ,   t h e r e   i s   h u n d r e d s   o f   X M L   s c h e m a   d e f i n e d   t o   e n c o d e   d a t a   i n t o   X M L   f o r m a t   f o r   s p e c i f i c   a p p l i c a t i o n   d o m a i n s .     O n   t h e   o t h e r   h a n d ,   r e l a t i o n a l   d a t a b a s e   d r i v e   m o s t   b u s i n e s s e s   o f   a n y   s i z e   t o d a y .     N e v e r t h e l e s s ,   r e l a t i o n a l   d a t a b a s e   c a n n o t   m e e t   a l l   t h e   d e m a n d s   o f   e l e c t r o n i c   b u s i n e s s   b e c a u s e   i t   p r o c e s s   d a t a   i n d e p e n d e n t l y   o f   t h e   c o n t e x t .   I n   o t h e r   w o r d s ,   r e l a t i o n a l   d a t a b a s e   i s   s i m p l y   n o t   a   g o o d   m a t c h   f o r   s e m i - s t r u c t u r e d   c o n t e n t   r e p r e s e n t e d   i n   X M L .     H o w e v e r ,   s i n c e   e n t e r p r i s e s   h a v e   i n v e s t e d   t r i l l i o n s   o f   d o l l a r s   i n   r e l a t i o n a l   d a t a b a s e ,   t h e y   w o u l d   b e   m u c h   r e l u c t a n t   t o   s i m p l y   r e p l a c e   r e l a t i o n a l   d a t a b a s e   w i t h   a   p u r e   X M L   s t o r e .     D u e   t o   t h e   d e m a n d   f o r   s t o r i n g   a n d   q u e r y i n g   X M L   d a t a ,   e s p e c i a l l y   f o r   d a t a   e x c h a n g e ,   a   m a p p e r   t o   s t o r e   a n d   r e t r i e v e   X M L   ( a   t r e e   s t r u c t u r e )   v i a   r e l a t i o n a l   d a t a b a s e   ( t a b l e s   w i t h   r o w s   a n d   c o l u m n s )   a n d   v i c e - v e r s a   i s   d e f i n i t e l y   e s s e n t i a l .   S i n c e   t h e r e   a r e   m i s m a t c h e s   b e t w e e n   t h e   X M L - s t r u c t u r e d   d a t a   a n d   r e l a t i o n a l   d a t a ,   m a p p i n g   p l a y s   a n   i m p o r t a n t   r o l e   i n   p r o v i d i n g   s e a m l e s s   i n t e g r a t i o n   b e t w e e n   t h e s e   d a t a b a s e   i n f r a s t r u c t u r e s .     T h e r e   a r e   f o u r   b a s i c   r e l a t i o n s h i p s   t h a t   a   g o o d   m a p p i n g   a p p r o a c h   n e e d s   t o   c a t e r   f o r ;   t h e   a n c e s t o r - d e s c e n d a n t ,   p a r e n t - c h i l d ,   s i b l i n g   a n d   l e v e l   r e l a t i o n s h i p s .   T h e s e   i n f o r m a t i o n   a r e   k n o w n   a s   s t r u c t u r a l   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 8 - 8 7 0 8   I J E C E     V o l .   2 ,   N o .   2 ,     A p r i l   2 0 1 2   :     2 3 9     2 4 6   2 4 0 r e l a t i o n s h i p   n e e d   t o   b e   s t o r e d   i n   t h e   r e l a t i o n a l   t a b l e s   t o   i d e n t i f y   t h e   c o n n e c t i o n   b e t w e e n   t h e   n o d e s   i n   t h e   X M L   d o c u m e n t .   T h i s   e n a b l e s   t h e   u s e r s   q u e r i e s   t o   b e   p r o c e s s e d   c o m p e t e n t l y .   T h e   d i l e m m a   t h a t   h a s   b e e n   e n d u r i n g   f o r   s o m e t i m e   i s   t o   c o m e   u p   w i t h   a   m a p p i n g   s c h e m e   t h a t   c a n   p r e s e r v e   b a s i c   r e l a t i o n s h i p s   a m o n g   t h e   n o d e s   f o r   p r o f i c i e n t   X M L   p r o c e s s i n g .   B a s i c a l l y ,   t h e r e   a r e   t w o   t y p e s   o f   u s e r   q u e r i e s ,   w h i c h   a r e   f u l l - t e x t   q u e r y   a n d   s t r u c t u r a l   q u e r y .   M a n y   e x i s t i n g   a p p r o a c h e s   s u p p o r t s   f u l l - t e x t   q u e r y   b u t   b e   o b l i v i o u s   t o   t h e   s t r u c t u r a l   o n e   w h i c h   r e s u l t s   i n   i n c o n s i s t e n c i e s   i n   q u e r y   r e t r i e v a l   a n d   i n c a p a b l e   t o   f u r n i s h   a n y   q u e r y   w i t h   t h e   c o m b i n a t i o n s   o f   m u l t i p l e   c r i t e r i a .   A p a r t   f r o m   t h e   s u p p o r t   f o r   b o t h   t y p e s   o f   q u e r i e s ,   a   g o o d   l a b e l i n g   s c h e m e   m u s t   b e   a b l e   t o   s u p p o r t   d y n a m i c   u p d a t e s .   D y n a m i c   u p d a t e   r e f e r s   t o   t h e   u p d a t i n g   p r o c e s s   ( i n s e r t i o n   o f   n e w   n o d e ( s )   a n d   d e l e t i o n   o f   e x i s t i n g   n o d e ( s ) )   t o   t h e   o r i g i n a l   X M L   d a t a   s o u r c e .   A   g o o d   l a b e l i n g   m e t h o d   s h o u l d   g e n e r a t e   i m m u t a b l e   l a b e l s   t h a t   d o e s   n o t   r e q u i r e   m o d i f i c a t i o n   d u r i n g   t h e   o c c u r a n c e   o f   d y n a m i c   u p d a t e .     T h e   r e s t   o f   t h e   p a p e r   i s   o r g a n i z e d   a s   f o l l o w s .   S e c t i o n   2   i l l u s t r a t e s   s o m e   r e v i e w   o n   t h e   e x i s t i n g   m a p p i n g   s c h e m e s .   S e c t i o n   3   d e s c r i b e s   t h e   n e w   m a p p i n g   s c h e m e ,   s - X M L .   S e c t i o n   4   e x p l a i n s   t h e   e x p e r i m e n t a l   d e s i g n ,   e x p e r i m e n t a l   r e s u l t s   a n d   d i s c u s s i o n s .   F i n a l l y ,   S e c t i o n   5   c o n c l u d e s   t h e   p a p e r .       2 .   R E L A T E D   W O R K   T h e r e   a r e   m a n y   m a p p i n g   t e c h n i q u e s   s u c h   a s   t h e   R e l a t i o n a l   D T D   a p p r o a c h   [ 1 3 ] ,   t h e   E d g e   a p p r o a c h   [ 3 ]   a n d   t h e   A t t r i b u t e   a p p r o a c h   [ 8 ] .   T h e   R e l a t i o n a l   D T D   a p p r o a c h   [ 1 3 ]   m a p s   X M L   d a t a   b a s e d   o n   t h e   f r e q u e n c y   o f   t h e   e l e m e n t   o c c u r r e n c e   i n   a n   X M L   d o c u m e n t .   T h e   e l i m i n a t i o n   o f   l e s s   i m p o r t a n t   e l e m e n t s   a n d   g r o u p i n g   o f   e l e m e n t s   b a s e d   o n   i n c i d e n c e   a l l o w s   l e s s e r   s p a c e   c o n s u m e d ,   s t r a i g h t f o r w a r d   t a b l e   s c h e m a   a n d   e f f i c i e n t   m a p p i n g   t o   t a b l e s .   H o w e v e r ,   t h i s   a p p r o a c h   c a n   o n l y   b e   u s e d   i f   t h e   D a t a   T y p e   D e f i n i t i o n   ( D T D )   o r   X M L   s c h e m a   o f   a n   X M L   d o c u m e n t   i s   a v a i l a b l e .   I n   E d g e   a p p r o a c h   [ 3 ] ,   X M L   d o c u m e n t   i s   s h r e d   i n t o   a   s i n g l e   r e l a t i o n a l   t a b l e .   A s   s u c h ,   t h i s   a p p r o a c h   m a y   s u f f e r s   f r o m   e x c e s s i v e   t a b l e   s i z e   e r r o r   a n d   m u l t i p l e   s e l f - j o i n s   m a y   b e   r e q u i r e   f o r   q u e r y   r e t r i e v a l .     A t t r i b u t e   a p p r o a c h   [ 8 ]   c r e a t e s   a s   m u c h   t a b l e   a s   d i s t i n c t   e l e m e n t   n a m e   t h a t   a p p e a r   i n   t h e   d o c u m e n t   i n t o   d i f f e r e n t   r e l a t i o n a l   t a b l e s .   T h i s   i s   o n e   o f   t h e   d r a w b a c k s   o f   t h e   A t t r i b u t e   a p p r o a c h   w h e r e   t h e   n u m b e r   o f   t a b l e s   d e p e n d s   o n   t h e   d i s t i n c t   e l e m e n t   n a m e s   i n   X M L   d o c u m e n t .     A n   a u t o m a t i c   m a p p i n g   t e c h n i q u e   w a s   p r o p o s e d   [ 7 ]   f r o m   a n   X M L   d o c u m e n t   t o   r e l a t i o n a l   d a t a b a s e s   e s p e c i a l l y   t h e   n e s t e d   s t r u c t u r e   o f   t h e   X M L   d o c u m e n t s   i s   p r e s e r v e d .   A s s o c i a t i o n   i n l i n i n g   w a s   p r o p o s e d   [ 1 2 ] ,   a   n e w   i n l i n i n g   m e t h o d ,   f o r   m a p p i n g   D T D   t o   r e l a t i o n a l   t a b l e s   b y   i m p r o v i n g   t h e i r   e a r l i e r   v e r s i o n s   o f   i n l i n i n g   m e t h o d s ,   i . e . ,   S h a r e d   i n l i n i n g   a n d   H y b r i d   i n l i n i n g   t o   r e d u c e   f r a g m e n t s   a n d   e x c e s s i v e   j o i n s .   A   l o s s l e s s   s c h e m a   m a p p i n g   a l g o r i t h m   w a s   p r o p o s e d   [ 1 ]   t o   g e n e r a t e   a   d a t a b a s e   s c h e m a   f r o m   a   D T D ,   w h i c h   m a k e s   s e v e r a l   i m p r o v e m e n t s   o v e r   e x i s t i n g   a l g o r i t h m s .   I n   a d d i t i o n ,   t h e y   a l s o   p r o p o s e d   t w o   l i n e a r   d a t a   m a p p i n g   a l g o r i t h m s   b a s e d   o n   D o c u m e n t   O b j e c t   M o d e l   ( D O M )   a n d   S i m p l e   A P I   f o r   X M L   ( S A X ) ,   r e s p e c t i v e l y ,   t o   m a p   o r d e r e d   X M L   d a t a   i n t o   r e l a t i o n a l   d a t a .   N e v e r t h e l e s s ,   t h e s e   m a p p i n g   t e c h n i q u e s   a r e   u n a b l e   t o   s u p p o r t   d y n a m i c   u p d a t e ,   a n   i m p o r t a n t   f e a t u r e   t o   s u p p o r t   e v e r - c h a n g i n g   e n v i r o n m e n t   b e c a u s e   o f   t h e   l i m i t a t i o n   o f   t h e   l a b e l i n g   s c h e m e   i n   t e r m s   o f   p e r s i s t e n c y .     A   g o o d   l a b e l i n g   s c h e m e   i s   c e r t a i n l y   n e e d e d   t o   e n s u r e   t h a t   t h e   l a b e l s   g e n e r a t e d   t o   u n i q u e l y   i d e n t i f y   X M L   n o d e s   a r e   i m m u t a b l e   a t   a n y   p o i n t   o f   t i m e ;   t o   b e   e x a c t   d u r i n g   d y n a m i c   u p d a t e .   D y n a m i c   u p d a t e   c o m p r i s e s   o f   u p d a t i n g   p r o c e s s e s   ( i n s e r t i o n   o f   n e w   n o d e ( s ) ,   d e l e t i o n   o f   e x i s t i n g   n o d e ( s )   o r   a n y   k i n d   o f   u p d a t i n g   p r o c e s s e s )   w h i c h   h a p p e n   a t   a n y   p o i n t   o f   t i m e   a n d   r e q u i r e   t h e   e x i s t i n g   l a b e l s   t o   b e   m a i n t a i n e d   w h i l e   g e n e r a t i n g   n e w   l a b e l s   f o r   t h e   n e w   n o d e s .   S e v e r a l   l a b e l i n g   s c h e m e   [ 1 1 ]   [ 1 4 ]   [ 5 ]   [ 9 ]   h a v e   b e e n   p r o p o s e d   w h i c h   c a n   b e   b r o a d l y   c l a s s i f i e d   i n t o   f o u r   m a i n   c a t e g o r i e s ;   n a m e l y ,   S u b t r e e ,   P r e f i x - b a s e d ,   M u l t i p l i c a t i v e   a n d   H y b r i d   [ 6 ] .     N e v e r t h e l e s s ,   n o t   m a n y   e x i s t i n g   l a b e l i n g   s c h e m e s   s u p p o r t   d y n a m i c   u p d a t e   e s p e c i a l l y   i n   s i t u a t i o n   w h e r e   a   m a s s i v e   u p d a t e s   a r e   r e q u i r e d .   Y e t ,   w e   o b s e r v e d   t h a t   u n d e r   h e a v y   u p d a t e ,   p r e f i x - b a s e d   s c h e m e   m a y   n o t   n e e d   t o   b e   r e - g e n e r a t e d .     A s   s u c h ,   w e   a d o p t   t h e   P e r s i s t e n t   L a b e l i n g   ( o n e   o f   t h e   p r e f i x - b a s e d   s c h e m e )   a s   t h e   l a b e l i n g   s c h e m e   i n   o u r   p r o p o s e   m a p p i n g   t e c h n i q u e .   I n   o r d e r   t o   s h o w   t h e   f e a s i b i l i t y   o f   o u r   m a p p i n g   a p p r o a c h ,   w e   e v a l u a t e   t h e   ( 1 )   q u e r y   r e s p o n s e   t i m e   n e e d e d   t o   r e t r i e v e   a   s e t   o f   q u e r i e s ,   ( 2 )   t i m e   r e q u i r e d   f o r   i n s e r t i o n ,   a n d   ( 3 )   t i m e   r e q u i r e d   f o r   d e l e t i o n   a g a i n s t   t h e   e x i s t i n g   t e c h n i q u e s .         3 .   s - X M L :   O U R   P R O P O S E D   A P P R O A C H   4 . 1 .   B a c k g r o u n d   o f   P e r s i s t e n t   L a b e l i n g   S c h e m e   I n   X M L ,   t h e r e   a r e   f o u r   m a i n   h i e r a r c h i c a l   r e l a t i o n s h i p s   n a m e l y   p a r e n t - c h i l d ,   a n c e s t o r - d e s c e n d a n t ,   s i b l i n g   a n d   l e v e l .   A   c o m p a c t   a n d   r o b u s t   l a b e l i n g   s c h e m e   i s   e s s e n t i a l   t o   a l l o w   q u i c k   d e t e r m i n a t i o n   o f   t h e s e   r e l a t i o n s h i p s   b e t w e e n   p a i r   o f   n o d e s .   I n   P e r s i s t e n t   L a b e l i n g   [ 4 ] ,   e a c h   n o d e   i s   l a b e l e d   a s   ( l , [ n p , d p ] , [ n , d ] ) ,   w h e r e   l   i s   t h e   l e v e l   o f   t h e   n o d e   i n   t h e   t r e e ,   [ n , d ]   i s   t h e   l o c a l   l a b e l   o f   t h e   n o d e ,   [ n p , d p ]   i s   t h e   l o c a l   l a b e l   o f   t h e   p a r e n t   n o d e .   P a r e n t   l a b e l   o f   a   n o d e   i s   t h e   s e l f   l a b e l   o f   t h e   p a r e n t   n o d e .     Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E       B r i d g i n g   X M L   a n d   R e l a t i o n a l   D a t a b a s e s :   A n   E f f e c t i v e   M a p p i n g   S c h e m e   b a s e d   o n   F i g u r e     1   e x p l a i n s   h o w   t h e   [       F i g u r e   2   s h o w s   a n   e x a m p l e   o f   l a b e l i n g   s c h e m e   b a s e d   o n   P e r s i s t e n t   L a b e l i n g   w i l l   b e   l a b e l e d   a s   ( 0 , [ 1 , 1 ] )   w h e r e   0   r e p r e s e n t s   t h e   l e v e l   a n d   [ 1 , 1 ]   r e p r e s e n t s   t h e   l o c a l   l a b e l   o f   t h e   n o d e .   T h i s   e l e m e n t   d o e s   n o t   h a v e   a   p a r e n t   l a b e l   s i n c e   t ( 1 , [ 1 , 1 ] , [ 1 , 1 ] ) .   i . e . ,   t h e   b o o k   r e s i d e   i n   l e v e l   1 ,   w i t h   t h e   p a r e n t   n o d e   l a b e l e d   a s   [ 1 , 1 ]   a n d   b o o k   i s   t h e   f i r s t   c h i l d   [ 1 , 1 ]   a m o n g   i t s   s i b l i n g .   L e t   u s   t a k e   a n o t h e r   e x a m p l e .   T h e   p u b l i s h [ 1 , 1 ] , [ 5 , 1 ] ) ,   w h e r e   2   i n d i c a t e s   t h a t   p u b l i s h e r   i s   i n   t h e   l e v e l   2 ,   [ 1 , 1 ]   d e n o t e s   t h e   p a r e n t s   l a b e l   o f   p u b l i s h e r   ( w h i c h   i n   t h i s   c a s e   t h e   l o c a l   l a b e l   f o r   b o o k ) ,   [ 5 , 1 ]   i s   t h e   o r d i n a l   o c c u r r e n c e   o f   p u b l i s h e r   a m o n g ( p u b l i s h e r   i s   t h e   5 th   c h i l d   o f   b o o k ) .           F i g u r e   2 .   T h e   l a b e l i n g   s c h e m e   a d o p t e d   f r o m   P e r s i s t e n t   L a b e l i n g       I n   t e r m s   o f   s u p p o r t   f o r   t h e   n e w   i n s e r t e d   n o d e ,   n e w   l a b e l s   w i l l   b e   g e n e r a t e d   b a s e d   o n   t h e   f o l l o w i n g   r u l e s   [ 4 ] .       L e t   C   b e   a   n o d e   t o   b e   i n s e r t e d ,   w h i l e   N o d e   A   a n d   N o d e   B   a r e   t h e   s i b l i n g   o f   N o d e   C . a )   N o d e   C   ( c i , c j )   i s   i n s e r t e d   b e f o r e   N o d e   A   p r o v i d e d   t h a t   n o   n o d e s   b e f o r e   N o d e   A .   L a b e l   C   =     ( s e e   F i g u r e   3 ( a ) ) .   b )   N o d e   C   i s   i n s e r t e d   a f t e r   N o d e   B   p r o v i d e d   t h a t   n o   n o d e s   a f t e r   N o d e   B F i g u r e   3 ( b ) ) .   c )   N o d e   C   i s   i n s e r t e d   b e t w e e n   N o d e   A   a n d   N o d e   B .   L a b e l   C   =   ( c i , c j )   c a n   b e   c o m p u t e d   a s   f o l l o w s :   c i   =   b i .   a j   +   a i .   b j   /   d ;   c j   =   2 .   a j .   b j   /   d ;     w h e r e   d   i s   H i g h e s t   C o m m o n   F a c t o r   f o r   ( b i . a j   +   a i . b j )   a n d   ( 2 . a j . F i g u r e   3 ( c ) ) .   B a s e d   o n   t h e   b e a u t i f u l   f e a t u r e s   o f   p e r s i s t e n t   l a b e l i n g   s u c h   a s   s u p p o r t s   f o r   t h e   f o u r   h i e r a r c h i c a l   r e l a t i o n s h i p s   a n d   t h e   s u p p o r t   f o r   d y n a m i c   u p d a t e ,   w e   a d o p t   t h e   l a b e l i n g   s c h e m e   i n   o u r   a p p r o a c h .     4 . 2 .   s - X M L   T a b l e   S c h e m a   I n   s - X M L ,   t h e r e   a r e   t w o   t a b l e s   n a m e l y   t h e   P a r e n t T a b l e   a n d   t h e   C h i l d T a b l e .   A l l   n o d e s   i n   t h e   X M L   w i l l   b e   s h r e d   i n t o   t h e   t w o   t a b l e s .   T h e   P a r e n t T a b l e   s t o r e s   a l l   t h e   i n t e r n a l   n o d e s   ( a n n o t a t e d   b a s e d   o n   P e r s i s t e n t   L a b e l i n g   e l a b o r a t e d   e a r l i e r   i n   S e c t i o n   3 . 1 ) ,   w h i l e   t h e   C h i l d T a b l e   m a i n t a i n s   l e a f   n o d e s   i n f o r m a t i o n .   T h e   s c h e m a s   o f   t h e   t a b l e s   a r e   e l l a b o r a t e d   a s   b e l o w .   P a r e n t T a b l e   ( I d N o d e ,   p N a m e ,   c N a m e ,   L e v e l ,   L P a r e n t ,   S e l f L a b e l ) a )   I d N o d e   -   u n i q u e l y   i d e n t i f y   t h e   n o d e s   I S S N :   2 0 8 8 - 8 7 0 8   B r i d g i n g   X M L   a n d   R e l a t i o n a l   D a t a b a s e s :   A n   E f f e c t i v e   M a p p i n g   S c h e m e   b a s e d   o n   .   1   e x p l a i n s   h o w   t h e   [ n , d ]   a n d   [ n p , d p ]   i s   a s s i g n e d .     F i g u r e   1 .   E x p l a n a t i o n   f o r   [ n , d ]   a n d   [ n p , d p ]   2   s h o w s   a n   e x a m p l e   o f   l a b e l i n g   s c h e m e   b a s e d   o n   P e r s i s t e n t   L a b e l i n g   w i l l   b e   l a b e l e d   a s   ( 0 , [ 1 , 1 ] )   w h e r e   0   r e p r e s e n t s   t h e   l e v e l   a n d   [ 1 , 1 ]   r e p r e s e n t s   t h e   l o c a l   l a b e l   o f   t h e   n o d e .   T h i s   e l e m e n t   d o e s   n o t   h a v e   a   p a r e n t   l a b e l   s i n c e   t h e   n o d e   i s   t h e   o r i g i n   o f   t h e   X M L   t r e e .   N e x t ,   t h e   l a b e l   f o r   b o o k   i s   ( 1 , [ 1 , 1 ] , [ 1 , 1 ] ) .   i . e . ,   t h e   b o o k   r e s i d e   i n   l e v e l   1 ,   w i t h   t h e   p a r e n t   n o d e   l a b e l e d   a s   [ 1 , 1 ]   a n d   b o o k   i s   t h e   f i r s t   c h i l d   [ 1 , 1 ]   a m o n g   i t s   s i b l i n g .   L e t   u s   t a k e   a n o t h e r   e x a m p l e .   T h e   p u b l i s h e r   i s   a n n o t a t e d   w i t h   t h e   l a b e l   o f   ( 2 ,   [ 1 , 1 ] , [ 5 , 1 ] ) ,   w h e r e   2   i n d i c a t e s   t h a t   p u b l i s h e r   i s   i n   t h e   l e v e l   2 ,   [ 1 , 1 ]   d e n o t e s   t h e   p a r e n t s   l a b e l   o f   p u b l i s h e r   ( w h i c h   i n   t h i s   c a s e   t h e   l o c a l   l a b e l   f o r   b o o k ) ,   [ 5 , 1 ]   i s   t h e   o r d i n a l   o c c u r r e n c e   o f   p u b l i s h e r   a m o n g c h i l d   o f   b o o k ) .               T h e   l a b e l i n g   s c h e m e   a d o p t e d   f r o m   P e r s i s t e n t   L a b e l i n g   I n   t e r m s   o f   s u p p o r t   f o r   t h e   n e w   i n s e r t e d   n o d e ,   n e w   l a b e l s   w i l l   b e   g e n e r a t e d   b a s e d   o n   t h e   f o l l o w i n g   t o   b e   i n s e r t e d ,   w h i l e   N o d e   A   a n d   N o d e   B   a r e   t h e   s i b l i n g   o f   N o d e   C . N o d e   C   ( c i , c j )   i s   i n s e r t e d   b e f o r e   N o d e   A   p r o v i d e d   t h a t   n o   n o d e s   b e f o r e   N o d e   A .   L a b e l   C   =     N o d e   C   i s   i n s e r t e d   a f t e r   N o d e   B   p r o v i d e d   t h a t   n o   n o d e s   a f t e r   N o d e   B .   L a b e l   C   =   ( c i , c j )   =     ( b i   +   1 , b j )   ( s e e   N o d e   C   i s   i n s e r t e d   b e t w e e n   N o d e   A   a n d   N o d e   B .   L a b e l   C   =   ( c i , c j )   c a n   b e   c o m p u t e d   a s   f o l l o w s :   c i   =   b i .   a j   +   a i .   b j   /   d ;   c j   =   2 .   a j .   b j   /   d ;     w h e r e   d   i s   H i g h e s t   C o m m o n   F a c t o r   f o r   ( b i . a j   +   a i . b j )   a n d   ( 2 . a j . B a s e d   o n   t h e   b e a u t i f u l   f e a t u r e s   o f   p e r s i s t e n t   l a b e l i n g   s u c h   a s   s u p p o r t s   f o r   t h e   f o u r   h i e r a r c h i c a l   r e l a t i o n s h i p s   a n d   t h e   s u p p o r t   f o r   d y n a m i c   u p d a t e ,   w e   a d o p t   t h e   l a b e l i n g   s c h e m e   i n   o u r   a p p r o a c h .   X M L ,   t h e r e   a r e   t w o   t a b l e s   n a m e l y   t h e   P a r e n t T a b l e   a n d   t h e   C h i l d T a b l e .   A l l   n o d e s   i n   t h e   X M L   w i l l   b e   s h r e d   i n t o   t h e   t w o   t a b l e s .   T h e   P a r e n t T a b l e   s t o r e s   a l l   t h e   i n t e r n a l   n o d e s   ( a n n o t a t e d   b a s e d   o n   P e r s i s t e n t   e l i n g   e l a b o r a t e d   e a r l i e r   i n   S e c t i o n   3 . 1 ) ,   w h i l e   t h e   C h i l d T a b l e   m a i n t a i n s   l e a f   n o d e s   i n f o r m a t i o n .   T h e   s c h e m a s   o f   t h e   t a b l e s   a r e   e l l a b o r a t e d   a s   b e l o w .   ( I d N o d e ,   p N a m e ,   c N a m e ,   L e v e l ,   L P a r e n t ,   S e l f L a b e l )   w h e r e :   u n i q u e l y   i d e n t i f y   t h e   n o d e s   s t o r e d   i n   t h e   P a r e n t T a b l e   ( a s s i g n e d   b a s e d   o n   b r e a t h   .   ( S a m i n i   S u b r a m a n i a m )   2 4 1   2   s h o w s   a n   e x a m p l e   o f   l a b e l i n g   s c h e m e   b a s e d   o n   P e r s i s t e n t   L a b e l i n g   [ 4 ] .   T h e   r o o t   e l e m e n t   w i l l   b e   l a b e l e d   a s   ( 0 , [ 1 , 1 ] )   w h e r e   0   r e p r e s e n t s   t h e   l e v e l   a n d   [ 1 , 1 ]   r e p r e s e n t s   t h e   l o c a l   l a b e l   o f   t h e   n o d e .   T h i s   h e   n o d e   i s   t h e   o r i g i n   o f   t h e   X M L   t r e e .   N e x t ,   t h e   l a b e l   f o r   b o o k   i s   ( 1 , [ 1 , 1 ] , [ 1 , 1 ] ) .   i . e . ,   t h e   b o o k   r e s i d e   i n   l e v e l   1 ,   w i t h   t h e   p a r e n t   n o d e   l a b e l e d   a s   [ 1 , 1 ]   a n d   b o o k   i s   t h e   f i r s t   e r   i s   a n n o t a t e d   w i t h   t h e   l a b e l   o f   ( 2 ,   [ 1 , 1 ] , [ 5 , 1 ] ) ,   w h e r e   2   i n d i c a t e s   t h a t   p u b l i s h e r   i s   i n   t h e   l e v e l   2 ,   [ 1 , 1 ]   d e n o t e s   t h e   p a r e n t s   l a b e l   o f   p u b l i s h e r   ( w h i c h   i n   t h i s   c a s e   t h e   l o c a l   l a b e l   f o r   b o o k ) ,   [ 5 , 1 ]   i s   t h e   o r d i n a l   o c c u r r e n c e   o f   p u b l i s h e r   a m o n g   i t s   s i b l i n g   T h e   l a b e l i n g   s c h e m e   a d o p t e d   f r o m   P e r s i s t e n t   L a b e l i n g     I n   t e r m s   o f   s u p p o r t   f o r   t h e   n e w   i n s e r t e d   n o d e ,   n e w   l a b e l s   w i l l   b e   g e n e r a t e d   b a s e d   o n   t h e   f o l l o w i n g   t o   b e   i n s e r t e d ,   w h i l e   N o d e   A   a n d   N o d e   B   a r e   t h e   s i b l i n g   o f   N o d e   C .   N o d e   C   ( c i , c j )   i s   i n s e r t e d   b e f o r e   N o d e   A   p r o v i d e d   t h a t   n o   n o d e s   b e f o r e   N o d e   A .   L a b e l   C   =       ( a i   - 1 , a j )   .   L a b e l   C   =   ( c i , c j )   =     ( b i   +   1 , b j )   ( s e e   N o d e   C   i s   i n s e r t e d   b e t w e e n   N o d e   A   a n d   N o d e   B .   L a b e l   C   =   ( c i , c j )   c a n   b e   c o m p u t e d   a s   f o l l o w s :   c i   =   b i .   a j   +   a i .   b j   /   d ;   c j   =   2 .   a j .   b j   /   d ;     w h e r e   d   i s   H i g h e s t   C o m m o n   F a c t o r   f o r   ( b i . a j   +   a i . b j )   a n d   ( 2 . a j . b j )   ( s e e   B a s e d   o n   t h e   b e a u t i f u l   f e a t u r e s   o f   p e r s i s t e n t   l a b e l i n g   s u c h   a s   s u p p o r t s   f o r   t h e   f o u r   h i e r a r c h i c a l   r e l a t i o n s h i p s   a n d   t h e   s u p p o r t   f o r   d y n a m i c   u p d a t e ,   w e   a d o p t   t h e   l a b e l i n g   s c h e m e   i n   o u r   a p p r o a c h .     X M L ,   t h e r e   a r e   t w o   t a b l e s   n a m e l y   t h e   P a r e n t T a b l e   a n d   t h e   C h i l d T a b l e .   A l l   n o d e s   i n   t h e   X M L   w i l l   b e   s h r e d   i n t o   t h e   t w o   t a b l e s .   T h e   P a r e n t T a b l e   s t o r e s   a l l   t h e   i n t e r n a l   n o d e s   ( a n n o t a t e d   b a s e d   o n   P e r s i s t e n t   e l i n g   e l a b o r a t e d   e a r l i e r   i n   S e c t i o n   3 . 1 ) ,   w h i l e   t h e   C h i l d T a b l e   m a i n t a i n s   l e a f   n o d e s   i n f o r m a t i o n .   T h e   s t o r e d   i n   t h e   P a r e n t T a b l e   ( a s s i g n e d   b a s e d   o n   b r e a t h - f i r s t   t r a v e r s a l ) .   Evaluation Warning : The document was created with Spire.PDF for Python.
                I J E C E     V o l .   2 ,   N o .   2 ,     A p r i l   2 0 1 2 2 4 2 b )   p N a m e - s t o r e s   p a r e n t   n o d e   n a m e . c )   c N a m e - m a i n t a i n s   c h i l d   n a m e . d )   L e v e l - m a i n t a i n s   l e v e l   i n f o r m a t i o n e )   L P a r e n t     m a i n t a i n s   t h e   p a r e n t   l a b e l   o f   t h e   n o d e   w h i c h   s t o r e s   t h e   r e f e r e n c e   o f   t h e   p a r e n t   l a b f )   S e l f L a b e l   -   m a i n t a i n s   t h e   s e l f     S c e n a r i o     ( a )     ( b )   ( c )   F i g u r e   3 .   N e w   l a b e l s   g e n e r a t e d   d u e   t o   i n s e r t i     F i g u r e   4 .     T h e   s t r u c t u r e   a n d   s a m p l e   d a t a   o f   s     C h i l d T a b l e   ( I d N o d e ,   L e v e l ,   p N a m e ,   S e l f L a b e l ,   L P a r e n t , V a l u e ) a )   I d N o d e   -   u n i q u e l y   i d e n t i f i e s   t h e   n o d e s   s t o r e d   i n   t h e   C h i l d T a b l e   ( a s s i g n t r a v e r s a l ) .   b )   L e v e l   -   s t o r e s   t h e   l e v e l   i n f o r m a t i o n   o f   t h e   n o d e   i n   t h e   X M L   d o c u m e n t . c )   p N a m e   -   s t o r e s   t h e   e l e m e n t   n a m e   o f   t h e   p a r e n t   n o d e   2   :     2 3 9     2 4 6   s t o r e s   p a r e n t   n o d e   n a m e .   m a i n t a i n s   c h i l d   n a m e .   m a i n t a i n s   l e v e l   i n f o r m a t i o n   m a i n t a i n s   t h e   p a r e n t   l a b e l   o f   t h e   n o d e   w h i c h   s t o r e s   t h e   r e f e r e n c e   o f   t h e   p a r e n t   l a b m a i n t a i n s   t h e   s e l f - l a b e l   o r   l o c a l   l a b e l   o f   t h e   n o d e   w h i c h   i s   [ n , d ]   i n   P e r s i s t e n t   L a b e l i n g .   T e c h n i q u e   t o   G e n e r a t e   U n i q u e   L a b e l   N o d e   C   i s   i n s e r t e d   b e f o r e   N o d e   A   p r o v i d e d   t h a t   n o   n o d e s   b e f o r e   N o d e   A ;     L a b e l   C   =   ( c i , c j )   : -     ( c i , c j )   =   ( a i   - 1 , a j )   N o d e   C   i s   i n s e r t e d   a f t e r     N o d e   B   p r o v i d e d   t h a t   n o   n o d e s   a f t e r   N o d e   B   a f t e r   N o d e   B ;     L a b e l   C   =   ( c i , c j )   : -   ( c i , c j )   =     ( b i   +   1 , b j )       N o d e   C   i s   i n s e r t e d   b e t w e e n   N o d e   A   a n d   N o d e   B     L a b e l   C   =   ( c i , c j )   c i   =   b i .   a j   +   a i .   b j   /   d   c j   =   2 .   a j .   b j   /   d                 :   w h e r e   d   i s   H i g h e s t   C o m m o n   F a c t o r   f o r                   ( b i . a j   +   a i . b j )   a n d   ( 2 . a j . b j )     F i g u r e   3 .   N e w   l a b e l s   g e n e r a t e d   d u e   t o   i n s e r t i o n   i n   P e r s i s t e n t   L a b e l i n g F i g u r e   4 .     T h e   s t r u c t u r e   a n d   s a m p l e   d a t a   o f   s - X M L   ( I d N o d e ,   L e v e l ,   p N a m e ,   S e l f L a b e l ,   L P a r e n t , V a l u e )   w h e r e :   u n i q u e l y   i d e n t i f i e s   t h e   n o d e s   s t o r e d   i n   t h e   C h i l d T a b l e   ( a s s i g n e d   b a s e d   o n   b r e a t h s t o r e s   t h e   l e v e l   i n f o r m a t i o n   o f   t h e   n o d e   i n   t h e   X M L   d o c u m e n t .   s t o r e s   t h e   e l e m e n t   n a m e   o f   t h e   p a r e n t   n o d e   m a p p i n g               I S S N :   2 0 8 8 - 8 7 0 8   m a i n t a i n s   t h e   p a r e n t   l a b e l   o f   t h e   n o d e   w h i c h   s t o r e s   t h e   r e f e r e n c e   o f   t h e   p a r e n t   l a b e l   ( I d N o d e ) .   l a b e l   o r   l o c a l   l a b e l   o f   t h e   n o d e   w h i c h   i s   [ n , d ]   i n   P e r s i s t e n t   L a b e l i n g .     N o d e   C   i s   i n s e r t e d   b e f o r e   N o d e   A   p r o v i d e d   t h a t   n o   n o d e s   b e f o r e   N o d e   N o d e   C   i s   i n s e r t e d   a f t e r     N o d e   B   p r o v i d e d   t h a t   n o   n o d e s   a f t e r   N o d e   B   o n   i n   P e r s i s t e n t   L a b e l i n g   e d   b a s e d   o n   b r e a t h - f i r s t   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E       B r i d g i n g   X M L   a n d   R e l a t i o n a l   D a t a b a s e s :   A n   E f f e c t i v e   M a p p i n g   S c h e m e   b a s e d   o n   d )   S e l f L a b e l   -   m a i n t a i n s   t h e   s e l f e )   L P a r e n t -   m a i n t a i n s   t h e   p a r e n t   l a b e l   o f   t h e   n o d e   w h i c h   s t o r e s   t h e   r e f e r e n c e   o f   t h e   p a r e n t   l a b e l   ( I d N o d e )   f r o m   t h e   P a r e n t T a b l e .   f )   V a l u e -   s t o r e s   t h e   v a l u e   o f   t h e   n o d e F i g u r e   4   i l l u s t r a t e s   s o m e   s a m p l e   d a t a   a f t e r   t h e   a n n o t a t i o n   a n d   m a p p i n g   p r o c e s s e s t h e   i n i t i a l   t r i p l e t s   o f   P e r s i s t e n t   L a b e l i n g   ( l e v e l ,   [ p a r e n t   l a b e l ] ,   [ l o c a l   l a b e l ] )   i s   s h r e d d e d   i n t o   t h r e e   c o l u m n s   n a m e l y ,   L e v e l ,   L P a r e n t   a n d   S e l f L a b e l . d e t e r m i n e d   f r o m   s - X M L .         P a r e n t A n c e s t o r   S i b l i n g   r e l a t i o n s h i p   L e v e l               4 .   E X P E R I M E N T A L   D E S I G N 4 . 1 .   E x p e r i m e n t a l   S e t u p   W e   h a v e   i m p l e m e n t e d   s - X M L   u s i n g   I n t e l l i J   I D E A   C o m m u n i t y   E d i t i o n   9 . 0 . 1   u s i n g   J D K   1 . 5 . 0   a n d   M y S Q L   a s   t h e   d a t a b a s e .   E x p e r i m e n t s   h a v e   b e e n   c a r r i e d   o u t   o n   t h e   U n i v e r s i t y   o f   W a s h i n g t o n   X M L   r e p o s i t o r y   [ 1 5 ] .   A l l   o u r   e x p e r i m e n t s   a r e   p e r f o r m e d   o n   A c e r   I n t e l   P e n t i u m   d u a l - c o r e   p r o c e s s o r   T 2 3 9 0   w i t h   1 6 0   G B   H D D   a n d   1 G B   D D R 2 .   A l l   n u m b e r s   p r e s e n t e d   h e r e   a r e   p r o d u c e d   b y   r u n n i n g   t h e   e x p e r i m e n t s   f i v e   t i m e s   a n d   a v e r a g i n g   t h e   e x e c u t i o n   t i m e s   o f   s e v e r a l   c o n s e c u t i v e   r u n s .     4 . 2 .   P e r f o r m a n c e   R e s u l t s   M a p p i n g   t o   R e l a t i o n a l   D a t a b a s e T h e   f i r s t   e x p e r i m e n t   w a s   c o n d u c t e d   t o   e v a l u a t e   t h e   e f f i c i e n c y   t h e   m a p p i n g   s c h e m e   t o   m a p   t h e   X M L   d a t a   t o   r e l a t i o n a l   d a t a b a s e .   s - X M L   w a s   c o m p a r e d   a g a i n s t   t h e   e x i s t i n g   m a p p i n g   a p p r o a c h e s   s u c h   a s   t h e   E d g e ,   A t t r i b u t e   a n d   D T D   s c h e m e s .   T h e   r e s u l t s   o f   t h e   e x p e r i m e n t s   a r e   s h o w n   i n   F i g u r e   6 . T h e   e x p e r i m e n t a l   r e s u l t s   s h o w   t h a t   E d g e   a p p r o a c h   t o o k   t h e   l o n g e s t   t i m e   t o   m a p   t h e   X M L   d a t a   t o   r e l a t i o n a l   d a t a b a s e ,   f o l l o w e d   b y   A t t r i b u t e   a n d   D T D   m a p p i n g   s c h e m e s .   T h i s   i s   d u e   t o   t h e   f a c t   t h a t   E d g e   a p p r o a c h   i s   o n l y   p r a c t i c a l   w h e n   s m a l l e r   d a t a s e t   i s   c o n c e r n   b e c a u s e E d g e   t a b l e .   T h i s   c o n s e q u e n c e   w i l l   b e   a n   i n v e r s e   w h e n   l a r g e r   d a t a s e t   i s   c o n c e r n   b c a u s e   i t   c o m p l i c a t e s   t h e   m a p p i n g   p r o c e s s   a n d   d a t a   m a n a g e m e n t   b e c o m e s   i n e f f i c i e n t .   T h e   d e l a y   i n   A t t r i b u t e   a n d   D T D   m a p p i n g   s c h e m e s   a r e   c a u s e d   b y   t h e   p r o p e r t y   o f   t h e s e   s c h e m e s   t h a t   i s   t o   c r e a t e   t a b l e s   b a s e d   o n   d i c t i n c t   e l e m e n t   n a m e s   t h a t   a p p e a r   i n   a n   X M L   d o c u m e n t   a n d   t a b l e   c r e a t i o n s   d e p e n d s   o n   t h e   c a r d i n a l i t y   o f   t h e   e l e m e n t s   i n   t h e   D T D   d o c u m e n t   r e s p e c t i v e l y .   T h e   s - t e c h n i q u e s   a n d   t h e   d a t a   i s   w e l l   d i s t r i b u t e d   a m o n g   a d e q u a t e   n u m b e r   o f   t a b l e s   w h e r e b y   t h e   n u m b e r   o f   t h e   t a b l e s   a n d   f o r m a t   o f   t h e   t a b l e s   a r e   f i x e d   r e g a r l e s s   o f   t h e   c o m p l e x i t y   o f   t h e   X M L   d o c u m e n t .   Q u e r y   P r o c e s s i n g   T a b l e   1   s h o w s   t h e   d e s c r i p t i o n   o n   t h e   q u e r y   p e r f o r m e d   o n   t h e   l i n e i t e m   d a t a s e t   s t o r e d   i n   r e l a t i o n a l   d a t a b a s e .   U s i n g   r e l a t i o n a l   d a t a b a s e   a s   t h e   u n d e r l y i n g   s t o r a g e ,   t h e   q u e r y   i s   w r i t t e n   b a s e d   o n   S t r u c t u r e d   Q u e r y   L a n g u a g e   ( S Q L )   c o m m a n d .   T h e   t i m e   t a k e n   t o   r e t r i e v e   t h e s h o w s   t h e   p e r f o r m a n c e   c o m p a r i s o n .   I S S N :   2 0 8 8 - 8 7 0 8   B r i d g i n g   X M L   a n d   R e l a t i o n a l   D a t a b a s e s :   A n   E f f e c t i v e   M a p p i n g   S c h e m e   b a s e d   o n   .   1 .   G e t   L P a r e n t   o f   N o d e   2   i n   C h i l d T a b l e   2 .   U s e   L P a r e n t   t o   t r a c e   i d N o d e   i n   P a r e n t T a b l e 3 . G e t   p N a m e   f r o m   P a r e n t T a b l e   b a s e d   o n   t h e   i d N o d e   m a i n t a i n s   t h e   s e l f - l a b e l   o r   l o c a l   l a b e l   o f   t h e   n o d e   n o d e   w h i c h   i s   [ n , d ]   i n   P e r s i s t e n t   m a i n t a i n s   t h e   p a r e n t   l a b e l   o f   t h e   n o d e   w h i c h   s t o r e s   t h e   r e f e r e n c e   o f   t h e   p a r e n t   l a b e l   ( I d N o d e )   s t o r e s   t h e   v a l u e   o f   t h e   n o d e   F i g u r e   4   i l l u s t r a t e s   s o m e   s a m p l e   d a t a   a f t e r   t h e   a n n o t a t i o n   a n d   m a p p i n g   p r o c e s s e s t h e   i n i t i a l   t r i p l e t s   o f   P e r s i s t e n t   L a b e l i n g   ( l e v e l ,   [ p a r e n t   l a b e l ] ,   [ l o c a l   l a b e l ] )   i s   s h r e d d e d   i n t o   t h r e e   c o l u m n s   n a m e l y ,   L e v e l ,   L P a r e n t   a n d   S e l f L a b e l .   F i g u r e   5   i l l u s t r a t e s   h o w   t h e   h i e r a r c h i c a l   r e l a t i o n s h i p s   c o u l d   b e   P a r e n t - c h i l d   r e l a t i o n s h i p     A n c e s t o r - D e s c e n d a n t   r e l a t i o n s h i p     S i b l i n g   r e l a t i o n s h i p     L e v e l           1 .   L e v e l   i n f o r m a t i o n   f o r   n o n - l e a f   n o d e   i s   s t o r e d   i n   P a r e n t T a b l e     2 .   L e v e l   f o r   l e a f   n o d e   i s   m a i n t a i n e d   i n   C h i l d T a b l e .   F i g u r e   5 .   R e l a t i o n s h i p   s u p p o r t e d   b y   s - X M L   E X P E R I M E N T A L   D E S I G N   X M L   u s i n g   I n t e l l i J   I D E A   C o m m u n i t y   E d i t i o n   9 . 0 . 1   u s i n g   J D K   1 . 5 . 0   a n d   M y S Q L   a s   t h e   d a t a b a s e .   E x p e r i m e n t s   h a v e   b e e n   c a r r i e d   o u t   o n   t h e   l i n e i t e m   d a t a s e t   o b t a i n e d   f r o m   t h e   U n i v e r s i t y   o f   W a s h i n g t o n   X M L   r e p o s i t o r y   [ 1 5 ] .   A l l   o u r   e x p e r i m e n t s   a r e   p e r f o r m e d   o n   A c e r   I n t e l   P e n t i u m   c o r e   p r o c e s s o r   T 2 3 9 0   w i t h   1 6 0   G B   H D D   a n d   1 G B   D D R 2 .   A l l   n u m b e r s   p r e s e n t e d   h e r e   a r e   p r o d u c e d   b y   n t s   f i v e   t i m e s   a n d   a v e r a g i n g   t h e   e x e c u t i o n   t i m e s   o f   s e v e r a l   c o n s e c u t i v e   r u n s .   M a p p i n g   t o   R e l a t i o n a l   D a t a b a s e   T h e   f i r s t   e x p e r i m e n t   w a s   c o n d u c t e d   t o   e v a l u a t e   t h e   e f f i c i e n c y   t h e   m a p p i n g   s c h e m e   t o   m a p   t h e   X M L   X M L   w a s   c o m p a r e d   a g a i n s t   t h e   e x i s t i n g   m a p p i n g   a p p r o a c h e s   s u c h   a s   t h e   E d g e ,   A t t r i b u t e   a n d   D T D   s c h e m e s .   T h e   r e s u l t s   o f   t h e   e x p e r i m e n t s   a r e   s h o w n   i n   F i g u r e   6 .   p e r i m e n t a l   r e s u l t s   s h o w   t h a t   E d g e   a p p r o a c h   t o o k   t h e   l o n g e s t   t i m e   t o   m a p   t h e   X M L   d a t a   t o   r e l a t i o n a l   d a t a b a s e ,   f o l l o w e d   b y   A t t r i b u t e   a n d   D T D   m a p p i n g   s c h e m e s .   T h i s   i s   d u e   t o   t h e   f a c t   t h a t   E d g e   a p p r o a c h   i s   o n l y   p r a c t i c a l   w h e n   s m a l l e r   d a t a s e t   i s   c o n c e r n   b e c a u s e   t h e   e n t i r e   d o c u m e n t   i s   l o a d e d   i n t o   s i n g l e   E d g e   t a b l e .   T h i s   c o n s e q u e n c e   w i l l   b e   a n   i n v e r s e   w h e n   l a r g e r   d a t a s e t   i s   c o n c e r n   b c a u s e   i t   c o m p l i c a t e s   t h e   m a p p i n g   p r o c e s s   a n d   d a t a   m a n a g e m e n t   b e c o m e s   i n e f f i c i e n t .   T h e   d e l a y   i n   A t t r i b u t e   a n d   D T D   m a p p i n g   c a u s e d   b y   t h e   p r o p e r t y   o f   t h e s e   s c h e m e s   t h a t   i s   t o   c r e a t e   t a b l e s   b a s e d   o n   d i c t i n c t   e l e m e n t   n a m e s   t h a t   a p p e a r   i n   a n   X M L   d o c u m e n t   a n d   t a b l e   c r e a t i o n s   d e p e n d s   o n   t h e   c a r d i n a l i t y   o f   t h e   e l e m e n t s   i n   t h e   D T D   - X M L   m a p p i n g   s c h e m e   p e r f o r m e d   t h e   b e s t   d u e   t o   i t s   s i m p l e   m a p p i n g   t e c h n i q u e s   a n d   t h e   d a t a   i s   w e l l   d i s t r i b u t e d   a m o n g   a d e q u a t e   n u m b e r   o f   t a b l e s   w h e r e b y   t h e   n u m b e r   o f   t h e   t a b l e s   a n d   f o r m a t   o f   t h e   t a b l e s   a r e   f i x e d   r e g a r l e s s   o f   t h e   c o m p l e x i t y   o f   t h e   X M L   d o c u m e n t . 1   s h o w s   t h e   d e s c r i p t i o n   o n   t h e   q u e r y   p e r f o r m e d   o n   t h e   l i n e i t e m   d a t a s e t   s t o r e d   i n   r e l a t i o n a l   d a t a b a s e .   U s i n g   r e l a t i o n a l   d a t a b a s e   a s   t h e   u n d e r l y i n g   s t o r a g e ,   t h e   q u e r y   i s   w r i t t e n   b a s e d   o n   S t r u c t u r e d   Q u e r y   L a n g u a g e   ( S Q L )   c o m m a n d .   T h e   t i m e   t a k e n   t o   r e t r i e v e   t h e   q u e r i e s   i s   d e p i c t e d   i n   T a b l e   2   w h i l e   F i g u r e   7   s h o w s   t h e   p e r f o r m a n c e   c o m p a r i s o n .   1 .   G e t   L P a r e n t   o f   N o d e   2   i n   C h i l d T a b l e   2 .   U s e   L P a r e n t   t o   t r a c e   i d N o d e   i n   P a r e n t T a b l e 3 .   G e t   t h e   L P a r e n t   o f   t h e   l o c a t e d   i n   P a r e n t T a b l e 4 .   T r a c e   L P a r e n t   u s i n g   S t e p   4   u n t i l   N o d e   1   i s   r e a c h e d   1 .   G e t   L P a r e n t   o f   a   N o d e   2   f r o m   C h i l d T a b l e 2 .   U s e   L P a r e n t   t o   g e t   i d N o d e     f r o m   P a r e n t T a b l e 3 .   I f   L P a r e n t   o f   N o d e   2   i s   s a m e   w i t h   N o d e   2   ( g e t   L P a r e n t           s i m i l a r   w i t h   N o d e   2 )   t h e n   N o d e   2   a n d   N o d e   3   a r e   s i b l i n g s     .   ( S a m i n i   S u b r a m a n i a m )   2 4 3 2 .   U s e   L P a r e n t   t o   t r a c e   i d N o d e   i n   P a r e n t T a b l e   3 . G e t   p N a m e   f r o m   P a r e n t T a b l e   b a s e d   o n   t h e   i d N o d e   l a b e l   o r   l o c a l   l a b e l   o f   t h e   n o d e   n o d e   w h i c h   i s   [ n , d ]   i n   P e r s i s t e n t   L a b e l i n g .   m a i n t a i n s   t h e   p a r e n t   l a b e l   o f   t h e   n o d e   w h i c h   s t o r e s   t h e   r e f e r e n c e   o f   t h e   p a r e n t   l a b e l   ( I d N o d e )       F i g u r e   4   i l l u s t r a t e s   s o m e   s a m p l e   d a t a   a f t e r   t h e   a n n o t a t i o n   a n d   m a p p i n g   p r o c e s s e s .   F r o m   F i g u r e   4 ,   t h e   i n i t i a l   t r i p l e t s   o f   P e r s i s t e n t   L a b e l i n g   ( l e v e l ,   [ p a r e n t   l a b e l ] ,   [ l o c a l   l a b e l ] )   i s   s h r e d d e d   i n t o   t h r e e   c o l u m n s   r c h i c a l   r e l a t i o n s h i p s   c o u l d   b e   X M L   u s i n g   I n t e l l i J   I D E A   C o m m u n i t y   E d i t i o n   9 . 0 . 1   u s i n g   J D K   1 . 5 . 0   a n d   l i n e i t e m   d a t a s e t   o b t a i n e d   f r o m   t h e   U n i v e r s i t y   o f   W a s h i n g t o n   X M L   r e p o s i t o r y   [ 1 5 ] .   A l l   o u r   e x p e r i m e n t s   a r e   p e r f o r m e d   o n   A c e r   I n t e l   P e n t i u m   c o r e   p r o c e s s o r   T 2 3 9 0   w i t h   1 6 0   G B   H D D   a n d   1 G B   D D R 2 .   A l l   n u m b e r s   p r e s e n t e d   h e r e   a r e   p r o d u c e d   b y   n t s   f i v e   t i m e s   a n d   a v e r a g i n g   t h e   e x e c u t i o n   t i m e s   o f   s e v e r a l   c o n s e c u t i v e   r u n s .     T h e   f i r s t   e x p e r i m e n t   w a s   c o n d u c t e d   t o   e v a l u a t e   t h e   e f f i c i e n c y   t h e   m a p p i n g   s c h e m e   t o   m a p   t h e   X M L   X M L   w a s   c o m p a r e d   a g a i n s t   t h e   e x i s t i n g   m a p p i n g   a p p r o a c h e s   s u c h   a s   t h e   E d g e ,   p e r i m e n t a l   r e s u l t s   s h o w   t h a t   E d g e   a p p r o a c h   t o o k   t h e   l o n g e s t   t i m e   t o   m a p   t h e   X M L   d a t a   t o   r e l a t i o n a l   d a t a b a s e ,   f o l l o w e d   b y   A t t r i b u t e   a n d   D T D   m a p p i n g   s c h e m e s .   T h i s   i s   d u e   t o   t h e   f a c t   t h a t   E d g e   t h e   e n t i r e   d o c u m e n t   i s   l o a d e d   i n t o   s i n g l e   E d g e   t a b l e .   T h i s   c o n s e q u e n c e   w i l l   b e   a n   i n v e r s e   w h e n   l a r g e r   d a t a s e t   i s   c o n c e r n   b c a u s e   i t   c o m p l i c a t e s   t h e   m a p p i n g   p r o c e s s   a n d   d a t a   m a n a g e m e n t   b e c o m e s   i n e f f i c i e n t .   T h e   d e l a y   i n   A t t r i b u t e   a n d   D T D   m a p p i n g   c a u s e d   b y   t h e   p r o p e r t y   o f   t h e s e   s c h e m e s   t h a t   i s   t o   c r e a t e   t a b l e s   b a s e d   o n   d i c t i n c t   e l e m e n t   n a m e s   t h a t   a p p e a r   i n   a n   X M L   d o c u m e n t   a n d   t a b l e   c r e a t i o n s   d e p e n d s   o n   t h e   c a r d i n a l i t y   o f   t h e   e l e m e n t s   i n   t h e   D T D   m e d   t h e   b e s t   d u e   t o   i t s   s i m p l e   m a p p i n g   t e c h n i q u e s   a n d   t h e   d a t a   i s   w e l l   d i s t r i b u t e d   a m o n g   a d e q u a t e   n u m b e r   o f   t a b l e s   w h e r e b y   t h e   n u m b e r   o f   t h e   t a b l e s   a n d   f o r m a t   o f   t h e   t a b l e s   a r e   f i x e d   r e g a r l e s s   o f   t h e   c o m p l e x i t y   o f   t h e   X M L   d o c u m e n t .   1   s h o w s   t h e   d e s c r i p t i o n   o n   t h e   q u e r y   p e r f o r m e d   o n   t h e   l i n e i t e m   d a t a s e t   s t o r e d   i n   r e l a t i o n a l   d a t a b a s e .   U s i n g   r e l a t i o n a l   d a t a b a s e   a s   t h e   u n d e r l y i n g   s t o r a g e ,   t h e   q u e r y   i s   w r i t t e n   b a s e d   o n   S t r u c t u r e d   Q u e r y   q u e r i e s   i s   d e p i c t e d   i n   T a b l e   2   w h i l e   F i g u r e   7   2 .   U s e   L P a r e n t   t o   t r a c e   i d N o d e   i n   P a r e n t T a b l e   3 .   G e t   t h e   L P a r e n t   o f   t h e   l o c a t e d   i n   P a r e n t T a b l e   4 .   T r a c e   L P a r e n t   u s i n g   S t e p   4   u n t i l   N o d e   1   i s   r e a c h e d   1 .   G e t   L P a r e n t   o f   a   N o d e   2   f r o m   C h i l d T a b l e   2 .   U s e   L P a r e n t   t o   g e t   i d N o d e     f r o m   P a r e n t T a b l e   r e n t   o f   N o d e   2   i s   s a m e   w i t h   N o d e   2   ( g e t   L P a r e n t     s i m i l a r   w i t h   N o d e   2 )   t h e n   N o d e   2   a n d   N o d e   3   a r e   s i b l i n g s     Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 8 - 8 7 0 8   I J E C E     V o l .   2 ,   N o .   2 ,     A p r i l   2 0 1 2   :     2 3 9     2 4 6   2 4 4 T a b l e   1 .     Q u e r y   d e s c r i p t i o n   f o r   l i t e i t e m   d a t a s e t                       T a b l e   2 .   T h e   S Q L   c o m m a n d   a n d   q u e r y   r e t r i e v a l   t i m e   f o r   E d g e ,   A t t r i b u t e ,   r e l a t i o n a l   D T D     a n d   s - X M L   a p p r o a c h e s .   A p p r o a c h   Q u e r y 1   T i m e   ( m s )   E d g e   s e l e c t   *   f r o m   e d g e t a b l e   w h e r e   d a t a   l i k e   c a r e f u l   p a c k a g e s   w a k e %   1 0 3 3   A t t r i b u t e   s e l e c t   *   f r o m   t   w h e r e   t a r g e t I D   =   ( s e l e c t   s o u r c e I D   f r o m   L _ C O M M E N T   w h e r e   d a t a   =   c a r e f u l   p a c k a g e s   w a k e % )   3 1 5   D T D   s e l e c t     *   f r o m   L _ C O M M E N T   w h e r e   d a t a     l i k e   c a r e f u l   p a c k a g e s   w a k e %   2 5 2   s - X M L   s e l e c t   p a r e n t N a m e   f r o m   c h i l d t a b l e   w h e r e   v a l u e   =   c a r e f u l   p a c k a g e s   w a k e .   2 1 8   A p p r o a c h   Q u e r y 2   T i m e   ( m s )   E d g e   s e l e c t   s u m ( d a t a )   f r o m   e d g e t a b l e   w h e r e   t a g   = ' L _ Q U A N T I T Y '   1 6 4 6   A t t r i b u t e   s e l e c t   s u m ( d a t a )   f r o m   l _ q u a n t i t y   4 9 5   D T D   s e l e c t   s u m ( d a t a )   f r o m   l _ q u a n t i t y   2 7 9   s - X M L   s e l e c t   s u m ( d a t a )   f r o m   c h i l d t a b l e   w h e r e   p a r e n t N a m e = L _ Q U A N T I T Y   3 1 0   A p p r o a c h   Q u e r y 3   T i m e   ( m s )   E d g e   s e l e c t   s h i p . d a t a   f r o m   E d g e t a b l e   s h i p ,   E d g e t a b l e   c o m m e n t T ,   E d g e t a b l e   t ,   E d g e t a b l e   t a b l e 1   w h e r e   s h i p . t a g = ' L _ S H I P I N S T R U C T '   a n d   c o m m e n t T . t a g = ' L _ C O M M E N T '   a n d   t . t a g = ' T '   a n d   t a b l e 1 . t a g = ' t a b l e '   a n d   t a b l e 1 . t a r g e t I D = t . s o u r c e I D   a n d   t . t a r g e t I D   =   s h i p . s o u r c e I D   a n d   s h i p . s o u r c e I D   =   c o m m e n t T . s o u r c e I D a n d   c o m m e n t T . d a t a   l i k e   ' e v e n   a c c o u n t s   c a j o l e   s l y l y % '   5 3 4 6   A t t r i b u t e   s e l e c t   s h i p . d a t a   f r o m   l _ s h i p i n s t r u c t 3   s h i p ,   l _ c o m m e n t 3   c o m m ,   t 3   t ,   t a b l e 3   t b   w h e r e   t b . t a r g e t I D   =   t . s o u r c e I D   a n d   t . t a r g e t I D   =   c o m m . s o u r c e I D   a n d   c o m m . s o u r c e I D   =   s h i p . s o u r c e I D   a n d   c o m m . d a t a   l i k e   ' e v e n   a c c o u n t s   c a j o l e   s l y l y % '   9 2 1   D T D   s e l e c t   t . L _ S H I P I N S T R U C T   f r o m   t 1   t ,   l _ c o m m e n t 1   c m ,   t a b l e   t b   w h e r e   t b . i d   =   t . p a r e n t I D   a n d     t . p a r e n t I D   =   c m . p a r e n t I D   a n d   c m . t e x t   =   ' e v e n   a c c o u n t s   c a j o l e   s l y l y '     5 3 7   s - X M L   s e l e c t   v a l u e   f r o m   c h i l d t a b l e   w h e r e   p a r e n t L a b e l   =   ( s e l e c t   s e l f L a b e l   f r o m   p a r e n t t a b l e   w h e r e   p a r e n t N a m e   =   ' L _ S H I P I N S T R U C T '   a n d   p a r e n t L a b e l   =   ( s e l e c t   p a r e n t L a b e l   f r o m   p a r e n t t a b l e   w h e r e   s e l f L a b e l   =   ( s e l e c t   p a r e n t L a b e l   f r o m   c h i l d t a b l e   w h e r e   v a l u e   =   ' e v e n   a c c o u n t s   c a j o l e   s l y l y ' ) ) )   5 9 1           F i g u r e   6 .   M a p p i n g   X M L   n o d e s   i n t o   t h e   r e l a t i o n a l   d a t a b a s e s     F i g u r e   7 .   P e r f o r m a n c e   E v a l u a t i o n   R e s u l t s       F r o m   t h e   r e s u l t s   o b t a i n e d ,   w e   o b s e r v e d   t h e   f o l l o w i n g :   a )   F o r   s i m p l e   q u e r y ,   Q u e r y 1 ,   t h e   p e r f o r m a n c e   o f   t h e   R e l a t i o n a l   D T D ,   A t t r i b u t e   a n d   s - X M L   a p p r o a c h e s   a r e   c o m p a r a b l e   w h i l e   t h e   E d g e   a p p r o a c h   p e r f o r m s   t h e   w o r s t .   A l l   a p p r o a c h e s   p e r f o r m   o n l y   s i m p l e   t a b l e   s c a n .   I n   t h e   E d g e   a p p r o a c h ,   a l l   d a t a   a r e   s h r e d d e d   i n t o   a   s i n g l e   t a b l e .   A s   s u c h ,   t h e   t a b l e   s c a n   o p e r a t i o n   o n   t h e   E d g e   a p p r o a c h   i s   r a t h e r   s l o w   d u e   t o   i t s   h u g e   n u m b e r   o f   r o w s .   b )   F o r   a g g r e g a t e d   q u e r y ,   Q u e r y 2 ,   t h e   R e l a t i o n a l   D T D   a n d   t h e   s - X M L   a p p r o a c h e s   p e r f o r m e d   t h e   b e s t .     7569680 6687196 5035045 3906848 0 1000000 2000000 3000000 4000000 5000000 6000000 7000000 8000000 T i m e ( m s ) M a ppi ng   S c he m e s E dg e A t t r i but e D T D s - X M L 1 5 3 3 1 6 4 6 5 3 4 6 3 1 5 4 9 5 9 2 1 2 5 2 2 7 9 5 3 7 2 7 8 3 1 0 5 2 5 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0 Q u e r y   1 Q u e r y   2 Q u e r y   3 T i m e   ( m s ) E d g e A t t r i b u t e D T D s - X M L Q u e r y   N o .   Q u e r y   D e s c r i p t i o n   Q u e r y 1   R e t r i e v e   t h e   l a b e l   n a m e   f o r   t h e   v a l u e   l i k e   c a r e f u l   p a c k a g e s   w a k e   Q u e r y 2   C a l c u l a t e   t o t a l   q u a n t i t y   o f   o r d e r s   i n   t h e   X M L   d o c u m e n t   Q u e r y 3   R e t r i e v e   t h e   s h i p   i n s t r u c t i o n   f o r   t h e   i t e m s   w i t h   t h e   c o m m e n t   l i k e   e v e n   a c c o u n t s   c a j o l e   s l y l y   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I S S N :   2 0 8 8 - 8 7 0 8       B r i d g i n g   X M L   a n d   R e l a t i o n a l   D a t a b a s e s :   A n   E f f e c t i v e   M a p p i n g   S c h e m e   b a s e d   o n   .   ( S a m i n i   S u b r a m a n i a m )   2 4 5 c )   R e l a t i o n a l   D T D   p e r f o r m a n c e   d e g r a d e s   f o r   q u e r i e s   i n v o l v i n g   c o m p l e x / a s s o r t e d   c o m b i n a t i o n s   ( e s p e c i a l l y   o n   Q u e r y 3 ) .   S i n c e   R e l a t i o n a l   D T D   s o l e l y   d e p e n d i n g   o n   t h e   o c c u r r e n c e s   o f   e l e m e n t s   i n   t h e   d a t a s e t ,   i t   p e r f o r m e d   s l o w e r   f o r   c o m p l e x   q u e r i e s   d u e   t o   m u l t i p l e   j o i n s   r e q u i r e d .   U n l i k e   R e l a t i o n a l   D T D ,   t h e   n u m b e r   o f   t a b l e s   g e n e r a t e d   i n   s - X M L   a p p r o a c h   i s   f i x e d   r e g a r d l e s s   o f   t h e   f r e q u e n c y   o c c u r r e n c e   o f   t h e   e l e m e n t .   A s   f o r   t h e   E d g e   a p p r o a c h ,   t h e   p e r f o r m a n c e   i s   t h e   w o r s t   a s   i t   i n v o l v e s   s e v e r a l   s e l f - j o i n s   w i t h i n   t h e   h u g e   t a b l e   i t s e l f .     S i n c e   j o i n s   a r e   t h e   m o s t   e x p e n s i v e   e v a l u a t i o n s   i n   r e l a t i o n a l   d a t a b a s e ,   t h e   q u e r y   p r o c e s s i n g   o n   t h e   d a t a b a s e   s t o r e d   w i t h   t h e   E d g e   a p p r o a c h   w a s   t h e   w o r s t .         F i g u r e   8 .   I n s e r t i o n   o f   n e w   n o d e s     F i g u r e   9 .   D e l e t i o n   o f   n o d e s       D y n a m i c   U p d a t e   T h e   n e x t   e x p e r i m e n t   w a s   c o n d u c t e d   t o   e v a l u a t e   t h e   e f f i c i e n c y   o f   t h e   l a b e l i n g   s c h e m e s   i n   t e r m s   o f   d y n a m i c   u p d a t e ,   t o   b e   e x a c t ,   m e a s u r i n g   t h e   t i m e   t a k e n   t o   i n s e r t   a n d   d e l e t e   b u l k   o f   n o d e s   f r o m   t h e   l i n e i t e m   d a t a s e t .   S i n c e   t h e   l a b e l i n g   s c h e m e   i n   t h e   R e l a t i o n a l   D T D ,   E d g e   a n d   A t t r i b u t e   a p p r o a c h   d o   n o t   s u p p o r t   d y n a m i c   u p d a t e ,   w e   e m p l o y   O R D P A T H   [ 1 0 ]   a n d   L S D X   [ 2 ]   a s   t h e   l a b e l i n g   s c h e m e   f o r   c o m p a r i s o n .   H e n c e f o r t h ,   O R D P A T H ,   L S D X   a n d   P e r s i s t e n t   l a b e l i n g   a r e   k n o w n   a s   O R D P A T H - m a p ,   L S D X - m a p   a n d   s - X M L   r e s p e c t i v e l y .   F i g u r e   8   s h o w s   t h e   e x p e r i m e n t a l   r e s u l t s   f o r   n e w   i n s e r t i o n   o f   n o d e s   i n t o   l i n e i t e m   d a t a s e t .   L S D X - m a p   t o o k   t h e   l o n g e s t   t i m e   t o   g e n e r a t e   n e w   l a b e l s   f o r   n e w l y   i n s e r t e d   n o d e s .   T h i s   i s   f o r   t h e   r e a s o n   t h a t   L S D X   c a u s e s   c o l l i s i o n   d u r i n g   n e w   l a b e l   g e n e r a t i o n   a n d   a l s o   c o m p l e x i t y   i n   m a p p i n g   p r o c e s s .     F u r t h e r m o r e ,   t h e   s i z e   o f   t h e   l a b e l s   r e d u c e s   t h e   e f f i c i e n c y   o f   t h i s   l a b e l i n g   s c h e m e   a s   c o m p a r e d   t o   s - X M L .   O n   t h e   o t h e r   h a n d ,   t h e   p e r f o r m a n c e   o f   O R D P A T H - m a p   i s   c o m p a r a b l e   t o   s - X M L   d u e   t o   s i m p l e   c a l c u l a t i o n   f o r   n e w   l a b e l   g e n e r a t i o n   a n d   f a s t e r   m a p p i n g   t o   t h e   r e l a t i o n s .   s - X M L   p e r f o r m e d   t h e   b e s t   d u e   t o   c o n t r o l l e d   l a b e l i n g   s i z e   r e g a r d l e s s   o f   t h e   c o m p l e x i t y   o f   t h e   X M L   d o c u m e n t   a n d   d y n a m i c   u p d a t e   w h i c h   i s   a n   a d d e d   a d v a n t a g e   c o m p a r e d   t o   o t h e r   a p p r o a c h e s .     B e s i d e s   t h a t ,   t h e s e   l a b e l i n g   s c h e m e s   w e r e   a l s o   e v a l u a t e d   i n   t e r m s   o f   t h e i r   r o b u s t n e s s   d u r i n g   n o d e   d e l e t i o n   f r o m   l i n e i t e m   d a t a s e t   a n d   t h e i r   r e s u l t s   w e r e   r e c o r d e d   i n   F i g u r e   9 .   L S D X - m a p   t o o k   t h e   l o n g e s t   t i m e   t o   d e l e t e   t h e   n o d e s   a n d   u p d a t e   t h e   n e w   d o c u m e n t   f o l l o w e d   b y   O R D P A T H - m a p   a n d   s - X M L .   T h e   p e r f o r m a n c e   o f   O R D P A T H - m a p   a n d   s - X M L   i s   a n a l o g o u s   s i n c e   t h e y   r e q u i r e   l e a s t   t i m e   t o   d e l e t e   t h e   n o d e s   a n d   u p d a t e   t h e   d o c u m e n t .   T h e   e v e r - i n c r e a s i n g   l a b e l   s i z e   o f   O R D P A T H - m a p   c a u s e s   i t s   p e r f o r m a n c e   t o   d e g r a d e   a s   c o m p a r e d   t o   s - X M L   w h i c h   m a i n t a i n s   t h e   l a b e l i n g   f o r m a t   i n   a n y   c i r c u m s t a n c e s .         5 .   C O N C L U S I O N   X M L   d o c u m e n t   r e q u i r e s   r o b u s t   a n d   s e a m l e s s   m a p p i n g   a p p r o a c h   w h i c h   a l l o w s   f o r   e f f i c i e n t   a n d   a c c u r a t e   d a t a   s h r e d d i n g   i n t o   r e l a t i o n a l   d a t a b a s e .   I n   t h i s   p a p e r ,   w e   p r o p o s e d   a   n e w   m a p p i n g   s c h e m e   n a m e d   s - X M L   w h i c h   i s   b a s e d   o n   P e r s i s t e n t   L a b e l i n g   s c h e m e   t o   s u p p o r t   s t r u c t u r a l   q u e r i e s   r e t r i e v a l   e f f i c i e n t l y .   T h e   e x p e r i m e n t a l   e v a l u a t i o n s   r e v e a l e d   t h a t   s - X M L   p r o c e s s e d   q u e r y   e f f i c i e n t l y ,   e s p e c i a l l y   o n   c o m p l e x   q u e r i e s   a s   c o m p a r e d   t o   R e l a t i o n a l   D T D ,   A t t r i b u t e   a n d   E d g e   a p p r o a c h e s .   I n   a d d i t i o n ,   t h e   p e r f o r m a n c e   o f   s - X M L   w a s   b e t t e r   t h a n   O R D P A T H - m a p   a n d   L S D X - m a p   i n   t e r m s   o f   t h e   s u p p o r t   d u r i n g   d y n a m i c   u p d a t e .       R E F E R E N C E S   [ 1 ]   M .   A t a y . ,   e t   a l . ,   E f f i c i e n t   s c h e m a - b a s e d   X M L - t o - Re l a t i o n a l   D a t a   M a p p i n g ,   I n f o r m a t i o n   S y s t e m s ,   v o l .   3 2 ,   n o .   3 ,   p p .   4 5 8 - 4 7 6 ,   2 0 0 7 .   0 2 0 0 4 0 0 6 0 0 8 0 0 1 0 0 0 L i n e   I t e m T i m e   ( s ) L S D X - M a p O R D P A T H - M a p s - X M L 0 5 1 0 1 5 2 0 2 5 L i n e   I t e m T i m e   ( s ) L S D X - M a p O R D P A T H - M a p s - X M L Evaluation Warning : The document was created with Spire.PDF for Python.
                I J E C E     V o l .   2 ,   N o .   2 ,     A p r i l   2 0 1 2 2 4 6 [ 2 ]   M .   D u o n g ,   a n d   Y .   Z h a n g ,   L S D X :   N e w   L a b e l i n g   S c h e m e   f o r   D y n a m i c a l l y   U p d a t i n g   X M L   D a t a ,   A u s t r a l i a n                       D a t a b a s e     C o n f e r e n c e ,   p p .   1 8 5 [ 3 ]   D .   F l o r e s c u ,   a n d   D .   K o s s m a n ,   S t o r i n g   a n d   Q u e r y i n g   X M L   D a t a   U s i n g   a n   RD BM S ,   B u l l e t i n ,   v o l .   2 2 ,   n o .   3 ,   p p .   2 7 - [ 4 ]   A .   G a b i l l o n ,   a n d   M .   F a n s i ,   A   P e r s i s t r e n t   L a b e l i n g   S c h e m e   f o r   X M L   a n d   t r e e   D a t a b a s e ,   1 1 5 ,   2 0 0 6   [ 5 ]   T .   H a r d e r ,   e t   a l .   N o d e   L a b e l i n g   S c h e m e s   f o r   D y n a m i c   X M L   D o c u m e n t s   Re c o n s i d e r e d ,   E n g i n e e r i n g ,   6 0 ,   p p .   1 2 6 - 1 4 9 ,   2 0 0 7 . [ 6 ]   S . C.   H a w ,   a n d   ,   C. S .   L e e ,   N o d e   L a b e l i n g   S c h e m e s   i n   X M L   Q u e r y   O p t i m i z a t i o n :   A   S u r v e y   a n d   T r e n T e c h n i c a l     R e v i e w ,     p p .   8 8 - 9 9 ,   2 0 0 9 . [ 7 ]   L .   K h a n ,   a n d   Y .   Ra o ,   A   P e r f o r m a n c e   E v a l u a t i o n   o f   S t o r i n g   X M L   D a t a   i n   Re l a t i o n a l   D a t a b a s e   M a n a g e m e n t   S y s t e m s ,   P r o c .   o f   t h e   W o r k s h o p   o n   W e b   I n f o r m a t i o n   a n d   D a t a   M a n a g e m e n t [ 8 ]   I .   N e k r e s t y a n o v ,   e t   a l .   A n   A n a l y s i s   o f   A l t e r n a t i v e   M e t h o d s   f o r   S t o r i n g   S e m i s t r u c t u r e d   D a t a   i n   Re l a t i o n s ,   No t e s   I n   C o m p u t e r   S c i e n c e ,   1 8 8 4 ,   p p   3 5 4 [ 9 ]   M . F .   O Co n n o r ,   a n d   M .   Ro a n t r e e ,   D e s i r a b l e   P r o p e r t i e s   o f   X M L   U p d a t e   M e c h a n i s m s ,   W o r k s h o p ,   2 0 1 0 .   [ 1 0 ]   P .   O N e i l ,   e t   a l .   O RD P A T H S :   I n s e r t [ 1 1 ]   V .   S a n s ,   a n d   D .   L a u r e n t ,   P r e f i x   Ba s e d   N u m b e r i n g   S c h e m e s   f o r   X M L :   T e c h n i q u e s ,   A p p l i c a t i o n s   a n d   P e r f o r m a n c e s ,   P r o c .   O f     V L D B [ 1 2 ]   B. J .   S h i n ,   a n d   M .   J i n ,   A s s o c i a t i o n   I n l i n i n g   f o r   M a p p i n g   X M L   D T D s   t o   Re l a t i o n a l   T a b l e s ,   Co m p u t e r   S c i e n c e ,   3 0 4 6 ,   p p   8 4 9 [ 1 3 ]   F . T i a n ,   e t   a l .   T h e   D e s i g n   a n d   P e r f o r m a n c e   E v a l u a t i o n   o f   A l t e r n a t i v e   X M L   S t o r a g S I G M O D ,   p p   5 - 1 0 ,   2 0 0 1 .   [ 1 4 ]   T a t a r i n o v ,   e t   a l .   S t o r i n g   a n d   Q u e r y i n g   O r d e r e d   X M L   U s i n g   a   Re l a t i o n a l   D a t a b a s e   S y s t e m ,   p p .   2 0 4 - 2 1 5 ,   2 0 0 2 .   [ 1 5 ]   U W   X M L   Re p o s i t o r y ,   h t t p : / / w w w . c s . w a s h i n g t o n . e d u / r e s e a r c h /   x m l / d a t a     B I O G R A P H Y   O F   A U T H O R S     S a m i n i   S u b r a m a n i a m s   r e s e a r c h   i n t e r e s t   a r e   i n   Re l a t i o n a l   D a t a b a s e   M a n a g e m e n t   S y s t e m   ( RD BM S ) ,   X M L   p r o c e s s i n g   a n d   Q u e r y   p r o c e s s i n g   a n d   o p t i m i z a t i o n .             S u - Ch e n g   H a w s   p r o c e s s i n g   a n d   o p t i m i z a t i o n ,   D a t a   M o d e l i n g   a n d   D e s i g n ,   D a t a   M a n a g e m e n t ,   D a t a   S e m a n t i c ,   Co n s t r a i n t s   &   D e p e n d e n c i e s ,   D a t a   W a r e h o u s e ,   E                 P o o   K u a n   H o o n g s s y s t e m s .   H e   i s   a   m e m b e r   o f   I E I C E ,   I E E E   a n d   A CM .               2   :     2 3 9     2 4 6   M .   D u o n g ,   a n d   Y .   Z h a n g ,   L S D X :   N e w   L a b e l i n g   S c h e m e   f o r   D y n a m i c a l l y   U p d a t i n g   X M L   D a t a ,   ,   p p .   1 8 5 -   1 9 3 ,   2 0 0 5 .   D .   F l o r e s c u ,   a n d   D .   K o s s m a n ,   S t o r i n g   a n d   Q u e r y i n g   X M L   D a t a   U s i n g   a n   RD BM S ,   - 3 4 ,   1 9 9 9 .   A .   G a b i l l o n ,   a n d   M .   F a n s i ,   A   P e r s i s t r e n t   L a b e l i n g   S c h e m e   f o r   X M L   a n d   t r e e   D a t a b a s e ,   T .   H a r d e r ,   e t   a l .   N o d e   L a b e l i n g   S c h e m e s   f o r   D y n a m i c   X M L   D o c u m e n t s   Re c o n s i d e r e d ,   1 4 9 ,   2 0 0 7 .   S . C.   H a w ,   a n d   ,   C. S .   L e e ,   N o d e   L a b e l i n g   S c h e m e s   i n   X M L   Q u e r y   O p t i m i z a t i o n :   A   S u r v e y   a n d   T r e n 9 9 ,   2 0 0 9 .   L .   K h a n ,   a n d   Y .   Ra o ,   A   P e r f o r m a n c e   E v a l u a t i o n   o f   S t o r i n g   X M L   D a t a   i n   Re l a t i o n a l   D a t a b a s e   M a n a g e m e n t   ,   P r o c .   o f   t h e   W o r k s h o p   o n   W e b   I n f o r m a t i o n   a n d   D a t a   M a n a g e m e n t ,   p p   3 1 - 3 8 ,   2 0 0 1 o v ,   e t   a l .   A n   A n a l y s i s   o f   A l t e r n a t i v e   M e t h o d s   f o r   S t o r i n g   S e m i s t r u c t u r e d   D a t a   i n   Re l a t i o n s ,   ,   1 8 8 4 ,   p p   3 5 4 - 3 6 1 ,   2 0 0 2 .   M . F .   O Co n n o r ,   a n d   M .   Ro a n t r e e ,   D e s i r a b l e   P r o p e r t i e s   o f   X M L   U p d a t e   M e c h a n i s m s ,   P .   O N e i l ,   e t   a l .   O RD P A T H S :   I n s e r t - F r i e n d l y   X M L   N o d e   L a b e l s ,   P r o c .   O f   A CM   S I G M O D V .   S a n s ,   a n d   D .   L a u r e n t ,   P r e f i x   Ba s e d   N u m b e r i n g   S c h e m e s   f o r   X M L :   T e c h n i q u e s ,   A p p l i c a t i o n s   a n d   ,   P r o c .   O f     V L D B ,   p p . 1 5 6 4 - 7 2 ,   2 0 0 8 .   B. J .   S h i n ,   a n d   M .   J i n ,   A s s o c i a t i o n   I n l i n i n g   f o r   M a p p i n g   X M L   D T D s   t o   Re l a t i o n a l   T a b l e s ,   ,   3 0 4 6 ,   p p   8 4 9 - 8 5 8 ,   2 0 0 4 .     e t   a l .   T h e   D e s i g n   a n d   P e r f o r m a n c e   E v a l u a t i o n   o f   A l t e r n a t i v e   X M L   S t o r a g e   S t r a t e g i e s ,   T a t a r i n o v ,   e t   a l .   S t o r i n g   a n d   Q u e r y i n g   O r d e r e d   X M L   U s i n g   a   Re l a t i o n a l   D a t a b a s e   S y s t e m ,   h t t p : / / w w w . c s . w a s h i n g t o n . e d u / r e s e a r c h /   x m l / d a t a s e t s / w w w / r e p o s i t o r y . h t m l .   S a m i n i   S u b r a m a n i a m s   r e s e a r c h   i n t e r e s t   a r e   i n   Re l a t i o n a l   D a t a b a s e   M a n a g e m e n t   S y s t e m   ( RD BM S ) ,   X M L   p r o c e s s i n g   a n d   Q u e r y   p r o c e s s i n g   a n d   o p t i m i z a t i o n .   Ch e n g   H a w s   r e s e a r c h   i n t e r e s t s   a r e   i n   X M L   D a t a b a s e s   a n d   i n s t a n c e   s t o r a g e ,   Q u e r y   p r o c e s s i n g   a n d   o p t i m i z a t i o n ,   D a t a   M o d e l i n g   a n d   D e s i g n ,   D a t a   M a n a g e m e n t ,   D a t a   S e m a n t i c ,   Co n s t r a i n t s   &   D e p e n d e n c i e s ,   D a t a   W a r e h o u s e ,   E - Co m m e r c e   a n d   W e b   s e r v i c e s . P o o   K u a n   H o o n g s   r e s e a r c h   i n t e r e s t s   a r e   i n   t h e   a r e a s   o f   p e e r - t o - p e e r   n e t w o r k s   a n d   d i s t r i b u t e d   s y s t e m s .   H e   i s   a   m e m b e r   o f   I E I C E ,   I E E E   a n d   A CM .                 I S S N :   2 0 8 8 - 8 7 0 8   M .   D u o n g ,   a n d   Y .   Z h a n g ,   L S D X :   N e w   L a b e l i n g   S c h e m e   f o r   D y n a m i c a l l y   U p d a t i n g   X M L   D a t a ,   P r o c .   O f   1 6 t h   D .   F l o r e s c u ,   a n d   D .   K o s s m a n ,   S t o r i n g   a n d   Q u e r y i n g   X M L   D a t a   U s i n g   a n   RD BM S ,   I E E E   D a t a   E n g i n e e r i n g   A .   G a b i l l o n ,   a n d   M .   F a n s i ,   A   P e r s i s t r e n t   L a b e l i n g   S c h e m e   f o r   X M L   a n d   t r e e   D a t a b a s e ,   P r o c .   o f   A CI ,   p p .   1 1 0 - T .   H a r d e r ,   e t   a l .   N o d e   L a b e l i n g   S c h e m e s   f o r   D y n a m i c   X M L   D o c u m e n t s   Re c o n s i d e r e d ,   D a t a   &   Kn o wl e d g e   S . C.   H a w ,   a n d   ,   C. S .   L e e ,   N o d e   L a b e l i n g   S c h e m e s   i n   X M L   Q u e r y   O p t i m i z a t i o n :   A   S u r v e y   a n d   T r e n d s ,   I E T E   L .   K h a n ,   a n d   Y .   Ra o ,   A   P e r f o r m a n c e   E v a l u a t i o n   o f   S t o r i n g   X M L   D a t a   i n   Re l a t i o n a l   D a t a b a s e   M a n a g e m e n t   3 8 ,   2 0 0 1   o v ,   e t   a l .   A n   A n a l y s i s   o f   A l t e r n a t i v e   M e t h o d s   f o r   S t o r i n g   S e m i s t r u c t u r e d   D a t a   i n   Re l a t i o n s ,   L e c t u r e   M . F .   O Co n n o r ,   a n d   M .   Ro a n t r e e ,   D e s i r a b l e   P r o p e r t i e s   o f   X M L   U p d a t e   M e c h a n i s m s ,   P r o c .   o f   E D B T / I CD T   P r o c .   O f   A CM   S I G M O D ,   p p . 9 0 3 -   9 0 8 ,   2 0 0 4 .   V .   S a n s ,   a n d   D .   L a u r e n t ,   P r e f i x   Ba s e d   N u m b e r i n g   S c h e m e s   f o r   X M L :   T e c h n i q u e s ,   A p p l i c a t i o n s   a n d   B. J .   S h i n ,   a n d   M .   J i n ,   A s s o c i a t i o n   I n l i n i n g   f o r   M a p p i n g   X M L   D T D s   t o   Re l a t i o n a l   T a b l e s ,   L e c t u r e   No t e s   I n   e   S t r a t e g i e s ,   P r o c .   o f   t h e   A CM   T a t a r i n o v ,   e t   a l .   S t o r i n g   a n d   Q u e r y i n g   O r d e r e d   X M L   U s i n g   a   Re l a t i o n a l   D a t a b a s e   S y s t e m ,   P r o c .   o f   S I G M O D ,   s e t s / w w w / r e p o s i t o r y . h t m l .     S a m i n i   S u b r a m a n i a m s   r e s e a r c h   i n t e r e s t   a r e   i n   Re l a t i o n a l   D a t a b a s e   M a n a g e m e n t   S y s t e m   X M L   D a t a b a s e s   a n d   i n s t a n c e   s t o r a g e ,   Q u e r y   p r o c e s s i n g   a n d   o p t i m i z a t i o n ,   D a t a   M o d e l i n g   a n d   D e s i g n ,   D a t a   M a n a g e m e n t ,   D a t a   S e m a n t i c ,   Co m m e r c e   a n d   W e b   s e r v i c e s .   p e e r   n e t w o r k s   a n d   d i s t r i b u t e d   Evaluation Warning : The document was created with Spire.PDF for Python.