A database is a collection of stored data that is logically related and that is accessible by one or more users. A popular type of database is the relational database management system (RDBMS), which includes relational tables made up of rows and columns. Each row represents an occurrence of an entity defined by a table, with an entity being a person, place, or thing about which the table contains information. To extract data from, or to update, a relational table, queries according to a standard database-query language (e.g., Structure Query Language or SQL) are used.
A table (also referred to as a relation) is made up of multiple rows (also referred to as tuples). Each row (or tuple) includes multiple columns (or attributes). Various types of aggregations can be performed on an attribute. For example, one aggregation function is a SUM function, which sums all values of a specified attribute. Another aggregation function is an AVG function, which calculates the average of values of an attribute. Other aggregation functions include MIN (to find the smallest value of an attribute), MAX (to find the largest value of an attribute), and so forth.
A special type of aggregation is referred to as a moving aggregate, such as a moving sum, a moving average, and so forth, on some attribute A of tuples of a relation R within a specified moving window. The specified moving window can be an arbitrarily large moving window. Generally, a moving aggregate is an aggregate of an attribute in tuples located within the specified moving window. For example, assume the specified moving window has a size of 15. Given a tuple Ti, the moving aggregate is an aggregate of attribute A of all tuples within the specified moving window of 15, namely tuples Ti−Ti+14.
An issue arises when a moving aggregate is implemented in a parallel RDBMS having multiple data server nodes. A relation R is typically distributed across the multiple nodes. If the specified moving window is large enough, then the moving aggregate may involve tuples from many (e.g., more than two) nodes. One technique is to copy the tuples from the many nodes to one of the nodes so that the moving aggregate can be calculated. If the window is large, then the number of tuples that need to be transferred among the nodes can be quite large, which leads to inefficient database system usage.
USPTO Backgrounds
USPTO Backgrounds