Homework Solution

Tuple Calculus (Tuple Relational Calculus)

-> Nearly all information gathered from http://en.wikipedia.org/wiki/Tuple_calculus

-> Part of the relational model used in database-query languages

-> Rules to define set of formulas F[S, type] given a database schema S:

Which we give the conventional semantics:

Thus we can make logical statements about the database that can be shown to be true or false given the database schema (which includes values in the database).

The example given in the Wikipedia article is

∀ t : {author, title, subject} ( ¬ ( Book(t) ∧ t.author = "C. J. Date" ∧ ¬ ( t.subject = "relational model")))

equivalent to the statement that every book by C.J. Date has relational models as its subject.

This could be expressed in a query expression so as to find an exception to the statement given the database schema, which takes the following form (this is another example from the article):

{ t : {name} | ∃ s : {name, wage} ( Employee(s) ∧ s.wage = 50.000 ∧ t.name = s.name ) }

My examples of query expressions and statements about databases, with translation:

1. { t : {ingredients, cooktime} | ∃ s : {ingredients, cooktime, servings} (s.cooktime < t.cooktime ∧ s.servings = 12 ∧ t.ingredients = s.ingredients ) }

--> For a given tuple with certain ingredients and cooking time, determine if there exists some other tuple with ingredients, cooking time, and servings produced such that the cooking time is shorter than that of t, the number of servings is 12, and the two tuples share the same value for the ingredients variable.

2. ∃ t : {flavor, toppings} (¬ (Sundae(t) ∧ t.flavor = “chocolate” ∧ t.toppings = [“sprinkles”, “M&Ms”]) )

--> There exists some sundae that isn’t comprised of chocolate ice cream and have sprinkles and M&Ms as its toppings.

3. ∀ t : {species, owner} ( Pet(t) ∧ t.owner = "John Doe" ∧ t.species = "dachshund" )

--> Everything in the database with a species and owner is a dachshund that is the pet of John Doe.