I-DLV: The new intelligent grounder of DLV

2.3.1 Deductive database applications

We start illustrating an ASP-based solution to Reachability, and then deal with Same Generation.

2.3.1.1 Reachability. Given a finite directed graph G = (N, A), we want to compute all pairs of nodes (a, b) ∈ N × N such that b is reachable from a through a nonempty sequence of arcs in A. In other words, the problem amounts to computing the transitive closure of the relation A.

In the following ASP encoding, we assume that A is represented by the binary relation arc (X, Y), where a fact arc (a, b) means that G contains an arc from a to b, i.e., (a, b) ∈ A; the set of nodes N is not explicitly represented, since the nodes appearing in the transitive closure are implicitly given by these facts. Hence, the following program computes a relation reachable (X, Y) containing all facts reachable (a, b) such that b is reachable from a through the arcs of the input graph G:

2.3.1.2. Same generation. Given a parent-child relationship, represented by acyclic directed graph, we want to find all pairs of persons belonging to the same generation. Two persons are of the same generation if either they are siblings, or they are children of two persons of the same generation. If input is encoded by a relation parent (X, Y), where a fact parent (a, b) states that a is a parent of b, the solution can be encoded by the following program, which computes a relation samegeneration (X, Y) containing all facts such that X is of the same generationas Y:

2.3.2 The GC declarative programming methodology

We introduce here one of the most common programming paradigm in ASP, namely the Guess&Check ( GC ) Technique [19], and illustrate its application on a number of examples. Many problems can be solved in a natural manner by using this declarative programming technique: the power of disjunctive rules allows to express problems which are more complex than NP, and the (optional) separation of a fixed, non-ground program from an input database allows to do so in a uniform way over varying instances.

Given a set F _I of facts that specify an instance I of some problem P, a GC program P for P consists of the following two main parts:

Guessing Part. The guessing part G ⊆ P of the program defines the search space, such that answer sets of G ∪ F _I represent “solution candidates” for I.

There are no restrictions on which rules G and C may contain; hence, in the extremal case we might set G to the full program and let C be empty, i.e., checking is completely integrated into the guessing part, so that solution candidates are always solutions. Thus, both G and C may consist of arbitrary collections of rules, and it depends on the complexity of the problem at hand which kinds of rules are needed to realize these parts (in particular, the checkingpart).

The GC programming methodology has also positive implications from the “Software Engineering” point of view. Indeed, the modular program structure typical of GC allows to develop programs in an incremental fashion, which is helpful to simplify testing and debugging. For instance, one can start by writing the guessing part G and testing that G ∪ F _I correctly defines the search space, and then add the checking part and hence verify that the answer sets of G ∪ C ∪ F _I actually encode the admissible solutions.

When dealing with optimization problems, the methodology can be further extended to match a “Guess/Check/Optimize” ( GCO ) paradigm [8]: ad-hoc means for expressing preferences among answer sets are employed, such as weak constraints [8, 10], thus implementing the Optimization Part that specifies a quantitative cost evaluation of solutions. It implicitly defines an objective function f : AS (G∪ C ∪ F _I ) → ℕ mapping the answer sets of G ∪ C ∪ F _I to natural numbers. The semantics of G ∪ C ∪ F _I  ∪ O optimizes f by filtering those answer sets featuring the minimum value; by doing so, the optimal (least cost) solutions are computed.

Let us consider a classical NP-complete problem in graph theory, namely Hamiltonian Path.

2.3.2.1. Hamiltonian path. Given a directed graph G = (N, A) and a node a ∈ N of this graph, does there exist a path in G starting from a and passing through each node in N exactly once?

If the graph G is specified by means of facts over predicates node (unary) and arc (binary), and the starting node a is specified by the predicate start (unary), then, the following GC program P _hp encodes a solution to the problem:

In the Guessing part, the two disjunctive rules guess a subset S of the arcs to be in the path, while the rest of the program checks whether S constitutes an Hamiltonian Path. Here, an auxiliary predicate reached is used, which is associated with the guessed predicate inPath using the third rule. Note that reached is completely determined by the guess for inPath, and no further guessing is needed. In turn, through the second rule, the predicate reached influences the guess of inPath, which is made somehow inductively: initially, a guess on an arc leaving the starting node is made by the first rule, followed by repeated guesses of arcs leaving from reached nodes by the second rule, until all reached nodes have been handled.

