WO2010029540A1

WO2010029540A1 - Rapid replication of sub-hierarchies from server to client computers

Info

Publication number: WO2010029540A1
Application number: PCT/IL2009/000876
Authority: WO
Inventors: Ilan Peleg
Original assignee: Ilan Peleg
Priority date: 2008-09-09
Filing date: 2009-09-09
Publication date: 2010-03-18

Abstract

A method for efficient handling and manipulating of information hierarchies that include multi-parent connectivity is disclosed. The hierarchy nodes are first mapped to a "Main tree" in which the path from the hierarchy root to each node is the longest possible and denoted "Main path". The Main path is further numerically specified by a "Numerical path" which is based on the hierarchical structure of the containing Main tree. The above notions are utilized for efficient transfers of sub-hierarchies from server to client computers. The client request for information is hierarchically formatted wherein the requested information may be specified for each node. The information that is transferred from the server in response is correspondingly formatted and may contain any combination if information types for each node, e.g. node name, its child nodes, its connectivity to parent nodes and associated content.

Description

RAPID REPLICATION OF SUB-HIERARCHIES FROM SERVER TO CLIENT COMPUTERS

FIELD OF THE INVENTION

[001] The present invention relates generally to the field of building up a semantic oriented working environment, based on fast copy of data hierarchies from server to client.

BACKGROUND OF THE INVENTION

[002] Information systems are normally organized in hierarchical order.

Simple systems, like file directories, are tree structured. The hierarchy structure in advanced information systems allow for multi-parent relationship between the hierarchy nodes. This feature is essential for providing multiple semantic meanings to the information objects in the hierarchy. However, the multi-parent feature implies excess complexity of usual operations like copy of sub-hierarchies from server computer to client computer, deletion of hierarchy nodes etc. That excess complexity impacts the performance of the relevant information systems, requires higher computing resources and loads the communication between servers and clients

[003] The present invention suggests how to considerably alleviate the above limitations by introducing an innovative method for efficiently handling and manipulating multi-parent hierarchies. In particular an efficient copy method is suggested that accelerates the transfer of sub-hierarchies while preserving their multi-parent property.

SUMMARY OF THE INVENTION

[004] The present invention solves the art limitations that are discussed in the background section by suggesting innovative methods for efficient handling and manipulating of information hierarchies that include multi- parent connectivity in server and client computers. Furthermore, a method for efficient copy of information hierarchies from the server computer to the client computer is suggested.

[005] The hierarchy nodes are first mapped to a "Main tree" in which the path from the hierarchy root to each node is the longest possible. This path is called the "Main path" of the node. Along a Main path, each parent node is defined as the "Main parent" of its child nodes and each child node is defined as a "Main child" of its Main parent. The location of each node in the Main child nodes table of its Main parent is called its "Ordinal number". The set of Ordinal numbers of the nodes along the Main path that connects the root to a specific node is called its "Numerical path".

[006] The node identification by its Numerical path is used in the present invention for easy retrieval and handling of hierarchy nodes while performing various actions like copy or delete. In particular, a copy action of sub-hierarchies from the server computer to the client computer is based on the Numerical path, while the Numerical path of each node is always preserved in the client version of the copied sub-hierarchy. A typical copy action refers to copy of a sub-hierarchy which is specified by its root's Numerical number and the requested depth, where depth is defined by the Main path length of the sub-hierarchy leaf nodes.

[007] The node information is transferred to the client in a nested format that corresponds to the hierarchical structure of the Main tree that pertains to the copied sub-hierarchy. The client would typically copy the node names and Main connectivity at first step and then would request additional information about all or part of the copied nodes, like node content and or connectivity to other parents than the Main parent. The client may delete nodes of no interest. This action is handled carefully by the client software part of the present invention in order to keep the necessary main connectivity and multi-parent connectivity at the client side intact.

[008] If the client wishes either to get from the server more information that relates to the nodes that are currently included in the client sub-hierarchy, or if more nodes shall be copied from the server hierarchy beneath the leaves of the client sub-hierarchy, the client software shall specify to the server the actual content of the client sub-hierarchy. This is done according to the present invention by sending the server the Ordinal numbers of the existing client nodes in a nested format that corresponds to the hierarchical structure of the actual client sub-hierarchy. The type of the requested information per each node can optionally be attached to its Ordinal number.

