Applied Mathematics for Database Professionals – Chapter 3

Some More Logic

This chapter is slightly shorter than the other chapters in the Mathematics section of the book, that however does not make it any easier. It continues on from where Chapter 1 finished. You can have a look at it, again via google books.

Starts off with a discussion of the various properties of the logical connectives. Then moves on to talking about Quantifiers. One way of turning a predicate into a proposition is by the use of quantification to say for how many possible values a parameter of a predicate actually meet a specific requirement.

The two fundamental quantifiers are universal quantification \forall (for all) and exitenstial quantification \exists (there exists). There follows some examples of these in action. An example might help clarify this:

\forall  x \epsilon N: x * 2   \epsilon N

The above can be read as “For all x that are members of the set N of natural numbers 2 times that value is also a member of the set of natural numbers”

Interesting point that when working with finite sets \exists can be treated as an iterated OR while the \forall can be treated as an iterated AND.

Quantification over the empty set is discussed. I fear that universal quantification over the empty set being always TRUE completely and utterly baffles me. Interestingly, wikipedia have this as a vacuous truth.

Moves on to discuss various properties of quantifiers, nesting, negation, distributive and various rewrite rules. I found this really quite challenging.

Finishes the chapter talking about normal forms (canonical form) is just a standard way of representing an object. In logic normal forms allow you to more easily compare two predicates. conjunctive normal form (CNF) is a conjunction (and) of clauses where a clause is a disjunction (or) of literals. disjunctive normal form (DNF).

As often seems to be the case as the mathematics section is building up a toolset for practical application later, normal forms are utilised later in the book in relation to data integrity constraints.

Advertisements

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

  1. Is that example from the book? Because it would very unusual to use a star to represent ordinary multiplication in mathematics. Usually you’d just write 2x.

    • Nope, that is not an example taken from the book.

      It may be my lack of mathematical knowledge showing through.

      I thought some kind of example would help a little in the blog article

  2. Jason,

    Good to see that you are able to keep up the chapter-a-week pace 🙂
    This time I’d like to point out an interesting quote on logic:

    “Logic is an analytical theory of the art of reasoning whose goal is to systematize and codify principles of valid reasoning. It has emerged from a study of the use of language in argument and persuasion and it is based on the identification and examination of those parts of language which are essential for these purposes.”

    Robert Stoll, SET THEORY AND LOGIC, Dover Publications, 1963

    I think it’s important to be aware of this: logic originates from studying natural language, and the way we humans use language to reason. And as it appears, we not only use the logical connectives, AND, OR, NOT, and IMPLICATION for this, but also the quantifiers EXISTS and FORALL. Which indeed are nothing else but iterated OR and iterated AND respectively. And with quantifiers, set theory comes into play, because quantification is done “over a set”.

    Databases are models of the real world. We talk about the real world in natural language. So what better way to (formally) specify ‘a model of the real world’, then to use the “analytical theory” of the informal vehicle we use when talking about the real world. Chapters 1-4 present the material of logic and set theory that will enable us to very precisely specify database designs.

    One more thing. I’ve mentioned in earlier posts that rewrite rules are very important. I cannot stress this enough. In chapter 3 some very important rewrite rules have been introduced. For instance with regards to transforming universal quantification into existential quantification and vice-versa. I’ll repeat just this one here:

    (Forall s in S: P(s)) == not(Exists s in S: not P(s))

    It shows how universal quantification can be rewritten into existential quantification. And if you look closely, it’s just an “iterated” version of the De Morgan rule, introduced in chapter 1.

    Why is this an important rewrite rule? Because SQL doesn’t support universal quantification. We only have the EXISTS quantifier available to us.

    So queries like “Give me the departments for which all employees in the department were hired before 1/1/2000”, which have in them a universal quantification (can you spot it?), will have to be transformed (using above rewrite rule) into “Give me the departments for which there doesn’t exist an employee who wasn’t hired before 1/1/2000”, to enable an easy translation into a SQL query.

    Knowing (and applying) the quantifier rewrite rules and, as pointed out before the implication rewrite rule, is one thing. Detecting them, when you talk about database designs, constraints in them, queries on them, is a whole other thing. The former you can learn (for instance by studying the AM4DP book :-)). The latter takes practice, lots of practice.

    Toon

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