CSE 532 Assignment #2
Due Thursday, February 28, 2013 (1 pm).
Problem Set (100 points)
- (25 points) Let us consider the following relations/predicates:
Note that courses are represented by their unique
numbers in relations Prereqs and Enrolls; students are represented
by their ID's. Prerequisites are immediate prerequisites only.
For example, if CS101 is a prerequisite of CS200, and CS200 is
a prerequisite of CS342, then only the pairs (CS200, CS101) and (CS342,
CS200) would appear in Prereqs. We refer to CS101 as an indirect prerequisite
of CS342. Write the following questions in Datalog:
- Courses(number, quarter, instructor)
- Prereqs(course, prerequisite)
- Students(id, name, address)
- Enrolls(studentID, course, quarter, grade)
- Find the prerequisites, including indirect prerequisites, of CS103.
- Find the students who enrolled in CS488 but never (i.e., in no previous
quarter) enrolled in one or more of its direct or indirect prerequisites.
- (25 points)
Consider a database for the Paris Metro and Bus lines, consisting of two relations
Metro(Station, Next) and Bus(Station, Next).
Find pairs of stations (m,n), such that m can be reached
from n by a bus path (using only buses) AND a metro path (using
We say that the metro is useless in a bus path from m to
n if by taking the metro at any intermediate point k one
can return to k, but not reach any other station along the
path. Find the pair of stations (m,n) such that the metro is
useless in all the bus paths connecting m and n.
- (25 points) A graph is a set of nodes, where some
pairs of nodes are connected by an edge. Let us consider a set of graphs
represented by the following two relations: GraphNodes(GraphName ,
Node) and GraphEdges(GraphName, Node1,
Node2 ). The relation GraphNodes stores the set of nodes for
each graph, and a tuple (g,x,y) in the relation GraphEdges means
that in graph g the nodes x and y are connected by an
edge. We assume that if a tuple (g, x, y) exists in GraphEdges then (g,
x) and (g, y) both exist in GraphNodes. However, GraphNodes may have
additional tuples. Write stratified datalog programs for each of the
Assume that the given graphs are DAGS (i.e., directed acyclic graphs). Also, assume
that you are given an EDB AddOne(m,n), which contains the tuple (m, m+1)
for any integer m.
- Find the set of graphs that have a diameter of at most k (i.e.,
the distance (length of shortest path) between each pair of nodes is at
most k). Here, k is a constant and may be used as part of
your datalog rules in arithmetic predicates. However, the number of
rules in your program should be independent of k.
- A 2-center of a graph G is a node A in G such that
every node is G is at most at a distance of 2 from A. For each
graph, find its 2-center, if one exists.
- (25 points) Suppose we have EDB relations: frequents(Drinker, Bar)
, serves(Bar, Beer), and likes(Drinker, Beer). The relations have obvious
meanings. Define the following predicates using safe datalog rules.
- veryHappy(D) if every bar that drinker D frequents
serves at least one beer he likes. You may assume that every drinker frequents
at least one bar.
- sad(D) if drinker D frequents all bars that serve
no beer he likes.