[009] Unless otherwise stated, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention relates. The methods, and examples provided herein are illustrative only and not intended to be limiting.

BRIEF DESCRIPTION OF THE DRAWINGS

[0010] The invention is herein described, by way of example only, with reference to the accompanying drawings. With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of the preferred embodiments of the present invention only, and are presented in order to provide what is believed to be the most useful and readily understood description of the principles and conceptual aspects of the invention. In this regard, no attempt is made to show structural details of the invention in more detail than is necessary for a fundamental understanding of the invention. Moreover, the drawings description that follows means to make apparent to those skilled in the art how the several forms of the invention may be embodied in practice. In the drawings:

[0011] Fig. 1 depicts the preferred data structures of server and client disk nodes.

[0012] Fig. 2 exemplifies "Main path", "No parent" and "Main child" notions of a disk node.

[0013] Fig. 3 illustrates the meaning and the way of creation of a disk node "Numerical path".

[0014] Fig. 4 illustrates a simple Server disk hierarchy and its Trimmed partial copy at the client side.

[0015] Fig. 5 A illustrates copy of Top sub-hierarchy from a Server disk hierarchy to a Client disk hierarchy.

[0016] Fig. 5B illustrates copy of Middle sub-hierarchy from a Server disk hierarchy to a Client disk hierarchy.

[0017] Fig. 6 clarifies some aspects regarding deletion of nodes at the Client disk hierarchy.

[0018] Fig 7. illustrates some typical forms that a Client disk hierarchy may acquire after some sequence of operations that are suggested in the present invention

DETAILED DESCRIPTION OF THE INVENTION

[0019] Fig. 1 illustrates a preferred embodiment of data structures of Server and Client disk nodes, which contains a set of fields that are needed in order to implement fast copy of disk hierarchies from a server computer to a client computer, as will be detailed in the subsequent paragraphs of this embodiment description. Server and Client disk nodes may contain, in other embodiments, additional fields such as the data type of the node content, last modification date etc.

A hierarchy, according to the present invention, is a data structure similar to a regular tree except that every node, except the root node, may have more than a single parent node. Consequently a node can be closer to the root than its parent. A path in the hierarchy is a directional route, either descending - along a node chain that connects parent nodes to child nodes, or ascending - along a node chain that connects child nodes to parent nodes. A two node connection actually comprises a descending pointer from a parent node to a child node, and the inverse ascending pointer from said child node to said parent node. A "disk hierarchy" is defined as a hierarchy of disk nodes, either in the server or in the client computer.

[0020] All the data tables and fields that are depicted in Fig. 1 reside in the dynamic memory of the corresponding computer, while the content 103 of the node, e.g. HTML lines, resides in a disk or in any other storage device that is connected to the corresponding computer. All the pointers or addresses in Fig. 1 and in all the other figures that are hereby described constitute virtual addresses, which are mapped by the memory management function of the underlying operating system to the dynamic memory of the hosting computer, unless otherwise mentioned. Table 101 contains pointers to other data structures of the node as well as additional node variables. Following are explanations to the various fields of table 101.

[0021] Name pointer field 110 points to the name of the node 102, which is a string that resides in the dynamic memory as well. Size field 111 contains the byte count of the content 103 of the node. This size may be 0.

Content pointer field 112 contains the number of the first disk block of the content 103 of the node. In the simple case this content resides in subsequent disk blocks in the current disk partition. If this is not the case, list of disk blocks and location of disk partition fields are used in the usual manner. GUI pointer field 113 points to the GUI object 104 that represents the current node when it is displayed by the GUI software. If the node is currently not displayed by the GUI the value of this field is null.

[0022] Children pointer field 114 points to the first entry of Array of child entries 105. If the current node has no children this field value is null. The Array of child entries 105 contains a row for each child node of the current node. Each row comprises the following 3 fields that pertain to the corresponding child:

Type field 117 attributes the child node as either Main or regular child. Main attribute is defined in the description of Fig. 2 hereafter. Address field 118 contains the memory address of the child node. Invisible attribute field 119 exists only at the Client disk node data structure and is defined in the description of Fig. 6 hereafter.

