subset.hpp File Reference

Enumerate tuple subsets satisfying an aggregate HAVING predicate. More...

#include <cstdint>
#include <string>
#include <vector>
#include "Aggregation.h"

Include dependency graph for subset.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
using	mask_t = std::vector<bool>
	A bitmask over \(n\) tuples representing one possible world.

Functions
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.
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_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.

Detailed Description

Enumerate tuple subsets satisfying an aggregate HAVING predicate.

For aggregate provenance evaluation, ProvSQL needs to determine which subsets of base tuples produce a group-aggregate value that satisfies the HAVING condition. This header declares the enumerate_valid_worlds() function that enumerates all such subsets ("valid worlds") as bitmasks.

A world is represented as a mask_t = std::vector<bool> of length \(n\), where bit \(i\) is true iff tuple \(i\) is present in that world. The function returns all worlds where the aggregate of the present tuples' values satisfies the given comparison.

Definition in file subset.hpp.

Typedef Documentation

mask_t

using mask_t = std::vector<bool>

A bitmask over \(n\) tuples representing one possible world.

mask_t[i] is true iff tuple \(i\) is present in this world.

Definition at line 29 of file subset.hpp.

Function Documentation

agg_cmp_holds_in_world()

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).

Parameters

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.

Returns

true iff a non-empty group's aggregate satisfies op.

Definition at line 360 of file subset.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

enumerate_array_agg_worlds()

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 = / <>.

Parameters

vals	Per-tuple element text (in the aggregate's input order).
target	The constant array's element texts.
want_equal	true for =, false for <>.

Returns

Vector of bitmasks, one per valid world.

Definition at line 465 of file subset.cpp.

enumerate_valid_worlds()

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.

Parameters

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.

Returns

Vector of bitmasks, one per valid world.

Definition at line 425 of file subset.cpp.

Here is the call graph for this function: