subset.hpp File Reference

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

#include <cstdint>
#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, int constant, ComparisonOperator op, AggregationOperator agg_kind, bool enumerate, bool &upset)
	Enumerate all subsets of n tuples satisfying an aggregate predicate.

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 28 of file subset.hpp.

Function Documentation

enumerate_valid_worlds()

std::vector< mask_t > enumerate_valid_worlds	(	const std::vector< long > &	values,
		int	constant,
		ComparisonOperator	op,
		AggregationOperator	agg_kind,
		bool	enumerate,
		bool &	upset
	)

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.

Returns

Vector of bitmasks, one per valid world.

Definition at line 347 of file subset.cpp.

Here is the call graph for this function:

Here is the caller graph for this function: