XML DATA SYSTEMS: A TREE BASED ALGEBRA FRAMEWORK WITH WORKED EXAMPLES  

Ali El Bekai, Nick Rossiter
School of Informatics, Northumbria University
Email: ali.elbekai@unn.ac.uk, nick.rossiter@unn.ac.uk

Keywords: XML documents, tree algebra, integration framework. 
Abstract: 
This paper introduces a framework in algebra for processing XML data. We develop a simple algebra, called TA (Tree Algebra), for processing storing and manipulating XML data, modelled as trees. We present assumptions of the framework, describe the input and the output of the algebraic operators, and define the syntax of these operators and their semantics in terms of algorithms. Furthermore we define the relational and their semantics in terms of algorithms. Examples show that this framework is flexible to capture queries expressed in the domain specific XML query language. As can be seen the input and output of our algebra is a tree, that is the input and output are XML document and the XML document is defined as a tree. We also present algorithms for many of the algebra operators; these algorithms show how the algebra operators such as join, union, complement, project, select, expose and vertex work on nodes of the XML tree or element and attributes of an XML document. Detailed examples show how the algebraic operators work.

1 INTRODUCTION   
XML (eXtensible Markup Language) is fast emerging as the dominant standard for representing and exchanging information over the Internet. If data is stored and represented as XML documents, then it should be possible to query the contents of these documents in order to extract, synthesize and analyze their contents. Furthermore XML provides a data standard for a wide variety of data transfer cases like data exchange between different programs, sending data between client and server, and facilitating the generation and management of metadata [Zisman 2000].
     In general, as XML is hierarchical (tree structured), many different XML schemas (or XML structures) and corresponding XML documents can be generated from the same conceptual database schema, and hence from an underlying database. Therefore, there is need for an XML schema design tool that can helps users in creating a specific XML document structure for their application. Over recent years, XML has achieved a remarkable success in handling structured data access on the web, and has been increasingly recommended and supported by major software vendors [Bourret 2004]. 
     In this paper we develop an algebraic model for data management, which unifies in a single framework data presentation, data communications and data processing based on an XML Schema. Starting with the XML Schema of the data we develop domain specific XML algebra suitable for data processing of the specific data. The algebraic model we are developing, based on the existing standard (W3C XML Query Algebra), is a domain specific model of collaborative information processing over the Web. Even though it is domain specific, however, it will be generic since it will model an integrated architecture for distributed information processing. The input and output of our algebra are XML documents defined as a tree. We also present examples and algorithms for most algebra operator; these examples and algorithms show how the relational algebra and its operators work. Furthermore we apply join, union, complement, project, select, expose and vertex operations to nodes to form the XML tree as elements and attributes of XML document.
   The rest of the paper is structured as follows: Section 2 presents the related work for XML algebra. This leads up to our algebra description in Section 3. Section 4 presents our XML data model. Section 5 presents the algebra relational operators. The examples for algorithms and input and output of the algebra operators are defined in Section 6. Section 7 presents a discussion of the algebra. Finally, Section 8 summarizes the framework and conclusion. 

