BACKGROUND OF THE INVENTION
The present invention relates in general to create joins between XML files, and in particular, to the logic for creation of joins between distributed XML documents.
The extended markup language (XML), which has been proposed as a standard language for information exchange on the Internet, is being widely used in computers and network systems (SyncML, UpnP) and also in many other industrial fields, such as, biological information (BSML, BioML), electronic commerce (ebXML, ECML), electronic data interchange (XML-EDI), geographic information and global positioning systems (GPS) (GML, NVML), multimedia (MPEG-7, EVIL), entertainment (MusicXML, GML), education (LMML, TML), medical care (CTDM, TDL), publication (BiblioML, DocBook), and TV broadcasting (TV-Anytime), etc.
Querying of two or more XML documents requires conditional selection of records from the documents involved. XML documents are not indexed entities like RDBMS and hence selecting a set of records by parsing a document multiple times can be resource intensive. Most of the platforms that implements XML joins creates an in memory model by selecting a set of records involved in the join and then applying the join logic on the in memory model. The join logic is often represented using a query plan based on the XQuery.
The existing technology primarily addresses join between XML documents at the same location. The logic requires, in order to perform join, a collection of all the elements that will be used in the XQuery be fetched into memory beforehand and then perform join operation. In case the present technology is applied for join between distributed XML documents it would require all the required nodes participating in a join to be transferred from one document location to the other.
The wide usage of XML as means of data storage and communication has resulted into XML document repositories across multiple locations in an enterprise.

This proliferation has lead to the requirement of querying XML documents located across multiple locations involving join condition.
Conventionally, experts have demonstrated the requirement for joins between distributed XML documents and proposed the idea of multiple XML servers (XML processing end points) participating in a join in the article titled "A distributed query engine for XML -QL". The article states movement of whole document between nodes to join XML documents.
Further, they have stated, optimization of distributed XML join by proposing the use of dataguide as a means of selecting sequence with less elements, getting distinct values and then sending the sequence to other XML document location, in an article entitled "Towards maintaining path selectivity statistics in distributed XML stores".
The conventional technologies, when applied for creation of joins across distributed XML documents, has two major shortcomings: (i). determining records that needs to transfer between XML documents (large XML documents), (ii). for creating joins, require transfer of all the nodes that are participating in the join from one document location to the other. This will lead to movement of large amount of data over the wire, which requires large bandwidth. So, whether the whole set of records in one XML document is required or not to join creation between XML documents at various locations?
In view of the foregoing, it has been found that conventional approaches to create join across distributed XML documents suffer from shortcomings and inefficiencies that warrant improvement. Accordingly, there is a need for unique way of creation of joins between distributed XML documents by selective movement of records between the participating documents. Further, there is also a need to significantly reduce the movement of data between distributed XML documents.

BRIEF DESCRIPTION
In one embodiment of the present technique, a method for creating a join between multiple distributed extensible Markup Language (XML) documents is disclosed. The method includes determining number of elements to be compared for distributed XML documents and defining a traverse procedure for each compared element. The method further comprises of retrieving elements from a first XML document of the multiple distributed XML documents that yields less number of elements while maintaining the hierarchy at the XML node and sending back to a XML processing endpoint where the first XML document of the multiple distributed XML documents exist. The method further includes creating the join between the retrieved elements and first XML document of the multiple distributed XML documents.
In another embodiment of the present technique, a method for defining a traverse procedure is disclosed. The traverse procedure includes obtaining the projection of each compared element for multiple distributed XML documents and verifying for their level of hierarchy for each of the multiple distributed XML documents. The traverse procedure further includes defining an alternative action to compensate for the difference in the level of hierarchy, if any. The present technique minimizes the movement of data over wire by selective movement of data across multiple distributed XML documents.
DRAWINGS
These and other features, aspects, and advantages of the present invention will become better understood when the following detailed description is read with reference to the accompanying drawings in which like characters represent like parts throughout the drawings, wherein:
FIG. 1 is a flow diagram illustrating a method for creation of join between multiple distributed XML documents, in one embodiment of the present technique;

