SYSTEM AND METHODS FOR SEARCHING DOCUMENTS IN A RELATIONAL DATABASE USING A TREE STRUCTURE STORED IN A TABULAR FORMAT

System and methods of searching documents in a relational database that includes receiving a search query from an application; identifying, via an ancestry table, node identifiers corresponding to the search query; determining, from the corresponding node identifiers, ancestor node identifiers having a depth value greater than zero; and displaying identifiers associated with the ancestor node identifiers to a user. Each entry in the ancestry table includes a node identifier, an ancestor node identifier associated with the node identifier and a depth value corresponding to a distance between the node identifier and the ancestor identifier.

REFERENCE TO SEQUENTIAL LISTING, ETC.

BACKGROUND

1. Field of the Disclosure

The present disclosure relates generally to processing a hierarchical model, and more specifically, processing a tree structure having one or more nodes.

2. Description of the Related Art

Hierarchical data structure models, such as a tree, have been widely used in computer science to store and organize data. Some of the most common uses of trees include representing hierarchical data, storing searchable data, routing algorithms, and representing sorted lists of data. There are many different applications of trees and consequently, there are many different algorithms available for manipulating tree structures. However, many of these existing algorithms perform a systematic visit to all the nodes in the tree, a process that is also called tree traversal.

Tree traversal refers to a process of examining and/or updating each of the nodes in a given tree. Traversal of a tree may be defined recursively such that most methods of traversing a tree involve a process of iteration or looping over the nodes in the tree. For trees not having a linear data structure, or trees having one or more nodes containing more than one possible next node, deferring some nodes during the tree traversal may be performed. For example, the deferred nodes may be implicitly stored and visited at a further step in the tree traversal process. While tree traversal is used in several operations, such as searching for and returning nodes having a certain property, the recursive nature of the process may make tree traversal slow and time-consuming, especially when the tree to be processed is large. Additionally, queries performed using tables stored in a relational database may be expensive to perform, and executing queries on tree structures, and as part of a recursive step, may represent prohibitive costs in computational time and memory usage.

Thus, there is a need for a more efficient method of processing a hierarchical model or a tree structure in a relational database in order to perform more efficient and fast queries on the tree without undergoing recursion or tree traversal every time a query is executed.

SUMMARY

System and methods of searching are disclosed herein. A first example embodiment of searching documents in a relational database includes receiving a search query from an application; identifying, via an ancestry table, node identifiers corresponding to the search query; determining, from the corresponding node identifiers, ancestor node identifiers having a depth value greater than zero; and displaying identifiers associated with the ancestor node identifiers to a user. Each entry in the ancestry table includes a node identifier, an ancestor node identifier associated with the node identifier and a depth value corresponding to a distance between the node identifier and the ancestor identifier.

A second example embodiment of searching a tree structure having one or more nodes includes receiving a search query; identifying, via an ancestry table, nodes matching the search query; returning the matching nodes; and using the matching nodes to identify corresponding container nodes. In an aspect of this example embodiment, the tree structure may correspond to a file system, and the one or more nodes of the tree structure may correspond to documents and/or folders in the file system.

DETAILED DESCRIPTION

It is to be understood that this disclosure is not limited to the details of construction and the arrangement of components set forth in the following description or illustrated in the drawings. This disclosure is capable of other example embodiments and of being practiced or of being carried out in various ways. For example, other example embodiments may incorporate structural, chronological, process, and other changes. Examples merely typify possible variations. Individual components and functions are optional unless explicitly required, and the sequence of operations may vary. Portions and features of some example embodiments may be included in or substituted for those of others. The scope of this disclosure encompasses the appended claims and all available equivalents. The following description is, therefore, not to be taken in a limited sense, and the scope of the present disclosure is defined by the appended claims.

Also, it is to be understood that the phraseology and terminology used herein is for the purpose of description and should not be regarded as limiting. The use herein of “including,” “comprising,” or “having” and variations thereof is meant to encompass the items listed thereafter and equivalents thereof, as well as additional items. Further, the terms “a” and “an” herein do not denote a limitation of quantity, but rather denote the presence of at least one of the referenced item.