2 RELATED WORK  
In this section we review the XML algebra models and concentrate on existing approaches to formulate an algebraic framework model. We first investigate the XML algebra models.    
   The IBM algebra [Beech, Mathotra & Rys 1999] data model was presented by a group of researchers from IBM Oracle and Microsoft in September 1999. This model provides an algebra that operates as a graph based data model. Basically, the IBM model is a logical model, which means it is independent from the underlying hardware and the physical storage synopsis and syntax. In addition to its standard operators, there are reshaping operators presented in this model. By using such operators, a new XML document can be created from fragments of XML documents. 
     The Niagara algebra [Galanis et al 2001] introduces an algebraic framework for expressing and evaluating queries over XML data. It presents the underlying assumptions of the framework, describes the input and output of the algebraic operators, and defines these operators and their semantics. It evaluates the framework with regard to other proposed XML query algebras [Fenkhauser, Simeon & Woder 2001]. 
    YATL algebra [Christophides, Cluet & Simeon 2000] is an advanced and modified version of the YAT algebra; it was developed in 2000. Basically, the YATL algebra model presents the usual relational algebra rules and operators but in addition, it has two distinctive features compared to other algebra models. To support integration, the researchers have provided two new operators, firstly bind and secondly tree. The bind operator is used to extract relevant information from different sources and then produce a new structure called Tab, which is equivalent to a first-normal-form (1NF) relation [Codd 1972]. The inverse operation to bind, called tree generates a new XML Structure. 
     The Lore algebra [McHugh et al 1997] is developed for a DMBS designed specifically for managing semi-structured information. The Lore data model is a very simple self-describing, nested object model called OEM (Object Exchange Model). Since the OEM database is self-describing there is no notion of fixed schema. This means, schema may change dynamically with no restriction. 
       The purpose of AT&T algebra is twofold [W3C February 2001]. First, the algebra is used to give semantics for the query language, so the operations of AT&T algebra should be well defined. Second, the algebra is used to support query optimisation. Basically, the researchers have also implemented types that can be used to detect certain kinds of errors at compile time and to support query optimisation. In addition the authors have also implemented a type checker and an interpreter for the algebra in OCaml, which is a functional programming language. Table 1 provides a summary of algebraic methods discussed so far.  

                                                 Table 1: Comparison of Different Algebraic Models
Algebraic
Model	IBM	YATL
	Niagara
	Lore
	AT&T
	
Data Model	Standalone XML algebra	Logical Data Model, Graph Based	Standalone XML algebra	Integrated DBMS
	Standalone XML algebra	
Approach	Represents the collection of vertices	Integrating data from different sources	Operates on a set of bags of vertices	Cost-based query optimization	Based on the iteration operation, NRA	
Distinctive
Features	- Not system specific, 
XQuery support.

- Provides an algebra operator that operates as graph-based data model.	- Ability to integrate data from different sources: can be used efficiently in querying distributed data.

- YATL has Tree operations for transforming relation structure to Tree structure	- Simple and powerful algebraic expressions, optimised rules
	- Optimised from cost-based perspective, dynamic schema structure.
- Each query is transformed into a logical query plan using logical operators such as Select, Project, Discover…etc	- Built in types for detecting errors at query compile time.

- SQL& OQL and NRA support
XQuery.

- Based on the iteration operation	
Drawbacks	- Deficiency of Optimisation Rules, 
- Complex query structure, data type should be known at query compile time	- The integration is exclusively based on YATL data model and type system, and does not provide a well-defined list of the operators and explicit optimisations.	- The algebraic framework assumes that at the time of writing the query, the type is known for each vertex (attribute, element and reference).
- Implementing a query using IBM model will lead to a complex structure.	- The physical operators are designed specifically for its own data model
	- Query plan based on this algebra, once generated, is difficult to optimize	
Special Operators	Reshaping Operators	Bind, Tree operators	-	Vindex, Lindex, once	-	
W3C	Proposed	-	Proposed	-	Proposed	

It can be seen from Table 1 that all algebras are quite distinctive, although they do share some common features, e.g. all algebra models 

studied support standard algebra operations. IBM algebra, Niagara and AT&T are standalone XML algebras.
In addition, they have the ability to act as graph based logical data models. These factors have been carefully taken into consideration by W3C in the proposal for the standard XML algebra [W3C February 2001].
Alongside these common characteristics, some of these models have unique features. For example, the Lore system has powerful feature for manipulating dynamic data structures.  AT&T has distinctive ability in detecting errors at query compile time with its well-defined list of the operators and explicit optimisations.  YATL algebra has the ability to integrate data from different sources. To use the advantages of these features, the algebra model needs special operators to perform such operations. These operators should be uniquely defined for their own data model. For instance, in YATL system there are Bind and Tree operators. These operators are used for structure transformation purposes.  Also, IBM algebra has a Reshaping operator, which is used to create new XML documents from a fragment of XML documents.
As can be seen, both YATL and Lore systems suffer from a major critical drawback: integration in both systems is exclusively dependent on their own data model. Therefore both systems have to be excluded from further consideration due to their lack of support for integration. In addition, the IBM model has major downfalls: a complex query structure and a deficiency in its optimisation rules. On the other hand both Niagara and AT&T systems support standard algebraic operators. In addition, they both have the ability to act as a standalone XML algebra system, allowing manipulation of algebraic expressions in a simple and powerful way. 

