1. Exercise 3 on page 154.
2. Exercise 4 on page 155.

1. direct redundancy detection (30 points). Have Linneus detect potential "direct'' redundancy in the database. Here the redundancy occurs when the newest user statement is implied by existing facts via transitivity or by the reflexive property of ISA.

   > A sockeye is a salmon.
   I understand.
   > A salmon is a fish.
   I understand.
   > A sockeye is a fish.
   You don't have to tell me that.
   > OK
   I don't understand.
   > A spade is a spade.
   You don't have to tell me that.
   > A sockeye is a salmon.
   You told me that earlier.
   

2. simple indirect redundancy detection (20 points). Have Linneus detect and remove simple indirect redundancy. Here the newest statement makes an earlier statement redundant because the older statement could now be derived using transitivity. This is a simple case involving only three relevant propositions.

   > A hawk is a bird.
   I understand.
   > A hawk is a raptor.  
   I understand.
   > A raptor is a bird.
   Your earlier statement that a hawk is a bird is now redundant.
   

3. intermediate indirect redundancy detection (20 points). Have Linneus detect and remove indirect redundancy in which a single earlier statement becomes implied by a chain of three or more statements including the newest one.

   > A hawk is a raptor
   I understand.
   > A hawk is an animal
   I understand.
   > A bird is an animal
   I understand.
   > A raptor is a bird
   Your earlier statement that a hawk is an animal is now redundant.
   

4. complex indirect redundancy detection (10 points). Have Linneus detect and remove multiple indirect redundancies in which any number of earlier statements become implied by chains of two or more statements including the newest one.

   > A chinook is an organism.
   I understand.
   > A sockeye is a salmon.
   I understand.
   > A fish is an animal.
   I understand.
   > A sockeye is an organism.
   I understand.
   > A chinook is an animal.
   I understand.
   > A chinook is a salmon.
   I understand.
   > A sockeye is an animal.
   I understand.
   > A fish is an organism.
   I understand.
   > A salmon is a fish.
   The following statements you made earlier are now all redundant:
   a chinook is an organism;
   a sockeye is an organism;
   a chinook is an animal;
   a sockeye is an animal.
   

• Cycle Detection and Elimination. Because the ISA relation is a partial order, it must obey the antisymmetry property, which states that if x R y and y R x, then x = y. Because of transitivity, this means than in any cycle, such as a R b, b R c, and c R a, it must be the case that a = b = c. When the user inputs statements that form such a cycle, your program should detect that a cycle would be formed by the latest statement, if processed normally. It should report that to the user and then perform the following changes to the database: Determine which node is the starting point in the cycle (for example x when x R y and y R x are input in that order). Make all the other nodes in the cycle become "aliases" of the starting node, and merge them into the starting node. That means any edge involving one of these nodes has one of its endpoints replaced by the starting node. The program should be able to use the aliases in further interactions. An example is given below.

  > A creature is a being.
  I understand.    
  > A being is a living-thing.
  I understand.    
  > A living-thing is a creature.
  I infer that creature, being, and living-things are all names
  for the same thing, and I'll call it creature.
  > A bug is a creature.
  I understand.
  > Is a bug a being?
  Yes.
  > Why is a bug a being?
  Because a bug is a creature, and being is another name for creature.
  > A living-thing is an organism.
  I understand.
  > Is a bug an organism?
  Yes.
  > Why is a bug an organism?
  Because a bug is a creature, and a creature is an organism.
  

Each student should Turn in a file PartI.txt and a file PartII.py.
Your PartI.txt file should contain your name and the answers to the questions in Part I. Your PartII.py file should begin with a multiline string that gives, on the first line, your name, and on the next four lines, the status of your solutions to the Part II and then an indication of whether you did the extra-credit option. Here is an example.

'''PartII.py
John Doe, CSE 415, Spring 2017, University of Washington
Instructor:  S. Tanimoto.
Assignment 2 Part II.  ISA Hierarchy Manipulation

Status of the implementation of new features:

All forms of redundancy detection and processing are working.
Extra credit (Cycle detection and processing) implemented and working.

'''

The rest of your file PartII.py should contain a version of the Linneus program that provides the implementation of the features according to your status comments.

If necessary, substantial updates and corrections will be posted here and mentioned in class or on GoPost.

After submitting your solution, please answer this survey