[0023] Parents pointer field 115 of table 101 points to the first entry of Array of parent entries 106. If a node has no parent, i.e. in case of the root node, the value of this field is null. This array contains a row for each parent node of the current node. Each row comprises the following 3 fields that pertain to the corresponding parent:

Address field 120 contains the memory address of the parent node. Numerical path 121 is defined in the description of Fig. 3 hereafter. Ordinal number 122 is defined as the entry number of the current node in the Array of child entries of the corresponding parent disk node. The last two fields exist in array 106 in Client disk node data structure only.

[0024] The other fields 116 that are included in table 101 are the following: Note: The initialization values in the following fields are used by the algorithm that computes the longest path to each of the nodes in the server disk hierarchy. a. Length of longest path from the root node to the current node. It is initialized to 0. b. No number - the entry number in the Array of parent entries that contains the No parent of the current node. "No parent", which is a synonym name to "Main parent", is defined as the parent of the current node that pertains to the longest path that connects the node to the root. The longest path in called in the context of this invention "Main path". If several equal length longest paths connect the node to the root one of them is chosen to be the Main path. No number is further explained in the description of Fig.2 hereafter. It is initialized to -1. c. Access counter - an auxiliary field that counts the times the current node is accessed by the longest path algorithm. It is initialized to 0. d. Size of the Array of parent entries. e. Size of the Array of child entries. f. Ordinal number - the entry number of the current node in the Array of child entries of the No parent of the current node. g. Number of parents. This field is relevant in the client only. h. Copy / download status: 0 = hierarchy only, 1 = other patents, 2 = content. This notion is explained hereafter. Fig. 2 exemplifies the notions "Main path", "No parent", Other parent and "Main child". All those notions are based on the notion of "longest path" which connects a given node to the hierarchy root. In Fig. 2 the longest path length is depicted beneath the name of each node. In Fig. 2a the D -> C connection 212 is not taken into account yet, hence the longest path length to any of the nodes C 204 and D 205 is 2. In Fig. 2b D -> C connection 212 is taken into account, hence the longest path of C is moved rightward to traverse nodes B 203 & D 205 rather than A 202, hence its length increases to 3. Once a longest path is found for a node in a Server disk hierarchy it is defined as the Main path of that node. The parent of a node along its Main path is defined as the "No parent" of this node. Each given node, except the root, always has one and only one No parent. That given node is defined as "Main child" of its No parent. Obviously a Main child descending pointer that pertain to its No parent node is the inverse pointer of the ascending pointer that pertains to the pointed Main child node and points to that No parent. Note that a given node may have 0 or more Main child nodes. In Fig. 2 all the pth segments along the main paths, which connect No parent to Main child, are denoted "no" and numbered 211. Following is a preferred recursive algorithm that would find out all the No parents within a given Server disk hierarchy in the described embodiment. Note that when exerting the algorithm the number of parents is known for each node in the Server disk hierarchy as the size of its Array of parent entries. The node names of Fig. 2 are used in the following description. a. Each currently processed node C, except the root, is assigned a main parent which is initialized to be the first parent node via which this node is first reached within the recursive processing. A length is also assigned to node C, which is initialized to 0, is calculated to be 1 plus the length of the main parent of node C, and is increased to be 1 plus the length of the parent node D via which this processed node is reached in a given step within the recursive processing if and only if the length of that node D is equal or higher than the length node C, wherein in this case node D is determined to be the new main parent of node C. b. The recursive processing continues to the child nodes of node C if and only if C has been already reached via all its parent nodes within the hierarchy. c. In each step where the No parent of a node has been changed within the algorithm, the appropriate fields and pointers are updated in that node and in the previous and new No parents before the next node is processed.

[0027] Any parent of a disk node that is not its No parent is called its "Other parent". In fig.2 for example, as a consequence of the transition from 2a to 2b, node A parenthood relation relative to C turns from No parent to Other parent because node D has become the new No parent of C.

