Answer Set Programming (ASP), that extends Datalog with powerful knowledge modeling constructs, is suitable for modeling both database-oriented applications and more complex combinatorial optimization tasks arising in decision-making. However, ASP systems were not conceived having the challenges of Big Data in mind; thus they are not applicable tout court in this new setting. This paper moves the rst steps towards enabling the speci cation of reasoning tasks on Big Data with ASP. In particular we present our ongoing work in the direction of extending the well-known DLV system to interact in a plausible way with Big Data repositories.
Modern information systems are facing an unprecedented phenomenon: the
massive production and storage of enormous amounts of data (Big Data). The need
for processing Big Data repositories has recently implied a technological switch
including the development of new hardware and software architectures [
The area of computing dedicated to representing and solving complex tasks
using information is called knowledge representation and reasoning (KRR) [
Recently less expressive logic languages, like Datalog [
This paper moves the rst steps towards enabling the speci cation of
reasoning tasks on Big Data with ASP. In particular we present our ongoing work in
the direction of extending the well-known DLV system [
In this Section, we brie y recall syntax of the ASP language. For ASP semantics
we refer the reader to [
A term is either a simple term or a functional term. A simple term is either
a constant or a variable. If t1 : : : tn are terms and f is a function symbol of
arity n, then f (t1; : : : ; tn) is a functional term. If t1; : : : ; tk are terms and p is
a predicate symbol of arity k, then p(t1; : : : ; tk) is an atom. A literal l is of the
form a or not a, where a is an atom; in the former case l is positive, otherwise
negative. A rule r is of the form 1j j k :{ 1; : : : ; n; not n+1; : : : ; not m:
where m 0, k 0; 1; : : : ; k and 1; : : : ; m are atoms. We de ne H(r) =
f 1; : : : ; kg (the head of r) and B(r) = B+(r) [ B (r) (the body of r), where
B+(r) = f 1; : : : ; ng (the positive body) and B (r) = fnot n+1; : : : ; not mg
(the negative body). If H(r) = ; then r is a (strong) constraint; if B(r) = ; and
jH(r)j = 1 then r is a fact. A rule r is safe if each variable of r has an occurrence
in B+(r). An ASP program is a nite set P of safe rules. A program (a rule,
a literal) is said to be ground if it contains no variables. A predicate is de ned
We remark that this de nition of safety is speci c for rules featuring only classical
literals. For a complete de nition we refer the reader to [
dlv2 [
External Computation in DLV2 As anticipated above, the new dlv2 system, via its grounder I-DLV, supports a special form for atoms, namely external atoms, geared towards external computations, whose extension is speci ed by means of external de ned Python functions.
Formally, an external atom is of the form &p(t0; : : : ; tn; u0; : : : ; um), where n + m 0, &p is an external predicate, t0; : : : ; tn are intended as input terms, and are separated from the output terms u0; : : : ; um by a semicolon (\;"). In the following, we denote an external atom by &p(In; Out), where In and Out represent input and output terms, respectively.
An external literal is either not e or e, where e is an external atom, and the
symbol not represents default negation. An external literal is safe if all input
terms are safe, according to the safety de nition in ASP-Core-2 standard [
Given an external atom &p(In; Out) and a substitution , a ground instance of such external atom is obtained by applying to variables appearing in In and Out, obtaining (&p(In; Out)) = &p(Ing; Outg). The truth value of a ground external atom is given by the value f&p(Ing; Outg) of a decidable n + m-ary two-valued oracle function, where n and m are the lengths of Ing and Outg, respectively. A negative ground external literal not e is true/false if e is false/true.
Intuitively, output terms are computed on the basis of the input ones, according to a semantics which is provided externally (i.e., from the outside of the logic program) by means of the de nition of oracle functions written in Python. Basically, for each external predicate &p featuring n/m input/output terms, the user must de ne a Python function whose name is p, and having n/m input/output parameters. The function has to be compliant with Python version 3. Example 1. As a simple example, let us consider the following rule, that makes use of an external predicate with two input and one output terms: append(X,Y,Z) :{ string(X), string(Y), &append strings(X,Y;Z).
A program containing this rule must come along with the proper de nition of append strings within a Python function, as, for instance, the following: def append strings(X,Y): return str(X)+str(Y) According to the given de nition, as they are completely evaluated by I-DLV as true or false, external predicates do not appear in the produced instantiation.
External atoms can be both functional and relational, i.e., they can return a single tuple or a set of tuples, as output. In Example 1, &append strings is functional : the associated Python function returns a single value for each combination of the input values. In general, a functional external atom with m > 0 output terms must return a Python sequence containing m values. If m = 1, the output can be either as sequence containing a single value, or just a value, as in the example; if m = 0, the associated Python function must be boolean. A relational external atom with m > 0 is de ned by a Python function that returns a sequence of m-sequences, where each inner sequence is composed by m values.
Example 2. The following rule uses a relational external atom:
prime factor(X,Z) :{ number(X), &compute prime factors(X;Z).
Intuitively, given a number X, the rule computes prime factors of X, demanding this task to a relational external atom, that receives as input the number X, and returns as output its factors. The semantics has to be provided via a Python function called compute prime f actors returning a sequence of numbers each one representing a di erent factor of X. 4
In this section we describe the main idea underlying our approach for integrating ASP computation, and in particular the dlv2 system, with Big Data sources. We rst introduce a motivating example that will be used through the rest of the paper for illustrating the idea underlying our approach. Then, we provide some details about the usage of external atoms for our purposes. 4.1
The following example showing a possible use case can be useful to grasp the intuition behind our approach.
https://docs.python.org/3
Let us consider the following scenario: Giovanni wants to go out for dinner and wants to invite a given number of people, possibly inviting friends of friends, in order to spend some funny and pleasant time. Invited people should be selected from a social network, choosing among the Giovanni's friendship net. In such social network subscribed people can add friends and mark some of these as close friends; moreover, the social network performs some stats on the degree of dislike among two people in the network. The following ASP program can be used to explore the friendship relations of such social network and then to provide Giovanni with suitable suggestions on people that could be invited.
nf riends(10): averageAge(25): r1 possible f riend(Y ) :{ close f riend(giovanni; Y ): r2 possible f riend(X) :{ possible f riend(Y ); close f riend(Y; X): r3 suggested f riend(Y; A) :{ possible f riend(Y ); person(Y; A); A > 18: r4 invite(X) j -invite(X) :{ suggested f riend(X): r5 :{ #countfX : invite(X)g! = N; nf riends(N ): r6 :{ #sumfA; X : suggested f riend(X; A; ); invite(X)g < AV G N; nf riends(N ); averageAge(AV G): r7 : invite(X); suggested f riend(X; ); dislike(giovanni; X; D): [D@1; X] The former two rules compute the transitive closure of the friendship relation of Giovanni, restricting the computation to close friends only; rule r3 suggests a person Y if he is a possible friend and is older than 18; rule r4 guesses if a suggested friend should be invited or not; rule r5 ensures that the number of invited friends is exactly the desired one; r6 imposes that the average age of the invited friends is not smaller than a given value; eventually, rule r7 prefers solutions in which the total degree of dislike among Giovanni and invited people is minimized.
Intuitively, computing the transitive closure of the friendship relation in a social network could be very expensive when performed on a huge database. Thus, traditional main memory ASP systems cannot handle it; indeed, also the simple import of the friend relation is not feasible in practice. So, the idea is to delegate this heavy part of the computation to an external Big Data source. The remaining part that takes as input a heavily reduced part of the friendship, instead, can be conveniently expressed in a purely declarative way by means of ASP rules as reported above. We remark that from a computational perspective, this latter part encodes a NP-hard task that cannot be expressed by means of canonical RDB query languages such as SQL, Datalog, etc. 4.2
In order to delegate the computation of data-intensive rules to Big Data tailored software, one can make use in the ASP program of a new external atom. Roughly, the external atom connects to a DB, may export some input facts to the DB, converts some given rules to queries, executes them on the DB and returns as output the extension of a speci c predicate. In order to enable the external evaluation on a DB db, the ASP program should contain a rule r having in the body an external atom called &bigasp, that receives as input:
db the name of the ODBC DSN (Data Source Name); user the name of the user who connects to the DB; password the password of that user; rules a string containing some Datalog rules that de ne the operations that will be performed on the DB; output a string representing the name of the relation to be imported in the ASP program; input [optional] a string containing a set of ASP facts that have to be exported to the DB.
During the evaluation, dlv2 invokes the external atom, imports the results of the evaluation and lls in the extension of the predicate output that has to appear as head in the rule r. Note that, this approach could be adopted to retrieve data from diverse Big Data sources.
Let us consider again our running example. We can delegate the computation of the transitive closure of the friendship relation to an external Big Data platform by replacing the rst three rules in the program above with the following one: suggested f riend(Y; A) :{ &bigasp(\my db"; \my user"; \my pass"; \ possible f riend(Y ) :{ close f riend(giovanni; Y ): possible f riend(X) :{ possible f riend(Y ); close f riend(Y; X): suggested f riend(Y; A) :{ possible f riend(Y ); person(Y; A); A > 18:"; \suggested f riend"; Y; A):
Apart from connection parameters and the name of the output relation, the external atom takes as input the extracted rules; it invokes the machinery for enabling their evaluation on the external my db and returns the results as a sequence of tuples representing the suggested friends with their age. Such tuples populate the extension of the suggested f riend relation so that the traditional ASP evaluation can continue. 5
We now describe an architecture where we indicate the software components that can be used to realize our idea. The general architecture of a framework for Big Data Analytics with ASP is composed by 3 macro-components as illustrated in Figure 1. In particular, the data layer of the system could rely on Hive, a data warehouse software project built on top of Hadoop for providing data summarization, query and analysis.
The choice of this tool is due to the fact that Hive is the mainstream for
OLAP analysis over Big Data. Hive brings three main advantages: (i) it exploits
http://hive.apache.org/
the computational power of Hadoop clusters, (ii) it implements a standard
relational model, that is equivalent to the data model supported by ASP, and
(iii) it supports a querying language called H-QL, which is very close to the
standard SQL. On top of Hive we nd BigDLV, the core of our framework for
Big Data Analytics. BigDLV should allow for reasoning in ASP over data stored
and pre-processed within Hive. In particular, BigDLV should be able to extract
extensions of input predicates from the underlying Big Data repository and,
moreover, delegate parts of the computation to Hive. Figure 1 shows the
internal architecture of BigDLV and focuses possible interactions with the underlying
layers. This component encapsulates the dlv2 system which allows to de ne
external atoms as discussed in Section 3: when an input program embeds a Datalog
rule to be evaluated against the Hive repository, DLV2, by means of an external
atom, invokes a Python component, called DataSQL, managing the interaction
between DLV2 and Hive. DataSQL is in turn composed by two sub-modules,
the Compiler and the Executor. The former compiles the rules received from
DLV2 into an SQL query, while the latter runs the compiled query over Hive
and retrieves the result. Results from Hive are rst ltered out by the Executor
and then returned back to DLV2. An end-user could ask the framework to store
the nal output of the whole evaluation process into the cluster. Note that,
the Compiler module interacts directly with Hive in order to get information
about table schemata matching the rule predicates. The implementation of the
Compiler can follow the lines of [
In this paper we described our idea for interfacing dlv2 with Big Data. Currently,
we are implementing all the components mentioned in Section 4 and 5. Moreover
we are developing a case of study that combines a Datalog sub-program modeling
a heavy data-mining task (demanded to a Big Data platforms), with another
component that models a computationally hard decision-making task (demanded
to the ASP system). The case of study is part of the research project S2BDW we
are currently involved in and that focuses on a prognostic problem for foreseeing
possible breaks on trains by analyzing data coming from sensors. Currently, we
are focusing on applications in which the computation demanded to the external
sources involves Big Data but returns an output which can be pro tably handled
in main memory. As a future work, we plan to better analyze the theoretical
boundaries and limitations of our approach, in order to determine which kind of
reasoning can be outsourced (e.g., going along the lines of [
Acknowledgments. Work partially supported by MISE under project \Smarter Solutions in the Big Data World (S2BDW)" (n. F/050389/01-02-03/X32).