subset.cpp File Reference

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>

Include dependency graph for subset.cpp:

Go to the source code of this file.

Macros
#define	MIN(x, y)   ((x)<(y)?(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, int constant, ComparisonOperator op, std::unique_ptr< Aggregator > aggregator)
	Evaluate whether the aggregation of values masked by mask satisfies op constant.
std::vector< mask_t >	enumerate_exhaustive (const std::vector< long > &values, int 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, int constant, ComparisonOperator op, AggregationOperator agg_kind, bool absorptive, bool &upset)
	Enumerate all subsets of n tuples satisfying an aggregate predicate.

Detailed Description

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.

Macro Definition Documentation

MIN

#define MIN	(		x,
			y
	)		((x)<(y)?(x):(y))

Return the minimum of two values.

Definition at line 73 of file subset.cpp.

Function Documentation

compare()

template<typename I , typename J >

static bool compare ( I  a, ComparisonOperator  op, J  b  )

static

Apply a comparison operator to two values.

Template Parameters

I	Type of the left operand.
J	Type of the right operand.

Parameters

a	Left operand.
op	Comparison operator.
b	Right operand.

Returns

Result of the comparison.

Definition at line 258 of file subset.cpp.

Here is the caller graph for this function:

enumerate_exhaustive()

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

Enumerate all subsets satisfying a HAVING predicate by exhaustive search.

Parameters

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

Returns

Vector of satisfying subset masks.

Definition at line 310 of file subset.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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:

evaluate()

bool evaluate	(	const std::vector< long > &	values,
		const std::vector< bool > &	mask,
		int	constant,
		ComparisonOperator	op,
		std::unique_ptr< Aggregator >	aggregator
	)

Evaluate whether the aggregation of values masked by mask satisfies op constant.

Parameters

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.

Returns

true if the aggregate result satisfies the comparison.

Definition at line 279 of file subset.cpp.

Here is the call graph for this function:

Here is the caller graph for this function: