DeductiveDatabases.pdf

Deductive Databases (DDBs) Introduction Prolog/Datalog Notation Rule Interpretation Inference Mechanisms 1 Introduction 1. DDBs is an area at the intersection of databases, AI, logic 2. a DDB is a database system including capabilities to define deductive r...

Deductive Databases (DDBs) Introduction Prolog/Datalog Notation Rule Interpretation Inference Mechanisms 1 Introduction 1. DDBs is an area at the intersection of databases, AI, logic 2. a DDB is a database system including capabilities to define deductive rules, via which we can deduce or infer additional information from the facts stored in a database 3. theoretical foundation for DDBs is mathematical logic 4. other types of systems (e.g. expert database systems or knowledge-based systems) also incorporate reasoning and inference capabilities 5. common characteristic: use of AI techniques (production systems) 6. difference: DDBs makes use of data in secondary storage, expert database systems assume that the data needed resides in main memory 2  Basic Notions of DDBs In a DDB we specify rules through a declarative language (what, not how, e.g. SQL) An inference engine or deduction mechanism in the DDB can deduce new facts from the database by interpreting these rules model used for DDBs is closely related to: 1. Relational Data Model (domain relational calculus) 2. logic programming, Prolog language a variation of Prolog, Datalog is used to define rules declaratively. the existing set of relations is treated as a set of literals in the language Datalog syntax is similar to Prolog syntax Datalog semanticsa 6= Prolog semantics a how programs are executed 3 a DDB uses two main types of specifications: facts and rules 1. Facts are specified in a manner similar to relations, but not necessarily including attribute names. In a DDB the meaning of an attribute is determined by its position in a tuple 2. Rules are similar to relational views. They specify virtual relations that are not actually stored but rather can be deduced from the facts by applying inference mechanisms based on the rule specifications Main difference between rules & views is that rules can involve recursion The evaluation of Prolog programs is based on backward chaining, which involves a top-down evaluation of goals The evaluation of Datalog programs is roughly based on bottom-up evaluation In Prolog the order of specification of facts and rules and the order of literals are significant, for the evaluation in Datalog an effort has been made to circumvent these problems 4 Prolog/Datalog Notation Principle: provide predicates with unique names implicit meaning (via a suggestive name) Predicate: fixed number of arguments If the arguments are all constant values, then the predicate states that a certain fact is true. If the arguments are variables, then the predicate is considered as a query or as a part of a rule or constraint Prolog Conventions adopted here: 1. constant values in a predicate are either numeric or character strings and they are represented by identifiers starting with a lowercase letter only 2. variable names start with an uppercase letter only 5 Example based on the company database 3 predicate names: supervise, superior, subordinate a) the supervise predicate: defined via a set of facts, each with two arguments: (supervisor name, supervisee name) supervise expresses the idea of direct supervision facts correspond to actual data stored in the database facts correspond to tuples in a relation with two attributes and schema: SUPERVISE(SUPERVISOR, SUPERVISEE) note the absence of attribute names in facts attributes are represented by position. 1st argument is the supervisor, 2nd argument is the supervisee. supervise(X,Y) states the fact that X supervises Y. b) the superior, subordinate predicates: defined via a set of rules (superior allows us to express the idea of non-direct supervision) MAIN IDEA OF DDBs specify rules and a framework to infer (deduce) new information based on these rules 6 7 Rule Syntax head :- body the symbol :- is interpreted as IFF (if and only if) the head is also called LHS or conclusion. it is (usually) made up of a single predicate the body is also called RHS or premise(s). its made up of one or more predicates separated by commas (implicitly connected by AND) predicates with constant arguments are called ground predicates or instantiated predicates the arguments of a predicate in a rule are (typically) variables Query Syntax A query typically involves a predicate symbol with some variable arguments. The answer to a query is to deduce all different combinations of constant values, that (when assigned to the variables) make the predicate true. 8 Datalog Notation A Datalog program is built from combining atomic formulas. Atomic formulas are literals of the form p(a1 ,... , an ) where p is the predicate name and n is the # of its arguments. n is called the arity or the degree of p The arguments can be constant values (lowercase) or variable names (uppercase). built-in predicates: (syntax: less(X,3), X