FIG. 2 is a flow diagram illustrating a method for traverse procedure of each compared element, in one embodiment of the present technique;
FIG. 3 is a flow diagram illustrating a method for alternative action to compensate for difference in the level of hierarchy, in one embodiment of the present technique; and
Fig. 4 is a system illustrating a generalized computer network arrangement, in one embodiment of the present technique.
DETAILED DESCRIPTION
The following description is full and informative description of the best method and system presently contemplated for carrying out the present invention which is known to the inventors at the time of filing the patent application. Of course, many modifications and adaptations will be apparent to those skilled in the relevant arts in view of the following description in view of the accompanying drawings and the appended claims. While the method described herein are provided with a certain degree of specificity, the present technique may be implemented with either greater or lesser specificity, depending on the needs of the user. Further, some of the features of the present technique may be used to advantage without the corresponding use of other features described in the following paragraphs. As such, the present description should be considered as merely illustrative of the principles of the present technique and not in limitation thereof, since the present technique is defined solely by the claims.
The present invention relates in general to create joins between distributed XML files, and in particular, to the logic for creation of joins between multiple distributed XML documents.
As will be appreciated by people skilled in the art, to best understand the present invention it is important to be familiar with the definitions in which it is used.
The term "XML" as used herein, refers to extensible Markup Language (XML). XML is a standard protocol for exchanging data between distributed

applications or layers of the same application in a database system. XML is used widely in software for describing structured data. XML is designed to provide flexible and adaptable information formatting and identification. An XML file uses markup symbols to describe the content of the file in terms of the type of data it contains. These markup symbols are unlimited and self-defining. An XML file can be processed purely as data to be stored, or it can be displayed or acted upon in any number of ways.
The term "distributed XML documents" as used herein, refers to XML document repositories across multiple locations, XML documents located at various locations.
The term "element" as used herein, defined as a logical structure in an XML document that is delimited by a start and an end tag. It is specified by using an XML tag.
The term "XML node" as used herein, defined as the smallest unit of valid, complete structure in a XML document. For example, a node can represent an element, an attribute, or a text string.
The term "projection of the compared element" as used herein, refers to obtaining the hierarchy level of compared element for each XML document. The term "hierarchy" as used herein, refers to finding the level of compared element from the root node in an XML document.
The term "text block" as used herein, refers to XML tags, attributes and text contents in a collection of XML nodes.
The term "Xquery" as used herein, refers to querying distributed XML data documents.
Referring to figures, FIG. 1 is a flow diagram depicting a method adapted for creation of join across distributed XML documents to reduce the movement of data over wire. The method starts in step 100, wherein the number of elements to be compared, hereinafter referred to "compared elements", between XML documents is

determined. At step 102, a traverse procedure is executed for each compared element. At step 104, the elements are retrieved from XML document location that yields lesser number of compared elements in comparison to other XML document location while maintaining hierarchy at the XML node. At step 106, the retrieved elements from first XML documents are sent to the second XML document processing end. Further, step 106 includes, bringing all the required elements from the second document (while maintaining the XML node the given hierarchy) for given set of compared element (from first document). At step 108, the retrieved elements are sent back to the XML processing end point where the first XML document exists. The method further includes step 110, wherein the join is created between the retrieved elements and first XML document. Each of the above steps will be explained in subsequent sections to follow.
FIG.2 is a flow diagram depicting a method for executing traverse procedure for each compared element. The method starts at step 102, wherein the step 102 includes the process of obtaining projection of compared element for both XML documents 200. In step 202, the projections of compared element from both the XML documents are verified to check whether they are at same level of hierarchy or not. If they are at the same level of hierarchy, then the document that yields lesser number of nodes of compared element (after removing duplicate elements) is selected for transfer of the compared elements to the other XML document as shown in step 204. If they are at different level of hierarchy, then compensating for difference of depth (hierarchy in XML document) between the compared elements in two XML documents by defining an alternative action (block 206). Each of the above steps will be explained in detail as explained below.
FIG.3 is a flow diagram defining an alternative embodiment (block 206) to compensate for difference of depth between the compared elements in two XML documents. The method starts in step 300, wherein a plurality of points is assigned for each incremental depth level. In Step 300, the method further includes plurality of points, wherein the plurality of points includes at least two additional overhead element tags for each incremental depth level. In step 302, the number of additional tags is determined by multiplying the number of elements in the XML document in

which the compared element is deeper than in the other XML document with the differential depth in the level of hierarchy. At step 304, compensation number is computed by dividing the number of additional tags with number of tags required to represent the compared element in the other XML document. At step 306, the total number of elements in other XML documents is calculated after removing duplicate elements. At step 308, the effective number of elements for transfer is calculated by subtracting the compensation number from total number of elements in the other XML document. Each of the above steps will be explained in detail as shown below.
As described earlier with reference to FIG. 1, FIG. 2 and FIG. 3, the following example illustrates the logical flow of steps to create join across distributed XML documents.