In the Checking part, the first two constraints ensure that the set of arcs S selected by inPath meets the following requirements, which any Hamiltonian Path must satisfy: (i) there must not be two arcs starting at the same node, and (ii) there must not be two arcs ending in the same node. The third constraint enforces that all nodes in the graph are reached from the starting node in the subgraph induced by S.

It is easy to see that any set of arcs S which satisfies all three constraints must contain the arcs of a path v₀, v₁, …, v _k in G that starts at node v₀ = a, and passes through distinct nodes until no further node is left, or it arrives at the starting node a again. In the latter case, this means that the path is in fact an Hamiltonian Cycle (from which an Hamiltonian path can be immediately computed, by dropping the last arc).

Thus, given a set of facts F for node, arc, and start, the program P _hp  ∪ F has an answer set if and only if the corresponding graph has an Hamiltonian Path. The above program correctly encodes the decision problem of deciding whether a given graph admits an Hamiltonian Path or not.

In the previous example we have seen how a search problem can be encoded in an ASP program whose answer sets correspond one-to-one to the solutions of the given instance. We see next another use of the GC programming technique: we build an ASP program whose answer sets witness that a property does not hold, i.e., the property at hand holds if and only if the ASP program has no answer set at all. We next apply the above programming scheme to a problem from the number and graph theories, namely Ramsey Numbers.

2.3.2.2. Ramsey numbers. The Ramsey number R (k, m) is the least integer n such that, no matter how we color the arcs of the complete undirected graph (clique) with n nodes using two colors, say red and blue, there is a red clique with k nodes (a red k-clique) or a blue clique with m nodes (a blue m-clique) [52].

We next show a program P _ramsey that allows us to decide whether a given integer n is not the Ramsey Number R (3, 4). By varying the input number n, we can determine R (3, 4), as described below. Let F be the collection of facts for input predicates node and arc encoding a complete graph with n nodes. P _ramsey is the following GC program:

Intuitively, the disjunctive rule guesses a color for each edge. The first constraint eliminates the colorings containing a red clique (i.e., a complete graph) with 3 nodes, and the second constraint eliminates the colorings containing a blue clique with 4 nodes. The program P _ramsey  ∪ F has an answer set if and only if there is a coloring of the edges of the complete graph on n nodes containing no red clique of size 3 and no blue clique of size 4. Thus, if there is an answer set for a particular n, then n is not R (3, 4), that is, n < R (3, 4). On the other hand, if P _ramsey  ∪ F has no answer set, then n ≥ R (3, 4). Thus, the smallest n such that no answer set is found is the Ramsey number R (3, 4).

3.2.1 Managing isolated variables

At the very beginning, rules possibly undergo a rewriting process in order to remove isolated variables. For instance, consider a non-ground rule r containing a body atom p (X₁, . . . , X _n ), with a variable X _i that does not appear anywhere else in r. While instantiating r, substitutions for X _i will not affect any failed match for other atoms, nor the instances obtained for the head atoms. Thus, we can safely eliminate X _i by projecting all variables X _k , k ≠ i of p to an auxiliary predicate p′. That is, a new (non-ground) rule is added: p′ (X₁, . . . , X_i-1, X_i+1, . . . , X _n )  : – p (X₁, . . . , X _n ) . and p (X₁, . . . , X _n ) . is substituted by p′ (X₁, . . . , X_i-1, X_i+1, . . . , X _n ) in the body of r. By doing so, the generation of ground instances of r which differ only on the binding of X _i is avoided. In many cases this reduces the size of the ground program, and consequently the instantiation time; nevertheless, an overhead is paid, due to the need for copying the projected instances of p in the extension of p′; such overhead, even if negligible in general, might become significant when the benefits of the projection are limited. For this reason, such projection rewriting can be disabled on request.

As a remark, the old DLV  grounder was endowed with a dedicated rewriting module that implemented, among others, also this functionality. Such a module was monolithic: either all strategies were applied, or none at all. However, every rewriting shows its benefits only in specific scenarios, and can worsen performance in others; thus, the contemporary activation of many is not typically convenient.