[0028] Fig. 3 illustrates the meaning and the way of creation of a disk node "Numerical path". Each path segment from parent to child is marked in Fig 3 with the child's Ordinal number that refers to the corresponding parent, which is the location of that child pointer within the Array of child entries of that parent. For example, Ordinal number 1 means the second child pointer because counting always starts at 0 in the described embodiment. The Ordinal numbers of node A 301 are denoted 305 and run from 0 to 5. The Ordinal numbers of node B 302 are denoted 306 and run from 0 to 3. Numerical path of a given node is defined as the Main descending path of the node wherein each node along the path, except the root node, is replaced by its Ordinal number relative to its No parent. Thus, the Numerical path of C 303 is {2, 1 }, which is the Ordinal numbers sequence along its Main path 304. The pointers 314 and 324 that correspond to Main path 304 are depicted in the arrays of child pointers of nodes A and B, which are tables 310 and 311 correspondingly.

[0029] Fig. 4 illustrates a Server disk hierarchy and a Client disk hierarchy wherein the later constitutes a "Trimmed copy" of the Server disk hierarchy. Normally a large disk hierarchy resides in the Server and the user copies only a part of it to his client computer. Such copy would constitute a Client disk copy that meets the conditions of the present invention if the following basic rules are kept for each copied node: a. For each Server disk node in the Server disk hierarchy there is at most one copied node in the Client disk hierarchy. b. The name pointer in each client disk node points to client side copy of the name of the node. c. When a node is copied its content may not be copied. Only names, pointers and some of the node fields are usually copied. d. If node A is copied from a Server disk hierarchy to a Client disk hierarchy then all the nodes along the Main path of Server disk node A are copied as well to the client disk hierarchy. This is illustrated in Fig. 4 by nodes 401 and 402 along the bold marked Main path of node A 403 which are necessarily copied from Server disk hierarchy 410 to Client disk hierarchy 411. All the other nodes in the figure are denoted as 404. Only part of them are copied in this example to the client and denoted 414. e. For each copied Client disk node A its numerical path is identical to the numerical path of Server disk node A from which it was copied. This is illustrated in Fig. 4 by the Ordinal numbers of 401, 402 and 403, which constitute A's numerical path, are depicted in box 420 and are preserved in 411. The following additional trimmed copy rules relate specifically to Child pointers: a. If a Server disk node points to M child nodes than the Array of child entries 105 of the corresponding copied Client disk node contains first M entries that are dedicated for said M Server disk child nodes. In particular they are located in the same Ordinal numbers as in the server side. After the copy action, some or all of said first M child entries in the copied node may acquire a Null value or any other special value which means temporary not used. However they may be later repopulated. This is illustrated in Fig. 4 by the lines without nodes in 414, which signify reserved entries in the Arrays of child nodes of 400, 401 and 402 nodes in 411 hierarchy. b. The copied Client disk node may acquire new child nodes and pointers that the user may add. Those will populate the children arrays beyond said first M input slots. This is depicted in Fig. 4 by node 418. c. The above child pointer rules are mandatory in order to support fast copy operation according to the present invention. However, these rules are recommended, and actually applied in the described embodiment, for parent pointers as well, for the sake of consistency and simplicity. Fig. 5a illustrates copy of a sub-hierarchy from a Server disk hierarchy that resides in server computer 511, starting from the root 521, in order to create a new Client disk hierarchy in the client computer 512. This basic operation is called "copy Top sub-hierarchy" in the present invention. The Server disk hierarchy is represented in the drawing as triangle 501. The server side Top sub-hierarchy is depicted as a smaller triangle 502. The copy is illustrated by arrow 513. The newly created Client disk hierarchy is depicted as triangle 503, which is identical to triangle 502 in terms of the contained nodes. Top sub-hierarchy 503 constitutes a Trimmed copy of Server disk hierarchy 501, for which the above defined Trimmed copy rules should apply. When a sub-hierarchy is copied the copy action refers basically to Main child nodes only, starting from the root. Those Main children constitute a regular tree, i.e. where each node (except the root) has only a single parent. [0032] A copy Top sub-hierarchy request shall include at least the following three parameters: a. Depth of the requested Top sub-hierarchy, which is the length of Main path that connects the root with any leaf node of the sub- hierarchy. It is denoted in Fig. 5a as D_τ 516. b. Server address, which actually contains the hierarchy number in the server and should be supplied to the user e.g. by the system administrator. c. Copy phase, which is selected out of the following three modes. Note that each phase is interpreted by the server software as including the previous phases, e.g. phase (3) would include phases (1) and (2).

