Many modern companies wish to maintain knowledge in the form of an enterprise knowledge graph [21] and to use and manage this knowledge via knowledge graph management systems (KGMS). We view a KGMS as a knowledge base management system (KBMS), which performs complex rule-based reasoning tasks over very large amounts of data and, in addition, provides methods and tools for data analytics and machine learning, whence the equation:
KGMS =
ous requirements for a fully- edged
KGMS. Such a system must be
capable of performing complex reasoning
tasks, guaranteeing, at the same time,
e ciency and scalability over Big
Data with an acceptable
computational complexity. Moreover, a KGMS
needs interfaces to many
heterogeneous data sources, including:
corporate RDBMS, NoSQL stores, the web,
machine-learning and analytics
packages. We present knowledge
representation and reasoning formalisms and a
system achieving these goals. To this
aim, we adopt speci c suitable frag- Fig. 1. KGMS Reference Architecture.
ments from the Datalog family of languages [
This paper is a short version of a fully detailed paper published in [
We now proceed to brie y summarize what we think are the most important desiderata for a fully- edged KGMS. We will list these requirements according to two categories, keeping in mind, however, that these categories are interrelated.
There should be a logical formalism for expressing facts and rules, and a reasoning engine that uses this language, which should provide the following features. Simple and Modular Syntax: It should be easy to add and delete facts and to add new rules. As in logic programming, facts should conceptually coincide with database tuples.
High Expressive Power: Datalog [
Probabilistic Reasoning: The language should be suited for incorporating appropriate methods of probabilistic reasoning, and the system should propagate probabilities or certainty values along the reasoning process.
Ontological Reasoning and Query Answering: First, ontological reasoning to
the extent of tractable description logics such as DL-LiteR should be possible.
Second, it should be expressive enough to cover all SPARQL queries over RDF
datasets under the entailment regime for OWL 2 QL [
Low Complexity: Reasoning should be tractable in data complexity Whenever possible, the system should recognize and take pro t of rule sets that can be processed within low space complexity classes such as nlogspace (e.g. for SPARQL) or even ac0 (e.g., for traditional conjunctive database queries).
Rule Repository, Rule Management, and Ontology Editor: A library for storing
recurring rules and de nitions should be provided, as well as a user interface for
rule management in the spirit of the ontology editor protege [
Big Data Access: The system must be able to provide e cient access to Big Data
sources and systems and fast reasoning algorithms over Big Data (see e.g. [
Data Cleaning, Exchange and Integration: Integrating, exchanging and cleaning data should be supported directly and via integration of third-party software. Web Data Extraction, Interaction, and IoT: A KGMS should be able to interact with the web by (i) extracting relevant web data and integrating these data into the local fact base, and (ii) exchanging data with web forms and servers that are available through a web interface.
Procedural Code and Machine Learning: A KGMS should have encapsulation methods for embedding procedural code and o er a logical interface to it. The system should be equipped with direct access to existing software packages for machine learning, text mining, data analytics, and data visualization. 3
The VADALOG Language
vadalog is a Datalog-based language that matches the requirements presented
in Section 2. It belongs to the Datalog family of languages that extend Datalog
by existential quanti ers in rule heads, as well as by other features, and restricts
at the same time its syntax in order to achieve decidability and data
tractability; see, e.g., [
R(x; y) ! P (y); the variable y in the body of the second rule is \dangerous" (w.r.t. ) since starting, e.g., from the database D = fP (a)g, the chase will apply the rst rule and generate R(a; ), where is a null that acts as a witness for the existentially quanti ed variable z, and then the second rule will be applied with the variable y being uni ed with that is propagated to the obtained atom P ( ).
The goal of wardedness is to tame the way null values are propagated during the construction of the chase instance by posing the following conditions: 1. all the \dangerous" variables should coexist in a single body-atom , called the ward; 2. the ward can share only \harmless" variables with the rest of the body, i.e., variables that are uni ed only with database constants during the construction of the chase.
Warded Datalog consists of all the ( nite) sets of warded existential rules.
As an example of a warded set of rules, the following rules encode part of the
OWL 2 direct semantics entailment regime for OWL 2 QL (see [
Type(x; y); SubClass(y; z) ! Type(x; z)
Triple(x; y; z); Inverse(y; w) ! Triple(z; w; x)
Triple(x; y; z); Restriction(w; y) ! Type(x; w): It is easy to verify that the above set is warded, where the underlined atoms are the wards. Indeed, a variable that occurs in an atom of the form Restriction( ; ), or SubClass( ; ), or Inverse( ; ), is trivially harmless. However, variables that appear in the rst position of Type, or in the rst/third position of Triple can be dangerous. Thus, the underlined atoms are indeed acting as the wards.
The functional architecture of the vadalog system, our KGMS, is depicted in Figure 1. The knowledge graph is organized as a repository, a collection of vadalog rules. The external sources are supported by means of transducers, intelligent adapters that integrate the sources into the reasoning process.
The vadalog system ful ls the requirements presented in Section 2. The
Big Data characteristics of the sources and the complex functional requirements
of reasoning are tackled by leveraging the underpinnings of the core language,
which are turned into practical execution strategies. In particular, in the
reasoning algorithms devised for Warded Datalog , after a certain number of chase
steps (which, in general, depends on the input database), the chase graph [
At compile time, thanks to wardedness, which limits the interaction between the labeled nulls, the engine rewrites the program in such a way that joins on speci c values of labeled nulls will never occur. At runtime, we do an eager optimal pruning of redundant chase branches: we exploit fact provenance to preempt the application of rules which will generate redundant facts. Due to wardedness, the provenance information needed is bounded.
The vadalog system uses a pull stream-based approach (or pipeline approach), where the facts are actively requested from the output nodes to their predecessors and so on down to the input nodes, which eventually fetch the facts from the data sources. The stream approach is essential to limit the memory consumption or, at least make it predictable, so that the system is e ective for large volumes of data. Our setting is made more challenging by the presence of multiple interacting rules in a single rule set and the wide presence of recursion. We address this by means of a specialized bu er management technique. We adopt pervasive local caches in the form of wrappers to the nodes of the access plan, where the facts produced by each node are stored. The local caches work particularly well in combination with the pull stream-based approach, since facts requested by a node successor can be immediately reused by all the other successors, without triggering further backward requests. Also, this combination realizes an extreme form of multi-query optimization, where each rule exploits the facts produced by the others, whenever applicable. To limit memory occupation, the local caches are ushed with an eager eviction strategy that detects when a fact has been consumed by all the possible requestors and thus drops it from the memory. Cases of actual cache over ow are managed by resorting to standard disk swap heuristics (e.g. LRU, LFU, etc.) 5
The vadalog system is already in use for a number of industrial applications. We believe that the vadalog system is a well-suited platform for knowledge graph applications that integrate machine learning (ML) and data analytics with logical reasoning. We are currently implementing applications of this type and will report about them soon.
Acknowledgments This work has been supported by the EPSRC Programme Grant EP/M025268/1 (http://vada.org.uk/). The VADALOG system as presented here is the intellectual property of the University of Oxford.