Environment Configuration: Linux+XSB Prolog

Instructions:

  1. Deductive databases in XSB Prolog CSE532 project 2 (file: tangerOutlet.pl submitted in Blackboard) = 50 points
    Due: 04/09/2012 (8:00AM EST)Write a predicate buy(Stores,Links,MinCustomers) that determines the minimum number of customers required to buy all the items on sale in an outlet with a given list of Stores and Links connecting them. The customers will buy all sales in the Stores one by one, and travel between stores along the available Links. A Store is a term store(Name,Capacity,Bankrupt,Waiting), where: Name is a unique name, Capacity is the number of customers required to buy all the sales in the store, Bankrupt is the number of customers bankrupt after buying all sales in the store, and Waiting are the number of customers that remain in the store to wait for more sales. Any remaining customers after a store sale that are not Waiting or Bankrupt, can move on to shop in the next store. A link connects two stores, and is represented by a term link(Namel,Name2) (you can assume that the Stores and Links form a connected graph). In your plan, you are free to start at any store, but you should travel at most once in either direction along a link.For example:|store(walm,5,5,5)|——|store(jcp,5,1,1)|——|store(tommy,10,5,5)|?-buy([store(walm,5,5,5),store(tommy,10,5,5),store(jcp,5,1,1)],[link(walm,jcp),link(tommy,jcp)],MinCustomers]).
    MinCustomers = 17Grading scheme (50 points): we will run in XSB Prolog 5 queries (with hidden test cases) with 10 points per query. If the query returns the right answer, then you will get 10 points, otherwise, you will get 0 points. The hidden test cases and the correct answers will be published after the project submission deadline.

Algorithm:

Find all paths -> Hamilton path -> Minimal Hamilton path

Hamiltonian path is a path in an undirected graph that visits each vertex exactly once.

Note:

I Datalog

1. basic syntax:

.    rule: R(t1, …, tn) :- Q1(s11, …, s1m), Q2(s21, …, s2m).

.    query: ?- R(t1, …, tn)

2. union: R(t1, …, tn) :- Q1(s11, …, s1m); Q2(s21, …, s2m).

3. recursion: R(t1, …, tn) :- Q(s1, …, sm), R(t1, …, tn) 

4. positive rule & negative rule: (semantics algorithms)

.    div: find all tuples in one relation that join with every tuple in another relation

Q: “find all students who took a course from every professor”

Answer(Sid) :- Student(Sid, Name, Addr),

.                          not DidNotTakeAnyCourseFromSomeProf(Sid).

not DidNotTakeAnyCourseFromSomeProf(Sid) :- Proffesor(Pid, Pname, Dept),

.                                                                                         Student(Sid, Name, Addr),

.                                                                                         not HasTaught(Pid, Sid).

HasTaught(Pid, Sid) :- Teaching(Pid, Crs, Sem),

.                                         Transcript(Sid, Crs, Sem, Grd).

?- Answer(Sid).

.    negative circle(well-defined/ill-defined): dependency graph(node: relation name, arc: P :- (not)QQ—>R/Q-=->R) ~ stratification

II XSB Prolog [tangerOutlet.P/pl]

1. Basic Syntax:

.    Variable: capital letter/_+alphanumberic

.    Relation name, Atom: lowercase letter+alphanumberic/_

.        nameless variable: store(Name, _, _, _),

.        variable name is not important, occurrence refer to the same variable

2. support Datalog: :- auto table

3. data controll:

:- dynamic store/4. //define dynamic variable

asserta(store(Name, Capacity, Bankrupt, Waiting)), //malloc

retract(store(Name, Capacity, Bankrupt, Waiting)), //delete

retractall(store(N, C, B, W)), //delete all tuples

4. negative rule: tnot(remain_sign(X)),√  not×

5. calculation: is√  =× Loose is Bankrupt + Waiting.

6. List: [A|Path1] binary tree structure

7. process control: 

.    cut: change_remain(Y, Remain_Y1),!

.    fail: asserta(nodelist(NodeList)), fail. 

.    if then else: (Capacity_Y < Remain_X) -> ;

8. output: write(X): output writeln(X): output+nl nl:nl

9. comment: /**/ //

10. debug: | ?-trace. tree structure analysis [manual1.pdf]

.    call: callinto

.    exit: exit successfully

.    fail:  exit unsuccessfully

.    redo: search for another tuple

Advertisements