3.2.2 Body ordering

Once the rewriting process is over, the order of literals in the rule bodies is analysed and possibly changed in a way inspired by techniques developed in the database setting, where a crucial task is to find an optimal execution ordering for the join operations. Several ordering strategies have been defined and implemented in ℐ-DLV, based on different heuristics; they perform differently, each one featuring some advantages case by case. We discuss next the Combined ⁺ criterion, which is the one that better performed in the experiments, and, hence, the one that ℐ-DLV uses as default; a more thorough discussion about other criteria is out of the scope of this work. This criterion has been defined by enhancing the Combined criterion [38] already implemented in DLV . In order to highlight how the new criterion acts, we formalize first the key ideas behind the Combined criterion, and then describe its improvements.

Intuitively, given a rule r, the Combined criterion processes B (r) generating a new version of it, namely B′ (r), where the literals have been rearranged according to a greedy algorithm; at each step, the “best” literal, which is determined relying on statistics over the involved predicates, is placed, and then the statistics are updated. The “best” literal is the one that minimizes a formula (see [38]) based on two factors: one is a measure of how much the choice of a literal reduces the search space for possible substitutions, and the other takes into account the binding of the variables of the literal (indeed, preferring literals with already bound variables might lead to detecting possible inconsistencies quickly). In order to outline how the Combined ⁺ criterion enhances the Combined one, we illustrate next some measures whose definition changes while moving from the old criterion to the new one.

Let us define B i ′ as the reordered (partial) body at step i, and var ( B i ′ ) as the set of variables within B i ′, which is also denoted as the set of bound variables in B i ′. Given a positive literal L over a predicate p, for each variable X ∈ var (L), the selectivity of X in L (i.e. the number of distinct values), denoted V (X, L), corresponds to the number of tuples in the projection of X over the ground extension of the predicate p. Furthermore, given a rule r, for each variable X appearing in B⁺ (r), the active domain of X is defined as dom ( X ) = max L ∈ B + ( r ) V ( X , L ). Being L the literal positioned at step i, i.e., B i ′ = B i - 1 ′ ∪ L, then, for each variable X ∈ var ( B i ′ ), the selectivity of X in B i ′ is defined as V ( X , B i ′ ) = V ( X , B i - 1 ′ ) · ( V ( X , L ) / dom ( X ) ) if X ∈ var ( B i - 1 ′ ); if otherwise X ∉ var ( B i - 1 ′ ), then V ( X , B i ′ ) = V ( X , L ). However, according to these measures, the criterion might fail at finding a “good” ordering. As a running example, let us consider the rule: a ( X , Y , Z ) : – b ( X ) , b ( Y ) , b ( Z ) , Z < X , Z < Y .

Here the criterion has no useful information for the selection of a proper order for literals b (X), b (Y), b (Z). Indeed, given that they all have the same predicate and that the considered measures do not take into account the comparisons built-in, each possible permutation of these atoms may be indiscriminately chosen.

However, their ordering can significantly affect performance, since their variables are involved in the comparisons Z < X, and Z < Y. To overcome such situations, the Combined ⁺ criterion improves the cited measures relying on linear interpolation techniques to determine how much the actual search space for variables substitution is influenced by the comparisons. The new criterion preserves the assumption of uniform distribution of data already adopted in the original criterion.

Given a positive literal L over the predicate p, and a variable X ∈ var (L) which features a domain consisting of integer numbers, we define min (X, L) as the minimum value, max (X, L) as the maximum value over such domain. Please notice that the assumption over integer domains is not restrictive, as it is always possible to define a proper mapping from a generic term to a number, according to the total order of terms defined in the ASP-Core-2 standard.

Let us now describe how the Combined ⁺ criterion estimates and updates the measures at each step i.

For each candidate literal L, for each variable X ∈ L, the criterion makes a pre-estimation V _e  (X, B _i ) of V (X, B _i ) if X is an evaluable variable, that is if the following conditions hold: (i) X is not bound (i.e., X ∉ var ( B i - 1 ′ )), and (ii) X appears in B (r) in some comparisons of the form X ≺ Y, where ≺ ∈ {< , < = , > , > = , = , < >} and Y is either a ground term or a bound variable such that Y ∈ var ( B i - 1 ′ ).