In addition, it should be understood that example embodiments of this disclosure include both hardware and electronic components or modules that, for purposes of discussion, may be illustrated and described as if the majority of the components were implemented solely in hardware.

It will be further understood that each block of the diagrams, and combinations of blocks in the diagrams, respectively, may be implemented by computer program instructions. These computer program instructions may be loaded onto a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions which execute on the computer or other programmable data processing apparatus may create means for implementing the functionality of each block or combinations of blocks in the diagrams discussed in detail in the description below.

These computer program instructions may also be stored in a non-transitory computer-readable medium that may direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable medium may produce an article of manufacture including an instruction means that implements the function specified in the block or blocks. The computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions that execute on the computer or other programmable apparatus implement the functions specified in the block or blocks. Output of the computer program instructions, such as tables corresponding to tree structures, as will be described in greater detail below, may be displayed in a user interface or computer display of the computer or programmable apparatus that implements the functions or the computer program instructions.

Disclosed are methods of processing a tree structure having one or more nodes. The method may include identifying container nodes of the tree structure and generating a depth value for each pair of the container nodes identified, wherein the depth value corresponds to a distance between the container nodes identified in the tree structure.

As used herein, a tree structure may refer to a data structure that stores and organizes data by simulating a hierarchical tree structure with a set of one or more linked nodes. The tree structure may be a collection of one or more nodes, wherein each node may consist of a value.

For illustrative purposes, the example tree structures discussed in this disclosure are represented as growing downwards. The tree structure may include at least one node, which may include a value and/or a condition.

Each of the nodes in the tree structure may have no child nodes or contain one or more child nodes. Child nodes are nodes that are connected below a particular node in the tree structure. A node in the tree structure having a child may be referred to as the child's parent node. A node that has no or zero child nodes is a leaf node. A leaf node may also be referred to as an outer node, an external node, or a terminal node.

A container node refers to any node of the tree structure that contains at least one child node. The container node may also be referred to as an inner node, an internal node or a branch node.

The tree structure has a topmost node that may be referred herein as a root node. The root node, being the node at the top of the tree structure, does not have a parent node. For illustrative purposes, the root node may be represented as the node drawn at the top of the tree.

In one example embodiment, the tree structure may refer to a file system, and the one or more nodes of the tree structure may refer to documents and/or folders in the file system organized hierarchically. Nodes that refer to documents may be represented by leaf nodes while nodes that refer to folders may be represented in the tree structure as container nodes.

FIG. 1illustrates one example tree, tree structure or hierarchical model100. Example tree100has four container nodes105,110,115, and120, labeled Node X, Node W, Node Y, and Node Z, respectively. Example tree100also has one leaf node125, labeled as Node A.

FIG. 2is one example method of processing a tree structure or hierarchical model and creating or generating a corresponding hierarchical or ancestry table.

At block205, a tree structure to be processed may be received. Receiving a tree structure may include receiving a hierarchical model from a user of the computing device. In some alternative example embodiments, receiving a tree may include identifying a hierarchical model stored in the memory of the computing device for processing.

Processing a tree structure or hierarchical model may include generating an ancestry or hierarchical table corresponding to the tree structure, as will be described in greater detail below.

At block210, an ancestry or hierarchical table corresponding to the tree structure may be created. The hierarchical table is a table which lists container nodes corresponding to the tree structure. The hierarchical may include multiple columns such as a Node_ID column, and Ancestor_ID column, and a Depth column.

The Node_ID column may include identifiers or values corresponding to container nodes from the tree structure. The ancestor identifier may correspond to the node represented by the node identifier generated. The Ancestor_ID column may include identifiers or values corresponding to one or more immediate or non-immediate parent nodes of the node in the Node_ID column. For every row entry in the hierarchical table, an ancestor identifier may be paired or associated with a container node identifier, and this pair may be referred to as a node-ancestor pair. All nodes in the tree structure received at block205may be generated with at least one entry in the table.

The Depth column contains values indicating the depth or distance between the container node and parent node of the same row (i.e., the node-ancestor pair). For example, for identity relationship records wherein the ancestor identifier paired with the node identifier is the node identifier itself, the depth value of the node-ancestor pair may be “0”. This indicates that the container node referred to by the ancestor identifier and the node identifier is the same node, thus the two identifiers having “0” depth or distance from each other. In another example, if the ancestor identifier paired with the node identifier is the immediate parent of the node, the depth value of the pair may be “1”.

