souffle::ast::transform::MaterializeAggregationQueriesTransformer Class Reference

Transformation pass to create artificial relations for bodies of aggregation functions consisting of more than a single atom. More...

#include <MaterializeAggregationQueries.h>

Inheritance diagram for souffle::ast::transform::MaterializeAggregationQueriesTransformer:

Collaboration diagram for souffle::ast::transform::MaterializeAggregationQueriesTransformer:

Public Member Functions
MaterializeAggregationQueriesTransformer *	clone () const override
std::string	getName () const override
Public Member Functions inherited from souffle::ast::transform::Transformer
bool	apply (TranslationUnit &translationUnit)
virtual	~Transformer ()=default

Static Public Member Functions
static bool	materializeAggregationQueries (TranslationUnit &translationUnit)
	Creates artificial relations for bodies of aggregation functions consisting of more than a single atom, in the given program. More...

Private Member Functions
bool	transform (TranslationUnit &translationUnit) override

Static Private Member Functions
static std::set< std::string >	distinguishHeadArguments (const TranslationUnit &tu, const Clause &clause, const Aggregator &aggregate)
	When we materialise an aggregate subclause, it's a good question which variables belong in the head of that materialised clause and which don't. More...
static void	groundInjectedParameters (const TranslationUnit &translationUnit, Clause &aggClause, const Clause &originalClause, const Aggregator &aggregate)
	Modify the aggClause by adding in grounding literals for every variable that appears in the clause ungrounded. More...
static void	instantiateUnnamedVariables (Clause &aggClause)
	Whatever variables have been left unnamed have significance for a count aggregate. More...
static bool	needsMaterializedRelation (const Aggregator &agg)
	A test determining whether the body of a given aggregation needs to be 'outlined' into an independent relation or can be kept inline. More...

Detailed Description

Transformation pass to create artificial relations for bodies of aggregation functions consisting of more than a single atom.

Definition at line 37 of file MaterializeAggregationQueries.h.

Member Function Documentation

clone()

MaterializeAggregationQueriesTransformer* souffle::ast::transform::MaterializeAggregationQueriesTransformer::clone ( ) const

inlineoverridevirtual

Implements souffle::ast::transform::Transformer.

Definition at line 59 of file MaterializeAggregationQueries.h.

distinguishHeadArguments()

std::set< std::string > souffle::ast::transform::MaterializeAggregationQueriesTransformer::distinguishHeadArguments ( const TranslationUnit &  tu, const Clause &  clause, const Aggregator &  aggregate  )

staticprivate

When we materialise an aggregate subclause, it's a good question which variables belong in the head of that materialised clause and which don't.

For a count aggregate for example, it's important that all variables (even unnamed ones) appearing in the subclause are given a space in the head. For min and max aggregates, we know that the entire subclause (as is the case for any aggregate) will need to appear as the body of the materialised rule, but what goes in the head is a bit less straightforward. We could get away with only exporting the column that we are taking the maximum over, because this is the only value that we need to retrieve. The same can be said for sum and mean.

BUT there is a caveat: We support the construct of witnesses to an aggregate calculation. A witness is some variable present in the aggregate subclause that is exported ungrounded to the base scope. If we do save all configurations of the variables in the aggregate subclause (as we are doing when we materialise it), then we can reuse this materialised subclause to retrieve the witness almost instantly.

(This is assuming that we have a good enough machinery to recognise when rules are exactly the same, because the witness transformation actually has to take place BEFORE the materialisation, meaning that there will be two separate relations that actually will represent exactly the same relation semantically, and we would want those to be recognised as a single relation)

So not only then (assuming we have good "equality of rules" machinery) does using the "count" aggregate technique (just giving each variable a place in the head) allow us to save and retrieve witnesses easily, but it also just makes the treatment of aggregates uniform, which I suppose is simpler, nicer, more aesthetic maybe.

Giving min/max/mean/sum aggregate materialised relations only a single column would be far more efficient, but then we would lose the ability to retrieve witnesses. So this was the tradeoff, and losing witnesses is just not an option. We NEED them to be able to give the user witness functionality.

To clarify, we don't want to include local variables of any inner aggregates appearing in this aggregate. My reasoning for deciding this was really just a hunch that I felt like local variables of an inner aggregate should be totally irrelevant. So we include "immediate" local variables, not local variables of any inner aggregate.