In order to minimize the movement of data over wire while creating join across distributed XML documents, the inventors proposed a logic that identify one XML document from which data needs to be sent to other XML document. The invention also proposes logic for what sub set of data needs to be sent in such a transfer. In other words, the proposed logic primarily aims at minimizing the overheads of moving data across locations.
In order to achieve the shortcomings of the conventional techniques in creating join across distributed XML documents, the following conditions may be assumed.
1. XQuery is the means of querying distributed XML data sources.
2. In a XML semi join condition where a particular leaf in one XML document is compared with another leaf in other XML document, the whole XML structure in one XML document needs to be sent to the second XML document location.
3. The requirement behind sending the whole structure instead of just the leaf node is due to the primary assumption that Xquery (subsequently XPath will be used) is dependent on document structure. The node hierarchy is maintained as XPath expressions depends on node hierarchy.
4. To maintain node hierarchy in both XML documents, the over heads of transferring XML tags are also considered while considering the amount of data that will be needed to be transferred for creation of semi join.
5. Two documents are considered for XML semi join at a time.

In one embodiment of the present invention, the Xquery used to create join across distributed XML documents is shown below:
{
for $b in doc("bom.xml")/bom/part
return

{$b/partid}
{ $b/supart/subpartid}
{$b/supart/consumedquantity}
{ for $c in doc("partnumber.xml")/partnumberdata/part
where $b/supart/subpartid = $c/subpartid
return
$c/supplier/supplierid
}
}
In the above XQuery, subpartid is chosen as the element to compare between bom.xml and partnumber.xml documents (block 100). As illustrated in block 102, a traverse procedure is executed wherein $b/supart/subpartid is compared to $c/subpartid for querying the bom.xml and partnumber.xml documents. Assuming that b/supart/subpartid is sent to the other XML processing node having access to $c/subpartid, then an array of one node containing the following structure is sent (block 104, block 106):

subpartl

The requirement behind sending the whole structure instead of just the leaf node i.e. subpartl, is due to the primary assumption that Xquery (subsequently XPath will be used) is dependent on document structure. The node hierarchy is maintained as XPath expressions depends on node hierarchy (block 104).
In another embodiment of the present technique, the method starts with obtaining the projection of the compared element for bom.xml and partnumber.xml documents. The compared elements are $b/supart/subpartid and c/subpartid for bom.xml and partnumber.xml respectively (block 100). As explained earlier in Fig 2, the compared elements are verified with reference to their level of hierarchy from their root node respectively (block 202). If the compared element is at same level of hierarchy (that is at same depth from root node) for both XML documents, then the document that yields lesser number of nodes is suitable from which these nodes are transferred to the other location (block 204). In the above example, if the subpartid is assumed to be at the same level of hierarchy for both bom.xml and partnumber.xml documents, then there will be lesser number of subpart in a BOM xml document as compared to partmaster xml document and hence bom xml is chosen to transfer and subpart elements from bom xml document are transferred to partnumber xml document. If the compared element in one XML document is at different depth than in the other XML document, then an alternative action is executed as represented in block 206 which is explained below.
If compared element in one XML document is at a different depth than the other XML document, then for each incremental depth level, two points are assigned (representing 2 additional element tags that will be needed to be transferred) as represented in block 300. This incremental value is compensated on the basis of additional compared element (if any), based on depth of compared element.
is used to illustrate the above statement using bom.xml and partnumber.xml documents. As it is evident that is at depth level 2 from root node for bom.xml document and is at depth level 1 from root node for partnumber.xml document. As observed for the difference in the depth levels for

element, for transferring each element from bom.xml document to partnumber.xml document will have overhead of 2 tags.
Assume a scenario where partmaster xml document has 10 elements, bom xml document has 4 , the depth of is one more in bom xml as compared to partmaster xml. As one additional depth level means 2 incremental elements (2 additional tags), 4 tags in bom.xml would mean 4*2 =8 additional tags (block 302).
In partnumber xml document, representing one element requires 4 element tags as shown below: l
2 subpartl3 4
Defining compensation number by dividing the additional tags with the number of element tags required to represent the compared element i.e. in the partnumber xml document, i.e. eight additional tags in bom.xml document are equivalent to (8/4) two elements in partnumber xml document. Therefore, for this scenario, the compensation number is two (block 304).
The effective number of compared elements, i.e. present in the partnumber xml document is calculated by substracting the compensation number from the total number of compared elements in the partnumber xml document. That is virtually, the partnumber xml document possess only 8 elements. The total number of compared elements in any XML document is calculated after removing duplicates (block 306, 308).
As the proposed logic demonstrates that the least number for compared elements that results in one of the two XML in question is sent to the other XML document processing end. Here, the number of element in BOM is 4 while the effective number of elements in the Part Master is 8 then the set of 4 nodes (capturing the subpart element and the XML node structure) in bom xml document is sent to the XML processing endpoint where the Part Master xml