The use of identifiers corresponding to the container nodes and nodes a table for illustrative purposes and should not be considered limiting. The example embodiments detailed in the present disclosure may also be performed without the use of identifiers, as is known in the art.

An entry in the hierarchical table having a node identifier and an ancestor identifier that refer to the same node may be referred to herein as an identity relationship entry of the node. In alternative example embodiments, the ancestor identifier may refer to a parent node of the node identifier. In other alternative example embodiments, the ancestor identifier may refer to the parent of the parent node. In yet other alternative example embodiments, each node identifier may be generated with an entry in the table with a corresponding ancestor identifier (i.e., a node-ancestor pair) until the ancestor identifier paired with the node identifier is the root node, as will be described in greater detail below.

In some example embodiments, additional columns indicating one or more properties of a node may be included in the table. For example, additional columns may include a user-definable name for the node, a timestamp indicating the time at which the node was added to the tree structure, and/or a status indicating whether the node is locked for modification by an entity in a multi-user system. Other properties may be apparent to one of ordinary skill in the art.

At block215, an entry in the hierarchical table may be generated. The entry or row in the table includes a node-identifier pair, which consists of node identifier and ancestor identifier, and a depth value for each node-ancestor pair. The entry in the table may be added by the user of the computing device, or may be added automatically through one or more methods that will be apparent.

FIGS. 3A-3Cillustrate example tree structure100ofFIG. 1and its corresponding table at various stages of generation using the example method ofFIG. 2.FIG. 3Dillustrates a hierarchical table300for example tree100after the processing of tree100has been completed.

Example tree portion100a,100b,and100chave one or more nodes, with corresponding tables100a′,100b′,and100c′, respectively. Example tree portions100a,100b,and100cand corresponding hierarchical tables100a′,100b′,and100c′, respectively are described herein for illustrative purposes and should not be considered limiting.

Each of tree portions100a,100b,and100crepresent example tree100that is built over time, with tree portion100abeing the starting point of the tree generation and tree100being the end point in example tree100generation. Similarly, hierarchical tables100a′,100b′ and100c′ show the building of hierarchical table300corresponding to example tree structure100, in conjunction with method100ofFIG. 2.

Tree portion100acontains one node—Node X. Node X may be the topmost node in tree100aand subsequent trees100band100c,and may be referred to as the root node. As will be known in the art, node X, being the topmost node, does not have a parent node.

Table100a′ inFIG. 3Amay contain one entry320corresponding to node X in tree300a.In entry320, NODE_ID305contains X which may refer to an example unique identifier for node X in tree300a.ANCESTOR ID310may contain X which may refer to the unique identifier for node X in tree300a.Depth value in DEPTH315for the node-ancestor pair in entry320is “0,” which may indicate that the node identifier and the ancestor identifier in entry320may correspond to the same node in tree300a.Entry320may be an example identity relationship entry—an entry having depth value “0”, and may indicate a node's relationship with and distance from itself.

As seen inFIG. 3B, in tree100b,container node W110and leaf node A125may be added as descendants of node X105. With the addition of node W125, two records may be added in table100b′ in order to correspond to the updated tree100b.In table100b′,entries325and330may be added to the table—an identity relationship for node W (entry325) and a relationship entry between node W and node X (entry330). The depth value in entry330is “1”, which may correspond to the distance between nodes W and Y. With the addition of node A, one record335may be added in table300b′ in order to correspond to the updated tree100b.

An entry in the table corresponding to a tree may be generated for every node and all of its parent nodes until the root node. For example, in tree100c,container node Y115and leave nodes B and C may be added to the tree, and eight records may be added to table100c′ to correspond to the updated tree100c.Table300c′ may contain new entries340-375. Entry340may be the identity relationship entry for node Y, having depth value “0.” Entry345may correspond to the relationship between node W and node Y, the immediate parent node of node Y. The relationship entry345having depth value “1”, corresponding to the distance between nodes W and Y. Entry355may correspond to the relationship between node B and node X, the root node. The relationship between nodes B and X may be indicated as having depth value “2”, which corresponds the distance between nodes B and X.