Initially, V e ( X , B i ′ ) = V ( X , L ); then, it is recursively updated taking into account each comparison involving X and satisfying the last condition, as described next.

If X is involved in a comparison in the form X < C or X < = C where C is a ground term and C _num is the reduction of C to a numeric value, then:

V e ( X , B i ′ ) = ( V e ( X , B i ′ ) - 1 ) × ( ( C num - min ( X , L ) ) ( max ( X , L ) - min ( X , L ) ) ) .

If the comparison is of the form X > C or X > = C, then it is equivalent to C < X or C < = X, respectively; hence:

V e ( X , B i ′ ) = V e ( X , B i ′ ) - ( ( V e ( X , B i ′ ) - 1 ) × ( C num - min ( X , L ) ) ( max ( X , L ) - min ( X , L ) ) ) .

On the other hand, when the X is compared to a variable, such as in X ≺ Y, where ≺ ∈ {< , < = , > , > =}, then a constant value Y _num for Y is first estimated, and then the formulae above are applied; in particular, if ≺in {< , < =} then Y _num  = max (Y, L₁), while if ≺in {> , > =} then Y _num  = min (Y, L₁), where L₁ is the literal binding Y in B_i-1.

Finally, if X appears in a comparison in the form X = Z, where Z is either a ground term or a variable, then: V e ( X , B i ′ ) = 1 V e ( X , B i ′ )

while if the comparison is like X ! = Z then:

V e ( X , B i ′ ) = V e ( X , B i ′ ) - ( 1 V e ( X , B i ′ ) ) .

In these last two cases, indeed, the algorithm tries to estimate the probability that the value that will bound the variable X will actually be equal (or different) to the one estimated. In addition, if Z is a constant, say C, it is possible to determine with certainty if the value C is admissible or not for X, by computing if C belongs to the domain of X; otherwise, if Z is a variable, it is still possible to estimate the probability that the values assignable to Z are admissible by estimating a ground value Z _num as 1 / V ( Z , B i - 1 ′ ).

After computing these pre-estimations, the criterion has a better measure of how much the comparisons can influence the variables selectivities, and thus it can properly select the next literal to add in B i - 1 ′, say L′, so that B i ′ = B i - 1 ′ ∪ L ′. Eventually, for each variable X ∈ L′, V ( X , B i ′ ) is updated in an unchanged way with respect to the old criterion, unless X is evaluable: in this case V ( X , B i ′ ) = V e ( X , B i ′ ).

Coming back to the running example, let us assume that instances for predicate b currently consists of the set b (1 . .100) (i.e., all from b (1) to b (100)); then, the Combined ⁺ algorithm arranges the rule asfollows: a ( X , Y , Z ) : – b ( X ) , b ( Z ) , Z < X , b ( Y ) , Z < Y .

Initially, B 0 ′ = b ( X ), and the next chosen literal is then b (Z): the algorithm prefers b (Z) over b (Y), as it computes that V ( Z , B 1 ′ ) = 99 and V ( Y , B 1 ′ ) = 100. Intuitively, b (X) and b (Z) are here involved in a cross-product operation, thus the algorithm estimates that, in general, Z ranges over values that are smaller than the ones assigned to X in 99/100 cases, except for when they have assigned the same value. At this point, we have B 1 ′ = b ( X ) , b ( Z ), and the comparison built-in Z < X can be safely selected: indeed, when adding a comparison literal its variables have to be bound in order to correctly evaluate them. Subsequently, b (Y), and finally Z < Y, can be chosen. It is worth noticing that an equally preferable ordering would be, in this case: a ( X , Y , Z ) : – b ( Y ) , b ( Z ) , Z < Y , b ( X ) , Z < X .

Indeed, both Z < X and Z < Y have the same influence on the selectivity of Z.

3.2.3 Backjumping

Once the non-ground rules have been “adapted”, they undergo the actual rule instantiation phase, based on a backtracking search. It is worth remembering that backtracking has a great impact on the whole rule instantiation machinery: fine-tuning it might lead to great performance improvements.