3 DESCRIPTION OF OUR  
   ALGEBRA
Our XML Algebra is a tree structure that consists of algebra operators [Greenwald et al 2003]. Each node in the tree has only one parent node, but a parent node can have multiple children nodes. The XML Tree is interpreted top-down, so the root of the tree at the top of the XML Tree is where the final XML document output is produced whereas the leaves of the tree correspond to the different data sources accessed, which in our system prototype are assumed to be object relational [Galanis et. al 2001; Scholl 1986]. 
There are two types of operators in our algebra: firstly, the algebraic operators are join, union, complement, project, select, expose and vertex. Every operator has a unique output of a tree, which makes it distinct from other algebra operators. Secondly, the relational operators are universal, subsuming, equivalence, and similarity.
 In the following sections we well explain in more detail all algebra operators and algebra relational operators. The algebra operators are based on W3C (standard algebra) and comprise XML-specific and special operations.

4 OUR XML DATA MODEL
Figure 1a shows an XML document, in which there is a topmost, unique element, collection, known as the root of the XML document (ancestor) [Comon et al 1997]. All elements are enclosed within the topmost element, collection1, known as the root of the XML document. Object1 and object3 sub-elements reside within the root node. This nesting of sub-elements can go to an arbitrary level. Figure 1b depicts the corresponding tree model for the document in Figure 1a. Elements and attributes correspond to nodes in the XML tree. Directed, named edges connect nodes, with the tag of the corresponding element or attribute name acting as the name of an edge. For each node of the tree, except the root node, there is a backward edge leading to the parent node. 
  Note that a parent node appears only between those connected with child nodes or leaf nodes. A path consists of the sequence of nodes names that one needs to follow in order to arrive at a node from the root node.

  4.1 Concepts in the tree model
   · Root (ancestor or parent)
The top node of the tree is identified as the root node
   · Node (parent or child)
      An edge is a link from a parent node to a  
      successor node, called child node
   · Leaf (child)
      Child nodes, atomic values
   · Path
      A path from node V1 to Vn sequence of 
      nodes, where 1<=n<=20 
   · Descendants
     Represent all nodes that are children of  
     current node or children of children of  
     current node and so on. 
   · Ancestor
     Ancestors of nodes V are parent,  
     grandparent, etc, that is all nodes found on 
     the path from node V to the root node. 
     The ancestor represents all nodes that 
     are parent of current node or parent of 
 parent of current node and so on. 

4.2 XML Document as Tree         
       Structure
    · XML document  ---> Tree
   · Element  ---> Root node, parent, child node 
   · Leaf        ---> child node, atomic values
   · Attribute ---> function, values.

                                                                            Figure 1a: an XML document

                                                       Figure 1b: Tree data model for Figure 1a 

5 RELATIONAL      
 In this section we introduce four types of relational algebra operators: Universal, Similarity, Equivalence and Subsumption. In the following sections we will explain these relations in more details. 

 5.1 Universal Element Relation
This relation is unary () and contains all information. In a case study for a museum objects information system the universal element would include the collections, their objects, object information and exhibition and institutions as described in [ICOM 1995; CIDOC 2002] and presented by Ali Elbekai in his thesis. 

 5.2 Similarity Relation 
for example the Doc4 tree is similar to the Doc3 tree, as in Figure 2, the                                                               node structure of the Doc4 tree is the same as that in the Doc3 tree. Also the similarity relation is a binary relation.  In general we can see the relation between any two XML documents or any two XML tree is similarity if the following holds: the root node in Docn tree and the root node in Docm tree are similar, the parent node in Docn tree and the parent node in Docm tree are similar and the child nodes in the Docn tree and the child node in Docm tree are similar. In addition if we find that any parent node or child node in Docn tree or Docm tree is an unnamed node then this node matches the corresponding named node at the same level and position as are depicted in Figure 2. As a result, we can conclude that the Similarity relation () means that the major structures of the two trees are similar.

                                                                   Figure 2: Similarity relational operator 

