Deductive Databases
CPS721: Artificial Intelligence September 22, 2021
CPS721: Artificial Intelligence Deductive Databases September 22, 2021 1 / 11
Back-chaining with recursion: Example 2
Copyright By PowCoder代写 加微信 powcoder
Consider three predicates: reachable(C) means a city C is reachable, e.g., by car from Toronto, init_loc(X) means a city X is an initial location, and road(X,Y) means there isahighwayfromacityX toacityY.
reachable(Z) :- reachable(Y), road(Y,Z). reachable(X) :- init_loc(X). init_loc(toronto). road(toronto,calgary). road(calgary,vancouver). road(new_york,boston).
?- reachable(vancouver).
/* Is it true that vancouver is reachable?*/
CPS721: Artificial Intelligence
Deductive Databases September 22, 2021 3 / 11
Back-chaining with recursion: Example 1
parent(charles, william). parent(elizabeth,charles). parent(diana,william).
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- ancestor(X,Z), parent(Z,Y).
?- ancestor(diana,elizabeth).
CPS721: Artificial Intelligence Deductive Databases September 22, 2021 2 / 11
PROLOG as a programming language
How the PROLOG rules and predicates can be understood from the CS perspective ? Consider a generic PROLOG rule written in pseudo-code
predicate (X ̄ ) : − predicate (X ̄ ), · · · , predicate (X ̄ ). 1122nn
where X ̄i is a tuple of variables local to this rule. Read this as follows. Call predicate (X ̄ )
Call predicate (X ̄ ) . 2 2
. ̄ Call predicaten(Xn)
• Upon backtracking, local variables can take values different from initial.
• Some arguments of a predicate may serve as inputs, while others – as outputs. • Recall each predicate represents a sentence that can be only True/False.
PROLOGhasanextensivelibraryofthepredicates. ?-help(predName/arity). You may see predName(+X , −Y ) that means X gets inputs, and Y returns outputs.
Example: sum(X,Y,Z):−ZisX+Y. /*Notation sum(+X,+Y,-Z)*/ Syntax for assignment: Variable is ArithmExpression.
Warning: if a Var is assigned a value in conjunction, you cannot change it later. Query ?- X is 2*2, Y is 5+6, X is Y. fails since 3rd “is” works as =:=
CPS721: Artificial Intelligence Deductive Databases September 22, 2021 4 / 11
Deductive Airline Reservation System
Consider a small deductive database for a simplified airline reservation system. nonStop(FlightNum,C1,C2): FlightNum is a non stop flight between cities C1 and C2
nonStop(ac103, toronto, montreal). nonStop(ac103, ny, miami). nonStop(us200, miami, la).
nonStop(ac103, montreal, ny). nonStop(us400, austin, la). nonStop(aa300, ny, austin).
dtime(FlightNumber,City,Time): The departure time of FlightNumber from City is Time; time is based on a 24 clock.
dtime(ac103, toronto, 635). dtime(ac103, montreal, 800). dtime(aa300, ny, 1200). dtime(us400, austin, 1400).
atime(FlightNumber,City,Time): The arrival time of FlightNumber to City is Time. atime(ac103, montreal, 735). atime(ac103, ny, 930).
atime(us200, la, 1800). atime(aa300, austin, 1600).
reserved(Person,FlightNumber,City1,City2,Day,Month,Year): Person has a reservation on FlightNumber on the non-stop flight from City1 to City2 on Day of Month of Year.
reserved(mary, ac103, toronto, montreal, 20, 4, 2019). reserved(mary, ac103, montreal, ny, 20, 4, 2019). reserved(mary, ac103, ny, miami, 20, 4, 2019). reserved(john, aa300, ny, austin, 1, 10, 2019).
CPS721: Artificial Intelligence Deductive Databases September 22, 2021 5 / 11
impossibleSchedule(Flight,City)
impossibleSchedule(Flight,City):
The airline schedule is in error in the sense that the arrival time of Flight in City is greater than its departure time from City.
impossibleSchedule(F,C) :- ?
/*a correct solution */
impossibleSchedule(Flight, City) : −
/*Hint: use atime,dtime*/
atime(Flight, City, T1), dtime(Flight, City, T2), T2 < T1.
CPS721: Artificial Intelligence Deductive Databases September 22, 2021 7 / 11
Simplifying Assumptions
1) All flights have the same daily schedule, seven days per week. That’s why we do not have predicates like
dtime(FlightNumber,City,DayOfWeek,Time) atime(FlightNumber,City,DayOfWeek,Time).
2) All flights begin and terminate within the same day. This means that there are no flights which depart in the evening, and arrive at their destination during the morning of the following day.
3) Time is measured w.r.t. "universal" time zone, so if it is now 1435 in Toronto, it is also 1435 in Vancouver.
The task is to write additional rules that implement new predicates. They will provide extra reasoning services on top of DB retrieval queries.
Think about the Pearson’s airport flights recorded as atomic statements. The new rules faciliate reasoning over this KB.
CPS721: Artificial Intelligence Deductive Databases September 22, 2021 6 / 11
possibleConnectingFlight(Flight1,Flight2,City)
possibleConnectingFlight(Flight1,Flight2,City):
It is possible for a passenger to arrive in City on Flight1 with enough time to catch the departing Flight2. Make the simplifying assumption that there is enough time to make the connection if the arrival time of Flight1 is 50 min less than the departure time of Flight2.
possibleConnectingFlight(F1,F2,C) :- ? /*Hint: use atime,dtime*/
/* A possible solution */
possibleConnectingFlight(Flight1,Flight2,City) :- atime(Flight1, City, Time1),
dtime(Flight2, City, Time2),
Time1 < Time2,
diff(Time1, Time2, Minutes), Minutes >= 50.
diff(T1, T2, M) : −Hours1 is T1//100, Hours2 is T2//100, Minutes1 is (T1 mod 100), Minutes2 is (T2 mod 100),
M is (Hours2 − Hours1) ∗ 60 + Minutes2 − Minutes1.
CPS721: Artificial Intelligence Deductive Databases September 22, 2021 8 / 11
conflictingReservation(Person)
conflictingReservation(Person):
Person has two conflicting reservations, meaning that Person has reservations on two different flights which overlap in time, i.e. the two flights are on the same date and the departure time of one of the flights lies between the departure time and arrival time of the other flight.
conflictingReservation(P) :- ?
conflictingReservation(Person) :-
reserved(Person, Flight, City1, City2, Day, Month, Year), reserved(Person, F, C1, C2, Day, Month, Year),
not Flight = F,
dtime(Flight, City1, Time1),
atime(Flight, City2, Time2),
dtime(F, C1, T),
Time1 < T, T < Time2.
CPS721: Artificial Intelligence
Deductive Databases
September 22, 2021
twoFlightConnection(Flight1,Flight2,City1,City,City2)
twoFlightConnection(Flight1,Flight2,City1,C,City2):
Flight1 is a direct flight from City1 to C, and Flight2 is a different direct flight from C to City2. In other words, one can fly from City1 to City2 via C, changing airplanes exactly once in C. Moreover, Flight2 must be a possibleConnectingFlight for Flight1 in C. For the above example, twoFlightConnection(ac103,aa300,toronto,ny,austin) is true, whereas the following two are both false (for different reasons):
twoFlightConnection(ac103,aa300,toronto,montreal,austin) twoFlightConnection(aa300,us400,ny,austin,la)
twoFlightConnection(F1,F2,City1,C,City2) :- ?
/*Hint: use directFlight*/
twoFlightConnection(F1,F2,C1,C,C2) :- directFlight(F1, C1, C), directFlight(F2, C, C2),
not F1=F2, possibleConnectingFlight(F1, F2, C).
CPS721: Artificial Intelligence Deductive Databases September 22, 2021 11 / 11
directFlight(Flight,City1,City2)
directFlight(Flight,City1,City2):
Flight connects City1 and City2, i.e. a passenger can take Flight from City1 to City2 without changing airplanes. For the above example, both statements
directFlight(ac103,toronto,miami)
directFlight(ac103,toronto,montreal)
would be true, whereas directFlight(ac103,toronto,vancouver) would be false.
directFlight(F,C1,C2) :- ? /* Hint: need recursion */
directFlight(F,City1,City2) :- nonStop(F,City1,City2).
directFlight( F, City1, City2) :- nonStop(F, City1, IntermediateCity), directFlight(F, IntermediateCity, City2).
CPS721: Artificial Intelligence Deductive Databases September 22, 2021 10 / 11
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com