ℐ-DLV employs the same non-chronological backtracking strategy of its predecessor, that reduces both the computation time and the size of the instantiation. In particular, while instantiating a rule, when a backtrack step is necessary, by considering the literal that most likely is involved in the reason of a failed match, it is possible to jump back many literals, rather than just one as in the chronological algorithm. Such “jumps” should be designed carefully, in order to avoid that some solution is missed, especially in our case, where we have to compute all (relevant) solutions. Moreover, our algorithm makes use of both semantic and structural information of the rule at hand, to compute only a relevant subset of its ground instances, yet fully preserving the semantics [50].

3.2.4 Indexing

The process is further optimized by making use of indexing techniques for the retrieval of matching instances from the predicate extensions. The indexing strategy adopted in ℐ-DLV is very flexible: any predicate argument can be indexed, allowing both single- and multiple-argument indices. For each predicate different indexing data structures can be built “on-demand”, only if needed, while instantiating a rule containing that predicate in its body.

The default configuration makes use of a heuristic which selects single- or double-indices relying on bindings; we recall here that, given a rule r whose body contains the literals L₁, …, L _n , an argument of a predicate p contained in a literal L _i is bound if it is either a ground term or contains only variables already present in some literals L _j with j = {0, …, i - 1}.

When ℐ-DLV retrieves the instances of a predicate p in r, it creates an indexing structure on-the-fly depending on its bound arguments, if needed. In particular, when multiple arguments are bound, ℐ-DLV adopts a double-argument strategy: it selects the two indexable arguments that feature the highest number of different values in the extension of p, as these are nearer to represent a double primary key for the extension of p. For instance, let us consider the rule: a ( X , Y , Z , W ) : – b ( X , Y ) , c ( X , Z ) , d ( X , Y , Z , W ) .

It is not possible to use any index for b (X, Y), due to the fact that both arguments are unbound; c (X, Z) can be indexed only on the first argument of predicate c, which is the only bound; eventually, d (X, Y, Z, W), features three bound arguments, namely the first, the second and the third, and so different indexing strategies are possible. In such situation, ℐ-DLV examines the number of different values of each bound argument, and proceeds indexing d on the most selective arguments.

An on-demand indexing strategy was present also in the old DLV  grounder [15]; however, the one herein presented is more general, more flexible, and, as experiments confirmed, moreeffective.

3.2.5 Aligning substitutions

The search for an “agreement” between body literals on variable substitutions is further eased thanks to an ad-hoc mechanism that was not present in the old DLV  grounder: before processing a rule r, for each variable X. Basically, we compute the intersection of all sets of possible substitutions for all the occurrences of X in r; intuitively, this reduces, in general, the number of possible values for X, by skipping those that would not match among distinct variable occurrences. Such technique performs best when the sets of substitutions differ significantly, thus can be enabled on demand.

More formally, given a predicate p of arity n, for each argument i with i ∈ {0, …, n}, ℐ-DLV stores set (p, i) as the set of possible (distinct) values for the argument i of p. Given a rule r, a variable X is said to be a “join variable” if it occurs in at least two different positive literal in B⁺ (r), and therefore if X corresponds to an argument of at least two different predicates. This alignment technique consists in determining, before the grounding of r actually starts, for each join variable X in B⁺ (r) the actual intersection of the sets set (q, j), where X is featured by the j-th arguments of the predicate q in B⁺ (r). As an example, let us consider therule r: a ( X , Y , Z ) : – b ( X , Y ) , c ( Y , X , Z ) , d ( Y , Z ) , e ( X ) . and in particular the variable X occurring three times in the body of r; furthermore let us suppose that |set (b, 0) |=30, |set (c, 1) |=50 and |set (e, 0) |=10. The computed intersection for X consists here in set (b, 0) ∩ set (c, 1) ∩ set (e, 0). Hence, the intersection will just contain the values on which predicates b, c and e “agree”. Intuitively, due to the presence of e (X), at most 10 values can be substituted to X in order to generate a significant substitution (i.e., a substitution that allows to obtain a relevant ground instance of r). Consequently, when substituting X with a ground value during the instantiation of r, each value that is not present in the computed intersection can be safely skipped.

3.2.6 Pushing down selections

