DATALOG

Created on March 12, 2013, 5:51 p.m. by Hevok & updated by Hevok on May 2, 2013, 5:35 p.m.

The DATALOG Language has been the basic if deductive Databases, which is nothing else then a Logical Rule Language that consists out of Horn Clauses without using function symbols. There are several Restrictions. Allowed is for example Conjunction, Constants, Universal Quantified Variables and predicate Symbols, while not allowed are Disjunction, Negation, Existential Quantification, nor function symbols. Knowledge Bases that are based on DATALOG Programs are nothing else, but a set of Horn Clauses without function Symbols complying to the Restrictions. DATALOG is decidable and is also computational efficient, which means that major problems like satisfiability for example can be decided in exponential time. Although it is quite complex it is still decidable. So one can work wit DATALOG and each single algorithm will come to an end in finite time.

  • is a logical Rule Language that consists of
    • horn Clauses without function Symbols
    • Conjunction, Constants, universally quantified Variables, predicate Symbols
    • no Disjunction, no Negation, no existential Quantification, no function Symbols
  • originally developed as foundation of deductive Databases.
  • *Knowledge Bases (DATALOG Programs) are sets of horn Clauses (without function Symbols)
  • DATALOG is decidable
  • DATALOG is computationally efficient, complexity corresponds to OWLS 1 Lite, i.e. ExpTime

DATALOG - Syntax

In DATALOG one is considering Terms, which are either Constants or Variables. From these Terms one creates Atoms which are usually Predicates p that are applied on a set of Terms (i.e. Constants or Variables), here t1 to tn.

A Rule based on DATALOG is nothing else than a Horn Clause where B1 to Bn are Atoms that are in the body of the Rule and H is Atom that is in the header of the Rule and all Variables are universally quanfified, which means the Rule holds for each Variable and Assignment. A DATALOG Program is nothing else than a set of DATALOG Rules.

  • DATALOG Term: constant c or variable v
  • DATALOG ATOM: p(t1, ..., tn) with predicate p, terms 1, ..., tn
  • DATALOG Rule: ∀x1 ... ∀xn (B1⋀...⋀Bn →H) with B1, ..., Bn, H atoms and x1, ..., xn Variables
  • DATALOG Program: set of DATALOG Rules

DATALOG Examples

DATALOG is much more expressive than for example Description Logics. Usually the the Implication in Description Logics is written as an Subsumption or Inclusion. This is a problem, because one can not make and Inclusion or an Subsumption from a Property that subsumes a Class. This is not possible in Description Logics, but it is possible in First Order Logic if one considers First Order Logic Rules like DATALOG Rules.

DATALOG Rules allow the mixing of Classes and Relations which are nothing else that unary and binary Predicates that can be mixed. Therefore DATALOG is much more expressive than Description Logics.

The Semantic Web Rule (SWRL) Language combines DATALOG with OWL.

  1. Vegatarian(x) ⋀ FishProduct(y) → dislikes(x,y)
  2. orderedDish(x,y) ⋀ dislkes(x,y) → Unhappy(x)
  3. orderedfish(x,y) → Dish(y)
  4. dislikes(x,z) ⋀ Dish(y) ⋀ contains(y,z) → dislikes(x,y)
  5. → Vegetarian(Hevok)
  6. Happy(x) ⋀ Unhappy(x) →

x dislikes y and y is a dish

  • DATALOG Rules allow mixing Classes and Relations (i.e. unary and binary Predicates)
  • therefore it can be more expressive than DL
  • A combination of DATALOG and OWL is the SWRL Language
datalog.jpg

Tags: logic, language
Categories: Concept
Parent: Rule

Update entry (Admin) | See changes

Comment on This Data Unit