neurolang.datalog.magic_sets module

Magic Sets [1] rewriting implementation for Datalog.

[1] F. Bancilhon, D. Maier, Y. Sagiv, J. D. Ullman, in ACM PODS ’86, pp. 1–15.

class neurolang.datalog.magic_sets.AdornedSymbol(expression, adornment, number)

Bases: Symbol

Attributes:

name

Methods

__call__(*args, **kwargs)	Call self as a function.
apply(*args)	Builds a new expression using a tuple of its parameters
type
unapply()	Returns a tuple of parameters used to build the expression.

cast
change_type
fresh
get_wrapped_attribute

property name

type = typing.Any

class neurolang.datalog.magic_sets.LeftToRightSIPS(datalog)

Bases: SIPS

LeftToRightSIPS which corresponds to the default SIPS as specified in Balbin et al. [1].

For a given body predicate P and head predicate H with adornment a, a variable v of P is bound iif:

• it corresponds to a bound variable of H in a.

• or it is a variable of a positive non probabilistic body literal

left of P in the rule.

[1]

Isaac Balbin, Graeme S. Port, Kotagiri Ramamohanarao, Krishnamurthy Meenakshi. 1991. Efficient Bottom-UP Computation of Queries on Stratified Databases. J. Log. Program. 11(3&4). p. 305.

Methods

creates_arcs(rule, adorned_head)

For a given rule and an adorned head predicate, create the arcs corresponding to this SIPS.

class neurolang.datalog.magic_sets.ReplaceAdornedSymbolWalker(*args, **kwargs)

Bases: ExpressionWalker

Attributes:

patterns

Property holding an iterator of triplets (pattern, guard, action).

Methods

match(expression)	Find the action for a given expression by going through the patterns.
pattern_match(pattern, expression)	Return True if pattern matches expression.
type

implication
pattern_match_expression
pattern_match_expression_parameters
pattern_match_expression_tuple
pattern_match_tuple
process_expression
process_iterable_argument
replace_adorned_symbol
walk

implication(exp)

replace_adorned_symbol(symbol)

type = typing.Any

class neurolang.datalog.magic_sets.SIPS(datalog)

Bases: ABC

Sideways Information Passing Strategy (SIPS). A SIPS defines how bound variables are passed from the head of a rule to the body predicates of the rule. SIPS formally describe what information (bound variables) is passed by one literal, or a conjunction of literals, to another literal.

Methods

creates_arcs(rule, adorned_head)

For a given rule and an adorned head predicate, create the arcs corresponding to this SIPS.

creates_arcs(rule, adorned_head)

For a given rule and an adorned head predicate, create the arcs corresponding to this SIPS.

For each predicate in the rule’s antecedent, this method will try to create an arc by calling self._create_arc, which should return None if no arc can be created for this predicate, or return the head and tail of the arc to be added.

Returns:

Union[Dict[Expression, Tuple[Expression]], Tuple[Expression]]

returns the created arcs as a dict mapping of head -> tails and the adorned antecedent of the rule

neurolang.datalog.magic_sets.adorn_antecedent(rule, adorned_head, rewritten_rules, sips: SIPS)

neurolang.datalog.magic_sets.adorn_code(query: Expression, datalog: DatalogProgram, sips: SIPS) → Union

Produce the rewritten datalog program according to the Magic Sets technique.

Parameters:

queryExpression

query to solve

datalogDatalogProgram

processed datalog program

sips_classSIPS

the SIPS instance to use for adornment of predicates

Returns:

Union

adorned code where the query rule is the first expression in the block.

neurolang.datalog.magic_sets.create_balbin_magic_rules(adorned_rules, sips)

Create the set of Magic Set rules according to Algorithm 2 of Balbin et al.

This method creates the ensemble Pm of rewritten rules from the ensemble P^a of adorned rules in the program (not including the adorned query rule).

The pseudo-code algorithm for this method is:

``` for each adorned rule Ra in P^a of the form head :- body

add the rule head :- Magic(head), body to Pm for each adorned predicate p in body :

add the rule Magic(p) :- Magic(h), ^(body predicates left of p)

```

neurolang.datalog.magic_sets.create_magic_query_inits(constant_predicates: Iterable[AdornedSymbol])

Create magic initialization predicates from the set of adorned predicates with at least one argument constant, according to Balbin et al.’s magic set algorithm. For each adorned predicate p^a(t) in the set, return an initialization rule of the form magic_p^a(t_d) :- True, where t_d is the vector of arguments which are bound in the adornment a of p.

Parameters:

constant_predicatesIterable[AdornedExpression]

the set of adorned predicates where at least one argument is a constant

Returns:

Iterable[Expression]

the set of magic initialization rules

neurolang.datalog.magic_sets.edb_with_prob_symbols(datalog: DatalogProgram) → Iterable[Symbol]

neurolang.datalog.magic_sets.magic_predicate(predicate, i=None, adorned=True)

Given a predicate of the form P^bf(x, y), create a magic predicate of the form magic_P^bf(x). If adorned is True, the magic predicate returned is an AdornedSymbol, otherwise it is a Symbol with the name magic_P^bf.

Parameters:

predicateExpression

a predicate with an adorned symbol

iint, optional

a rule number, by default None

adornedbool, optional

whether to return an AdornedSymbol, by default True

Returns:

Expression

a new predicate.

neurolang.datalog.magic_sets.magic_rewrite(query: Expression, datalog: DatalogProgram) → Tuple[Symbol, Union]

Implementation of the Magic Sets method of optimization for datalog programs using Balbin et al [1] algorithm.

[1]

Isaac Balbin, Graeme S. Port, Kotagiri Ramamohanarao, Krishnamurthy Meenakshi. 1991. Efficient Bottom-UP Computation of Queries on Stratified Databases. J. Log. Program. 11(3&4). p. 311.

queryExpression

the head symbol of the query rule in the program

datalogDatalogProgram

a processed datalog program to optimize

Returns:

Tuple[Symbol, Union]

the rewritten query symbol and program

neurolang.datalog.magic_sets.reachable_adorned_code(query, datalog, sips: SIPS)