The other thing we must include is any injected variables. Depending on the assignment of the injected variable, the aggregate's value may change, but so, still, why would it be important to include the injected variable in the head then?

  A(x, n) :- B(x), n = sum y : { C(y, x) }.

Because we need the assignment of x in the outer scope to COINCIDE with the assignment of x in the inner scope. The only thing visible to the outer scope is whatever is in the head. That is good enough justification. And this applies to any type of aggregate.

So the overall conclusion is that what we should include are:

• injected variables
• immediate local variables

The head atom should contain immediate local and injected variables. No witnesses! They have already been transformed away. This means that we exclude any inner aggregate local variables. But we do NOT exclude inner aggregate injected variables!! It's important that the injected variable ends up in this head so that we do not obfuscate the injected variable's relationship to the outer scope. It does not affect the aggregate value because adding an extra column for the injected variable, where that column will only have one value at a time, will essentially replicate the aggregate body relation for as many possible values of the injected variable that there are. The fact that the injected variable will take one value at a time is key.

Definition at line 77 of file MaterializeAggregationQueries.cpp.

                                  : analysis::getLocalVariables(tu, clause, aggregate)) {
        headArguments.insert(localVarName);
    }
    // find local variables of inner aggregate and remove them
    visitDepthFirst(aggregate, [&](const Aggregator& innerAggregate) {
        if (aggregate == innerAggregate) {
            return;
        }
        for (const auto& innerLocalVariableName : analysis::getLocalVariables(tu, clause, innerAggregate)) {
            headArguments.erase(innerLocalVariableName);
        }
    });
    // find injected variables of this aggregate and add them
    for (const auto& injectedVarName : analysis::getInjectedVariables(tu, clause, aggregate)) {
        headArguments.insert(injectedVarName);
    }
    return headArguments;
}
 
