Transcript CSCE 330 Programming Language Structures

CSCE 580
Artificial Intelligence
Ch.12 [P]: Individuals and Relations
Datalog
Fall 2009
Marco Valtorta
[email protected]
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Acknowledgment
• The slides are based on [AIMA] and other sources, including
other fine textbooks
• David Poole, Alan Mackworth, and Randy Goebel.
Computational Intelligence: A Logical Approach. Oxford,
1998
– A second edition (by Poole and Mackworth) is under
development. Dr. Poole allowed us to use a draft of it in
this course
• Ivan Bratko. Prolog Programming for Artificial Intelligence,
Third Edition. Addison-Wesley, 2001
– The fourth edition is under development
• George F. Luger. Artificial Intelligence: Structures and
Strategies for Complex Problem Solving, Sixth Edition.
Addison-Welsey, 2009
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Databases and Recursion
• Datalog is a subset of Prolog that can be used to define
relational algebra
• Datalog is more powerful than relational algebra:
– It has variables
– It allows recursive definitions of relations
– Therefore, e.g., datalog allows the definition of the
transitive closure of a relation.
• Datalog has no function symbols: it is a subset of
definite clause logic.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Relational DB Operations
• A relational db is a kb of ground facts
• datalog rules can define relational algebra database
operations
• The examples refer to the database in course.pl
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Selection
• Selection:
– cs_course(X) <- department(X, comp_science).
– math_course(X) <- department(X, math).
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Union
• Union: multiple rules with the same head
– cs_or_math_course(X) <- cs_course(X).
– cs_or_math_course(X) <- math_course(X).
• In the example, the cs_or_math_course relation is the
union of the two relations defined by the rules above.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Join
• Join: the join is on the shared variables, e.g.:
– ?enrolled(S,C) & department(C,D).
– One must find instances of the relations such that the
values assigned to the same variables unify
• in a DB, unification simply means that the same variables
have the same value!
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Projection
• When there are variables in the body of a clause that
don’t appear in the head, you say that the relation is
projected onto the variables in the head, e.g.:
– in_dept(S,D) <enrolled(S,C) &
department(C,D).
• In the example, the relation in_dept is the projection of
the join of the enrolled and department relations.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Databases and Recursion
• Datalog can be used to define relational algebra
• Datalog is more powerful than relational algebra:
– It has variables
– It allows recursive definitions of relations
– Therefore, e.g., datalog allows the definition of the
transitive closure of a relation.
• Datalog has no function symbols: it is a subset of
definite clause logic.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Relational DB Operations
• A relational db is a kb of ground facts
• datalog rules can define relational algebra database
operations
• The examples refer to the database in course.pl
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Selection
• Selection:
– cs_course(X) <- department(X, comp_science).
– math_course(X) <- department(X, math).
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Union
• Union: multiple rules with the same head
– cs_or_math_course(X) <- cs_course(X).
– cs_or_math_course(X) <- math_course(X).
• In the example, the cs_or_math_course relation is the
union of the two relations defined by the rules above.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Join
• Join: the join is on the shared variables, e.g.:
– ?enrolled(S,C) & department(C,D).
– One must find instances of the relations such that the
values assigned to the same variables unify
• in a DB, unification simply means that the same variables
have the same value!
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Projection
• When there are variables in the body of a clause that
don’t appear in the head, you say that the relation is
projected onto the variables in the head, e.g.:
– in_dept(S,D) <enrolled(S,C) &
department(C,D).
• In the example, the relation in_dept is the projection of
the join of the enrolled and department relations.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Recursion
• Define a predicate in terms of simpler instances of
itself
– Simpler means: easier to prove
• Examples:
– west in west.pl
– live in elect.pl
• “Recursion is a way to view mathematical induction
top-down.”
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Well-founded Ordering
• Each relation is defined in terms of instances that are
lower in a well-founded ordering, a one-to-one
correspondence between the relation instances and the
non-negative integers.
• Examples:
– west: induction on the number of doors to the west--imm_west is the base case, with n=1.
– live: number of steps away from the outside--live(outside) is the base case.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Verification of Logic Programs
• Verifiability of logic programs is the prime motivation
behind using semantics!
• If g is false in the intended interpretation and g is
proved from the KB,
– Find the clause used to prove g
– If some atom in the body of the clause is false in the
intended interpretation, then debug it
– Else return the clause as the buggy clause instance
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Verifiability II
• Also need to show that all cases are covered: if an
instance of a predicate is true in the intended
interpretation, then one of the clauses is applicable
to prove the predicate.
• Also need to show termination---this is in general
impossible, due to semidicidability results, but it is
possible in many practical situations.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Limitations
• No notion of complete knowledge!
– Cannot conclude that something is false.
– Cannot conclude something from lack of
knowledge. Example:
• The relation empty_course(X) with the obvious
intended interpretation cannot be defined from
enrolled(S,C) relation.
• The Closed World Assumption (CWA) allows
reasoning from lack of knowledge.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Case Study: University Rules
•
•
•
•
univ.pl
DB of student records
DB of relations about the university
Rules about satisfying degree requirements.
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Case Study: University Rules
• This is an example of representing regulatory
knowledge.
– (Another great example: Sergot, M.J. et al., “The
British Nationality Act as a Logic Program.” CACM,
29, 5 (may 1986), 370-386.)
• DB of relations about the university (univ.pl)
• Rules about satisfying degree requirements (univ.pl)
• Lists are used (lists.pl)
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
Some facts
• grade(St, Course, Mark)
• dept(Dept,Fac)
– We would say College, not Faculty
• course(Course, Dept, Level)
• core_courses(Dept,CC, MinPass)
– CC is a list
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
A Rule
• satisfied_degree_requirements(St,Dept) <covers_core_courses(St,Dept) &
dept(Dept, Fac) &
satisfies_faculty_req(St, Fac) &
fulfilled_electives(St, Dept) &
enough_units(St, Dept).
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
More Rules
• Covers_core_courses(St, Dept) <core_courses(dept, CC, MinPass) &
passed_each(CC, St, MinPass)
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
More Rules
• passed(St, C, MinPass) <grade(St, C, Gr) &
Gr >= MinPass.
• A recursive rule that traverses a list.
• passed_each([], S, M).
• passed_each([C|R], St, MinPass) <passed(St, C, MinPass) &
passed_each(R, St, MinPass).
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
More Rules
• passed_one(CL, St, MinPass) <member(C, CL) &
passed(St, C, MinPass).
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering
A KB about rooms (Fig.12.2[P])
UNIVERSITY OF SOUTH CAROLINA
Department of Computer Science and Engineering