User:Aandre156/sandbox

Aandre156/sandbox

Paradigm	Logic, Declarative
Family	Datalog
Designed by	Oxford University
Major implementations
into JupyterLab

The Vadalog system is a state-of-the-art Knowledge Graph Management System (KGMS) that offers a language for performing complex logic reasoning tasks over data stored in knowledge graphs and that, at the same time, it delivers a platform to support the entire spectrum of data science tasks: data integration, pre-processing, statistical analysis, machine learning, algorithmic modeling and probabilistic reasoning. Its language is based on an extension of the rule-based language Datalog, Warded Datalog ±, a high-performance Datalog system using an aggressive termination control strategy. The system is implemented and integrated in JupyterLab, which is therefore at the hearth of the Vadalog system. Through this integration, Vadalog can support the entire spectrum of data science activities and tools. The system can make use of relational databases, such as Postgres and MySQL, graph databases, such as neo4j, machine learning tools (e.g., Weka and scikit-learn), and a web data extraction tool, OXPath. Additional Python libraries and extensions can also be easily integrated into the system.

Vadalog is the result of the VADA research programme, a joint effort of the universities of Oxford, Manchester and Edinburgh and around 20 industrial partners.

Knowledge Graph Management Systems (KGMS)

A knowledge graph management system (KGMS) has the purpose to manage and handle knowledge graphs, which incorporate large amounts of data in the form of facts and relationships. It can be seen as the sum of three components:

$KGMS=KBMS+BigData+Analytics$

where:

1. KBMS is a knowledge base management system
2. Big Data, which is the need of handling large amounts of data, especially when considering that knowledge graphs have been thought as a solution for integrating multiple data sources, both corporate and public knowledge, which results in a very large knowledge graph.
3. (Data) Analytics is the need to provide access to existing software packages for machine learning, text mining, data analytics, and data visualization and to combine them together in the same platform

On a more technical basis, the main requirements that can be identified for defining a KGMS are:

• Define a language and a formalism with high expressive power, in terms of the kind of rules it is possible to define.
• Cost-effective data wrangling, in all its steps, from data cleaning to web data extraction and big data access from many different sources
• Efficient logical, probabilistic and ontological reasoning
• Low complexity, both in terms of space complexity and syntax
• Need of interfaces to access many heterogeneous data sources, such as corporate RDBMS, NoSQL or RDF stores, the web, machine-learning and analytics packages.

Other requirements reflect standard DBMS functions and services, as proposed by Codd.

Vadalog System

Vadalog offers a platform that fulfills the requirements of a KGMS. It is able to perform rule-based reasoning tasks on top of knowledge graphs and it also supports the data science workflow, such as data visualization and machine learning.

Reasoning task and recursion

Example of a Cyclical Dependency Graph derived from a program P where recursion occurs

A rule is an expression of the form $n:-a_{1},...,a_{n}$ where:

• $a_{1},...,a_{n}$ are the atoms of the body
• $n$ is the atom of the head.

A rule allows to infer new knowledge starting from the variables that are in the body: when all the variables in the body of a rule are successfully assigned, the rule is activated and it results in the derivation of the head predicate: given a database $D$ and a set of rules $\Sigma$, a reasoning task aims at inferring the so-called intensional knowledge, applying the rules $\Sigma$ to the database $D$ (the extensional knowledge).

The most wide-spread form of knowledge that has been adopted over the last decades has been in the form of rules, be it in rule-based systems, ontology-based systems or other forms and it can be typically captured in knowledge graphs. The nature of knowledge graphs also makes the presence of recursion in these rules a particularly important aspect. Recursion means that the same rules might be called multiple times before obtaining the final answer of the reasoning task and it is particularly powerful as it allows an inference based on previously inferred results. This implies that the system must provide a strategy that guarantees termination. More technically, a program is recursive if the dependency graph built with the application of the rules is cyclical. The simplest form of recursion is that in which the head of a rule also appears in the body (self-recursive rules).

The query language

The Vadalog language allows to answer reasoning queries that also include recursion. It is based on Warded Datalog ±, which belongs to the Datalog± family of languages that extends Datalog by existential quantifiers in rule heads and at the same time restricts its syntax in order to achieve decidability and tractability. Existential rules are also known as tuple-generating dependencies (tgds), which are rules where existential quantification is allowed in the head.

