deductive database
   HOME

TheInfoList



OR:

A deductive database is a
database system In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases spa ...
that can make deductions (i.e. conclude additional facts) based on
rules Rule or ruling may refer to: Education * Royal University of Law and Economics (RULE), a university in Cambodia Human activity * The exercise of political or personal control by someone with authority or power * Business rule, a rule pert ...
and facts stored in the (deductive) database.
Datalog Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties ...
is the language typically used to specify facts, rules and queries in deductive databases. Deductive databases have grown out of the desire to combine
logic programming Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic pro ...
with relational databases to construct systems that support a powerful formalism and are still fast and able to deal with very large datasets. Deductive databases are more expressive than relational databases but less
expressive Expressivity, expressiveness, and expressive power may refer to: *Expressivity (genetics), variations in a phenotype among individuals carrying a particular genotype *Expressive loa, a type of loanword in phono-semantic matching *Expressive power ...
than logic programming systems. In recent years, deductive databases such as Datalog have found new application in
data integration Data integration involves combining data residing in different sources and providing users with a unified view of them. This process becomes significant in a variety of situations, which include both commercial (such as when two similar companies ...
,
information extraction Information extraction (IE) is the task of automatically extracting structured information from unstructured and/or semi-structured machine-readable documents and other electronically represented sources. In most of the cases this activity concer ...
, networking,
program analysis In computer science, program analysis is the process of automatically analyzing the behavior of computer programs regarding a property such as correctness, robustness, safety and liveness. Program analysis focuses on two major areas: program op ...
, security, and cloud computing.Datalog and Emerging applications
/ref> Deductive databases reuse many concepts from logic programming; rules and facts specified in the deductive database language Datalog look very similar to those in
Prolog Prolog is a logic programming language associated with artificial intelligence and computational linguistics. Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primarily ...
. However important differences between deductive databases and logic programming: * Order sensitivity and procedurality: In Prolog, program execution depends on the order of rules in the program and on the order of parts of rules; these properties are used by programmers to build efficient programs. In database languages (like SQL or Datalog), however, program execution is independent of the order of rules and facts. * Special predicates: In Prolog, programmers can directly influence the procedural evaluation of the program with special predicates such as the
cut Cut may refer to: Common uses * The act of cutting, the separation of an object into two through acutely-directed force ** A type of wound ** Cut (archaeology), a hole dug in the past ** Cut (clothing), the style or shape of a garment ** Cut (ea ...
, this has no correspondence in deductive databases. * Function symbols: Logic Programming languages allow function symbols to build up complex symbols. This is not allowed in deductive databases. *
Tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
-oriented processing: Deductive databases use set-oriented processing while logic programming languages concentrate on one tuple at a time.


References


Further reading

* Author: Herve Gallaire,
Jack Minker Jack Minker (4 July 1927 – 9 April 2021) was a leading authority in artificial intelligence, deductive databases, logic programming and non-monotonic reasoning. He was also an internationally recognized leader in the field of human rights of c ...
, Jean-Marie Nicolas: ''Logic and Databases: A Deductive Approach''. Publisher: ACM. doi:10.1145/356924.356929 * Author: Stefano Ceri,
Georg Gottlob Georg Gottlob FRS is an Austrian computer scientist who works in the areas of database theory, logic, and artificial intelligence and is Professor of Informatics at the University of Oxford. Education Gottlob obtained his undergraduate and PhD ...
, Letizia Tanca: ''Logic Programming and Databases''. Publisher: Springer-Verlag. * Author: Ramez Elmasri and Shamkant Navathe: ''Fundamentals of Database Systems'' (3rd edition). Publisher: Addison-Wesley Longman. Database management systems {{database-stub