 |
ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
|
|
ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
|
Valid-world enumeration for aggregate HAVING predicates. More...
#include "subset.hpp"#include <algorithm>#include <cstddef>#include <cstdint>#include <limits>#include <vector>#include <stdexcept>#include <cassert>
Go to the source code of this file.
Macros | |
| #define | MIN(x, y) |
| Return the minimum of two values. | |
Functions | |
| template<typename I, typename J> | |
| static bool | compare (I a, ComparisonOperator op, J b) |
| Apply a comparison operator to two values. | |
| bool | evaluate (const std::vector< long > &values, const std::vector< bool > &mask, long constant, ComparisonOperator op, std::unique_ptr< Aggregator > aggregator) |
Evaluate whether the aggregation of values masked by mask satisfies op constant. | |
| bool | agg_cmp_holds_in_world (const std::vector< long > &values, const mask_t &present, long constant, ComparisonOperator op, AggregationOperator agg_kind) |
Canonical per-world decision: does agg(present) op constant hold in the world where exactly the present tuples are present? | |
| std::vector< mask_t > | enumerate_exhaustive (const std::vector< long > &values, long constant, ComparisonOperator op, AggregationOperator agg_kind, bool absorptive, bool &upset) |
| Enumerate all subsets satisfying a HAVING predicate by exhaustive search. | |
| std::vector< mask_t > | enumerate_valid_worlds (const std::vector< long > &values, long constant, ComparisonOperator op, AggregationOperator agg_kind, bool absorptive, bool &upset, bool is_scalar) |
Enumerate all subsets of n tuples satisfying an aggregate predicate. | |
| std::vector< mask_t > | enumerate_array_agg_worlds (const std::vector< std::string > &vals, const std::vector< std::string > &target, bool want_equal) |
Enumerate the non-empty worlds whose ordered present elements equal (want_equal true) or differ from (want_equal false) target. | |
Valid-world enumeration for aggregate HAVING predicates.
Implements enumerate_valid_worlds() declared in subset.hpp.
For a list of \(n\) tuples with individual values, the function iterates over all \(2^n\) possible worlds (bitmasks), computes the aggregate of the present tuples' values using the requested AggregationOperator, and tests the comparison predicate. All valid worlds are collected and returned.
The upset output flag is set to true when the set of valid worlds is upward-closed (every superset of a valid world is also valid), which is the case for monotone aggregation predicates (e.g. SUM ≥ k). This information is used to optimise the evaluation of monotone HAVING clauses.
Internal helpers in an anonymous namespace:
increment(): advance a bitmask to the next possible world.compute_agg(): compute the aggregate value for one bitmask. Definition in file subset.cpp.
| #define MIN | ( | x, | |
| y ) |
| bool agg_cmp_holds_in_world | ( | const std::vector< long > & | values, |
| const mask_t & | present, | ||
| long | constant, | ||
| ComparisonOperator | op, | ||
| AggregationOperator | agg_kind ) |
Canonical per-world decision: does agg(present) op constant hold in the world where exactly the present tuples are present?
The single source of truth for "value of @c agg θ k in one world", shared by the all-worlds expansion (the exhaustive enumerator builds its world set from this predicate) and by any sampler that draws one world (so sample and expand agree by construction).
Enforces the empty-group exclusion: a world with no present tuple makes the predicate false (SQL evaluates HAVING only on groups that exist, so an all-absent group never satisfies it – even for e.g. sum(x) >= -5 or min(x) <= k). Otherwise it aggregates the present tuples' values with agg_kind and applies op against constant on the integer grid (the caller having scaled numeric / decimal-float domains; see matchAggCmp).
| values | Per-tuple aggregate contribution (scaled to a common grid). |
| present | Which tuples are present in this world (same length). |
| constant | Right-hand side of the comparison, on the same grid. |
| op | Comparison operator. |
| agg_kind | Aggregation function. |
true iff a non-empty group's aggregate satisfies op. Definition at line 360 of file subset.cpp.
|
static |
Apply a comparison operator to two values.
| I | Type of the left operand. |
| J | Type of the right operand. |
| a | Left operand. |
| op | Comparison operator. |
| b | Right operand. |
Definition at line 318 of file subset.cpp.
| std::vector< mask_t > enumerate_array_agg_worlds | ( | const std::vector< std::string > & | vals, |
| const std::vector< std::string > & | target, | ||
| bool | want_equal ) |
Enumerate the non-empty worlds whose ordered present elements equal (want_equal true) or differ from (want_equal false) target.
The general array_agg() HAVING pipeline: no aggregate-specific shortcut, just an exhaustive scan that compares, in each world, the array of present tuples' element texts (kept in the aggregate's input order) against the constant array. Element values are compared as their text representations, so any element type is supported for = / <>.
| vals | Per-tuple element text (in the aggregate's input order). |
| target | The constant array's element texts. |
| want_equal | true for =, false for <>. |
Definition at line 465 of file subset.cpp.
| std::vector< mask_t > enumerate_exhaustive | ( | const std::vector< long > & | values, |
| long | constant, | ||
| ComparisonOperator | op, | ||
| AggregationOperator | agg_kind, | ||
| bool | absorptive, | ||
| bool & | upset ) |
Enumerate all subsets satisfying a HAVING predicate by exhaustive search.
| values | Input values. |
| constant | Constant for the comparison. |
| op | Comparison operator. |
| agg_kind | Aggregation function to apply. |
| absorptive | Whether the semiring is absorptive. |
| upset | Set to true if the result set forms an upset (monotone). |
Definition at line 390 of file subset.cpp.
| std::vector< mask_t > enumerate_valid_worlds | ( | const std::vector< long > & | values, |
| long | constant, | ||
| ComparisonOperator | op, | ||
| AggregationOperator | agg_kind, | ||
| bool | enumerate, | ||
| bool & | upset, | ||
| bool | is_scalar = false ) |
Enumerate all subsets of n tuples satisfying an aggregate predicate.
For each subset \(W \subseteq \{0, \ldots, n-1\}\) of the tuples, computes the aggregate of their values, tests the predicate \(\text{agg}(W) \;\mathit{op}\; \text{constant}\), and includes \(W\) in the result if the predicate holds.
| values | Aggregate contribution of each tuple (one value per tuple). |
| constant | The constant on the right-hand side of the comparison. |
| op | Comparison operator (=, ≠, <, ≤, >, ≥). |
| agg_kind | Aggregation function (SUM, COUNT, MIN, MAX…). |
| enumerate | If false, only determine whether the set of valid worlds is an upset; the returned vector may be empty. |
| upset | Output: set to true if the set of valid worlds forms an upset (upward-closed set), false otherwise. |
| is_scalar | Scalar (no GROUP BY) aggregation: the output row exists even in the empty world, so the empty subset is also tested against the predicate. |
Definition at line 425 of file subset.cpp.
| bool evaluate | ( | const std::vector< long > & | values, |
| const std::vector< bool > & | mask, | ||
| long | constant, | ||
| ComparisonOperator | op, | ||
| std::unique_ptr< Aggregator > | aggregator ) |
Evaluate whether the aggregation of values masked by mask satisfies op constant.
| values | Input values to aggregate. |
| mask | Boolean mask selecting which values to include. |
| constant | Right-hand side constant of the comparison. |
| op | Comparison operator. |
| aggregator | Aggregator to apply to the selected values. |
true if the aggregate result satisfies the comparison. Definition at line 339 of file subset.cpp.