An existential rule has the following form:

$\varphi (x)\Rightarrow \exists z\Psi (x,z)$

or, alternatively, in Datalog syntax, it can be written as follows:

p(X,Z) :- r(X).

It should be noted that variables in Vadalog are like variables in first-order logic and that a variable is local to the rule in which it occurs. This means that occurrences of the same variable name in different rules refer to different variables.

Warded Datalog ±

In case of a set of rules $\Sigma$, consisting of the following:

r(X,Y) :- p(X).
p(Z) :- r(X,Z).

the variable Z in the second rule is said to be dangerous, since the first rule will generate a null in the second term of the atom r and this will be injected to the second rule to get the atom p, leading to a propagation of nulls when trying to find an answer to the program. If arbitrary propagation is allowed, reasoning is undecidable and the program will be infinite. Warded Datalog± overcomes this issue asking the requirement that for every rule in a set $\Sigma$, all the variables in the rule bodies must coexist in at least one atom in the head, called a ward. The concept of wardness restricts the way dangerous variable can be used inside a program. Although this is a limit in terms of expressive power, with this requirement and thanks to its architecture and termination algorithms, Warded Datalog± is able to find answers to a program in a finite number of steps. It also exhibits a good trade-off between computational complexity and expressive power, capturing PTIME data complexity while allowing ontological reasoning and the possibility of running programs with recursion.

Vadalog extension

Vadalog replicates in its entirety Warded Datalog± and it extends it with the inclusion in the language of:

• monotonic aggregations (min, max, sum, prod, count operators)
• the support of different data types (strings, integer, double, date, boolean, set, lists, marked nulls)
• rich annotation mechanism to define how to interact with data sources and external libraries

In addiction, the system provides an highly engineered architecture to allow efficient computation. This is done in two ways:

1. adopting an in-memory processing architecture and a pull stream-based approach, which limits the memory consumption or make it predictable.
2. using an aggressive termination control strategy, which detects patterns and redundancy while building of the chase-graph (used to generate the answers) as early as possible and cuts off computation when they occur. This refers to the isomorphism of facts, which means that if a fact h is isomorphic to h', the system will only explore the chase graph of fact h, reducing the number of steps needed.

The Vadalog system is therefore able to perform ontological reasoning tasks, as it belongs to the Datalog family. Reasoning with the logical core of Vadalog captures OWL 2 QL and SPARQL (through the use of existential quantifiers), and graph analytics (through support for recursion and aggregation). The declarative nature of the language makes the code concise, easy-to-read and manageable.

Jupyter Support

The system provides an integration with the JupyterLab platform, where Vadalog programs can be written and run and the output can be read, exploiting the functionalities of the platform. It gives also the possibility to evaluate the correctness of the program, run it and analyse the derivation process of output facts. The integration with data science tools are realized in terms of data bindings primitives and functions.

1. Data binding primitives: bindings allows to connect to external data sources or systems like a database, a framework or a library. This include connection with relational database as Postgres or MySQL, and graph databases, such as neo4j. it is also possible to integrate machine learning libraries (Weka, scikit-learn, Tensorflow) and a web data extraction tool, OXPath, which allows to retrieve data directly from the web. This is possible through the so-called annotations: these are special facts that augment the sets of existential rules with specific behaviors. The @input annotation tells the system that the facts for an atom of the program are imported from an external data source, for example a relational database. The @output annotation specifies that the facts for an atom of the program will be exported to an external target, for example the standard output or a relational database. Other annotations like @bind, @mapping, @qbind allow to customize the data sources for the @input annotation or the targets for the @output annotation.
2. Functions: custom expressions which make use of arithmetic operators, string manipulation or comparison can also be supported. Libraries written in Python are also enabled and they can be integrated with the dedicated annotation @library

The Jupyter support includes the possibility to dispose of tools as syntax highlighting, code analysis (checking whether the code is correct or there are errors) and explanations of results (how the result has been obtained): all these functionalities are embedded in the notebook and help in writing and analyzing Vadalog codes.

See also

• Datalog
• Prolog
• DBMS
• Semantic Web Rule Language