// TODO (Issue 1696): Deal with recursive parameters with an assert statement.
void MaterializeAggregationQueriesTransformer::groundInjectedParameters(
        const TranslationUnit& translationUnit, Clause& aggClause, const Clause& originalClause,

getName()

std::string souffle::ast::transform::MaterializeAggregationQueriesTransformer::getName ( ) const

inlineoverridevirtual

Implements souffle::ast::transform::Transformer.

Definition at line 46 of file MaterializeAggregationQueries.h.

       :
    bool transform(TranslationUnit& translationUnit) override {

groundInjectedParameters()

void souffle::ast::transform::MaterializeAggregationQueriesTransformer::groundInjectedParameters ( const TranslationUnit &  translationUnit, Clause &  aggClause, const Clause &  originalClause, const Aggregator &  aggregate  )

staticprivate

Modify the aggClause by adding in grounding literals for every variable that appears in the clause ungrounded.

The source of literals to copy from is the originalClause.

Mask inner aggregates to make sure we don't consider them grounded and everything.

Go through body literals. If the literal is an atom, then replace the atom with a negated version of the atom, so that injected parameters that occur in an inner aggregate don't "seem" grounded.

Definition at line 114 of file MaterializeAggregationQueries.cpp.

                                : public NodeMapper {
        std::unique_ptr<Node> operator()(std::unique_ptr<Node> node) const override {
            if (auto* aggregate = dynamic_cast<Aggregator*>(node.get())) {
                /**
                 * Go through body literals. If the literal is an atom,
                 * then replace the atom with a negated version of the atom, so that
                 * injected parameters that occur in an inner aggregate don't "seem" grounded.
                 **/
                std::vector<Own<Literal>> newBody;
                for (const auto& lit : aggregate->getBodyLiterals()) {
                    if (auto* atom = dynamic_cast<Atom*>(lit)) {
                        newBody.push_back(mk<Negation>(souffle::clone(atom)));
                    }
                }
                aggregate->setBody(std::move(newBody));
            }
            node->apply(*this);
            return node;
        }
    };
 
    auto aggClauseInnerAggregatesMasked = souffle::clone(&aggClause);
    aggClauseInnerAggregatesMasked->setHead(mk<Atom>("*"));
    NegateAggregateAtoms update;
    aggClauseInnerAggregatesMasked->apply(update);
 
    // what is the set of injected variables? Those are the ones we need to ground.
    std::set<std::string> injectedVariables =
            analysis::getInjectedVariables(translationUnit, originalClause, aggregate);
 
    std::set<std::string> alreadyGrounded;
    for (const auto& argPair : analysis::getGroundedTerms(translationUnit, *aggClauseInnerAggregatesMasked)) {
        const auto* variable = dynamic_cast<const ast::Variable*>(argPair.first);
        bool variableIsGrounded = argPair.second;
        if (variable == nullptr || variableIsGrounded) {
            continue;
        }
        // If it's not an injected variable, we don't need to ground it
        if (injectedVariables.find(variable->getName()) == injectedVariables.end()) {
            continue;
        }
 
        std::string ungroundedVariableName = variable->getName();
        if (alreadyGrounded.find(ungroundedVariableName) != alreadyGrounded.end()) {
            // may as well not bother with it because it has already
            // been grounded in a previous iteration
            continue;
        }
        // Try to find any atom in the rule where this ungrounded variable is mentioned
        for (const auto& lit : originalClause.getBodyLiterals()) {
            // -1. This may not be the same literal
            bool originalAggregateFound = false;
            visitDepthFirst(*lit, [&](const Aggregator& a) {
                if (a == aggregate) {
                    originalAggregateFound = true;
                    return;
                }
            });
            if (originalAggregateFound) {
                continue;
            }
            // 0. Variable must not already have been grounded
            if (alreadyGrounded.find(ungroundedVariableName) != alreadyGrounded.end()) {
                continue;
            }
            // 1. Variable must occur in this literal
            bool variableOccursInLit = false;
            visitDepthFirst(*lit, [&](const Variable& var) {
                if (var.getName() == ungroundedVariableName) {
                    variableOccursInLit = true;
                }
            });
            if (!variableOccursInLit) {
                continue;
            }
            // 2. Variable must be grounded by this literal.
            auto singleLiteralClause = mk<Clause>();
            singleLiteralClause->addToBody(souffle::clone(lit));
            bool variableGroundedByLiteral = false;
            for (const auto& argPair : analysis::getGroundedTerms(translationUnit, *singleLiteralClause)) {
                const auto* var = dynamic_cast<const ast::Variable*>(argPair.first);
                if (var == nullptr) {
                    continue;
                }
                bool isGrounded = argPair.second;
                if (var->getName() == ungroundedVariableName && isGrounded) {
                    variableGroundedByLiteral = true;
                }
            }
            if (!variableGroundedByLiteral) {
                continue;
            }
            // 3. if it's an atom:
            //  the relation must be of a lower stratum for us to be able to add it. (not implemented)
            //  sanitise the atom by removing any unnecessary arguments that aren't constants
            //  or basically just any other variables
            if (const auto* atom = dynamic_cast<const Atom*>(lit)) {
                // Right now we only allow things to be grounded by atoms.
                // This is limiting but the case of it being grounded by
                // something else becomes complicated VERY quickly.
                // It may involve pulling in a cascading series of literals like
                // x = y, y = 4. It just seems very painful.
                // remove other unnecessary bloating arguments and replace with an underscore
                VecOwn<Argument> arguments;
                for (auto arg : atom->getArguments()) {
                    if (auto* var = dynamic_cast<ast::Variable*>(arg)) {
                        if (var->getName() == ungroundedVariableName) {
                            arguments.emplace_back(arg->clone());
                            continue;
                        }
                    }
                    arguments.emplace_back(new UnnamedVariable());
                }
 
                auto groundingAtom =
                        mk<Atom>(atom->getQualifiedName(), std::move(arguments), atom->getSrcLoc());
                aggClause.addToBody(souffle::clone(groundingAtom));
                alreadyGrounded.insert(ungroundedVariableName);
            }
        }
        assert(alreadyGrounded.find(ungroundedVariableName) != alreadyGrounded.end() &&
                "Error: Unable to ground parameter in materialisation-requiring aggregate body");
        // after this loop, we should have added at least one thing to provide a grounding.
        // If not, we should error out. The program will not be able to run.
        // We have an ungrounded variable that we cannot ground once the aggregate body is
        // outlined.
    }
}
 
bool MaterializeAggregationQueriesTransformer::materializeAggregationQueries(
        TranslationUnit& translationUnit) {
    bool changed = false;

References souffle::clone().

Here is the call graph for this function:

instantiateUnnamedVariables()

void souffle::ast::transform::MaterializeAggregationQueriesTransformer::instantiateUnnamedVariables ( Clause &  aggClause )

staticprivate

Whatever variables have been left unnamed have significance for a count aggregate.

They NEED to be in the head of the materialized atom that will replace this aggregate subclause. Therefore, we give them dummy names (_n rather than just _) so that the count will be correct.

Definition at line 53 of file MaterializeAggregationQueries.cpp.

                                                            {
            if (isA<UnnamedVariable>(node.get())) {
                return mk<Variable>("_" + toString(count++));
            }
            if (isA<Aggregator>(node.get())) {
                // then DON'T recurse
                return node;
            }
            node->apply(*this);
            return node;
        }
    };
 
    InstantiateUnnamedVariables update;
    for (const auto& lit : aggClause.getBodyLiterals()) {
        lit->apply(update);
    }
}
 