(1) Copy hierarchy - Nodes are copied along with names but without content. Only Main paths related connectivity information is transferred to the client computer.

(2) Copy other parents - Other parent connectivity information is transferred as well.

(3) Copy content - nodes content is transferred as well.

Phase (1) is typically used for copy Top sub-hierarchy and copy Middle sub-hierarchy that is described hereafter. Phase (2) and (3) are typically used in a selective request of nodes, which is later described, that the user would issue after examining the Client disk hierarchy that has been earlier copied by copy Top sub-hierarchy or copy Middle sub-hierarchy.

[0033] For building the Client disk hierarchy 503 its root node 521 is first created, typically as a child of a higher root node of all Client disk hierarchies. The server address is then associated with the created root node. The data that is transferred from server to client in phase (1) is formatted as follows < Root name, No number, Size Array of parent entries, Size Array of child entries > (Main child 1, Main child2,... ) where each of nested Main childl, Main child2,... and their children etc. are all formatted like the Root. No number is always 0 in the root node because it has no parents. This data formatting saves transfer capacity because the Main connectivity of the copied sub-hierarchy is implied from the nesting structure of the transferred data formatting. Note: the above node's attributes format is designated hereafter as < attributes >.

[0034] Fig. 5b illustrates copy action 514 of Middle sub-hierarchy 502 from a Server disk hierarchy 501 to a Client disk hierarchy 503. A Middle sub- hierarchy is defined as a group of Main child nodes within a larger disk hierarchy that are the descendants of a given node, which is designated in the figure M 522. This given node constitutes a root for the Middle sub- hierarchy. A depth parameter D^ 517 specifies the length of Main path that connects M with any leaf node of the Middle sub-hierarchy 503. A request for copy of a Middle sub-hierarchy from a Server disk hierarchy to a Client disk hierarchy shall include the following parameters: a. Address of the server in which the Server disk hierarchy resides. This can be supplied by the system administrator. b. Numerical path of the root of the Middle sub-hierarchy 522 to be copied. This can be supplied by the system administrator. c. Depth of the requested Middle sub-hierarchy 517. d. Copy phase, typically hierarchy only.

[0035] When the server receives a request for copy of Middle sub-hierarchy it shall first locate the Middle sub-hierarchy root node M 522according to its Numerical path. All its actions from this point forth are the same as in the case of copy Top sub-hierarchy, including the data that it transfers to the client side. The client software associates the server's address and the Numerical path of the Middle sub-hierarchy root M 522 with the data structure of that root in the Client disk hierarchy. All the client software actions from this point forth are the same as in the case of copy Top sub- hierarchy.

[0036] After either a top or a middle sub hierarchy were copied from the Server to the client, typically in phase (1) that comprises main connectivity and node names, the user may examine the copied names and may request accordingly to copy, for example, a Middle sub- hierarchy that stems from a specific node N 523 that has been already copied to the client. This copy is illustrated in Fig 5b as arrow 515. The copied Middle sub-hierarchy is depicted as "triangle" 504, which comprises triangle 505 that already exists in the Client disk hierarchy and trapezoid 506 beneath 505 that shall be copied from the server. In this case the client software sends the server software the Numerical path of N as a concatenation of R^M and M->N, the depth of the sub-hierarchy 505 and the depth of 504. The server software would transfer in response a plurality of Middle sub-hierarchies, the root of each is a leaf of 505, the depth of each is 504 depth minus 505 depth. The data format of each of those Middle sub-hierarchies is given in [0033] abovef&ΘS&j — abeve- where only the root's < attributes > are redundant.

