Tag Archives: set theory

Learning the Relational Model – Predicate Logic (Part II)

In the first part we have seen the concept of Set theory and relational theory. In this part we are going to learn about the concept of predicate logic.

Part II – Predicate Logic

What is logic?

Logic is a language for reasoning and is a collection of rules we use when doing reasoning. In logic we are interested in true or false of statements, and how the truth/falsehood of a statement can be determined from other statements. There are various types of logic such as logic of sentences (propositional logic), logic of objects (predicate logic), logic involving uncertainties, logic dealing with fuzziness, temporal logic etc.

Propositional logic is logic at the sentential level. The smallest unit we deal with in propositional logic is a sentence. Sentences considered in this logic are not arbitrary sentences but are the ones that are true or false. This kind of sentences is called proposition. For example, “Grass is green”, and “2 + 5 = 5” are propositions. The first proposition has the truth value of “true” and the second “false”. But “Close the door”, and “Is it hot outside?” are not propositions. Also “x is greater than 2”, where x is a variable representing a number, is not a proposition, because unless a specific value is given to x we cannot say whether it is true or false, nor do we know what x represents.

Let P be the proposition “It is snowing”, Q be the proposition “I will go the beach”, and R be the proposition “I have time”, then the English sentence, “I will go to the beach if it is not snowing” is restated as “If it is not snowing, I will go to the beach”. This can be represented as symbols as below:

¬P -> Q

The symbols are called connectives and below is the list of connectives and there meaning.

¬ – NOT

^ – AND

v – OR

-> – IF THEN (or IMPLY)

<->  – IF AND ONLY IFF

Similarly, “It is not snowing and I have time only if I will go to the beach” is restated as “If it is not snowing and I have time, then I will go to the beach”, and it is translated as (¬P ^ R)  -> Q.

Predicate Logic

 

The propositional logic is not powerful enough to represent all types of assertions that are used in computer science and mathematics, or to express certain types of relationship between propositions such as equivalence. For example, the assertion “x is greater than 1”, where x is a variable, is not a proposition because you cannot tell whether it is true or false unless you know the value of x. Thus the propositional logic cannot deal with such sentences. However, such assertions appear quite often in mathematics and we want to do inference on those assertions.

A predicate is a verb phrase template that describes a property of objects, or a relationship among objects represented by the variables.

Consider the following sentences:

  1. “John gives the book to Mary”
  2. “Jim gives a loaf of bread to Tom”
  3. “Jane gives a lecture to Mary”

We can derive a template here. The template is “……gives……to…..”. This template is called a predicate and it describes a relationship among three objects. The predicate can be written as G(x, y, z). The x, y, and z are the variables. So G(John, Book, Mary) represents “John gives the book to Mary and G(Jane, lecture, Mary) represents “Jane gives a lecture to Mary”.

I’m omitted some other aspects of predicate logic like, quantifiers, well-formed formula (wff) etc. since these are not relevant in our discussions on relational model at present.

Next

So we have covered two fundamental theories of relational model viz. set theory and predicate logic. In the next section we will merge these concepts to build the relational model

Leave a comment

Filed under Basics, Theory

Learning the Relational Model – Basic Set Theory (Part I)

This blog series on Relational Model is my attempt to understand the foundation of relational model of database. My intention is to learn and understand how Edgar F Codd designed the relational model, the basis of the model and how this is implemented in the relational database.

Introduction

Edgar F Codd built the foundation of relational model of database above two fundamental mathematical concepts viz. Set theory and predicate logic. The basic set theory is explained in this part of the series.

Sets and Relations

A set is a collection of distinct objects. For example a fruit basket is a collection of fruits and can be represented as B = {Apple, Orange, Grape}. Set of employees in a particular firm E = {Alice, Bob, Charlie}. There can be empty sets as well. For example an empty fruit basket, B = {}.

We know that the algebra of numbers include many operators like addition (+), subtraction (-), multiplication (X), division (/) etc. Likewise algebra of sets includes its own collection of useful operators. Like the operators of arithmetic, some of the set operators combine two sets and yield a set. These are the set operators.

  1. Union

Let A and B be sets with the same universe U. The union of A and B, denoted AB, is the set containing those elements of U that are either elements of A or elements of B (or elements of both). The union of {1, 2, 3} and {2, 3, 4} is the set {1, 2, 3, 4}

  1. Intersection

Let A and B be sets with the same universe U. The intersection of A and B, denoted A∩B, is the set containing those elements of U that are both elements of A and elements of B. The intersection of {1, 2, 3} and {2, 3, 4} is the set {2, 3}

  1. Set Difference

Let A and B be sets with the same universe U. The set difference of A and B, denoted A\B, is the set containing those elements of U that both elements of A and non-elements of B. The set difference {1,2,3} \ {2,3,4} is {1}

  1. Cartesian Product

Let A and B be sets with the same universe U. The Cartesian product of A and B, denoted by A X B, is the set whose members are all possible ordered pairs (a,b) where a is a member of A and b is a member of B. The Cartesian product of {1, 2} and {red, white} is {(1, red), (1, white), (2, red), (2, white)}.

  1. Power Set

Power set of a set A is the set whose members are all possible subsets of A. For example, the power set of {1, 2} is { {}, {1}, {2}, {1,2} }

 How can we apply this to data? What it says is everything can be collected to a set. That is a set of employees, a set of customers, a set of orders, a set of addresses, a set of products etc. If we can define an entity as a set of data, then we can also apply the set operators! For example, we can derive a set of vehicle by applying the union operator on a set of cars and set of bikes. We can find a set of both English speaking and Hindi speaking people by applying the intersect operator on the set of English speaking people and the set of Hindi speaking people. Since set operations are also associative and commutative we can combine the sets in many combinations and get different result sets (I am not going in detail to the associative and commutative properties of sets, since we have already studied this for numbers in high school classes).

Multiset

Based on the definition, set do not allow duplicates. However the idea of multiset has been introduced to allow more than one similar object (or duplicate object). Multiset is also called bag. Multiset and operations on multisets are very much similar to set. I will explain the practical importance of multiset later in this series.

From Set to Relation

A relation in mathematics is an association between various objects. Relation can also be represented by a set. A relation is a set of ordered pair and the pair has certain association. For example, let us consider a set of employee, E = {Alice, Bob, Charlie}, and a set of department D = {Sales, Purchase, Marketing}. So a relationship “is of department”, R can be represented as R = {(Bob, Marketing), (Alice, Sales), (Charlie, Sales)} and this can be read in English as ‘Bob is of department Marketing’, ‘Charlie is of department Sales’ etc. There are two elements in the result set, employee name and department name, a set of double. This can be triple, quadruple, quintuple, sextuple, septuple, etc. to n-tuple. This is generalized to a term called tuple. So in the above relation (Bob, Marketing) is a tuple and (Alice, Sales) is another tuple and so (Charlie, Sales).

Next

In the next part of the series we will see the predicate logic, the next fundamental concept of relational model.

 

Leave a comment

Filed under Basics, Theory