document is located. Thus the minimum count of compared nodes sent to other XML processing endpoint is 14 as shown below as represented in block 104,106:
(l)
(2)
(3 )(4)subpart 1 (5)
(6)
(7)
(8)
(9)
(10)( 11 )subpart4( 12)
(13)
(14)
For given set of compared element, retrieve all the required elements from the second xml document (while maintaining the XML node the given hierarchy) and send the nodes back to the XML processing endpoint where the first document exists (block 106). For this example, the following elements are sent back to the bom.xml document before creating join at the first XML document, that is bom.xml, is located. (15)
(16)( 17)subpart 1 ( 18) (19)
(20)krish(21 )(22) (23) (24) (25)
(26)(27)subpart4(28) (29)
(3 0)(31 )mohit(32) (33) (34)
As seen above, the number of text blocks sent from bom.xml document to partnumberdata.xml document is 34. The term "text blocks" refers to XML tags,

attributes and text contents in a collection of XML nodes. The reason for inclusion of XML tags under text blocks is that they also contribute towards the communication overheads.
If the convention join logic is used to create join between distributed XML documents, it illustrates the requirement to move records across XML documents. The movement of data across XML documents will occur in two ways as illustrated below.
The first way is to assume that a collection of needed elements from the bom.xml document location are moved to the partnumberdata.xml document location and consequently perform the join. This action will require the movement of the following elements from the bom.xml to the partnumberdata.xml document.


(38) (39)
As seen above, the number of text blocks sent from bom.xml document to partnumberdata.xml document is 39. The term "text blocks" refers to XML tags, attributes and text contents in a collection of XML nodes. The reason for inclusion of XML tags under text blocks is that they also contribute towards the communication overheads.
The second way is to assume that a collection of needed elements from the partnumberdata.xml document location are moved to the bom.xml document location and consequently perform the join. This action will require the movement of the following elements from the partnumberdata.xml to bom.xml the document.



As seen above, the number of text blocks sent from bom.xml document to partnumberdata.xml document is 50. The term "text blocks" refers to XML tags, attributes and text contents in a collection of XML nodes. The reason for inclusion of XML tags under text blocks is that they also contribute towards the communication overheads.
The above two situations, using the conventional logic to create join across distributed XM documents, arise two basic questions as stated below:
- There is no way to determine records from which document to be sent to
the other; (the question is more relevant in the case of large XML
documents)
- There is no way to determine whether the whole set of records in one
document is required for creation of join.
The invention proposes unique way of creation of joins between distributed XML documents by selective movement of records between the participating documents. The invention brings about significant reduction in the number of records required to be moved between XML documents. The advantages becomes more evident as the size of the participating XML documents increases and as the number of fields selected from participating XML documents increases.

Table 1 below is a schematic representation showing comparision of the text blocks required to be moved in case join needs to perform across distributed XML documents using the conventional logic and the present logic. The term text blocks refer to XML tags, attributes and text contents in a collection of XML nodes. We have included XML tags as they also contribute towards the communication overheads.

Based on the above information, as will be appreciated by a person skilled in the art, the advantages of the present logic is more evident in the following scenarios:
The number of nodes in an XML document increases.
In case where the number of elements selected from documents are more.
Exemplary Computing Environment
One or more of the above-described techniques can be implemented in or involve one or more computer systems. FIG. 4 illustrates a generalized example of a computing environment 400. The computing environment 400 is not intended to suggest any limitation as to scope of use or functionality of described embodiments.