5.3 Equivalence Relation                
Equivalence relation () means that two trees are indistinguishable as in Figure 3 where the nodes in the Doc3 tree are equivalent to those in the Doc4 tree. As the nodes present in the Doc3 tree are equivalent to the nodes present in Doc4 tree then we can identify that the Doc3 tree is equivalent to the Doc4 tree. In other words the major structure represent the both trees are equivalent and the identity represent both trees structure are node-by-node equivalent. Also the equivalence relation is a binary relation. In general we can explore that the relation is equivalence between any two XML document or any two XML tree if the following holds: the root node Docn tree and the root node Docm tree are equivalent, the parent node Docn tree with parent node Docm tree are equivalent and the chid nodes Docn tree and child nodes Docm tree are equivalent. In addition if the parent node or child node in both Doc trees is unnamed, then the unnamed node matches the corresponding node in the same level and position.

                                                 Figure 3: An Equivalence relational operator

5.4 Subsumption Relation  
Subsumption () means that one tree is a subset of the other, for example the Doc3 tree is a subset of the Doc1 tree as it is a binary. If the nodes present in Doc3 tree are a subset of the nodes present in Doc1 tree then we can see the Doc3 tree is a subsumption of the Doc1 tree. In general we can conclude that the Docn tree is subsumption or equal of Docm tree if the following holds:  the root node Docn tree exists in Docm tree, the parent node Docn tree exists in the Docm tree and the child node Docn tree exists in the Docm tree. In other words the Docn tree is part of Docm tree. 

                                                   Figure 4: Subsumption relational operator

6. ALGEBRA OPERATORS 
All operators in tree algebra take one tree or more as input and produce one tree of data as output [Roth, Korth & Silberschatz 1988].    

6.1 Join Operator
A join () is a binary operator, which takes two trees as input, and combines them into one tree as output. This combination is made whenever a certain expression holds true, that is the two tree collections are joined on a predicate. The predicate can be as generic as the conditions accepted by the selection operator. The query operation selects documents that meet the stated criteria from a collection of documents. It may also extract components from selected documents and construct new documents from these components. In some cases, we may want to start with more than one source collection and perform the initial selection on documents from those collections that are related by some condition. Also the join operator has the property of being commutative. More precisely Doc1 tree  Doc2 tree = Doc2 tree  Doc1 tree. Furthermore, it is associative which means (Doc1 tree  Doc2 tree)  Doc3 tree = Doc1 tree  (Doc2 tree  Doc3 tree).
Algorithm 1 shows how to join any two XML documents or two Doc trees in general.

                                              Algorithm 1: Join of two XML documents or two Doc trees

// Input two XML document or two DOC tree (DOCn, DOCm)
// Output DOCnm Tree = (DOCn Tree  DOCm Tree)
1.	start from root node DOCn tree and root node DOCm tree
2.	if root node has parent\child node
2.1	perform depth-first algorithm
2.2	if the parent node DOCn tree has child node and parent node DOCm tree has child node
2.2.1  While child node DOCn tree agrees with child node DOCm tree repeat:
           2.2.1.1 join such child node (concatenation without repetition)
           2.2.1.2 set the output in DOCnm tree
           2.2.1.3 if child node in DOCn tree has leaf node agree with leaf node DOCm tree 
     2.2.1.3.1 join such leaf node (concatenation without repetition)  
              2.2.1.3.2 set joined leaf node to the output DOCnm tree
          2.2.1.4 join such leaf node in DOCn tree to leaf node DOCm tree
               2.3 set parent node to DOCnm tree
3.	set no parent/child node and root node into DOCnm tree and terminate
4.	end/terminate

Figure 5 is an example of the joining of two XML trees. The root node collection1 in Doc1 tree data model is concatenated with the root node collection3 of the Doc3 tree data model. The parent node object1 of Doc1 tree data model is concatenated with the parent node object1 of the tree Doc3 tree data model. Furthermore, the parent node object3 of Doc1 tree data model is concatenated with the parent node object3 in the Doc3 tree data model. The child node objectInfor1 and child node objectInfor2 of Doc1 tree data model appear 
in the output tree, because they belong to the parent node object1. The child nodes object1 of Doc1 tree data model appears in the output tree, because it belongs to the parent node in Doc3 tree data model. The child nodes object3 of Doc1 tree data model join with the child nodes in object3 and appear in the output tree. 
In general the syntax of the join operator is DOCn Tree ⋈ [condition] DOCm Tree
where DOCn Tree (1<=n<=10) and DOCm Tree (1<= m< = 10).

                                                                           Figure 5: join operator example

