Nikolay Pavlovich Laptev
CS240A
Professor Zaniolo
Problem Set #1
[Ex. 8.1]
Idea: We want to find all suppliers who have all basic parts
/* Get all suppliers who have all basic parts */
/* Check if particular supplier has all basic parts */
/* This simply checks if our supplier has a certain part */
[Ex. 8.2]
Idea: We want to find all students who have taken at least two classes and got the highest score in all of them.
/* Get all students with at least two classes and highest grade in those classes */
/* Make sure that out student has at least two classes */
/* Make sure that our student has the highest (possibly ties with another student) grade in all of his/her classes */
[Ex. 8.5]
(a)Claim: If we drop set intersection from RA then the expressive power of RA does not change.
Proof: Set intersection of two relations can be constructed either by taking the equijoin of the two relations in every column (and then projecting out duplicate columns) or by using the following property:
(b)RA functions are all monotonic operations. Clearly set difference is not monotonic.
(c)Claim: If we drop set difference then there is a loss of expressive power.
Proof: Set difference operator cannot be expressed as any combinations of any other operator.
[Ex. 8.7]
Before we define safe rules and safe predicates it is important to note that:
- A predicate q of P is safe is
- q is a database predicate, or
- every rule defining q is safe.
- A rule r is safe if all its variable are safe.
- A variable X in rule r is safe if
- X is contained in some positive goal where the predicate is safe, or
- r contains some equality goal X=Y, where Y is safe.
SAFE.
RA Expression:
[Step 1] Since our expression above does not have any equality goals, we leave it unchanged.
[Step 2]Here we translate the body into an RA expression.
[Step 3] Now we translate each rule r into a generalized projection on
SAFE.
RA expression:
[Step 1] Since our expression above does not have any equality goals, we leave it unchanged.
[Step 2] Here we translate the body into an RA expression.
[Step 3] Now we translate each rule r into a generalized projection on
NOT SAFE, because there are infinite amount of possibility for X.
LDL++ Exercises:
Note: Database definition and tables were simply inputted by hand into a file and then imported into LDL++ by issuing commands :
- open city.prg
- compile %compiles the rules and database scheme
- initdb city.fac % initialized database with values in city.fac.
%Contents of city.fac
city('Houston', 'Texas', 300000).
city('Dallas', 'Texas', 2000).
city('Huntsville', 'Texas', 150000).
city('Austin', 'Texas', 750000).
city('Corsicana','Texas',60000).
city('Shreveport ', 'Luisiana',90000).
city('Bastrop', 'Texas', 6000).
city('San Antonio', 'Texas', 1500000).
distance('Houston', 'Bastrop', 130.0).
distance('Austin', 'Bastrop', 30.0).
distance('Austin', 'San Antonio', 80.0).
distance('San Antonio', 'Houston', 190.0).
distance('Houston', 'Huntsville', 60.0).
distance('Huntsville', 'Dallas', 100.0).
distance('Austin', 'Waco', 110.0).
distance('Waco', 'Dallas', 100.0).
distance('Dallas', 'Shreveport', 200.0).
% Contents of city.prg
%schema
database({city(Name:string, State:string, Population:integer),
distance(City1:string, City2:string, Distance:real)}).
%rules ...
lcity(C, Pop) <- city(C, 'Texas', Pop), Pop > 400000.
reachable_cities_from_austin(C,Miles) <- distance('Austin',C,Miles).
reachable_and_farthest(C,Miles) <- reachable_cities_from_austin(C,Miles),
~farther_city(C,Miles).
farther_city(C,Miles) <- distance('Austin', C,Miles),
distance('Austin', C2, Miles2),
Miles2 > Miles.
total_pop_in_texas(sum<Pop>) <- city(Name,'Texas',Pop).
%query forms
export lcity(X, Y).
export lcity($X, Y).
export reachable_cities_from_austin(X,Y).
export reachable_and_farthest(X,Y).
export total_pop_in_texas(X).
1)Below is the rule which was exported to get result for query “find the cities which are reachable from Austin, with their distance from Austin.”
reachable_cities_from_austin(C,Miles) <- distance('Austin',C,Miles).
Result:
ldl++(39)> query reachable_cities_from_austin(X,Y)
Querying : reachable_cities_from_austin(X,Y) ...
(Bastrop, 30)
(San Antonio, 80)
(Waco, 110)
The number of records is 3.
2)Below is the rule which was exported to get result for query “Find which of the above city is the furthest from Austin”
reachable_and_farthest(C,Miles) <- reachable_cities_from_austin(C,Miles),
~farther_city(C,Miles).
farther_city(C,Miles) <- distance('Austin', C,Miles),
distance('Austin', C2, Miles2),
Miles2 > Miles.
Result:
ldl++(40)> query reachable_and_farthest(X,Y)
Querying : reachable_and_farthest(X,Y) ...
(Waco, 110)
The number of records is 1.
3)Below is the rule which was exported to get result for query “Write an LDL++ program to add up the population of cities in Texas”
Using LDL++ aggregates this query is simple:
total_pop_in_texas(sum<Pop>) <- city(Name,'Texas',Pop).
Result:
Querying : total_pop_in_texas(X) ...
(7)
(2768000)
The number of records is 2.