Database processor
View Patent ↗A database processor is provided for on-line analytical processing. The processor is arranged to obtain multi-dimensional aggregates of an input relation. Prior to aggregation, the processor performs a pre-processing stage in which the processor identifies Group-bys that are equivalent to the root relation and thus can be derived directly from the root relation without computation. In this manner, the computational time and storage of the multidimensional aggregates is reduced since only unique Group-bys in the lattice are computed and stored.
1. A database processor and system architecture capable of operating as an On-line Analytical Processing (OLAP) system for the implementation of multidimensional aggregates of an input relation, and which is arranged to obtain such multidimensional aggregates after a preprocessing stage which identifies aggregates which can be obtained without computation, said pro-processing stage being arranged to:
i) prior to obtaining multidimensional aggregates, in the preprocessing stage, identify and store the primary keys derived from the schema of the input relation;
ii) establish a Group-by schema generator to generate schemas from minimum arity to maximum arity of aggregate for the possible aggregates of the input relation;
iii) sequentially in an arity order beginning with single columns and proceeding in an order in which each lower level of every sub-tree is visited before any root comparing the generated schemas with the primary keys stored in step (i) augmented by any previous schema identified as being a key and in the event of a generated schema containing a stored key treating the input relation as the virtual representation of the corresponding Group-by aggregate, such that the Group-by aggregate is identified as capable of being obtained without computation.
2. A database processor as claimed in claim 1 , wherein the arity order is the sequence minimum arity to maximum arity.
3. A database processor as claimed in claim 1 , where in sequence, each schema which is not found to contain a stored key according to step (iii) is subjected to a secondary check step, wherein an upper bound size of the Group-by relation defined by the current such schema is evaluated and the size of the input relation is compared against that upper bound size and in the event of the upper bound size not being less than the size of the input relation sequentially comparing the tuples of the current schema, and in the absence of tuple-duplication recognizing that the current schema is a key and treating the input relation as the virtual representation of the corresponding Group-by aggregate without computation.
4. A database processor as claimed in claim 3 , wherein the upper bound size of the Group-by relation defined by the current schema is evaluated according to a predetermined algorithm.
5. A database processor as claimed in claim 1 , wherein those generated Group-by schemas which are recognized as being or as containing a key are effectively stored to permit subsequent retrieval of the corresponding Group-by aggregate without computation.
6. A database processor as claimed in claim 5 , wherein the store contains pointers to those generated Group-by schemas which are recognized as being or as containing a key, such pointers in effect representing the schema.
7. A database processor as claimed in claim 1 , wherein those Group-by schemas which require computational aggregation are computationally aggregated and each aggregate is assessed to identify whether or not it is similar to the parent relation by having almost the same cardinality as the input relation, in which case to reduce storage space only, those tuples that differ from the input relation need to be represented, whereby the aggregate can be obtained from this representation of the difference and from the input relation.
8. An on-line analytical processing system comprising a database processor and system architecture as claimed in claim 1 .
9. A database processor and system architecture capable of operating as an On-line Analytical Processing (CLAP) system for the implementation of multidimensional aggregates of an input relation, and which is arranged to obtain such multidimensional aggregates after a preprocessing stage which identifies aggregates which can be obtained without computation, said pre-proces sing stage being arranged to:
i) prior to obtaining multidimensional aggregates, in the preprocessing stage, identify and store the primary keys derived from the schema of the input relation; and
ii) establish a Group-by schema generator to generate schemes from minimum arity to maximum arity of aggregate for the possible aggregates of the input relation,
wherein those Group-by schemas which require computational aggregation are computationally aggregated and each aggregate is assessed to identify whether or not it is similar to the parent relation by having almost the same cardinality as the input relation, in which case to reduce storage space only those tuples that differ from the input relation need to be represented, wherein aggregates that can be obtained from this representation of the difference and from the input relation are identified as aggregates that are capable of being obtained without computation.