ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
subset.hpp
Go to the documentation of this file.
1/**
2 * @file subset.hpp
3 * @brief Enumerate tuple subsets satisfying an aggregate HAVING predicate.
4 *
5 * For aggregate provenance evaluation, ProvSQL needs to determine which
6 * subsets of base tuples produce a group-aggregate value that satisfies
7 * the HAVING condition. This header declares the @c enumerate_valid_worlds()
8 * function that enumerates all such subsets ("valid worlds") as bitmasks.
9 *
10 * A *world* is represented as a @c mask_t = @c std::vector<bool> of length
11 * @f$n@f$, where bit @f$i@f$ is @c true iff tuple @f$i@f$ is present in
12 * that world. The function returns all worlds where the aggregate of the
13 * present tuples' values satisfies the given comparison.
14 */
15#ifndef SUBSET_HPP
16#define SUBSET_HPP
17
18#include <cstdint>
19#include <string>
20#include <vector>
21
22#include "Aggregation.h"
23
24/**
25 * @brief A bitmask over @f$n@f$ tuples representing one possible world.
26 *
27 * @c mask_t[i] is @c true iff tuple @f$i@f$ is present in this world.
28 */
29using mask_t=std::vector<bool>;
30
31/**
32 * @brief Throw if @p count worlds of a group, held for enumeration, are
33 * more than @c provsql.max_worlds allows.
34 */
35void check_world_count(std::size_t count);
36
37/**
38 * @brief Enumerate all subsets of @p n tuples satisfying an aggregate predicate.
39 *
40 * For each subset @f$W \subseteq \{0, \ldots, n-1\}@f$ of the tuples,
41 * computes the aggregate of their @p values, tests the predicate
42 * @f$\text{agg}(W) \;\mathit{op}\; \text{constant}@f$, and includes @f$W@f$
43 * in the result if the predicate holds.
44 *
45 * @param values Aggregate contribution of each tuple (one value per tuple).
46 * @param constant The constant on the right-hand side of the comparison.
47 * @param op Comparison operator (=, ≠, <, ≤, >, ≥).
48 * @param agg_kind Aggregation function (SUM, COUNT, MIN, MAX…).
49 * @param enumerate If @c false, only determine whether the set of valid worlds
50 * is an upset; the returned vector may be empty.
51 * @param upset Output: set to @c true if the set of valid worlds forms an
52 * upset (upward-closed set), @c false otherwise.
53 * @param is_scalar Scalar (no GROUP BY) aggregation: the output row exists
54 * even in the empty world, so the empty subset is also
55 * tested against the predicate.
56 * @return Vector of bitmasks, one per valid world.
57 */
58std::vector<mask_t> enumerate_valid_worlds(
59 const std::vector<long> &values,
60 long constant,
62 AggregationOperator agg_kind,
63 bool enumerate,
64 bool &upset,
65 bool is_scalar = false
66 );
67
68/**
69 * @brief Canonical per-world decision: does @c agg(present) @c op @c constant
70 * hold in the world where exactly the @p present tuples are present?
71 *
72 * The single source of truth for "value of @c agg θ k in one world", shared by
73 * the all-worlds expansion (the exhaustive enumerator builds its world set from
74 * this predicate) and by any sampler that draws one world (so sample and expand
75 * agree by construction).
76 *
77 * Enforces the **empty-group exclusion**: a world with no present tuple makes
78 * the predicate @c false (SQL evaluates HAVING only on groups that exist, so an
79 * all-absent group never satisfies it -- even for e.g. @c sum(x) >= -5 or
80 * @c min(x) <= k). Otherwise it aggregates the present tuples' @p values with
81 * @p agg_kind and applies @p op against @p constant on the integer grid (the
82 * caller having scaled numeric / decimal-float domains; see @c matchAggCmp).
83 *
84 * @param values Per-tuple aggregate contribution (scaled to a common grid).
85 * @param present Which tuples are present in this world (same length).
86 * @param constant Right-hand side of the comparison, on the same grid.
87 * @param op Comparison operator.
88 * @param agg_kind Aggregation function.
89 * @return @c true iff a non-empty group's aggregate satisfies @p op.
90 */
92 const std::vector<long> &values,
93 const mask_t &present,
94 long constant,
96 AggregationOperator agg_kind
97 );
98
99/**
100 * @brief Enumerate the non-empty worlds whose ordered present elements equal
101 * (@p want_equal true) or differ from (@p want_equal false) @p target.
102 *
103 * The general @c array_agg() HAVING pipeline: no aggregate-specific shortcut,
104 * just an exhaustive scan that compares, in each world, the array of present
105 * tuples' element texts (kept in the aggregate's input order) against the
106 * constant array. Element values are compared as their text representations,
107 * so any element type is supported for @c = / @c <>.
108 *
109 * @param vals Per-tuple element text (in the aggregate's input order).
110 * @param target The constant array's element texts.
111 * @param want_equal @c true for @c =, @c false for @c <>.
112 * @return Vector of bitmasks, one per valid world.
113 */
114std::vector<mask_t> enumerate_array_agg_worlds(
115 const std::vector<std::string> &vals,
116 const std::vector<std::string> &target,
117 bool want_equal
118 );
119
120/**
121 * @brief Enumerate the worlds where the arrays of two @c array_agg()
122 * aggregates are equal (@p want_equal) or differ.
123 *
124 * A world is a subset of the contributing tuples of both aggregates, which
125 * may share tuples: @p lbits and @p rbits give, for each element of the left
126 * and the right array, the bit of the tuple it comes from, among @p nbits.
127 * A side with no present tuple is @c NULL, which no comparison satisfies, so
128 * those worlds are left out.
129 *
130 * @param lbits Bit of each element of the left array, in its order.
131 * @param lvals Element texts of the left array, in its order.
132 * @param rbits Bit of each element of the right array, in its order.
133 * @param rvals Element texts of the right array, in its order.
134 * @param nbits Number of tuples the worlds range over.
135 * @param want_equal @c true for @c =, @c false for @c <>.
136 * @return Vector of bitmasks, one per valid world.
137 */
138std::vector<mask_t> enumerate_array_agg_pair_worlds(
139 const std::vector<std::size_t> &lbits,
140 const std::vector<std::string> &lvals,
141 const std::vector<std::size_t> &rbits,
142 const std::vector<std::string> &rvals,
143 std::size_t nbits,
144 bool want_equal
145 );
146
147#endif /* SUBSET_HPP */
Typed aggregation value, operator, and aggregator abstractions.
AggregationOperator
SQL aggregation functions tracked by ProvSQL.
Definition Aggregation.h:52
ComparisonOperator
SQL comparison operators used in gate_cmp circuit gates.
Definition Aggregation.h:40
std::vector< mask_t > enumerate_array_agg_pair_worlds(const std::vector< std::size_t > &lbits, const std::vector< std::string > &lvals, const std::vector< std::size_t > &rbits, const std::vector< std::string > &rvals, std::size_t nbits, bool want_equal)
Enumerate the worlds where the arrays of two array_agg() aggregates are equal (want_equal) or differ.
Definition subset.cpp:494
void check_world_count(std::size_t count)
Throw if count worlds of a group, held for enumeration, are more than provsql.max_worlds allows.
Definition subset.cpp:40
std::vector< bool > mask_t
A bitmask over tuples representing one possible world.
Definition subset.hpp:29
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 prese...
Definition subset.cpp:388
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.
Definition subset.cpp:454
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 ...
Definition subset.cpp:526