LogicBlox is a database product designed for enterprise software development, combining transactions and analytics. The underying data model is a relational database, and the query language, LogiQL, is an extension of Datalog [13]. As such, LogiQL features a simple and unified syntax for traditional relational manipulation as well as deeper analytics. Moreover, its declarative nature allows for substantial static analysis for optimizing evaluation schemes, parallelization, and incremental maintenance, and it allows for sophisticated transactional management [11]. In this paper, we describe various extensions of Datalog for supporting prescriptive and predictive analytics. These extensions come in the form of mathematical optimization (mixed integer programming), machine-learning capabilities, statistical relational models, and probabilistic programming. Some of these extensions are currently implemented in LogicQL, while others are in either development or planning phases. In this section we briefly (and informally) describe LogiQL. (See [13] for a full description of the language.) The core components of LogiQL are its rules and constraints, which are stated over the predicates of the database schema. A (basic) derivation rule is a standard Datalog rule that defines how new facts are derived in the database. For example, the following rules define Anc as the transitive closure of the predicate Par.
Par(x; y)
Anc(x; z); Par(z; y) An integrity constraint does not derive new facts, but rather fires an error when violated. For example, the rule Anc(x; y) ! x 6= y states that ancestorship is antireflexive, and the rule
Par(x; y); Par(x; z) ! y = z states that every object has at most one parent, that is, in Par the first element is a key. For interpretability sake, brackets are used to implicitly express key constraints, as in Par[x] = y. Derivation rules and constraints syntactically differ in the direction of the implication arrow. The logical language for specifying the right-hand-side of ? Taub Fellow – supported by the Taub Foundation rules, as well as both sides of constraints, allows arbitrary propositional formulas with numerical operations and comparisons (while safety conditions, such as stratification, may be imposed to bound complexity).
Predicate-to-Predicate (P2P) rules are used for deriving whole relations over tuples. An example of such a rule is the aggregate P2P rule, such as the following one that sums up the salaries for each employee.
Annual[e] = a agg a = sum(s)
Salary(e; 2014; s) Such a rule always includes a component of the form func arg , where func is the type of the predicate rule, and arg is an additional argument that gives specific arguments for the rule. In the above rule, e is a grouping variable (as it occurs in the head). This rule derives a fact Annual(e; a) for every e in the first attribute of Salary. 3
We now describe several extensions of the LogicBlox system, for supporting prescriptive and predictive analytics. 3.1
MIP is often applied for effectively solving real-world optimization problems that
naturally arise in prescriptive analytics, such as network flow optimization, resource
allocation, and scheduling. Solutions for various classes of mathematical programming
problems can be obtained by deploying specialized, highly optimized solvers (e.g., [
Maximize (X dis i;s
mis) pi subject to: 8i; s wis + qis + mis dis ; qis
B s ;
X qis0 s0 ai ; X
s0 s0
N 8i; s mis 0 ; qis 0 ; s 2 f0; 1g In this program, we assume that a store can hold at most 1000 units of each product. Observe that the unknown variables are the qis, mis and s (while the others are fixed).
MIP declaration in LogiQL is done by means of predicates with free second-order variables, which are essentially unknown functions over predefined domains, except that they are eventually assigned actual values (by invoking a MIP solver). Moreover, the objective function (that one wishes to minimize or maximize) is simply an attribute of a relation. Linear constraints are phrased as LogiQL constraints. Hence, a LogiQL program with MIP is an ordinary program, with the addition that attributes are marked as second-order variables or objectives. As an example, the following program corresponds to the above MIP specification. Here, the second-order variables are m[i; s], q[i; s] and psi[s], and the objective is Obj(v).
Obj(v) v = sum(z) z = (d[i; s]
m[i; s]) p[i] agg agg Store(s); Prod(i) ! w[i; s] + q[i; s] + m[i; s] d[i; s] TotalTrans[i] = v
TotalTrans[i] = v ! v q[i; s] = v1; psi[s] = v2 ! v1 v = sum(z)
q[i; s] = z a[i] v2
1000
agg v = sum(z) psi[s] = z TotalTrucks(v) ! v m[i; s] = v ! v
Observe that the constraints are used in a fashion similar to the stable-model (or
answer-set) semantics [8], except that we also optimize an objective. Other similar
approaches include [
The engine automatically synthesizes the necessary mathematical programming
instances from the program, and invokes a MIP solver (e.g., [
The next extension is predictive analytics by means of a built-in set of ML algorithms. We use the special predict P2P rule that comes in two modes: learning mode (where a model is being learned) and evaluation mode (where a model is being applied to make predictions). We do not give here the formal syntax and semantics for these rules; rather, we give an illustrative example.
Suppose that we wish to predict the monthly sales of products in branches. We have the following predicates: – Hstr[sku; branch; month]=amount contains historical sales per sku (“stock keeping unit”) and branch; – Ftr[sku; branch; name]=value associates with every sku, branch and feature name a corresponding feature value.
The following learning rule learns a logistic-regression model for each sku and branch, and stores the resulting model object (which is handle to a representation of the model) in the predicate SM[sales; branch] = model.
SM[s; b] = m predict m = logist(vjf )
Hstr[s; b; t] = v; Ftr[s; b; t; n] = f And the following evaluation rule evaluates the model to get specific predictions.
Sales[s; b; t] = v
predict v = eval(mjf )
Unknown(s; b; t); SM[s; b] = m; Ftr[s; b; t; n] = f 3.3
Such models are specified by various mechanisms, including Markov Logic Networks
(MLN) [
R(x)
R(y) ; Friends(x; y) where R describes a person property (e.g., “smokes” or “votes”). This rule states that whenever x and y are friends, the property R propagates from y to x; this rule should be taken as a hint on the unknown, and not as rigid truth. While an ordinary Datalog program specifies a unique extension of the database, soft rules specify a probability space over such extensions. Intuitively, the probability of a possible extension is determined by the extent to which the rules are satisfied (where weights of rules are taken into account). A common practice is to find the most likely extension (i.e. Maximum APriori, or MAP, inference), such as the most likely votes given partial knowledge about votes, and use that world as an ordinary database. We make an ongoing effort to support MLN and PSL within LogicBlox. Our current implementation applies MAP inference by translation into MIP. In future work we plan to include specialized algorithms to reduce the execution cost. 3.4
Formalisms for specifying general statistical models, such as probabilistic-programming
languages [9], typically consist of two components: a specification of a stochastic
process (the prior), and a specification of observations that restrict the probability space
to a conditional subspace (the posterior). We plan to enhance LogiQL with capabilities
of probabilistic programming, in order to facilitate the design and engineering of ML
solutions. Towards that, we have initiated a theoretical exploration of such an extension.
In a recent paper [
associates with the client a random number of visits in the branch, where that number is drawn from the Poisson distribution with average (parameter) #visits.
The semantics of a program is a probability distribution over the possible outcomes
of the input database with respect to the program; these possible outcomes are minimal
solutions with respect to a related program that involves existentially quantified
variables in conclusions. Observations are naturally incorporated by means of constraints.
We focused on discrete numerical distributions (such as Poisson), but even then the
space of possible outcomes may be uncountable (as a solution can be infinite). We
defined a probability measure over possible outcomes by applying the known concept of
cylinder sets [
We described four approaches taken by LogicBlox to extend LogiQL with built-in analytics. While MIP and ML aggregates are conceptually syntactic bridges between Datalog and external solvers, statistical relational models, and PPDL feature stronger ties to Datalog (and naturally require more in-house implementation effort). In future work we plan to investigate the applicability of our statistical specifications to real-life problems that arise in our business, as well as their theoretical and system aspects. 8. M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Logic Programming, Proceedings of the Fifth International Conference and Symposium, Seattle, Washington, August 15-19, 1988 (2 Volumes), pages 1070–1080. MIT Press, 1988. 9. N. D. Goodman. The principles and practice of probabilistic programming. In POPL, 2013. 10. S. Greco, C. Molinaro, I. Trubitsyna, and E. Zumpano. NP datalog: A logic language for expressing search and optimization problems. TPLP, 10(2):125–166, 2010. 11. T. J. Green, M. Aref, and G. Karvounarakis. LogicBlox, platform and language: A tutorial.
In Int Conf on Datalog in Academia and Industry, 2012. 12. I. Gurobi Optimization. Gurobi optimizer reference manual, 2015. 13. T. Halpin and S. Rugaber. LogiQL: A Query Language for Smart Databases. CRC Press, 2014. 14. A. Meliou and D. Suciu. Tiresias: The database oracle for how-to queries. In SIGMOD, pages 337–348, 2012. 15. F. Niu, C. Re´, A. Doan, and J. W. Shavlik. Tuffy: Scaling up statistical inference in markov logic networks using an rdbms. PVLDB, 4(6):373–384, 2011. 16. T. E. Sheard. Painless programming combining reduction and search: Design principles for embedding decision procedures in high-level languages. In ICFP, pages 89–102, 2012.