Back to results
US 11,379,451 B2Granted
Hierarchical data grouping in main-memory relational databases
AssigneeSap SE
InventorsRobert Brunel, Norman May
Life of this patent
Estimating the term…
Abstract
Addressed herein is the problem of expressing and evaluating computations on hierarchies represented as database tables. Engine support for such computations is very limited today, and so they are usually outsourced into stored procedures or client code. Structural grouping is applied to relational algebra to provide concise syntax to express a class of useful computations. Algorithms are also provided to evaluate such structural groupings efficiently by exploiting available indexing schemes. Related apparatus, systems, techniques and articles are also described.
Claims18
A method for implementation by one or more data processors forming part of at least one computing device, the method comprising:
- receiving, by a database, a query which comprises at least one request specifying a table whose rows can be related to a hierarchy of nodes, the query specifying an aggregation operation for hierarchically aggregating data in the specified table according to the hierarchy of nodes, the table encoding a forest of ordered, rooted, labeled trees such that one tuple represents one hierarchy node and labels of a node are fields for an associated row in the table;
- determining a hierarchical window for the query;
- evaluating, based on the hierarchical window, recursive expressions on the hierarchical window using unary structural grouping having structural recursion in which each node acts as an input node and an output node;
- accessing the specified table that represents the data to be aggregated hierarchically;
- checking, for a tuple, whether a hierarchy node associated to such tuple matches a node for a previous processed tuple, such previous processed tuple having a previously calculated aggregation value;
- reusing, for a tuple, a previously calculated aggregation value if the node of such tuple matches the node for such previous processed tuple;
- and
- generating, for each tuple, an aggregation value when the aggregation value for such tuple cannot be reused from any previously processed tuple.
5 more elements
A system comprising:
- at least one data processor;
- and
- memory storing instructions which, when executed by the at least one data processor, result in operations comprising:
- receiving, by a database, a query that can be related to a table encapsulating a hierarchy of nodes, the query specifying an aggregation operation for hierarchically aggregating data in the specified table according to the hierarchy of nodes, the table encoding a forest of ordered, rooted, labeled trees such that one tuple represents one hierarchy node and labels of a node are fields for an associated row in the table;
- determining a hierarchical window for the query;
- evaluating, based on the hierarchical window, recursive expressions on the hierarchical window using unary structural grouping having structural recursion in which each node acts as an input node and an output node;
- accessing the specified table that represents the data to be aggregated hierarchically;
- checking, for a tuple, whether a hierarchy node associated to such tuple matches a node for a previous processed tuple, such previous processed tuple having a previously calculated aggregation value;
- reusing, for a tuple, a previously calculated aggregation value if the node of such tuple matches the node for such previous processed tuple;
- and
- generating, for each tuple, an aggregation value when the aggregation value for such tuple cannot be reused from any previously processed tuple.
8 more elements
A method for implementation by one or more data processors forming part of at least one computing device, the method comprising:
- receiving, by a database, a query that can be related to data in a form according to a hierarchy of nodes encapsulated in a table, the query specifying an aggregation operation for hierarchically aggregating the data in the according to the hierarchy of nodes, the table encoding a forest of ordered, rooted, labeled trees such that one tuple represents one hierarchy node and labels of a node are fields for an associated row in the table;
- determining a hierarchical window for the query;
- evaluating, based on the hierarchical window, recursive expressions on the hierarchical window using unary structural grouping having structural recursion in which each node acts as an input node and an output node;
- accessing tuples of data to be aggregated hierarchically which each can be associated to at most one node of the hierarchy of nodes;
- checking, for a tuple, whether a hierarchy node associated to such tuple matches a node for a previous processed tuple, such previous processed tuple having a previously calculated aggregation value;
- reusing, for a tuple, a previously calculated aggregation value if the node of such tuple matches the node for such previous processed tuple;
- and
- generating, for each tuple, an aggregation value when the aggregation value for such tuple cannot be reused from any previously processed tuple.
5 more elements
Dependencies are inferred from the claim text.