6.2 Union Operator 
The purpose of the Union operator () is to union two XML documents or two XML trees. It is a binary operator with two XML documents or two XML trees as input and one XML tree or XML document as output. This is depicted in Algorithm 2 and an example is given in Figure 6. Furthermore, the union 
operator is commutative. More precisely, DOC1 tree  DOC2 tree = DOC2 tree  DOC1 tree. Also it is an associative operator, meaning that (DOC1 tree  DOC2 tree)  DOC3 tree = DOC1 tree  (DOC2 tree  DOC3 tree). Furthermore the output of the union operators is a new XML tree data containing all the elements, root node, parent nodes and child nodes in the two input Doc trees data model without the duplication of any elements such as root nodes, parent nodes and child nodes. In general the syntax of the 
union is DOCn Tree  DOCm Tree, where operator is (1<=n<=10) and (1<=m<=10). The union is disjoint: duplicates are purged.

Algorithm 2: Union two XML documents or two Doc Trees

// Input two XML document or two DOC tree (DOCn Tree, DOCm Tree)
// Output DOCnm Tree = (DOCn Tree  DOCm Tree)
1.	start with root node DOCn Tree and root node DOCm Tree
2.	set root node DOCn Tree or root node DOCm Tree in new DOCnm Tree
3.	if root node has parent/child node in either DOC Tree
3.1 perform depth-first algorithm
3.2 if the parent node DOCn Tree = parent node DOCm Tree
      3.2.1 set parent node DOCn Tree or DOCm Tree in new DOCnm Tree
      3.2.2 while parent node DOCn Tree has child node or parent node
                             DOCm Tree has child node 
3.2.2.1	set child node to new DOCnm Tree
3.2.2.2	eliminate duplicate child node
                      3.2.3 repeat
                3.3 set null to new DOCnm and terminate
4.	set null and terminate
5.	terminate/end

As an example, the Doc tree data model in Figure 6 shows the union operators. The root node collection2 in XML Doc2 tree data merges with the root node collection3 in the Doc3 tree data.  Following the path from parent to child node, the object1 in Doc2 tree data model merges with the parent node object1 in the XML Doc3 tree data.  In 

addition, the parent node object3 in Doc2 tree model merges with the parent node object3 in the Doc3 tree data model. Because they do not exist in the Doc2 tree, the child node objectInfor1 and child node objectInfor2 in Doc3 tree data appear in the output tree and the child nodes object1 in Doc3 tree appear in the output tree with their leaf nodes and atomic values. 

                                                              Figure 6: union operator example

6.3 Complement Operator

 The complement operator (), as a binary operator, operates on two XML documents or two XML trees as input, and produces one XML document or one XML tree as an output. In other words the XML document is a tree; the result of the complement of the two DOC trees is a new DOC tree containing all the nodes present in the first input DOC tree but not in the second DOC tree. That is the output of the complement operator is a new XML tree containing all element nodes (root node, parent nodes, children nodes, function, values) existing in the input Doc1 tree data model and not existing in the Doc3 tree. Algorithm 3 shows how we can complement the two DOC trees in general. 

                                         Algorithm 3: Complement two XML documents or two DOC trees

// Input two XML document or two DOC tree (DOCn Tree, DOCm Tree)
// Output DOCnm Tree = (DOCn Tree - DOCm Tree)
1.	start from root node DOCn
2.	If root node DOCn Tree and root node DOCm Tree has parent/child node  
2.1	Perform depth-first algorithm  
        2.2   if DOCn Tree has parent node not exist in DOCm Tree
 2.2.1 set parent node DOCn Tree to the new DOCnm Tree
 2.2.2 while parent node DOCn Tree has child node not exist in DOCm Tree 
 2.2.2.1 set child node DOCn Tree to DOCnm Tree
 2.2.2.2 if child node DOCn Tree has leaf node not exist in DOCm Tree
                                     2.2.2.2.1 set leaf node DOCn Tree to DOCnm Tree
                      2.2.2.3 set null to DOCnm Tree
            2.2.3 repeat 
           2.3 set null to DOCnm Tree
