Datalog
In plain wordsA small logic language for asking questions of a database with rules, including rules that refer to themselves, such as 'X is an ancestor of Y if X is a parent of an ancestor of Y'.
A rule language for querying databases obtained by restricting PrologProlog, prop. n.: A programming language from 1972 in which you state facts and rules in logic and then ask questions; the computer finds answers by searching for proofs. to function-free Horn clausesHorn clause, n.: A simple, restricted form of logical rule ('if these conditions all hold, then this one conclusion holds') that computers can reason with very efficiently.: with no function symbols to build new terms, every program has a finite least model, computable bottom-up by forward chainingforward chaining, n.: A way of reasoning that starts from known facts and keeps applying rules to them, adding each new conclusion, until it reaches an answer or nothing new can be concluded., and every query terminates. Its main advantage over the original core of SQL is natural support for recursion, such as transitive closure (reachability, ancestry). Efficient engines use semi-naive evaluation, which joins only newly derived facts in each round, and 'magic sets' rewriting to focus computation on a query. Extensions add stratified negation, aggregation and constraints. Datalog is used in deductive databases, static program analysis (Soufflé; GitHub's CodeQL derives from it), access-control and network-policy languages, and knowledge graphknowledge graph, n.: A huge web of facts stored as connections between things — 'Paris is the capital of France', 'Marie Curie won a Nobel Prize' — that computers can search, combine and reason over. reasoning, and it is a common target language for neuro-symbolicneuro-symbolic AI, n.: AI that combines neural networks, which learn patterns from data, with symbolic methods, which follow explicit rules and logic, aiming for systems that both learn flexibly and reason reliably. systems.
Writing the points-to analysis in Datalog took 200 lines instead of 20,000.
Origin
The name, a blend of 'data' and 'logic', is generally credited to the database theorist David Maier and was current by the mid-1980s. The underlying deductive-database research dates from the 1977 Toulouse workshop on logic and databases organized by Hervé Gallaire, Jack Minker and Jean-Marie Nicolas.
Related
- logic programminglogic programming, n.: A style of programming in which you write down facts and rules in logic and then ask questions; the computer works out the answers itself by logical deduction.
- Horn clauseHorn clause, n.: A simple, restricted form of logical rule ('if these conditions all hold, then this one conclusion holds') that computers can reason with very efficiently.
- PrologProlog, prop. n.: A programming language from 1972 in which you state facts and rules in logic and then ask questions; the computer finds answers by searching for proofs.
- forward chainingforward chaining, n.: A way of reasoning that starts from known facts and keeps applying rules to them, adding each new conclusion, until it reaches an answer or nothing new can be concluded.
- knowledge graphknowledge graph, n.: A huge web of facts stored as connections between things — 'Paris is the capital of France', 'Marie Curie won a Nobel Prize' — that computers can search, combine and reason over.
- closed-world assumptionclosed-world assumption, n.: The rule of treating whatever a system cannot confirm as false: if a library's catalog does not list a book, the library is assumed not to have it.
Sources
- Gallaire, H. & Minker, J. (eds.) (1978). Logic and Data Bases. Plenum Press.
- Ceri, S., Gottlob, G. & Tanca, L. (1989). What You Always Wanted to Know About Datalog (and Never Dared to Ask). IEEE Transactions on Knowledge and Data Engineering 1(1), 146–166.
Mentioned in
forward chainingforward chaining, n.: A way of reasoning that starts from known facts and keeps applying rules to them, adding each new conclusion, until it reaches an answer or nothing new can be concluded., logic programminglogic programming, n.: A style of programming in which you write down facts and rules in logic and then ask questions; the computer works out the answers itself by logical deduction., closed-world assumptionclosed-world assumption, n.: The rule of treating whatever a system cannot confirm as false: if a library's catalog does not list a book, the library is assumed not to have it., general game playinggeneral game playing, n.: Building AI players that are handed the rules of a game they have never seen and must work out how to play it well on their own, with no game-specific help from their programmers., Horn clauseHorn clause, n.: A simple, restricted form of logical rule ('if these conditions all hold, then this one conclusion holds') that computers can reason with very efficiently.