This is a short abstract based on the recently published VLDB 2018 paper [6] - the main technical paper describing the Vadalog system. It describes the central motivations and gives useful pointers on the architecture and the main algorithms.
Introduction and motivation. The importance of capitalizing and exploiting corporate knowledge has been clear to decision makers since the late 1970s, when this idea was gradually made concrete in the context of expert systems, software frameworks able to harness such knowledge and provide answers to structured business questions. Through deductive database systems – database systems that have advanced reasoning capabilities – and in particular the language Datalog, the area became of high interest to the database community in the 1980s and 1990s. Nevertheless, even though the importance of harnessing knowledge certainly has grown steadily since then, culminating in today’s desire of companies to exploit knowledge graphs, the interest in deductive databases has faltered due to immature technology and overly complicated KRR formalisms.
Yet, we are currently assisting to a resurgence of Datalog in academia and industry
[
In this context, it has been recognized that to handle the complex knowledge-based scenarios encountered today, such as reasoning over large knowledge graphs, Datalog has to be extended with features such as existential quantification. Yet, Datalogbased reasoning in the presence of existential quantification is in general undecidable. Many e orts have been made to define decidable fragments. Warded Datalog is a very promising one, as it captures PTIME complexity while allowing ontological reasoning. Yet, so far, no implementation of Warded Datalog was available.
We recently introduced the Vadalog system, a Datalog-based system for performing
complex logic reasoning tasks, such as those required in advanced knowledge graphs;
it is Oxford’s contribution to the VADA research programme [
Reasoning over knowledge graphs. The term knowledge graph (KG) has no standard
definition. It can be seen as referring only to Google’s Knowledge Graph, to triple-based
models, or to multi-attributed graphs, which represent n-ary relations [
Example 1. An example of a simple knowledge graph reasoning setting is given in [
Spouse(x; y; start; loc; end) ! Spouse(y; x; start; loc; end) This rule expresses that when a person x is married to a person y at a particular location, starting date and end date, then the same holds for y and x. That is, the graph of persons and their marriage relations is symmetric.
As stated in [
Beyond these specific requirements, the competition between powerful recursion,
powerful existential quantification and low complexity has spawned fruitful research
throughout the community to address the mentioned Datalog undecidability in the presence of
existential quantification. This has been done under a number of di erent names, but
which we shall here call Datalog , the “+” referring to the additional features (including
existential quantification), the “-” to restrictions that have to be made to obtain
decidability. Many languages within the Datalog family of languages have been proposed
and intensively investigated [
Figure 1 gives an overview of the main Datalog languages. In fact, most of these
candidates, including Linear Datalog , Guarded Datalog , Sticky Datalog and Weakly
Sticky Datalog do not fulfil (1). Datalog itself does not fulfil (2). Warded and Weakly
Frontier Guarded Datalog satisfy (1) and (2), thus are expressive enough. However,
the expressiveness of Weakly Frontier Guarded Datalog comes at the price of it being
EXPTIME-complete [
Before summarising the characteristics of the Vadalog system, let us propose an
example of a Datalog program, which we consider representative of the complexity of
a typical reasoning setting involving KGs. The example is at the same time close to a
classical scenario [
Control(x; x):
Own(x; y; w); w > 0:5 ! Control(x; y)
Control(x; y); Own(y; z; w); v = msum(w; hyi); v > 0:5 ! Control(x; z):
Here, for fixed x, the aggregate construct msum(w; hyi) forms the sum over all values w
such that for some company y, Control(x; y) is true, and Own(y; z; w) holds, i.e.,
company y directly owns fraction w of company z. Now, with the described knowledge
graph, many questions can be asked, such as: (i) obtain all the pairs (x; y) such that
company x controls company y; (ii) which companies are controlled by x? Which
companies control x? (iii) does company x control company y?
The Vadalog system. The Vadalog system is built around the Vadalog language, with
Warded Datalog as its logical core. It is currently used as the core deductive database
system of the overall Vadalog Knowledge Graph Management System described in [
While the na¨ıve solution would imply a full caching of all the generated facts, the challenge here is guaranteeing limited memory footprint. We identify a number of guide data structures that closely exploit the underpinnings of Warded Datalog and allow to abstract large KG areas by means of single representative facts (or patterns thereof). More in particular, we propose structures that play a complementary role for exploiting the periodicity of the KG: warded forest, which actually allows vertical pruning of isomorphic trees based on root isomorphism, and (lifted) linear forest, which allows horizontal pruning of entire pattern-isomorphic trees. – A system and architecture that implements this algorithm in a relational databaseinspired operator pipeline architecture. The pipeline’s operators rely on termination strategy wrappers which transparently prevent the generation of facts that may lead to non-termination while ensuring the correctness of the result. The system is completed by a wide range of standard and novel optimisation techniques such as the dynamic construction of in-memory indices, stream-optimized “slot machine” joins, monotonic aggregation, materialization points, etc. – The technical paper also presents a full-scale experimental evaluation of the Vadalog system on a variety of real-world and synthetic scenarios that thoroughly validate the e ectiveness of our techniques on Warded Datalog in absolute terms and comparatively with the top existing systems, which are outperformed by our reasoner. Acknowledgements. This work is supported by the EPSRC programme grant VADA EP/M025268/1, the Vienna Science and Technology Fund (WWTF) grant VRG18-013, and the EU Horizon 2020 grant 809965.