Category Archives: Functions

The Predicate Returns A Relation

We have seen that the predicate:

x is to the left of y

is mapped to the truth value TRUE when Charles is substituted for x and Genghis Khan is substituted for y.  The Relation TO_THE_LEFT_OF comprises all true propositions and only true propositions that get generated when values are substituted for x and y.  So the predicate is a function whose range is the truth value TRUE for every proposition that is included in the relation, and FALSE for every proposition that is not included in the relation.

I think, however, that we would get a slightly simpler account if we see the predicate as a function returning Relations comprising the single proposition TRUE, or the single proposition FALSE.  In the Relational Algebra, we would get a relation comprising the single tuple (and therefore proposition) TRUE if, after doing the Restriction that gives us:

Charles is to the left of Genghis Khan.

we then projected on the null set of attributes (“columns”).  We would then end up with Chris Date’s TABLE_DEE, that is, the Relation with cardinality 0 (o attributes, that is, 0 “columns”) and a single tuple.  TABLE_DEE is the Relation that corresponds to (I guess I should say ‘is identical with’) the weird classical logic proposition TRUE.  The predicate returns the proposition TRUE wrapped in the Relation TABLE_DEE when the Charles and Genghis Khan substitution is made.

Correspondingly, when John is substituted for x and Genghis Khan is subsituted for y, so that we get:

John is to the left of Genghis Khan.

the Restriction selects no tuple in the Relation TO_THE_LEFT_OF.  We then have a Derived Relation with a cardinality of 2 (i.e., the Relation has 2 “columns”) holding the null set of tuples.   If we then project on the null set of attributes, we end up with a Relation of cardinality 0 comprising 0 tuples.  Chris Date calls this Relation TABLE_DUM, and it holds the tuple, that is to say, the proposition FALSE.  The predicate returns the proposition FALSE wrapped in the Relation TABLE_DUM when the John and Genghis Khan substitution is made.

Thinking of the predicate as returning either TABLE_DEE or TABLE_DUM simplifies things a bit, because it means we never have to leave the Relational Algebra when modeling the predicate.  Everything gets explained in terms of just one set of operations, the operations of the Relational Algebra.





And One More Thing Before I Move On

It seems to me Kroch’s and Santorini’s rendition of this function:

(1)     [[ invite ]] = { Chris Andrew T ) ,
  David Andrew T ) ,
  Eddie Andrew F ) ,
  Chris Brian F ) ,
  David Brian F ) ,
  Eddie Brian T ) }

is off, since in a function the first entity in a given ordered pair can be mapped to one and only one entity.

Shouldn’t the function be represented this way:

(2)     [[ invite ]] = { Chris { ( Andrew T ) , ( Brian F ) , . . . }
  David Andrew T ) , ( Brian F ) , . . . }
  Eddie Andrew F ) , ( Brian T ) , . . . }


Or am I missing something obvious?

Trying To Make The Problem A Bit Clearer

In the hopes of making it a bit clearer why it is a problem, let me restate the question that I think the Relational Algebra will resolve.

So far we have been modeling sentences in which nothing is left unspecified.  Chris invites AndrewLukas laughs.  How could we model, however, sentences such as Chris invited someone, Someone invited Andrew, Someone invited someone, Joe ate something, Someone laughed … sentences in which at least one of the “central participants in a situation” is left unspecified?

‘Somebody’, ‘someone’, ‘something’ and so on pose a problem for the model presented in the post The Verb Considered As A Function.  Sets always comprise definite, clear-cut individuals.  Since functions are sets of ordered pairs, the primary and recursive functions discussed so far are pairings of definite entities.  What would it mean anyway to have a function that included an indefinite or unknown, entity, as if some function could be pictured this way:
brackets instead.

(1)     [[ laugh ]] = {   T,
  Eva F,
  Lukas T,
  Tina T }


How would we model a sentence “Somebody laughed” that is true, and a corresponding sentence “Somebody laughed” that is false?


The Predicate As A Truth Valued Function

So far we have been modeling sentences in which nothing is left unspecified.  Chris invites AndrewLukas laughs.  How could we model, however, sentences such as Chris invited someone, Someone invited Andrew, Someone invited someone, Joe ate something, Someone laughed … sentences in which at least one of the “central participants in a situation” is left unspecified?  We can model these sentences, I think, by applying the Relational Algebra to them — or, more precisely, to the propositions that underlie them.  In this post, I start laying the groundwork for showing how we can use the Relational Algebra to model sentences containing ‘someone’, ‘anyone’, and the like.