Another optimization simulates the classic relational algebra operation of pushing selections down the execution tree. Let us consider, for instance, the following rule r: p ( X ) : – t ( X , Y , Z ) , q ( Z , V , S ) , V < S .

It is easy to see that, instead of first joining t with q and then selecting what complies with the comparison V < S, it is more convenient, in general, to first select, in the extension of q, the instances complying with the comparison, and then to join them with the ones of t. This can be obtained by means of a rewriting process similar to the one already described to project-out isolated variables. In order to avoid a possibly significant overhead, we do not actually perform the rewriting, but we simulate it during the instantiation of r: while retrieving the instances of q, only those complying with the comparison are actually taken into account. Such technique can be easily applied to cases in which more than one comparison occurs, and the involved terms appear in more than one atom.

This strategy, just like the one described in Section 3.2.1, was implemented in the rewriting module of DLV , whose disadvantages have already been mentioned. Furthermore, as already stated above, the technique is further optimized in ℐ-DLV, as the rewriting is performed virtually.

3.2.7 Isolated variables filtering

Just like the process of pushing down selections, the projection rewriting described above can be simulated as well during the instantiation, even if only in some cases. In particular, when instantiating a rule r, if a predicate p is solved (i.e., it is an EDB predicate, or it depends only on EDB and solved predicates), when looking for next matches for it, all instances that differ just because of the substitution of an isolated variable X could be ignored. To this end, the matching of atoms is empowered with a special filter mechanism that suggests only the relevant instances. This filter, combined with the backjumping machinery, when the projection rewriting (described in Section 3.2.1) is disabled, can simulate its behaviour without paying the overhead. However, the projection rewriting is more general, since it can safely be applied to all predicates, with no distinction between solved and unsolved; if p is unsolved, instead, all its instances must be considered as relevant in order to preserve semantics of the produced ground program; thus, the use of the described filter mechanism must be prevented.

This technique was not present in the old DLV  grounder.

3.2.8 Simplifications

The output of the rule instantiation process is a set of ground instances of the rule at hand. The size of the output is further reduced by examining the produced ground rules and possibly simplifying, or even eliminating them. Indeed, body literals which are already known to be true can be safely dropped. Moreover, once the rule instance has been created, when some negative literal already known to be false occurs in the body, the rule instance is already (trivially) satisfied: it does not contribute to the semantics of the ground program, and it is removed.

In case the input program is non-disjunctive and stratified w.r.t. negation, the modular evaluation guided by the Program Modules Instantiator along with the simplification mechanism allows ℐ-DLV, just like the predecessor DLV  grounder, to completely evaluate the input program: the output consists of a set of facts, that correspond to the unique answer set of the program. In such cases, there is no need to rely on a further solving module.

3.2.9 Anticipating strong constraints evaluation

The described rule grounding process can be applied also to strong constraints, with a few simplifications and adaptations due to the missing heads, when compared to “standard” rules. Notably, precisely because of this, their evaluation does not affect the aforementioned dynamic creation of the predicate extensions: thus, they could be safely processed at the very end, once the instantiation of all program modules is completed, as it was done by the old DLV  grounder. However, due to the simplification mechanism, literals appearing into the body of a ground constraint can be removed, possibly leading to an empty-body constraint. By definition, such constraints are always violated; thus, the input program is inconsistent, and the grounding process can be safely aborted. For this reason, ℐ-DLV anticipates constraints grounding, and a constraint undergoes the instantiation process as soon as the extensions of its body predicates are available.

3.2.10 Magic sets

We conclude this overview with a technique for the effective use of ℐ-DLV in a deductive database setting, where efficient query answering over logic programs is essential: the magic-sets rewriting technique. It has been originally defined in [3] for non-disjunctive Datalog (i.e., with no function symbols) queries only, and afterwards many generalizations have been proposed; a thorough presentation can be found in [9, 59]. ℐ-DLV integrates an adapted version already presented in [2, 16]; in the following, we report some basic intuitions.

