# US 2019/0317939 A1 · Hierarchical window function

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0317939 A1
- Document ID: US20190317939A1
- Status: Published application
- Kind: A1
- Application number: 16/274,903
- Filed: 2019-02-13
- Published: 2019-10-17
- Earliest claimed: 2018-04-11
- Assignees: Sap SE
- Applicants: Sap SE
- Inventors: Manuel Caroli; Aleksei Burlakov
- Web page: https://patentgrep.com/patent/US20190317939A1

## CPC

- G06F 16/24554: {Unary operations; Data partitioning operations}
- G06F 16/284: {Relational databases}
- G06F 16/185: Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof (details of archiving G06F16/11)
- G06F 16/2264: {Multidimensional index structures}
- G06F 16/2272: {Management thereof}
- G06F 16/24578: {using ranking}
- G06F 16/282: {Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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

### Claim 9 (depends on 1)

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.

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 1)

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.

### Claim 12 (depends on 11)

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.

### Claim 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.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 13)

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.

### Claim 16 (depends on 13)

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.

### Claim 17 (depends on 13)

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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 13)

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.

### Claim 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.