Let me begin by outlining the key premise behind Relational Database Theory: 

Predicates generate propositions which are either true or false.  A given Database Relation comprises all and only the true propositions generated by a given predicate.  (This is the Closed World Assumption.)  We can apply various operations of the Relational Algebra to the propositions contained in a Database Relation.

The key premise in Relational Database Theory talks about predicates.  What, then, is a predicate?

What the database theorist C.J. Date calls a predicate is what Kroch and Santorini call, in the primer on Chomskyan linguistics quoted from in the post below (The Verb Considered As A Function) a verb.  Date explains what a predicate is better than I can, so let him speak (LOGIC AND DATABASES THE ROOTS OF RELATIONAL THEORY, Trafford Publishing, Canada, 2007, p. 11):

A predicate in logic is a truth valued function.

In other words, a predicate is a function that, when invoked, returns a truth value.  Like all functions, it has a set of parameters; when it’s invoked, arguments are substituted for the parameters; substituting arguments for the parameters effectively converts the predicate into a proposition; and we say the arguments satisfy the predicate if and only if that proposition is true.  For example, the argument the sun satisfies the predicate “x is a star,” while the argument the moon does not. 

Let’s look at another example:

x is further away than y

This predicate involves two parameters, x and y.  Substituting arguments the sun for x and the moon for y yields a true proposition; substituting arguments the moon for x and the sun for y yields a false one. 

The key premise mentions Database Relations.  What, then, is a Database Relation?

The concept of a Database Relation is an elaboration on the concept of a Relation as defined in mathematics.  In mathematics, a Relation is defined as the subset of the Cartesian Product of two or more sets.  (What a Cartesian Product is will be obvious from the example.)  For example, in the sets {John, Charles, Cliff, Dan} and {Leon Trotsky, Genghis Khan}, the Cartesian Product is { (John; Leon Trotsky), (John; Genghis Khan), (Charles; Leon Trotsky), (Charles; Genghis Khan), (Cliff; Leon Trotsky), (Cliff; Genghis Khan), (Dan; Leon Trotsky), (Dan; Genghis Khan)}.  If, now, we pick out a subset of this Cartesian Product by seeing who happens to be standing to the left of whom at the moment, we get this Relation:  { (Charles; Genghis Khan), (Cliff; Genghis Khan), (Dan; Leon Trotsky)}. 

In other words, our Relation is what we get when we start with the predicate:

x is standing to the left of y

and plug in values for x from the set {John, Charles, Cliff, Dan} and values for y {Leon Trotsky, Genghis Khan}, throw away all the false propositions that result, and keep all of the true propositions.

Let me go out on a limb, then, and say that a proposition (remember, our key premise mentions propositions) is a tuple, that is to say, an ordered pair (for example, (Charles, Genghis Khan) ) in a Relation.  (Please, pretty please, don’t saw this limb off.) 

This means then that a proposition is a state of affairs ala R.M. Chisholm.  For example, the proposition Charles is standing to the left of Genghis Khan is the state of affairs comprising the flesh and blood Charles standing to the left of the flesh and blood Genghis Khan.  Propositions as states of affairs are the meaning of sentences… But I digress.

Back to Relations. 

A Database Relation, I have said, is an elaboration of a Mathematical Relation.  A Database Relation comprises a Heading consisting of ordered pairs of (Name Of Type; Type) and a Body consisting in a set of ordered pairs (Name Of Type, Value).  A type is a set, for example, the set of integers, the set of words in a given language, the set of people, the set of cities in the world, and so on.  A value of a type is a member of the set identical with that type.  I will leave name undefined. 

A Database Relation is an abstract object;  it is either an object really existing in some Platonic Heaven someplace or it is a fiction, depending upon which theory of abstract objects is the correct one.  Database Relations form the conceptual skeleton of databases concretely implemented by an RDBMS (Relational Database Management System) functioning inside a physical computer, but at least at the moment I am not talking about physical computers and the software they run.  I am talking about the abstract object, something that has the same status as the number 3 or the isoceles triangle. 

Why do I want to talk about Database Relations rather than Mathematical Relations?  It will be easier in the  posts that (hopefully) will follow to illustrate the Relational Algebra operations Projection and Restriction.  I know how to apply these operations to Database Relations; I am not sure how to apply them to Relations simpliciter.   Projection and Restriction are the Relational Algebra operations which, I claim, will give us a model for sentences such as Joe ate something. 

I’ve laid the groundwork for such a model; now let me go on to produce the model.