# US 11,907,203 B2 · Path encoded tree structures for operations > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,907,203 B2 - Document ID: US11907203B2 - Status: Granted - Kind: B2 - Application number: 17/854,651 - Filed: 2022-06-30 - Published: 2022-10-20 - Granted: 2024-02-20 - Earliest claimed: 2019-12-20 - Assignees: Oracle International Corporation - Applicants: Oracle International Corporation - Inventors: Evgueni Perkov - Web page: https://patentgrep.com/patent/US11907203B2 ## CPC - G06F 16/2365: {Ensuring data consistency and integrity} - G06F 16/2246: {Trees, e.g. B+trees} - G06F 16/24558: {Binary matching operations} - G06F 16/288: {Entity relationship models} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Example embodiments facilitate creation of efficient tree structures (and strategic modification of and manipulation of existing tree structures), such that the resulting tree structures enable rapid computing operations, including, but not limited to, rapid relational set operations (e.g., joining trees, comparing tree structures, determining structural similarities of trees, adding tree nodes, removing or replacing tree nodes, accessing tree data, updating tree data, and so on). An example method relates to a method and/or system for creating and manipulating tree data structures (also simply called trees herein) as, for example, in relational databases. One embodiment uses compact bit-wise path encoding that stores structural data related to tree branches to which a current node belongs. The embodiment facilitates manipulating a representation of a tree and includes traversing at least a portion of the tree from a starting node, and then for each traversed node, modifying node metadata depending on whether or not the traversed node is a sibling node or a child node. ## Claims ### Claim 1 A non-transitory tangible processor-readable medium including instructions executable by one or more processors, and when executed operable for: providing a tree of nodes stored in a relational database; storing a binary path representation value as metadata for each node of a branch of the tree having a path across from older sibling nodes to younger sibling nodes at a given level and to child nodes at next levels, wherein of the sibling nodes in the given level, only an oldest child is directly connected to a parent node, wherein the binary path representation value for a current node that is a younger sibling node in the path is the binary path representation value of a directly connected older sibling node in the path that is appended with an additional binary path representation value for the current node, wherein the branch includes a terminator node that has no younger sibling and no younger child node, and the binary path representation value of the terminator node incorporates the binary path representation value of each node in the branch from the path including at least a root node through an oldest child at a second level to each sibling child node at the second level and through each grandchildren node at a third level of the tree, wherein at least the second level or the third level includes more than one sibling node in the path; detecting a request to perform an operation on at least a portion of the tree including the branch; and performing the operation by accessing the metadata of the binary path representation value of the terminator node of the branch. ### Claim 2 (depends on 1) The non-transitory tangible processor-readable medium of claim 1, wherein the binary path representation value uses a binary string of only “0” and “1” symbols encoded as an integer number. ### Claim 3 (depends on 2) The non-transitory tangible processor-readable medium of claim 2, wherein the binary path representation value of the oldest child of the set of sibling nodes includes an appended first symbol and the binary path representation value of each sibling of the oldest child includes an appended second symbol, wherein the first symbol is different than the second symbol. ### Claim 4 (depends on 1) The non-transitory tangible processor-readable medium of claim 1, wherein the operation includes a relational set operation of one or more of union, intersection, or difference. ### Claim 5 (depends on 4) The non-transitory tangible processor-readable medium of claim 4, wherein the operation includes searching for patterns in sub-trees of the tree. ### Claim 6 (depends on 1) The non-transitory tangible processor-readable medium of claim 1, wherein operation includes one or more of select, insert, delete, and update. ### Claim 7 (depends on 1) The non-transitory tangible processor-readable medium of claim 1, wherein the operation is to locate a sub-tree inside the tree. ### Claim 8 (depends on 1) The non-transitory tangible processor-readable medium of claim 1, wherein the request for the operation is by a client-side application and the metadata is stored in a server-side database. ### Claim 9 A method for using at least a portion of a tree for an operation, the method comprising: providing a tree of nodes stored in a relational database; storing a binary path representation value as metadata for each node of a branch of the tree having a path across from older sibling nodes to younger sibling nodes at a given level and to child nodes at a next level, wherein of the sibling nodes in the given level, only an oldest child is directly connected to a parent node, wherein the binary path representation value for a current node that is a younger sibling node in the path is the binary path representation value of a directly connected older sibling node in the path that is appended with an additional binary path representation value for the current node, wherein the branch includes a terminator node that has no younger sibling and no younger child node, and the binary path representation value of the terminator node incorporates the binary path representation value of each node in the branch from the path including at least a root node through an oldest child at a second level to each sibling child node at the second level and through each grandchildren node at a third level of the tree, wherein at least the second level or the third level includes more than one sibling node in the path; detecting a request to perform an operation on at least a portion of the tree including the branch; and performing the operation by accessing the metadata of the binary path representation value of the terminator node of the branch. ### Claim 10 (depends on 9) The method of claim 9, wherein the binary path representation value uses a binary string of only “0” and “1” symbols encoded as an integer number. ### Claim 11 (depends on 10) The method of claim 10, wherein the binary path representation value of the oldest child of the set of sibling nodes includes an appended first symbol and the binary path representation value of each sibling of the oldest child includes an appended second symbol, wherein the first symbol is different than the second symbol. ### Claim 12 (depends on 9) The method of claim 9, wherein the operation includes a relational set operation of one or more of union, intersection, or difference. ### Claim 13 (depends on 9) The method of claim 9, wherein operation includes one or more of select, insert, delete, and update. ### Claim 14 (depends on 9) The method of claim 9, wherein the request for the operation is by a client-side application and the metadata is stored in a server-side database. ### Claim 15 An apparatus comprising: one or more processors; and logic encoded in one or more tangible media for execution by the one or more processors and when executed operable for: providing a tree of nodes stored in a relational database; storing a binary path representation value as metadata for each node of a branch of the tree having a path across from older sibling nodes to younger sibling nodes at a given level and to child nodes at a next level, wherein of the sibling nodes in the given level, only an oldest child is directly connected to a parent node, wherein the binary path representation value for a current node that is a younger sibling node in the path is the binary path representation value of a directly connected older sibling node in the path that is appended with an additional binary path representation value for the current node, wherein the branch includes a terminator node that has no younger sibling and no younger child node, and the binary path representation value of the terminator node incorporates the binary path representation value of each node in the branch from the path including at least a root node through an oldest child at a second level to each sibling child node at the second level and through each grandchildren node at a third level of the tree, wherein at least the second level or the third level includes more than one sibling node in the path detecting a request to perform an operation on at least a portion of the tree including the branch; and performing the operation by accessing the metadata of the binary path representation value of the terminator node of the branch. ### Claim 16 (depends on 15) The apparatus of claim 15, wherein the binary path representation value uses a binary string of only “0” and “1” symbols encoded as an integer number. ### Claim 17 (depends on 15) The apparatus of claim 15, wherein the binary path representation value of the oldest child of the set of sibling nodes includes an appended first symbol and the binary path representation value of each sibling of the oldest child includes an appended second symbol, wherein the first symbol is different than the second symbol. ### Claim 18 (depends on 15) The apparatus of claim 15, wherein the operation includes a relational set operation of one or more of union, intersection, or difference. ### Claim 19 (depends on 15) The apparatus of claim 15, wherein operation includes one or more of select, insert, delete, and update. ### Claim 20 (depends on 15) The apparatus of claim 15, wherein the request for the operation is by a client-side application and the metadata is stored in a server-side database.