With reference to Figure 4, the computing environment 400 includes at least one processing unit 410 and memory 420. In Figure 4, this most basic configuration 430 is included within a dashed line. The processing unit 410 executes computer-executable instructions and may be a real or a virtual processor. In a multiprocessing system, multiple processing units execute computer-executable instructions to increase processing power. The memory 420 may be volatile memory (e.g., registers, cache, RAM), non-volatile memory (e.g., ROM, EEPROM, flash memory, etc.), or some combination of the two. In some embodiments, the memory 420 stores software 480 implementing described techniques.
A computing environment may have additional features. For example, the computing environment 400 includes storage 440, one or more input devices 450, one or more output devices 460, and one or more communication connections 470. An interconnection mechanism (not shown) such as a bus, controller, or network interconnects the components of the computing environment 400. Typically, operating system software (not shown) provides an operating environment for other software executing in the computing environment 400, and coordinates activities of the components of the computing environment 400.
The storage 440 may be removable or non-removable, and includes magnetic disks, magnetic tapes or cassettes, CD-ROMs, CD-RWs, DVDs, or any other medium which can be used to store information and which can be accessed within the computing environment 400. In some embodiments, the storage 440 stores instructions for the software 480.
The input device(s) 450 may be a touch input device such as a keyboard, mouse, pen, trackball, touch screen, or game controller, a voice input device, a scanning device, a digital camera, or another device that provides input to the computing environment 400. The output device(s) 460 may be a display, printer, speaker, or another device that provides output from the computing environment 400.
The communication connection(s) 470 enable communication over a communication medium to another computing entity. The communication medium

conveys information such as computer-executable instructions, audio or video information, or other data in a modulated data signal. A modulated data signal is a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media include wired or wireless techniques implemented with an electrical, optical, RF, infrared, acoustic, or other carrier.
Implementations can be described in the general context of computer-readable media. Computer-readable media are any available media that can be accessed within a computing environment. By way of example, and not limitation, within the computing environment 500, computer-readable media include memory 520, storage 540, communication media, and combinations of any of the above.
Having described and illustrated the principles of our invention with reference to described embodiments, it will be recognized that the described embodiments can be modified in arrangement and detail without departing from such principles. It should be understood that the programs, processes, or methods described herein are not related or limited to any particular type of computing environment, unless indicated otherwise. Various types of general purpose or specialized computing environments may be used with or perform operations in accordance with the teachings described herein. Elements of the described embodiments shown in software may be implemented in hardware and vice versa.
In view of the many possible embodiments to which the principles of our invention may be applied, we claim as our invention all such embodiments as may come within the scope and spirit of the following claims and equivalents thereto.

We Claim;
1. A method for creating a join between at least two distributed
extensible Markup Language (XML) documents, comprising:
determining number of elements to be compared for the at least two XML documents;
defining a traverse procedure for each compared element;
retrieving elements from a first document of the at least two XML documents that yields lesser number of elements while maintaining the hierarchy at the XML node and sending back to a XML processing endpoint where the first document of the at least two XML documents exists; and
creating the join between the retrieved elements and first document of the at least two XML documents.
2. The method of claim 1, wherein the traverse procedure for each compared element comprises obtaining projection of the compared element for the at least two XML documents.
3. The method of claim 1, wherein the traverse procedure for each compared element comprises of verifying if the compared element is at same level of hierarchy for at least two XML documents, then the document that yields less number of elements is eligible for transfer of elements to the other document of the at least two XML documents.
4. The method of claim 1, wherein the number of elements in the at least two XML documents is calculated after removal of duplicate elements in each of the at least two XML documents.
5. The method of claim 1, wherein the traverse procedure for each compared element comprises of verifying if the compared element is at different level of hierarchy for at least two XML documents, then defining an alternative action to

compensate for difference in the level of hierarchy prior to deciding the XML document for transfer.
6. The method of claim 5, wherein the traverse procedure for each compared element comprises selecting the document that yields lesser number of compared elements for transfer of elements to other document of the at least two XML documents after compensating for the difference in the level of hierarchy.
7. The method of claim 5, wherein the alternative action to compensate for difference in the level of hierarchy comprises assigning a plurality of points for each incremental depth level to the XML document where the compared element is deeper than the other document of the at least two XML documents.
8. The method of claim 7, wherein the plurality of points includes at least two additional overhead element tags.
9. The method of claim 5, wherein the alternative action to compensate for difference in the level of hierarchy comprises determining number of additional tags by multiplying the number of elements in the XML document in which the compared element is more deeper than in the other document of the at least two XML documents with the differential depth in the level of hierarchy.
10. The method of claim 9, wherein the alternative action to compensate for difference in the level of hierarchy comprises computing a compensation number by dividing the number of additional tags with number of tags required to represent the compared element in the other document of the at least two XML documents.
11. The method of claim 10, wherein the alternative action to compensate for difference in the level of hierarchy comprises calculating number of effective elements in the other document of the at least two XML documents by subtracting the compensation number from total number of elements in the other document of the at least two XML documents.

12. The method of claim 11, wherein the total number of elements in the
other document of the at least two XML documents is calculated after removing the
duplicate elements.
13. The method of claim 12, wherein the number of compared elements in
the other document of the at least two XML documents is equal to the number of
effective elements in the other document of the at least two XML documents.