3.	set root node to DOCnm Tree and terminate
4.	end/terminate

The purpose of the complement operator is to compute the difference between the two input trees. DOCn Tree - DOCm Tree, where DOCn Tree (1<=n<=10) and DOCm Tree (1<=m<= 10). The complement operator is not commutative, which means DOC1 tree – DOC3 tree  DOC3 tree –  DOC1 tree. Also it is not an associative operator.
As an example suppose we want the complement to the Doc1 tree and Doc3 tree shown in Figure 7. We start by comparing the Doc1 and the Doc3 trees. The root node exists in both tree successor, the parent node object1 exists in both tree data models and also the parent node object3 exists in both tree data models. But the parent node object3 contains two child nodes objectInfor3 and objectInfor4 in the Doc1 tree data model that do not exist in the Doc3 tree data model. The child nodes of objectInfor4 in Doc1 tree data model do not exist in the Doc3 tree data model. The output returned is a new tree data model. That is the complement result between the Doc1 and Doc3 trees is all the nodes present in the Doc1 tree that do not appear in the Doc3 tree.  

                           Figure 7: Complement operator

6.4 Projection Operator
The input for the projection operator () is one XML document or one XML tree, as it is unary. In general Algorithm 4 shows how the projection operator works and Figure 8 shows how we can project any node of the DOC tree.
                                                       
                                                     Algorithm 4: Projection operator  

// Input one DOC tree or one XML document
// Output one DOC tree or one XML document
1.	start from the root node of DOC Tree
2.	if root node has parent/child node
2.1	Perform depth-first algorithm
2.2	if projected node/selected node is equal to current node
        2.2.1 set the projected node as output to new DOC Tree
2.3	node projected/selected not exist and terminate
   3. end/terminate 

As can be seen from Figure 8 we take object3 as a parameter and the searching is performed at the root node collection1 in Doc1tree. The output of the projection operator is a new XML document or new DOC1p tree.                
For trees, projection may be regarded as eliminating nodes other than those specified. In the substructure resulting from node elimination, we would expect the (partial) hierarchical relationship between surviving nodes that existed in the input collection to be 
preserved. Projection in tree algebra takes one collection <C> (tree) as input and <P> as parameters. 
Projection starts the search at the root node and follows the path parent node successor, the child node, until it finds the node projected. The syntax of the projection operator is defined as follows:  
  <P> < C > where <p> is parameter and <C> is tree. 
                                                                                                Figure 8: Projection operator example
                          <object3> <collection1>                    

6.5 Select Operator

The purpose of a select () operation is to filter out tuples in the XML algebra satisfying an expression given as a predicate. The select operator is a unary operator to take one XML document or one tree as input and produce one XML document or one tree as output. 
The selection operator, allows us to determine a subset over a collection of documents. It applies a given condition to each member of the collection of nodes and returns a result node or collection of nodes consisting of those members for which the condition evaluates true. Selection in tree algebra takes tree as input, and a pattern <P> as parameter, and returns an output tree <C>. Formally, the output  <p> <C> of the selection is a tree. We can take the parameter and start our selection by depth-first from the root node of the tree and successor, the parent nodes and successor, child node until the selection condition is satisfied. This is depicted in the example shown in Figure 9. The single forward slash (/) signifies the parent-child relationship between the nodes or the element in XML tree or XML document.

                                           Figure 9:  An example for selection operator

           Infor_id=10 <collection1>/<object1>/<objectInfor1

6.6 Expose Operator
The Expose operator () has one XML document or one Doc tree as input, as it is a unary operator and produces one Doc tree as the output. The purpose of the Expose operator is to retrieve specific elements of the XML document or specific nodes of the Doc tree. The Expose operator accepts as its parameters a list of path expression to be exposed from the document on which it operates, with the path expression in entry-point notation. Algorithm 6 shows how we can expose specific nodes of the Doc tree in general. Furthermore, Figure 9 shows the result of exposing specific nodes of the Doc1 tree.

                                     Algorithm 6: For Exposing specific node of Doc tree

