Applied Mathematics for Database Professionals – Chapter 2

Set Theory

I think this chapter starts off less intimidating than the one on logic. Sets are quite a familiar concept from school and Tom Kyte is always extolling the virtue of “thinking in sets”. This chapter is available to peruse via google books.

Starts off with definition of a set as a collection of distinct objects each of which is a member (element) of the collection (set). The set is fully characterised by these elements. Two sets are the same if each element of one set is a member of the other, and vice versa.

Discussion of how to specify the elements of a set.

  • Enummerative: This is naming each element of the set individually.
  • Predicative: An element is a member of the set when the predicate with that element is true.
  • Substitutive: This uses an expression and a set from which you substitute values into the expression
  • Hybrid: This is a combination of the predicative and substitutive method.
  • In mathematics sets can be finite or infinite but with databases all the sets are finite. The cardinality of a (finite) set is the number of elements in the set.

    Discussion of subsets, supersets, and powersets. Basic operations on sets are described including the familiar union, intersection and difference (minus), the properties (commutivity, associativity, distributivity) of the operators are also described.

    Cartesian product is defined as the set of all ordered pairs of the elements of the two sets you are creating the cartesian product of, e.g.

    A:={1,2} and B:={3,4} 
    then 
    AxB = {{1,3}, {1,4}, {2,3}, {2,4}}
    

    update
    One of the hard parts of mathematics is that things need to be exact, so thanks again to Toon Koppelaars for pointing out that the above example is not the correct cartesian product!

    To try again:

    A:={1,2} and B:={3,4} 
    then 
    AxB = {(1;3), (1;4), (2;3), (2;4)}
    

    Ordered pairs in Applied Mathematics for Database Professionals use the ; to separate the coordinates of an ordered pair.

    Note that AxB does not equal BxA. It is non-commutative.

    The concept of ordered pairs is quite a crucial one in this book and operators \pi_1 and \pi_2 are introduced for choosing the first and second parts of an ordered pair. Note unlike the elements of a set the ordering of an ordered pair is important.

    Finally, the chapter ends with a series of exercises, which I’ve been finding useful to gauge my understanding of the chapters. As I say I found this chapter less hard going than the first chapter, but having read further on, one of the great things of the book is how you can see in later chapters the theory in these chapters being put to good use.

    Advertisements

    2 thoughts on “Applied Mathematics for Database Professionals – Chapter 2

    1. Jason,

      I need to correct your cartesian product example.

      Ordered pairs are represented using parenthesis (not curly brackets), and the elements of the pair are seperated by a semicolon (not a comma).
      In mathematics it’s all about precisely stating what is meant.

      So your example:

      {{1,3}, {1,4}, {2,3}, {2,4}}

      is just a set of four elements and each of those element in itself is again a set of two elements.
      This is not the cartesian product of A and B.

      AxB should be:

      {(1;3}, (1;4), (2;3), (2;4)}

      which is indeed a set of four elements and each of those elements is an ordered pair.

      Cheers,

      Toon

      PS. Beware of the next chapter (3). It’s about logic again and will introduce the important concept of quantification (over a set).

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s