HIERARCHICAL WINDOW FUNCTION

• US 20190317939A1
• Filed: 02/13/2019
• Published: 10/17/2019
• Est. Priority Date: 04/11/2018
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Caroli, Manuel, Burlakov, Aleksei
• Granted Patent: US 11,544,267 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/185 Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

A method may include generating, based on a representation of a hierarchy stored in a database, a visiting sequence data structure. The hierarchy may be stored in a table in the database. Each of a plurality of rows comprising the table may correspond to one of a plurality of nodes comprising the hierarchy. The visiting sequence data structure may include a row vector specifying an order for traversing the plurality of nodes in the hierarchy. A hierarchical window function may be executed by iterating through the plurality of rows in the table in accordance with the order specified by the row vector. The execution of the hierarchical window function may further include determining, for a first node in the hierarchy, a summary value corresponding to a first value of the first node and a second value of a second node descendent from the first node.

Claims

1. A system, comprising:

at least one data processor; and

at least one memory storing instructions which, when executed by the at least one data processor, result in operations comprising;

generating, based at least on a representation of a first hierarchy stored in a database, a visiting sequence data structure, the first hierarchy being stored in a table in the database, each of a plurality of rows comprising the table corresponding to one of a plurality of nodes comprising the first hierarchy, and the visiting sequence data structure include a first row vector specifying an order for traversing the plurality of nodes in the first hierarchy; and

executing a hierarchical window function by at least iterating through the plurality of rows comprising the table in accordance with the order specified by the first row vector and determining, for a first node in the first hierarchy, a summary value corresponding to a first value of the first node and a second value of a second node descendent from the first node.

2. The system of claim 1, wherein the summary value comprises an average, a count, a maximum, a medium, a minimum, a mode, a range, and/or a sum of the first value of the first node and the second value of the second node.

3. The system of claim 1, wherein the execution of the hierarchical window function further comprises determining, for a third node comprising a parent node of the first node and/or the second node, another summary value corresponding to a third value of the third node and at least one of the first value of the first node and the second value of the second node.

4. The system of claim 1, wherein the visiting sequence data structure further includes a second row vector enumerating one or more rows in the table corresponding to parent nodes in the first hierarchy or children nodes in the first hierarchy.

5. The system of claim 1, wherein the hierarchical window function is associated with a frame comprising one or more levels of the first hierarchy, wherein the summary value is determined based on the first value of the first node and the second value of the second node based at least on the first node and the first node occupying the one or more levels of the frame, and wherein the summary value is determined without a third value of a third node occupying a level outside of the frame.

6. The system of claim 5, wherein the visiting sequence data structure further includes a second row vector enumerating ancestor nodes of the first node occupying the one or more levels of the frame.

7. The system of claim 1, wherein the executing the hierarchical window function further includes iterating from the first node of the first hierarchy to the second node in the first hierarchy, wherein the second node comprises a child node of the first node when the hierarchical window function is executed in a top down order, and wherein the second node comprises a parent node of the first node when the hierarchical window function is executed in a bottom up order.

8. The system of claim 1, wherein the first hierarchy comprises a rooted product or a join between a second hierarchy and a third hierarchy.

9. The system of claim 1, wherein the first hierarchy comprises a partition from a second hierarchy that is divided into the first hierarchy and a third hierarchy, wherein the executing of the hierarchical window function further includes generating another visiting sequence data structure including a second row vector specifying an order for traversing a plurality nodes comprising the third hierarchy and iterating through the plurality of nodes comprising the third hierarchy in the order specified by the second row vector.

10. The system of claim 1, wherein executing the hierarchical window function further comprises generating a second hierarchy that is a partition from the first hierarchy or a result of a rooted join between the first hierarchy and a third hierarchy.

11. The system of claim 1, wherein the representation of the first hierarchy is generated by at least applying an indexing scheme to the first hierarchy, and wherein the applying of the indexing scheme includes assigning, to each of the plurality of nodes comprising the first hierarchy, one or more labels to enable an identification of parent nodes, children nodes, and sibling nodes in the first hierarchy.

12. The system of claim 11, wherein the indexing scheme comprises a Pre, Post, Parent, and Level (PPPL) indexing scheme and/or a Pre, Size, and Level (PSL) indexing scheme.

13. A computer-implemented method, comprising:

generating, based at least on a representation of a first hierarchy stored in a database, a visiting sequence data structure, the first hierarchy being stored in a table in the database, each of a plurality of rows comprising the table corresponding to one of a plurality of nodes comprising the first hierarchy, and the visiting sequence data structure include a first row vector specifying an order for traversing the plurality of nodes in the first hierarchy; and

executing a hierarchical window function by at least iterating through the plurality of rows comprising the table in accordance with the order specified by the first row vector and determining, for a first node in the first hierarchy, a summary value corresponding to a first value of the first node and a second value of a second node descendent from the first node.

14. The method of claim 13, wherein the summary value comprises an average, a count, a maximum, a medium, a minimum, a mode, a range, and/or a sum of the first value of the first node and the second value of the second node.

15. The method of claim 13, wherein the execution of the hierarchical window function further comprises determining, for a third node comprising a parent node of the first node and/or the second node, another summary value corresponding to a third value of the third node and at least one of the first value of the first node and the second value of the second node.

16. The method of claim 13, wherein the visiting sequence data structure further includes a second row vector enumerating one or more rows in the table corresponding to parent nodes in the first hierarchy or children nodes in the first hierarchy.

17. The method of claim 13, wherein the hierarchical window function is associated with a frame comprising one or more levels of the first hierarchy, wherein the summary value is determined based on the first value of the first node and the second value of the second node based at least on the first node and the first node occupying the one or more levels of the frame, and wherein the summary value is determined without a third value of a third node occupying a level outside of the frame.

18. The method of claim 17, wherein the visiting sequence data structure further includes a second row vector enumerating ancestor nodes of the first node occupying the one or more levels of the frame.

19. The method of claim 13, wherein the executing the hierarchical window function further includes iterating from the first node of the first hierarchy to the second node in the first hierarchy, wherein the second node comprises a child node of the first node when the hierarchical window function is executed in a top down order, and wherein the second node comprises a parent node of the first node when the hierarchical window function is executed in a bottom up order.

20. A non-transitory computer readable medium storing instructions, which when executed by at least one data processor, result in operations comprising:

generating, based at least on a representation of a first hierarchy stored in a database, a visiting sequence data structure, the first hierarchy being stored in a table in the database, each of a plurality of rows comprising the table corresponding to one of a plurality of nodes comprising the first hierarchy, and the visiting sequence data structure include a first row vector specifying an order for traversing the plurality of nodes in the first hierarchy; and

executing a hierarchical window function by at least iterating through the plurality of rows comprising the table in accordance with the order specified by the first row vector and determining, for a first node in the first hierarchy, a summary value corresponding to a first value of the first node and a second value of a second node descendent from the first node.