[0037] The user may also request to complete the information of sub-hierarchy 505 to either phase (2) or phase (3) as defined in [^"00321 c abover0027] c above. If phase (2) is requested the server would append within the < attributes > part of each node in 10033] above{00281 above a list of numerical paths of all the Other parent of that node. If phase (3) is requested the server would append within the < attributes > part of each node in [00331 abovefOO^&l — abθ¥© a list of Numerical paths of all the Other parents of that node plus a link to its content. The client software fills the Other parents Numerical paths in the corresponding fields in the Array of parent entries of each transferred disk node. Then a special client software process goes over all the Client disk nodes and for every Other parent Numerical path that lacks an Other parent pointer it checks if that Other parent exists in the Client disk hierarchy and if positive it attaches its memory address to its Numerical path in the appropriate Other patent entry.

[0038] Fig. 6 clarifies some aspects regarding deletion of nodes in the Client disk hierarchy.

Fig. 6a illustrates a case wherein a user uses the GUI of a Client disk hierarchy and marks a current child node A 600 for deletion from the point of view if its current parent P 601. IfP were a regular parent both the pointers to and from A would be deleted. As P is a main parent of A, A will assume a status of Invisible in the GUI from the point of view of P. Besides, A is assigned Invisible in the Array of child entries of P. This is denoted by the notation 610 IMCP which means Invisible Main Child Pointer. However, the mutual pointing P <→ A shall be retained for preserving the main path of node B 603, for example, as dictated by the trimmed copy rules in [00291 [0024] above. Pointing 611 is denoted MCP to indicate that B is a a Main child of A. The child nodes of A, 603, 605 and 606 are not candidates for deletion because they shall be allowed for access from Q 602 via A.

[0039] Fig. 6b illustrates a case wherein the user has deleted A from the point of view of both P 601 and Q 602. In this case there is no parent of A that would like to access A's children via A, hence the client software would descend to all A's children in order to exert recursively the same process as was previously exerted on A. Therefore A -> B pointer 611 turns from MCP to IMCP and so on.

Fig. 6c illustrates a case wherein the recursive deletion process has reached L2 605. Though there is no parent of L2 that wishes to access it, it can't be deleted due to the need to preserve the main path of Ll 607. Then the deletion process reaches Ll as L2's child, and deletes Ll and pointing 613 because it cannot be accessed by any parent and no main child shall be accessed via Ll. Consequently L2 becomes an IMCP leaf node, hence L2 and its pointing 612 can be deleted as Ll was deleted previously. The process further ascend to A but cannot delete it because it is not a leaf.

[0040] Fig. 7a illustrates a typical form which a Client disk hierarchy 701 may acquire after some sequence of copy and deletion operations of the types that were described above. Fig. 7 further illustrates copy actions like those discussed in IO0361 1^"003 Il and 1^"0037I above[0032] above in a more complex situation where the Client disk sub-hierarchy form is not a simple triangle, i.e. its leaf depths, in terms of main path length, is not uniform. Fig. 7a illustrates the corresponding Server disk hierarchy.

[0041] The user may wish to copy from the server a Middle sub-hierarchy of depth D_N 710 that stems from node N 712 and depicted as triangle 702. The dotted part of this sub-hierarchy - 703 already resides in the client computer. Hence only the lined area 704 shall be copied from the server. Hence the client software would issue a request that comprises a plurality of sub-hierarchies, each of them stems from another leaf of 703 and has a depth D_R 702 of D_N - D_L, where D_L 711 is the leaf depth. The user may, alternatively, specify a uniform depth D_R for all the requested sub- hierarchies.

[0042] The user may also wish to complete the information within sub- hierarchy 703 to either phase (2) or phase (3) as defined in [00321 c above[0027] c above. However, the information that is currently available in each node may not be the same because, for example, either Other parents or content might have been already copied from the server earlier for part of 703 nodes. In this case the client software would issue an "Ordinal number hierarchy" based request that is formatted per each node in the specified sub-hierarchy as follows: ■Ordinal number, Attributes code> (Main child 1, Main child2, ...)• For the root node, which is N in case of sub-hierarchy 703, its Numerical path substitutes the Ordinal number. "Attributes code" indicates the specific information that is requested for the specific node. In the general case it may be any combination of {name, Other parents connectivity, content,... } e.g. by assigning a bit for each attribute. Each of nested childl, child2,... and their children etc. are all formatted like their parents. The Ordinal number hierarchy indicates the server software the exact structure of the Client disk hierarchy 701 as part of the Server disk hierarchy 700 in Fig 7a. In fig. 7 root 711 is common to both hierarchies.

[0043] The format and structure of the data that is transferred from the server in response to the above request is similar to the request format, except that the requested information comes in the place of the Attributes code. The Ordinal numbers are optional because are implied for the client software from the structure of the request.

The above request format wherein the Attribute codes of all the nodes are null describes the main path connectivity of the specified sub hierarchy. This may be used, for example, by userl to exports a sub-hierarchy structure to user2 who would then request from the server the node names and any other information about the exported nodes. The request format of paragraph [0042] abovefθθ^l — above may be also used for a simple tree where the nodes are any child nodes rather than main only.

[0044] Persons skilled in the art will appreciate that the present invention is not limited to what has been particularly shown and described hereinabove. Rather the scope of the present invention is defined by the appended claims and includes both combinations and sub combinations of the various features described hereinabove as well as variations and modifications thereof, which would occur to persons skilled in the art upon reading the foregoing description.

Claims

What is claimed is:

1. A method for constructing a data structure in a computer, the method comprising: providing a hierarchy of logical nodes, wherein each of said nodes contains some data structure that may includes but is not limited to a pointer to some content that is thus associated with said logical node, wherein each of said hierarchy and content are retained in either a physical memory or in some storage device that is connected to or comprised within said computer; providing one, zero or a plurality of pointers for each of said nodes; for each node provided, pointing each pointer to another node in said hierarchy that is defined as a "child" of said pointing node, such that each node except the root node of said hierarchy is pointed by either one or a plurality of nodes, which are defined the "parents" of said pointed node, wherein one and only one of the parents of each pointed node is defined as the main pointing node of said node and is defined the "main parent" of said pointed node while said pointed node is defined "main child" of said main parent; and connecting said root node to each node in said hierarchy by an accumulated path, said path comprising transitions from nodes to their child nodes only along said longest path, such that said path is the longest possible path in terms of number of traversed nodes within said hierarchy, which is defined the "main path" that connects said node to said root, while the number of said traversed nodes plus 1, due to said node itself, is defined as the length of said main path.

2. A method for constructing a data structure in a computer, the method comprising: providing a hierarchy of logical nodes, wherein each of said nodes contains a pointer to content associated with said logical node, wherein each of said hierarchy and content are retained in either a physical memory or in some storage device that is connected to or comprised within said computer; providing a table of one, zero or a plurality of pointers for each of said nodes, wherein each of said pointers is assigned an Ordinal number in said table; for each node provided, pointing each pointer to another node in said hierarchy, which is defined a "child" of said pointing node, such that each node except the root node of said hierarchy is pointed by either one or a plurality of nodes, which are defined the "parents" of said pointed node; identifying each node within said hierarchy according to a series of the Ordinal numbers of all the pointers that comprise a path within said hierarchy that connects said node with said root node; and defining a numerical path for said node according to said series of Ordinal numbers.

3. The method of claim LJk-wherein the main parent of each node except the root is determined in a recursive processing of the nodes along said hierarchy, starting from the root; wherein each currently processed node except said root is assigned a main parent which is initialized for said currently processed node to be the first parent node via which said currently processed node is first reached within said recursive processing, a length is also assigned to said currently processed node, which is initialized as 0 for said root, is calculated to be 1 plus the length of the main parent of said currently processed node, and is increased to be 1 plus the length of the parent node via which said currently processed node is reached in a given step within said recursive processing if and only if the length of said parent node is equal or higher than the length of said currently processed node, wherein in this case said parent node is determined to be the new main parent of said currently processed node; and said recursive processing continues to the child nodes of said currently processed node if and only if said currently processed node has been already reached via all its parent nodes within said hierarchy.

4. The method of claim 2J-k-wherein the numerical paths of a node or a group of nodes are used for locating said node or group of nodes for performing common operations including but not limited to copy or delete.

5. The method of claim ZJ_-r-wherein each child node contains also pointers to either part or all its parent nodes, as well as the Ordinal numbers of said child node that relates to said parent nodes, such that the numerical path of a given node can be generated by going upward from said node along a path of child to parent pointers up to the root node, while prepending the Ordinal number of each traversed nodes, starting with that of said given node, to the generated numerical path.

6. The method of either claim L_4τ-or claim a3- wherein a first hierarchy of nodes resides in a first computer, a numerical path is assigned to any node within said first hierarchy, further comprising copying a node or a group of nodes from said first hierarchy to a second computer, such that said copied node or group of nodes constitute a second hierarchy that may comprise either the whole or part of the nodes of said first hierarchy, wherein said second hierarchy forms a trimmed copy according to the following rules: a. for each node that pertains to said first hierarchy there is at most one copied node in the second hierarchy, b. for each node that is copied from said first hierarchy to said second hierarchy all the nodes along the main path of said copied node in said first hierarchy are copied as well to said second hierarchy, and c. after a node is copied from said first hierarchy to said second hierarchy its numerical path along its main path in said second hierarchy is identical to that in said first hierarchy.

7. The method of claim 4^-expressing numerical paths that pertain to a node or a group of nodes as a concatenation of two or more numerical paths.

8. The method of claim (xJir-Further comprising copying a second hierarchy of nodes from said first hierarchy to said second computer, wherein said second hierarchy may be either the whole or part of said first hierarchy, and wherein the second hierarchy is specified to said first computer in the request for copy by the numerical path of the root of said second hierarchy within the first computer and a depth parameter, and wherein that request would result said first computer to transfer to said second computer all the main child nodes that pertain to said first hierarchy that are direct or indirect child nodes of the specified root and the length of their main path is limited to said depth parameter.

9. The method of claim (xJjr-Further comprising adding nodes to said second hierarchy while said trimmed copy rules are still kept for all the nodes that were copied to said second hierarchy from said first hierarchy.

10. The method

a given node that pertains to said second hierarchy from said second hierarchy such that said given node is invisible to users of said second computer or associated content of said given node is deleted, while leaving said given node in said second hierarchy as a main parent of another node to avoid violation of any of said trimmed copy rules..

11. The method of claim

or a group of nodes that pertain to a hierarchy and form a tree structure within said hierarchy are identified by the numerical path of the root node of said tree and farther recursively such that each node's data structure format comprises its Ordinal number and a nested list of its child nodes that are formatted in the same manner.

12. The method

the information about the copied nodes is transferred from said first computer to said second computer recursively in a way that each node's data structure format comprises a nested list of its child nodes that are formatted in the same manner.

13. The method of claim 11. 44τ-wherein said identification is applied to the format of a copy request that said first computer sends to said second computer while requesting some information that refers to a tree structured group of nodes within said second hierarchy.

14. The method of claim 11. wherein said group of nodes adheres to said trimmed copy rules and said identification is applied to the format of a message that is sent to a user that can connect to said first computer, for indicating him about a group of nodes within said first hierarchy that may be of interest to him.

15. The method of claim 12. -l^-W-wherein additional information elements are transferred per each copied node, while non limiting examples of said information elements are name of the node, its content and a table of numerical paths of its parents.

16. The method of

comprising associating an attributes code with part or all the nodes for which some information is requested from said second computer, and said code indicates for said second computer the type or combination of types of information that is requested for said nodes.

17. The method of claim 16, wherein said information types comprise one or more of the node's content and a table of numerical paths of its parents.

18. The method of claim 13.4-3_^- wherein the data that is transferred from said second computer to said first computer in response to said request for information is formatted recursively in the same manner as in said request, besides that the requested information itself is sent in addition or instead of the Ordinal number of each node for which said information was requested.

19. The method of claim 13. 43τ-wherein said group of nodes adheres to said trimmed copy rules and said copy request indicates to said first computer that said requested information refers to nodes that pertain to hierarchies that are partial to said first hierarchy, wherein the root nodes of said partial hierarchies are the leaf nodes of said trimmed copy hierarchy and the depth of each said partial hierarchy is specified in said request, as either specific or the same for all of said partial hierarchies.

20. The method and system of claim 15. 45τ-wherein the information that is transferred from said first computer to said second computer is further formatted in XML.

21. The method of claim 18. 4-Tτ-wherein some status code is added to said response in addition or instead of the Ordinal number of each node for which said information was requested.