Leaf nodes may not be generated with an entry in the table. For example, in tree100a,a node A may be added to the tree. Since new node A is a leaf node—or a node having no child in the tree—node A may not be generated with a corresponding entry in the table. Thus, it may be appreciated that a table generated to correspond to a tree structure may represent one or more non-leaf nodes in the table. In alternative example embodiments, leaf nodes may be generated with corresponding entries in the table, along with ancestor identifiers and depth values of the ancestor for its one or more parent nodes.

Example tree100aand corresponding table100a′ may be used to illustrate one or more example applications that may be performed using the example embodiments described herein.

FIG. 3Dillustrates a hierarchical table300for example tree100without leaf node entries after the processing of tree100has been completed. Hierarchical table300may include columns labeled NODE_ID135, ANCESTOR_ID140, and DEPTH145and row entries320-395. Row entries320-395in hierarchical table300show permutations of the relationships and corresponding depths (or distance values) between container nodes. For example, the depth or distance value of Node X from Node Z of tree300is 3, as reflected in row entry395.

FIG. 4is an example node table400corresponding to the tree100ofFIG. 1. Node table400may represent relationships between leaf nodes and container nodes as well as the immediate parent node of each unique node. Node table400may include columns with labels such as, but not limited to, NODE_ID405, NODE TYPE410, PARENT NODE415and NODE_NAME415. NODE_NAME420may be the identifier, such as a directory or file name associated with corresponding NODE_ID420. For example, node X may correspond to a directory named “C”, and node A may be a file named “DOC1”.

FIG. 5shows one shows one example method500for searching a relational database using the example hierarchical table ofFIG. 3D.

At block505, an example application receives a query to search for descendants of a given container node X. For example, the search may be for all directories having a root node X.

At block510, using ancestry table300, all row entries having container node X as ANCESTOR_ID140(an ancestor) are identified as matching the received search query. In this example embodiment, row entries320,330,360and395are identified as matching entries.

At block515, each matching row entry320,330,360and395is examined to determine whether its DEPTH145is greater than 0. If DEPTH145is greater than 0, then NODE_ID135corresponding to each such entry is identified. Continuing with this example embodiment, only row entries330,360and395with corresponding NODE_ID135values of W, Y and Z, respectively, are identified. NODE ID135values from row entries330,360and395are returned, identified and/or temporarily stored at block520.

Sample code for identifying and returning such entries is as follows:

The SELECT clause returns nodes from NODE_ID405. The JOIN clause joins together hierarchical table300and node table400on a matching table column to form a temporary table from which results of the query may be determined.

FIG. 6shows an example temporary table formed using an example query that uses the JOIN clause. For example, JOIN node ON ancestry. ancestor_id=node.node_id returns a temporary table wherein the entries from ANCESTOR_ID140in ancestry table300match entries in NODE_ID405in node table400. The WHERE clause further narrows down the results of the query by specifying that the entries in the temporary table created using the JOIN clause adhere to the condition that ANCESTOR_ID140of ancestry table300is equal to X and the value of DEPTH145is greater than 0. The example query returns descendant container nodes of node X (i.e., W, Y and Z), as shown in temporary table600. In some aspects, the example query may also return descendant leaf nodes. In some alternative example embodiments, matching data may be temporarily stored in an array or other format.

Referring back toFIG. 5, at block525, the matched nodes may then be used to determine the corresponding directory descendants. Such determination is based upon identifying PARENT NODEs415corresponding to the matched nodes. As shown inFIG. 5, NODE_ID135values W, Y, and Z correspond to directories having NODE_NAMEs420of “USER 1”, “USERS” and “DOC”.

In some example embodiments, where the search query is to identify files within a directory path of C as the root directory C, the matched nodes may be used to identify the corresponding file descendants by identifying PARENT_NODEs415corresponding to the matched node and examining NODE_TYPE410to determine if the matched nodes are “LEAF” nodes (block530). In addition, where a NODE_ID405entry corresponds to the original search query but not PARENT NODE entry, such node is a leaf node. In this example embodiment, method500would produce the results of identifying leaf nodes having files named DOC1, DOC2, DOC 3, DOC 4 and DOC 5.