The magic-set method is essentially a rewriting strategy for simulating the top-down evaluation of a query: the original program is modified in order to narrow the computation to what is relevant to answer the query. Intuitively, the goal is to use the constants appearing in the query to reduce the size of the instantiation by eliminating a priori a number of ground instances of the rules which cannot contribute to the (possible) derivation of the query goal. Basically, given an input program, the binding information for IDB predicates which would be propagated during a top-down computation are materialized by means of proper adornments of the input predicates. Hence, the adorned program is used to generate a set of magic rules, which single out the atoms potentially relevant for the input query. The adorned rules are modified by adding magic atoms in the rule bodies: this limits the range of the head variables avoiding the inference of facts which cannot contribute to deriving the query. Eventually, a magic version of the query goal is produced, that will “trigger” the bottom-up generation.

The following example shows the effectiveness of the technique while dealing with the already introduced Reachability problem.

Example 3. Let us consider the program P_q-reach constituted by the encoding for the Reachability problem reported in Section 2.3.1, along with the ground query reachable (1, 5) ? and the following facts encoding a graph:

arc (1, 2) .   arc (1, 3) .   arc (3, 4) .   arc (4, 5) .   arc (2, 6) .

arc (6, 7) .   arc (3, 6) .   arc (7, 8) .   arc (8, 6) .   arc (2, 8) .

In order to answer, without the Magic Sets technique, the system should first complete the instantiation, and then check whether the query atom is actually contained in the unique answer set (we are dealing here with a stratified datalog program, hence there is no need for a solver, as discussed in Section 3.2.8). Such answer set contains 25 instances of the predicate reachable, while not all of them are (possibly) relevant in order to answer thequery.

The application of the magic-set technique would produce the following rewritten program, instead:

In this rewriting, the extension of magic _reachable ^bb represents the set of start- and end-nodes of all potential sub-paths of paths from 1 to 5. Therefore, when answering the query via a bottom-up computation, only these sub-paths will be actually considered: in this case, just 8 instances of magic _ reachable ^bb , leading to the generation of only 3 instances of reachable.

3.3.1 Command-line customization

In what follows, we describe the most relevant options that the user can set via command-line in order to customize the behaviour of ℐ-DLV. A more comprehensive list of options, along with further details, is available via the online documentation [13].

ℐ-DLV allows to completely control the indexing strategy, thus providing the user with a mean to handle situations where the default behaviour is not satisfactory. In particular, the indexing module can set per each predicate in the program a single- or multiple-index, on the desired arguments. Since only ground arguments can be indexed, if the user specifies a non indexable argument, the default indexing strategy is adopted.

As for body ordering, the user can currently choose among the following alternatives: ord₀: a basic ordering that aims at preserving the original literal positions in the rule; ord₁: the DLV  Combined criterion [38]; ord₂: the aforementioned Combined ⁺ criterion (enabled by default); ord₃: an enhanced version of the Combined criterion that pushes literals with functional terms down in the body; ord₄: a strategy that tries to improve the quality of available indices; ord₅: a criterion that works in synergy with backjumping in order to facilitate it; ord₆: a criterion combining the latter two.

Furthermore, the projection rewriting and the filter mechanism for isolated variables in solved predicates, both enabled by default, can be disabled. Conversely, the technique to align variable substitutions can be enabled at will: it is disabled by default, given that its benefits strictly depend from the distribution of the input data.

By default, choice rules are natively managed by directly instantiating them, possibly undergoing a conservative rewriting/rearrangement that aims at optimizing efficiency; however, the user can ask for a rewriting approach that makes use of disjunction and removes them, thus generating a choice-rule-free program. Both approaches preserve thesemantics.

ℐ-DLV is able to process both ground and non-ground queries. By default, it simply produces the instantiation; upon request, for non-disjunctive and stratified programs, that are completely evaluated by the system, it can directly provide the query answer. The magic-set technique, enabled by default, can be disabled.

For advanced users, insights on the grounding process might be of great interest: they are available via a number of statistics that can be produced on demand. In particular, the following information are provided for each input rule: total instantiation time, number of produced ground instances, number of iterations required for instantiation (in case the rule is recursive); in addition, size of extension and selectivity of all arguments are reported, for each predicate in the rule.

3.3.2 Inline customization and optimizations via annotations

In order to ease and improve system customization and tuning, ℐ-DLV introduces a new special feature: annotations of ASP code.

