Assignments for Week 2

• ADS book: study Sections 9.1--9.3 and Section 9.5 till 9.5.3
  (excluded). Also study Section 9.7
  
• DB2 book (i.e., the Complete Guide to DB2 Universal Database by D. Chamberlin): Read Sections 1--3 and study Section 5.8.
  
• Assume that you have facts as in Example 8.22. Write an LDL++
  program to compute the number of suppliers for each part, and to
  find the part that has the largest number of suppliers. Finally
  explain how your rules are implemented by a Datalog compiler
  (i.e., will the differential fixpoint be used? What are the
  re-written rules? Will the magic set or the left/right linear
  recursion method be used, and if so, what are the rewritten rules?
• Express in LDL++ the recursive queries at pages 253 and 262 of the
  DB2 book (you can also find them in the following text file). A short description of these queries is attached.
• On page 353, we have a fedemp(Name Salary, Manager) relation and we want to find the employees who have Hooever as a manager (at any level in the management chain) and make more than 100K. The textbook proposes the following SQL query to solve this problem:
  
  ***********************************************************************
  echo ***** Recursion *****;
  --***********************************************************************
  
  CREATE TABLE fedemp (NAME varchar(15),
                       SALARY decimal(8,2),
                       MANAGER varchar(15));
  
  INSERT INTO fedemp VALUES ('Elliot Ness', 150000, 'Hoover'),
                            ('Ryan Baker', 75000, 'Hoover'),
                            ('Bill Bathgate', 140000, 'Elliot Ness'),
                            ('Susan Crandall', 50000, 'Bill Bathgate'),
                            ('Sam Anders', 125000, 'Steve Smith');
  
  WITH agents(name, salary) AS
     ((SELECT name, salary 
       FROM   fedemp
       WHERE  manager = 'Hoover')
     UNION ALL
      (SELECT f.name, f.salary
       FROM   agents AS a, fedemp AS f
       WHERE  f.manager = a.name))
  SELECT name 
  FROM   agents
  WHERE  salary > 100000;
  
  -----------------------------------------------------------------------
• On page 262 we have the problem of finding flight from San Francisco to New York,
• in less than 3 segments (also you can exclude flight that ends in San Francisco or 
• start in New York). 
• -------------------------------------------------------------------------
  
  create table flights
     (flightno    varchar(5),
      origin      char(3),
      destination char(3),
      cost        integer);
  
  insert into flights values
     ('HY120', 'DFW', 'JFK', 225),
     ('HY130', 'DFW', 'LAX', 200),
     ('HY140', 'DFW', 'ORD', 100),
     ('HY150', 'DFW', 'SFO', 300),
     ('HY210', 'JFK', 'DFW', 225),
     ('HY240', 'JFK', 'ORD', 250),
     ('HY310', 'LAX', 'DFW', 200),
     ('HY350', 'LAX', 'SFO',  50),
     ('HY410', 'ORD', 'DFW', 100), 
     ('HY420', 'ORD', 'JFK', 250),
     ('HY450', 'ORD', 'SFO', 275),
     ('HY510', 'SFO', 'DFW', 300),
     ('HY530', 'SFO', 'LAX',  50),
     ('HY540', 'SFO', 'ORD', 275);
  
  
  
  WITH trips(destination, route, nsegs, totalcost) AS
    ((SELECT destination, CAST(destination AS Varchar(20)), 1, cost
      FROM flights                   
      WHERE origin = 'SFO')
     UNION ALL                              
     (SELECT f.destination,          
             CAST(t.route || ', ' || f.destination AS Varchar(20)),
             t.nsegs + 1,
             t.totalcost + f.cost
      FROM trips t, flights f
      WHERE t.destination = f.origin
      AND f.destination <> 'SFO'     
      AND f.origin <> 'JFK'     
      AND t.nsegs < 3 ))             
  SELECT route, totalcost             
  FROM trips
  WHERE destination = 'JFK'
  AND totalcost =                    
     (SELECT min(totalcost)
      FROM trips
      WHERE destination = 'JFK');
• ----------------------------------------------------------------
  Note: In  LDL++ you should  use list append instead of ||
  ***********************************************************************
  

Assignments for Week 1

• Study Sections 8.1--8.5 of ADS textbook.
• BDW: here is the Errata for the ADS Book.
• Do Exercises 8.1, 8.2, 8.5, and 8.7 of ADS textbook. (hint: for part c. Set difference is the only nonmonotonic operation in our RA).
• Read the LDL++ tutorial, up to Negation and Stratification (included).
• Using the tables/facts in example1.fac of the LDL++ tutorial write and run following queries:
  1. Write an LDL++ program to find the cities which are reachable from Austin, with their distance from Austin.
  2. Find which of the above city is the furthest from Austin. (You can express this query using stratified negation.)
  3. Write an LDL++ program to add up the population of cities in Texas. (Here you need recursive rules that exploit the lexicographical order of city names.)