In yet other example embodiments, where the search query is to identify all files and directories C as the root directory C, example method500would result in not only identifying leaf nodes having files named “DOC1”, “DOC2”, “DOC 3”, “DOC 4” and “DOC 5” but also subdirectories named “USER 1”, “USERS” and “DOC”.

FIG. 7shows one shows one example method500for searching a relational database using the example hierarchical table ofFIG. 3D.

At block705, an example application receives a query to search for ancestors of a given container node Y. For example, the search may be for all directories of a given directory Y.

At block710, using ancestry table300, all row entries having container node Y as NODE_ID140are identified as matching the received search query. In this example embodiment, row entries340,345and360are identified as matching entries.

At block715, each matching row entry340,345and360is examined to determine whether its DEPTH145is greater than 0. If DEPTH145is greater than 0, then ANCESTOR_ID140corresponding to each such entry is identified. Continuing with this example embodiment, only row entries345and360with corresponding ANCESTOR_ID140values of W and X, respectively, are identified. ANCESTOR_ID135values from row entries345and360may then be returned, identified and/or temporarily stored at block720.

In some example aspects, ANCESTOR ID135values identified at block720may then be used to correlate the search query results with file or document names. Using this example embodiment, the corresponding NODE_NAME420values of the matched entries are “USER 1” and “C”, which then transmitted by the application as the results of the search query.

Corresponding sample code for application performing the example method inFIG. 7is shown below.

In this example application, the query returns all container nodes whose descendant is the given container node Z, excluding itself.

The SELECT clause selects all values of ANCESTOR_ID110that satisfy the condition set in the WHERE clause. The WHERE clause specifies that the entries of NODE_ID105is equal to ‘Z’ and the depth is greater than 0, which indicates that the nodes to be returned from ANCESTOR_ID110has a descendant node Z. Specifying that results have depth values greater than 0 excludes the given container node Z. This query returns all the ancestors of node Z (i.e., Y and X) excluding itself.

In another example application, a query to retrieve the distance of a given container node Z from the root is given below:

The maximum value from the DEPTH115of ancestry table100a′ is returned using the query. The value is specified to be the maximum depth value of container node Z using the WHERE ancestry.node_id=‘z’ clause. The value returned using this example query is 2, which is the depth value between container node Z and root node X.

Another example application performs a query to retrieve the distance of a given leaf node A from the root.

The maximum value of DEPTH115in ancestry table100a′ retrieved and a value of “1” may be added to the result to account for the leaf node which is not represented in ancestry table100a′. The JOIN clause creates a temporary table based on node table300wherein the values of NODE_ID105is equal to the values of PARENT NODE415and wherein the value from NODE_TYPE120is equal to ‘leaf’ and yet another condition wherein the value from NODE_ID405is equal to ‘A’. This query then returns the distance of leaf node A to the root node which is 3.

FIG. 8shows a third example method for searching a relational database using the hierarchical table ofFIG. 3D. In this example embodiment, an example application performs a query to count all descendants of a given container node X.

At block805, the application receives a request to count all of the descendants of a container node X. At block810, the nodes matching the query are identified using ancestry table300. At block815, the matching nodes are used to count the corresponding container and leaf nodes, and the number of descendants for X is returned at block820. Corresponding sample code for performing this query is shown below:

The SELECT COUNT returns the number of entries from ancestry table100a′ wherein NODE_ID405entries are equal to PARENT NODE415entries or NODE_TYPE410records include ‘leaf’ entries, which indicate that all descendants of node X, including container and leaf nodes but excluding itself, are counted. The condition specified in the WHERE clause indicates that the given node whose number of descendants is queried is X, and depth is specified to be greater than 0 to only count descendant nodes. This query then returns the number of descendants of given node X which is 3.

In the example query applications discussed above, selecting one or more entries from the table are performed using single access queries without performing tree traversals and recursions.

It will be understood that the example applications described herein are illustrative and should not be considered limiting. It will be appreciated that the actions described and shown in the example flowcharts may be carried out or performed in any suitable order. It will also be appreciated that not all of the actions described inFIG. 1need to be performed in accordance with the embodiments of the disclosure and/or additional actions may be performed in accordance with other embodiments of the disclosure.