// Input one DOC tree or one XML document
// Output one DOC tree or one XML document
1.	start with entry point is root node
2.	perform depth-first algorithm
2.1	if parameter is equal the specific node needed to expose
2.1.1	return the specific node
2.1.2	set specific node in new tree
2.2	exposed element not exist and terminate
     3. end/terminate

The Expose operator accepts as its parameter the element (parent, child) exposed from the tree data model on which it operates, with the path in entry point notation, and follows the path root node, parent node and successor child node until the element required to be exposed is found. The output of an Expose operator imposes a new ordering, the same as the order of its arguments. Once the nodes denoted by the path are reached, a new element content is constructed. In general the syntax of the expose operation is:
Expose[edge1<element>](element: expression)    
As an example suppose we want to expose the child node info_id of the parent node objectinfor3 in the Doc1 tree data using the command in Figure 10. The entry point is the root node collection1 and following the path, parent node object3, child node objectinfor1 and child node info_id we then retrieve the specific element. The output of the expose operator is a new XML tree as Doc1e tree.    

                                                         Figure 10: An example of the expose operator
     
  (<info_id>) [<collection1>/<object3>/<objectInfor3>]

6.7 Vertex Operator     

The Vertex operator () has one XML document or Doc tree as input, as it is a unary operator, and creates the actual XML vertex that will encompass everything created by the Expose operator. It arranges the element content according to the order indicated by its input. Figure 11 shows how we can use the vertex operator to create an actual XML vertex. Furthermore we will use the notation () to express the Vertex operator and the notation () to express the Expose operator. 
It creates the XML to which nodes can be connected, as well as the named edges that lead to the newly defined tree. As can be seen from the example shown in Figure 11 for complex Vertex and Expose operations the output is generated as a new XML tree. In the example we used the single forward slash (/) to signify the parent-child relationship between elements or nodes. In tracing a path through a tree the expression starts at the root node.

                                                  Figure 11:  Vertex operator example  
