CSc 8710, DDLP - Spring 2007
Exam 3: Take Home (Due: Monday, 7 May, 2007 - by midnight)
Electronic submission under assignment 6
NOTE: This exam should be done individually WITHOUT any 
collaboration. 
------------------------------------------------------------
(1) Consider the following deductive database:

    r(1,2).
    r(2,3).
    r(3,4).
    p(X,X) :- r(X,Y), not q(Y).
    q(X) :- r(Y,X), not p(X,Y).

    (a) Using the paraconsistent relational model and algebra compute the 
        Fitting model. Write the algebraic expressions for paraconsistent 
        relations P and Q. Show the work after each iteration including the 
        intermediate steps (complement, join, project etc) of evaluating 
        the algebraic expression. 

    (b) Compute the well-founded model. Show the interpretation after each
        iteration.

(2) Are the union, projection, selection, and join operators defined
    for the paraconsistent relations monotonic? For the operations that
    are monotonic, write a proof and for the ones that are not monotonic
    show a counter example. FYI: A paraconsistent relation  is
    less than (i.e. subset) of paraconsistent relation  if R+ is a
    subset of S+ and R- is a subset of S-.

(3) Consider the following transaction database created from the item set
    I = {B,C,E,F,G,H,L,M,N,P,R,S,T,W}

    TID	Items
    -------------------------
    10   C,B,R,T,E
    11   M,N,W,S,P
    12   F,N,R,G,E
    13   C,B,R,S,E
    14   C,N,W,L,P
    15   C,B,R,H,E
    16   M,N,R,L,E
    17   C,N,R,S,P
    18   C,N,W,S,P
    19   M,N,R,L,E
    20   F,N,R,H,P
    21   F,B,R,S,E
    22   M,B,W,G,P
    23   F,N,R,H,P
    24   M,B,W,G,P
    25   C,N,W,L,P
    26   C,N,W,S,P
    27   F,N,R,G,E
    28   C,B,R,S,E
    29   F,N,R,G,E


    Mine association rules by hand from this dataset by faithfully 
    following the AprioriTid algorithm with minimal support = 25% and 
    minimal confidence 90%. That is, start by generating candidate 
    itemsets and frequent itemsets level by level and after all frequent 
    itemsets have been generated, produce from them all the rules with 
    confidence greater than or equal to the min. confidence. 
    Show values after each iteration.

    Repeat for minimal support 50% and min confidence 90%

    Repeat again for minimal support 75% and min confidence 90%

(4) (a) Code the Large Item Set generation part of the AprioriTid algorithm in 
        your favorite language (if you code it in my favorite language, Prolog,
        you get extra credit!). For Prolog implementation, the database items 
        and transactions are available in a file (say db.pl) as:

    items([1,2,3,4,5]).
    db([1,3,4]).
    db([2,3,5]).
    db([1,2,3,5]).
    db([2,5]).

    A sample run is shown below:

    $ pl

    ?- ['db.pl'].
    % db.pl compiled 0.00 sec, 1,276 bytes

    Yes
    ?- ['ap.pl'].
    % ap.pl compiled 0.00 sec, 5,896 bytes

    Yes
    ?- aprioriTid(2).
    [1]
    [2]
    [3]
    [5]
    [1, 3]
    [2, 3]
    [2, 5]
    [3, 5]
    [2, 3, 5]

    Yes
    ?- halt.

    Note: The top level predicate is aprioriTid(N) where N is the 
          Minimum Support.

    (b) Code the second part of the Apriori algorithm that generates association rules.
      The predicate should be called genARs(F,C,R), where F is the set of frequent
      item sets and C is the minimum confidence level, and R is the output set of association
      rules of the form [lhs,rhs,c] where lhs is the left hand side item set of the rule,
      rhs is the right hand side item set of the rule, and c is the confidence of the rule. 
      You should print R, one rule per line.