Annotations and meta-data have been applied in different programming paradigms and languages; Java annotations, for instance, have no direct effect on the code they annotate: a typical usage consists in analysing them at runtime in order to change the code behaviour. Some sorts of annotations have been proposed also for declarative paradigms, although to different extents and purposes with respect to our setting; a more detailed discussion is carried out in Section 5.

ℐ-DLV annotations allow to give explicit directions on the internal grounding process, at a more fine-grained level with respect to the command-line options: they “annotate” the ASP code in a Java-like fashion, while embedded in comments: hence, the resulting programs can still be given as input to other ASP systems that do not support them, without any modification. In particular, our annotations can have two different scopes: at the global level, meaning that they are applied to the whole program, or at the rule level, and hence annotations acts just on the rule they precede.

Syntactically, all annotations start with the prefix “% @” and end with a dot (“.”). The current ℐ-DLV release supports annotations for customizing two of the major aspects of the grounding process: body ordering and indexing; additional options are being developed.

A specific body ordering strategy can be explicitly requested for any rule, simply preceding it with the line:

where Ordering_Type is a number representing an ordering strategy (Section 3.3.1). In addition, it is possible to specify a particular partial order among atoms, no matter the employed ordering strategy, by means of before and after directives. For instance, in the next example, ℐ-DLV is forced to always put literals a (X, Y) and X = # count {Z : c (Z)}} before literal f (X, Y), whatever the order chosen:

As for indexing, directives on a per-atom basis can be given; the next annotation, for instance, requests that, in the subsequent rule, atom a (X, Y, Z) is indexed, if possible, with a double-index on the first and third arguments:

Multiple preferences can be expressed via different annotations; in case of conflicts, priority is given to the first appearing in the program. In addition, preferences can also be specified at a global scope, by replacing the rule directive with the global one. Such kind of annotations are applied on the rules, if possible. While a rule annotation must precede the intended rule, global annotations can appear at any line in the input program. Both global and rule annotations can be expressed in the same program; in case of overlap on a particular rule/setting, priority is given to the more specific rule ones.

Intuitively, the way annotations change the grounding mechanisms can noticeably affect performance on the program at hand; in order to give an idea, we illustrate next a few interesting cases related to problems featured in the 6th ASP Competition benchmark suite (see Section 4), where performance is significantly affected by the body orderings. It is worth noting that the heuristic-based nature of the default ordering criterion (see Section 3.2.2) does not guarantee optimality, and thus it is possible that the introduction of further policies, directly indicated by the user or inferred from other criteria, lead to a better-performing ordering. Indeed, in the following examples the standard strategy turns out as not the best one: customization via annotations allows the grounder to improve efficiency. As first example let us consider the rule:

which is taken from the encoding of Labyrinth. In this case, by annotating the rule with:

that corresponds to ask ℐ-DLV to select as first literals inverse (D, E) in its ordering strategy no matter how the other literals are positioned, average grounding time over all instances is reduced up to 90%. Similarly, by annotating the following rule in the Visit-all encoding:

 step (T) ,  atrobot (O, T) ,  O ! = N .

that requires the use of criterion ord₅ instead of the default one on this specific rule, the average grounding time computed over all instances reduces by 15%; the same improvement is obtained with the ordering criterion ord₆. Having a closer look at what changes, we can observe that while the default algorithm orders the rule body as already reported, the mentioned criteria orders the body as follows:

Let us give some insights about the reasons of the performance improvements. In the case of Labyrinth instances, intuitively, since the extension of the predicate inverse is very small, it is better to add it as soon as possible, possibly at first. As for Visit-all, both criteria ord₅ and ord₆ try to prefer literals binding output variables (i.e., variables appearing in head or in body literals with unsolved predicates) in order to facilitate the backjumping mechanism. In that rule, the output variables are N, T and O, and thus the literal atrobot (O, T) is inserted as soon as possible (in fact, it is the one containing the largest number of output variables).

It is worth noting that, in all reported cases, acting at a global scope, as one could do via command-line options, does not bring the same improvements: indeed, experiments showed that the gain due to the change of strategy over the reported rules is overshadowed by corresponding losses over the rest of the program; the flexible customization means featured by ℐ-DLV, that allows to configure and fine-tune the grounder as needed, even at a rule level, are exactly aimed at better dealing with such scenarios.