<newcollection3>[ (v<newobject1>[<collection3/object1>], (<newobject3>[collection3/object3>])]

7 DISCUSSIONS

The results from our literature review gave us a choice of an existing solution for applications in our context of either (1) Lore algebra, adopting an existing standard for building an original solution, (2) the standard XML algebra of W3C, or (3) developing a more targeted solution, that is a domain specific algebra, to handle our requirements. All the considerations, given earlier in the review, have already been taken into account by the team working on the standard XML algebra [W3C February 2001] and XQuery [W3C 2004]. In fact, the standard algebra is largely based on the AT&T model with some additional features and revisions in the spirit of Niagara. So, the standard is a satisfactory starting point for us in our efforts to develop domain specific algebra and was therefore adopted as the basis for our way forward. However, it does not make sense to implement the full algebra defined by the standard for one single specific task or even for a class of similar tasks. Because of this we develop a formal data model as a restricted version of the universal algebra suitable for a representative class of problems. Of course, such an approach may lead to a non-universal model, but at the same time, it is feasible and does produce a more effective solution for particular classes of problems. On this basis, we started with the XML Schema [W3C September 2001] of the data to develop domain specific XML algebra more suitable for data processing of the specific data and then we used it for implementing the main offline components of the system for data processing.  
Again, there are two types of operators in our algebra: firstly, the algebraic operators are join, union, complement, project, select, expose and vertex. Every operator has a unique output of a tree, which makes it distinct from other algebra operators. Secondly, the relational operators are universal, subsuming, equivalence, and similarity. This means our work is based on the tree based algebra framework for XML data systems. Also, our algebra has a sound data structure and a simple representation of the data. A contribution of this work is that it introduces an algebra that operates on a new data model, because our algebra employs XML trees as data sources and targets. Our algebra framework can be used in integrated architectures for distributed information processing and its components will be XML schema driven. Furthermore, as a test framework of our integrated approach we will prototype a system for the exchange of information between several independent museums for organising virtual exhibitions over the Web. Also, we plan to extend the algebra to support some of the more advanced features of the XML query language. 

8 CONCLUSION
We have presented a framework for representing XML algebra over XML documents. The operators and the relational operators we have defined explore XML data as well as enabling the construction of new XML documents. The operator works on one tree if it is a unary operator and on two trees if it is a binary operator producing one XML tree as output. The input and output of our algebra are XML trees. The relational operators work on XML documents and XML document defined as a tree. Furthermore, our XML algebra is generic, since our XML algebra model is XML Schema driven. Our tree algebra is a data structure with operators and presentation formats that satisfy our requirements.

9 REFERENCES
Bourret, Ronald, XML and Database (2004) at:
http://www.rpbourret.com/xml/XMLAndDatabases.htm
Beech, D, Malhotra A, & Rys, M, (eds.). A formal data model and algebra for XML, Communication W3C, (1999).   
Christophides, V, Cluet, S & Simeon, J, On wrapping, query languages and efficient XML integration. In ACM SIGMOD Conference on Management of Data. Dallas. Pp. 141-152, (May 2000).
CIDOC Group (July 2002)
http://www.willpowerinfo.myby.co.uk/cidoc/cidoc0.htm
Codd, E F, Relational Completeness of Data Base, in:  Data Base Systems, Courant Computer Symposia Series, Prentice Hall, 6, 65-98. (1972).
Comon, H., Dauchet, M., Gilleron, R., 
       Jacquemard, F., Lugiez, D., Tison, S., & 
       Tommasi, S, Tree Automata Techniques and 
       Applications., at:
  http://www.grappa.lille3.fr/tata.  (1997)
Fernandez, M, Simeon, J, & Wadler, P, A semi-monad for semi-structured data, International Conference on Database Theory 263-300. London, January (2001)
Fenkhauser, M, Simeon, J, & Woder, P, An algebra for XML Query. In Proc. FST TCS, New Delhi, December (2000).
Galanis, L, Viglas, E, DeWitt, D J,  Naughton, J F, & Maier, D, Following the paths of XML Data: An Algebraic Framework for XML Query Evaluation. Technical Report, University of Wisconsin, Madison (2001).
Greenwald, M B, Moore, J T, Pierce, B C, Schmitt, A, Language for Bi-Directional Tree Transformations. Technical Report MS-CIS-03-08. Department of Computer Department of Computer and Information Science, University of Pennsylvania. (August 2003).
ICOM, International Guidelines for Museum Object Information (IGMO): The CIDOC Information Categories, produced by the (CIDOC) of the (ICOM). October (1995).       http://www.cidoc.icom.org/guide
McHugh, J, Abiteboul, S, Goldman, R, Quass, D, & Widom, J, Lore: A Database Management      System for Semi-structured Data. SIGMOD 3(26) 54-66 (September 1997).
McHugh, J, & Widom, J, Query optimization for Semi-structured data, Technical Report, Stanford
University Database Group, August (1998).
http://www-db.standford.edu/pub/papers/qo.ps.
Roth, M A, Korth, H F, & Silberschatz, A, Extended algebra and calculus for nested relational databases, ACM Transactions on Database Systems (TODS), Vol. 13 (4) 389-417 (1988).
Scholl, M H, Theoretical foundations of algebraic optimization utilization unnormalized relation, in: G. Ausiello, P. Atzeni (Eds.), ICDT’86, Lecture Notes in Computer Science, Springer-Verlag, 234 409-420. (1986).
W3C, the XML Query Algebra, Working Draft, February (2001). http://www.w3.org/TR/2001/WD-query-algebra-20010215.
W3C, XML Schema: Formal Description, Working Draft, September (2001). 
W3C, XQuery 1.0: An XML Query Language, Working Draft (23 July 2004) at
 http://www.w3.org/TR/2004/WD-xquery-
20040723/  
Zhang, X. and Rundensteiner, E A, XML Algebra for the Rainbow System. Technical Report
WPI-CS-TR-02-24. Worcester Polytechnic Institute, July (2002).
Zisman, A, An Overview of XML, Computing and Control Engineering Journal 11 (4), (2000).