Vadalog

Key takeaways

Vadalog belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Vadalog to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Vadalog from memory before moving on to harder problems.

Reference excerpt

Vadalog is a system for performing complex logic reasoning tasks over knowledge graphs. Its language is based on an extension of the rule-based language Datalog, Warded Datalog±. Vadalog was developed by researchers at the University of Oxford and Technische Universität Wien as well as employees at the Bank of Italy.

Knowledge graph management systems (KGMS)

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

KBMS, that is, a knowledge base management system, 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 can be integrated into large knowledge graphs, (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. From a more technical standpoint, some additional requirements can be identified for defining a proper KGMS:

definition of a language and a formalism with high expressive power, 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 (to handle big data) and syntax, interfaces (APIs) to access many heterogeneous data sources, such as corporate RDBMS, NoSQL or RDF stores, the web, machine-learning and analytics packages. Other requirements may include more typical DBMS functions and services, as the ones proposed by Codd.

Vadalog system Vadalog offers a platform that fulfills all the requirements of a KGMS listed above. 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

A rule is an expression of the form n :− a1, ..., an where:

a1, ..., an 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 Σ, a reasoning task aims at inferring new knowledge, applying the rules of the set Σ to the database D (the extensional knowledge). The most widespread 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 with 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). An existential rule has the following form:

φ ( x ) ⇒ ∃ z Ψ ( x , z ) {\displaystyle \varphi (x)\Rightarrow \exists z\Psi (x,z)}

or, alternatively, in Datalog syntax, it can be written as follows:Variables in Vadalog are like variables in first-order logic and 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 Σ {\displaystyle \Sigma } , consisting of the following: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 that for every rule defined in a set Σ {\displaystyle \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 extends it with the inclusion in the language of:

monotonic aggregations (min, max, sum, prod, count operators), stratified negation, support for 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 addition, the system provides a highly engineered architecture to allow efficient computation. This is done in the following two ways.

… excerpt ends here. Continue reading the full article.

Illustrations

Worked examples

Example 1 — a first encounter with Vadalog

Start with the simplest possible case. Write down what Vadalog claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Vadalog before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Vadalog ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Vadalog

In research: Vadalog appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Vadalog in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Vadalog is common in secondary-school and first-year university syllabi. It links to neighbouring topics Declarative programming languages, Graph databases, Logic programming languages, so understanding it makes those chapters shorter.
In everyday life: Look for Vadalog outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Vadalog in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Vadalog means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Vadalog out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Vadalog in simple terms?

Vadalog is a system for performing complex logic reasoning tasks over knowledge graphs. Its language is based on an extension of the rule-based language Datalog, Warded Datalog±.

Why does Vadalog matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Vadalog?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Vadalog.