std::set<std::string> MaterializeAggregationQueriesTransformer::distinguishHeadArguments(
        const TranslationUnit& tu, const Clause& clause, const Aggregator& aggregate) {
    /**

References souffle::test::count(), and souffle::toString().

Here is the call graph for this function:

materializeAggregationQueries()

bool souffle::ast::transform::MaterializeAggregationQueriesTransformer::materializeAggregationQueries ( TranslationUnit &  translationUnit )

static

Creates artificial relations for bodies of aggregation functions consisting of more than a single atom, in the given program.

Parameters

program

the program to be processed

Returns

whether the program was modified

GENERAL PROCEDURE FOR MATERIALISING THE BODY OF AN AGGREGATE: NB:

• Only bodies with more than one atom or an inner aggregate need to be materialised.
• Ignore inner aggregates (they will be unwound in subsequent applications of this transformer)
• Copy aggregate body literals into a new clause
• Pull in grounding atoms
• Set up the head: This will include any local and injected variables in the body.
• Instantiate unnamed variables in count operation (idk why but it's fine)

Definition at line 249 of file MaterializeAggregationQueries.cpp.

                                                        {
        visitDepthFirst(agg, [&](const Aggregator& innerAgg) {
            if (agg != innerAgg) {
                innerAggregates.insert(&innerAgg);
            }
        });
    });
 
    visitDepthFirst(program, [&](const Clause& clause) {
        visitDepthFirst(clause, [&](const Aggregator& agg) {
            if (!needsMaterializedRelation(agg)) {
                return;
            }
            // only materialise bottom level aggregates
            if (innerAggregates.find(&agg) != innerAggregates.end()) {
                return;
            }
            // begin materialisation process
            auto aggregateBodyRelationName = analysis::findUniqueRelationName(program, "__agg_subclause");
            auto aggClause = mk<Clause>();
            // quickly copy in all the literals from the aggregate body
            for (const auto& lit : agg.getBodyLiterals()) {
                aggClause->addToBody(souffle::clone(lit));
            }
            if (agg.getBaseOperator() == AggregateOp::COUNT) {
                instantiateUnnamedVariables(*aggClause);
            }
            // pull in any necessary grounding atoms
            groundInjectedParameters(translationUnit, *aggClause, clause, agg);
            // the head must contain all injected/local variables, but not variables
            // local to any inner aggregates. So we'll just take a set minus here.
            // auto aggClauseHead = mk<Atom>(aggregateBodyRelationName);
            auto* aggClauseHead = new Atom(aggregateBodyRelationName);
            std::set<std::string> headArguments = distinguishHeadArguments(translationUnit, clause, agg);
            // insert the head arguments into the head atom
            for (const auto& variableName : headArguments) {
                aggClauseHead->addArgument(mk<Variable>(variableName));
            }
            aggClause->setHead(Own<Atom>(aggClauseHead));
            // add them to the relation as well (need to do a bit of type analysis to make this work)
            auto aggRel = mk<Relation>(aggregateBodyRelationName);
            std::map<const Argument*, analysis::TypeSet> argTypes =
                    analysis::TypeAnalysis::analyseTypes(translationUnit, *aggClause);
 
            for (const auto& cur : aggClauseHead->getArguments()) {
                // cur will point us to a particular argument
                // that is found in the aggClause
                aggRel->addAttribute(mk<Attribute>(toString(*cur),
                        (analysis::isOfKind(argTypes[cur], TypeAttribute::Signed)) ? "number" : "symbol"));
            }
            // Set up the aggregate body atom that will represent the materialised relation we just created
            // and slip in place of the unrestricted literal(s) body.
            // Now it's time to update the aggregate body atom. We can now
            // replace the complex body (with literals) with a body with just the single atom referring
            // to the new relation we just created.
            // all local variables will be replaced by an underscore
            // so we should just quickly fetch the set of local variables for this aggregate.
            auto localVariables = analysis::getLocalVariables(translationUnit, clause, agg);
            if (agg.getTargetExpression() != nullptr) {
                const auto* targetExpressionVariable =
                        dynamic_cast<const Variable*>(agg.getTargetExpression());
                localVariables.erase(targetExpressionVariable->getName());
            }
            VecOwn<Argument> args;
            for (auto arg : aggClauseHead->getArguments()) {
                if (auto* var = dynamic_cast<ast::Variable*>(arg)) {
                    // replace local variable by underscore if local, only injected or
                    // target variables will appear
                    if (localVariables.find(var->getName()) != localVariables.end()) {
                        args.emplace_back(new UnnamedVariable());
                        continue;
                    }
                }
                args.emplace_back(arg->clone());
            }
            auto aggAtom =
                    mk<Atom>(aggClauseHead->getQualifiedName(), std::move(args), aggClauseHead->getSrcLoc());
 
            VecOwn<Literal> newBody;
            newBody.push_back(std::move(aggAtom));
            const_cast<Aggregator&>(agg).setBody(std::move(newBody));
            // Now we can just add these new things (relation and its single clause) to the program
            program.addClause(std::move(aggClause));
            program.addRelation(std::move(aggRel));
            changed = true;
        });
    });
    return changed;
}
 
bool MaterializeAggregationQueriesTransformer::needsMaterializedRelation(const Aggregator& agg) {
    // everything with more than 1 atom  => materialize
    int countAtoms = 0;

References souffle::ast::visitDepthFirst().

Here is the call graph for this function:

needsMaterializedRelation()

bool souffle::ast::transform::MaterializeAggregationQueriesTransformer::needsMaterializedRelation ( const Aggregator &  agg )

staticprivate

A test determining whether the body of a given aggregation needs to be 'outlined' into an independent relation or can be kept inline.

Definition at line 357 of file MaterializeAggregationQueries.cpp.

                             : agg.getBodyLiterals()) {
        const Atom* currentAtom = dynamic_cast<const Atom*>(literal);
        if (currentAtom != nullptr) {
            ++countAtoms;
            atom = currentAtom;
        }
    }
 
    if (countAtoms > 1) {
        return true;
    }
 
    bool seenInnerAggregate = false;
    // If we have an aggregate within this aggregate => materialize
    visitDepthFirst(agg, [&](const Aggregator& innerAgg) {
        if (agg != innerAgg) {
            seenInnerAggregate = true;
        }
    });
 
    if (seenInnerAggregate) {
        return true;
    }
 
    // If the same variable occurs several times => materialize
    bool duplicates = false;
    std::set<std::string> vars;
    if (atom != nullptr) {
        visitDepthFirst(*atom, [&](const ast::Variable& var) {
            duplicates = duplicates || !vars.insert(var.getName()).second;
        });
    }
 
    // If there are duplicates a materialization is required
    // for all others the materialization can be skipped
    return duplicates;
}
 
}  // namespace souffle::ast::transform

transform()

bool souffle::ast::transform::MaterializeAggregationQueriesTransformer::transform ( TranslationUnit &  translationUnit )

inlineoverrideprivatevirtual

Implements souffle::ast::transform::Transformer.

Definition at line 64 of file MaterializeAggregationQueries.h.

---

The documentation for this class was generated from the following files:

• ast/transform/MaterializeAggregationQueries.h
• ast/transform/MaterializeAggregationQueries.cpp