Category Archives: Relational Model (Databases)

Some More Clean-Up Work: Propositions And States Of Affairs

Following Chisholm, I have been identifying propositions with states of affairs.  A proposition is a subset of the set of states of affairs.  The state of affairs of John grasping a doorknob at time t_0 in Chicago is a state of affairs that always occurs (or always fails to occur).   States of affairs like this one are propositions.  The truth (falsity) of a proposition is nothing but a certain state of affairs occurring (failing to occur).  I am ignoring the question, which is pestering me right now, of why then it seems so awkward to talk about a ‘true’ (‘false’) state of affairs.  From The Stanford Encyclopedia of Philosophy article on Roderick Chisholm:

Consider the state of affairs that is expressed by the sentence ‘Someone is walking’. Chisholm wanted to say that this state of affairs occurs whenever someone walks, and fails to occur at times when no one is walking. Other states of affairs are not like this. For them, it is impossible to sometimes occur and sometimes fail to occur. Chisholm claims that this provides the opportunity for an ontological reduction. We can define a proposition as a state of affairs of this latter sort — it is impossible for there to be times when it occurs and other times when it does not occur. A true proposition is thus one that occurs; and afalse proposition is one that does not occur. Chisholm thinks that we may understand the principles of logic to be about these propositions. By saying that a fact is a true proposition, Chisholm gains yet another ontological reduction ([P&O], 123).

Chisholm thought that in some cases it makes sense to speak of the location at which a state of affairs occurs. Suppose John walks in Chicago at a certain time. Then Chisholm would be willing to say that the state of affairs of John’s walking occurs in Chicago and at that time.

Those states of affairs that are not propositions are events.   I am going through this stuff a bit impressionistically; the chances of my making an error someplace are high.

The tuples in the body of a database relation are propositions.  That is to say, they are states of affairs.  In a conventional database, these are always states of affairs occurring now, and now, and now…. John is an employee of WIDGETS_R_US now, the ‘now’ being implicit in the presence of that tuple in the relation.   In a temporal database as described by Date and Darwen (TEMPORAL DATA AND THE RELATIONAL MODEL),  these are states of affairs that occurred during a time period, or are occurring now (“Since t_0….”), the relevant time periods being explicitly stated in the tuple.

Since propositions are nothing but states of affairs of a certain kind, the operations of the Relational Algebra are operations on states of affairs of that kind.  On the relation ‘Standing_To_The_RIGHT_Of’, for example, we can perform a RESTRICT operation that delivers to us the state of affairs of Don standing to the right of Genghis Khan, then perform a PROJECT operation on that derived relation to obtain just Don.

We will figure out later what to do with Don now that we have him.

My homage to Plato’s SYMPOSIUM for this post will be Matt Damon.  This time we are a bit further along on the way towards eros for mathematical beauty:

mattdamon2a

But let’s not forget it all originally stems from eros for gorgeous young men.

Advertisements

The Relational Algebra Gives Us Something (Or Somebody, Or At Least Someone)

Now onto trying to show how the Relational Algebra gives us ‘something’, ‘somebody’, ‘someone’, and so on.

When I talk about database relations in the following, I am, unless I state otherwise, talking about the abstract object, not those relations concretely realized in an RDBMS.

A brief explanation of the Relational Algebra:  Posit a world all of whose people are members of the set {John, Cliff, Charles, Genghis Khan, Leon Trotsky}.  Moreover, suppose that currently, the predicate:

 x is standing to the left of y

generates the Database Relation pictured below when all the members of this set are substituted for the parameters x and y:

TO_THE_LEFT_OF (0)
PERSON_ON_THE_LEFT PERSON_ON_THE_RIGHT
Charles Genghis Khan
Dan Leon Trotsky
Cliff Genghis Khan

(The above picture, by the way, is just that — a picture of the Relation.  It is not the Relation itself.)  As indicated by the number 0 in the name, this Relation is a base Relation, i.e., what we have before any operations are applied to it.

The Relational Algebraic operation RESTRICT is a function that takes the Relation pictured above as input and produces another Relation as output.  For example, the following RESTRICTion, expressed in Tutorial D:

TO_THE_LEFT_OF where PERSON_ON_THE_LEFT = ‘Charles’;  (Yes, I’ve suddenly gone from the flesh and blood Charles as member of a set to the name ‘Charles’; God only knows what confusions this sudden shift will introduce.)

generates the Relation pictured below:

TO_THE_LEFT_OF (1)
PERSON_ON_THE_LEFT PERSON_ON_THE_RIGHT
Charles Genghis Khan
Dan Leon Trotsky
Cliff Genghis Khan

The operation RESTRICT has given us a Relation comprising a single proposition expressed by the sentence ‘Charles is standing to the left of Genghis Khan.’  As indicated by the number 1, this is a Derived Relation, produced as output from a function that took as input the Base Relation.  The charcoal-grayed out portions of the picture are meant to convey that the derived relation is tied to the base relation in a way in which I will discuss later.

As with RESTRICT, the Relational Algebraic operation PROJECT takes the Base Relation as input and generates a Derived Relation as output.  The following RESTRICT and PROJECT operations, expressed in Tutorial D:

(TO_THE_LEFT_OF where PERSON_ON_THE_LEFT = ‘Charles’ ){PERSON_ON_THE_LEFT}

generates the Relation pictured below:

TO_THE_LEFT_OF (2)
PERSON_ON_THE_LEFT PERSON_ON_THE_RIGHT
Charles Genghis Khan
Dan Leon Trotsky
Cliff Genghis Khan

whose body is the set containing the tuple or proposition expressed by the sentence “Charles is to the left of somebody.”

But wait — all we see in this picture is the value Charles.  (Or, more precisely, the name ‘Charles’ appearing as a set of black pixels on a screen.)  Isn’t this a tuple in a one-place relation?  And if it is, wouldn’t it be a proposition belonging to one-place relation, a proposition such as “Charles laughs”, or “Charles runs”, or “Charles eats”?

Well, if it were such, it could be any proposition belonging to a one-place relation.  The only way to constrain which proposition this tuple is to just one proposition is to place it in its context, the source from which it is derived, i.e., the base relation TO_THE_LEFT_OF.  By performing the Projection, we are for the moment blacking-out the identity of Genghis Khan, the person to whom Charles is to the left, so that we can focus on the identity of Charles.  But we haven’t forgotten that we are working with the relation TO_THE_LEFT_OF, so we know that Charles is to the left of somebody.  We haven’t suddenly switched to the relations LAUGHS, or RUNS, or EATS.

To turn for the moment for relations concretely implemented in an RDBMS running in some stuff made out of the same substance as the red paint on the Golden Gate Bridge, complete chaos would ensue, the world would become a topsy-turvey place, objects would start falling up, if, say, a Projection on EMPLOYEE_NAME in the EMPLOYEE (select EMPLOYEE_NAME from EMPLOYEE) would result, not in the set of people employed by the company (more precisely, the set of propositions ‘John, employee of Widgets_R_US’, ‘Jesse, employee of Widgets_R_US’, and so on), but the set of people designated to live on Mars one moment, the set of ambassadors to Vietnam the next moment, and the set of of Pulitzer Prize winners the third moment.

So the meaning of a Projection on an attribute (“column”) of a relation is constrained by the relation from which it is standing out (“projecting”), so to speak.  The derived relation never ceases to, well, derive its meaning from the base relation.  It never ceases to be a derived relation.  Charles never ceases to be one member of a pair whose member on his right is being ignored or blacked-out for the moment.

(Compare this argument with C.J. Date’s argument in LOGIC AND DATABASES, pp. 387-391.)

Let’s trace then what happens, in this relational model, when we plug in Charles to replace x in the predicate:

Person x, to the left of somebody

The ‘somebody’ is not a parameter — no argument gets plugged into it — but it along with the x indicate that the base relation we are dealing with is TO_THE_LEFT_OF.  It tells us that one of the ‘central participants in the situation’ is some person to the right.  The relevant Relational Algebra Operations — the relevant RESTRICT and the relevant PROJECT — are then performed to generate the proposition:

Charles, to the left of somebody.

According to the Closed World Assumption, a Relation contains all and only those tuples — those propositions — those states of affairs — that obtain, and for which plugging in arguments to the parameters of the predicate defining the Relation results in a true sentence.  Therefore, each tuple in the Relation is paired with the truth value TRUE, and of course, within the Range comprising the two truth values, only the truth value TRUE.

So the set of tuples in a Relation and the set of Truth Values is a function.  So, finally — if I may end this string of ‘therefores’ and ‘so’s’ (“Feel free to come to the point when you finally decide what it is, I hear someone say”), when a single tuple is selected, as was done when the RESTRICT and PROJECT were performed on the Relation TO_THE_LEFT_OF, we can see this as the application of the function on that tuple, an application which returns TRUE.  So (this really is the final ‘so’ — I promise) plugging in the argument ‘Charles’ into the parameter x in the predicate:

x is to the left of somebody

triggers a RESTRICT and PROJECT on the Relation TO_THE_LEFT_OF, which in turn constitutes a selection of a single tuple in that relation, which in turn returns TRUE, which lets us regard the predicate as a function returning TRUE when ‘Charles’ is plugged into the parameter marked by x.

Just so, when the RESTRICT and PROJECT fail to select a tuple, as it does when we substitute ‘John’ for x (John is standing to the right of everyone else, including Genghis Khan), FALSE is returned.

Voila!  We now we have somebody (or, as the case may be, nobody).

It is clear that the predicate:

x is to the left of y

can be treated the same way.

Treating verbs aka predicates relationally this way — that is, as functions implemented by Relations and operations on Relations — has two advantages over simply seeing them as functions in the way described by Kroch and Santorini.  First, we get a semantics for ‘somebody’, ‘something’, etc.  Second, we have a way of conceptualizing in terms of operations of the Relational Algebra the select that occurs when, to use the verb laughs as our example, Luke is selected and the truth value TRUE is returned.  The notion of select is no longer a primitive.

 

Updated on 05/10/2012 to correct an obvious oversight.


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.


Predicate = Topic Structure In Tagalog Sentences

Titser ang….

Imagine a Tagalog speaker in the act of uttering a sentence, beginning with those words.  Not having yet uttered the noun phrase that is about to come after the ang, the speaker hasn’t yet come to the topic — what the utterance is about.  So far we, the speaker’s audience, have no handle on any definite person or object being talked about — this will come a bit later, after the ang noun phrase.  What we can reasonably guess, though, is that the person being talked about is identical with some member(s) of the set titser, i.e., the set of teachers.  (We can guess that, that is, if we are familiar with the notion of sets.)  To use the database theorist C.J. Date’s terminology,  we already know that the person, whoever he or she is, putatively belongs to the type titser.

Titser ang babae.

If the speaker’s utterance has not misfired — if his confidence is not misplaced that we will know whom he is talking about — then at the utterance’s conclusion we, his audience, will have identified from the context which person is being talked about.  The context can be either perceptual (say, the person has just walked into the room) or spoken (the person, say, was previously mentioned in conversation).  The identification is something happening at the pragmatic level.  (Warning:  I have recently picked up just enough linguistics to be a danger both to myself and to society at large.  I am now able to persuade myself that I can distinguish between the pragmatic, semantic, and syntactic levels of an utterance.)  Assuming the statement is true, we now know which member of the set of teachers is being talked about.  So the utterance has the effect of:  [Do I need to cash out this ‘has the effect of’?]

I embraced the summer dawn

One member of {A, B, C…} = this particular woman. (Where A, B, C … are members of the set of teachers.)

I embraced the summer dawn

I advance this analysis of Titser ang babae in an attempt to cash out the linguist Paz Buenaventura Naylor’s claim that the canonical Tagalog sentence (comprising predicate on the left + topic or ang phrase on the right) is an equality.  Consider the following English sentences, identical with or almost the same as the examples Naylor uses:

xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Teacher = the woman.

Beautiful = the man.

Left = the woman.

xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

These express in English the force of:   [Can I get away with the metaphor ‘force’?]

xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Titser ang babae.

Maganda ang lalaki.

Umalis ang babae.

xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

At first sight, Naylor’s claim is, I think, more intuitive in the case of Titser ang babae than it is in the other two cases. How is beautiful equal to this particular man?  What could that possibly mean?  Likewise, how is left (as in ‘left the room’ ) equal to this particular woman?  But if we cash out thse equations as:

xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

One member of {A, B, C…} = this particular woman.  (Where A, B, C, etc. are particular teachers.)

One member of {A, B, C…} = this particular man.  (Where A, B, C… are particular beautiful objects or people.

One member of {A, B, C…} = this particular woman. (Where A, B, C…are particular people ((or animals, or anythings else with agency)) who have left some place, e.g., a  particular room, a city, a country.) [Can I get away with restricting ‘left’ in the third example to leaving a particular place, as opposed to a job, a wife, a party, and so on?]

xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

… then the equality becomes much more intuitive in the case of the second and third examples.

If, like me, you like to think in terms of wildly undisciplined, not completely respectable pictures and metaphors, picture at the start of the utterance — Titser ang…. — a crowd comprising all the teachers in the world.  [How strict do I need to be in specifying this set?]  Our view of each teacher is fuzzed out or grayed out so that no teacher can be distinguished from another.  The utterance completes:  Titser ang babae.  The moment the utterance is understood, our view of one teacher in the crowd resolves itself.  We now clearly see one particular woman who is a teacher.  Likewise, gather in one’s imagination all the beautiful objects or people…and all the entities with agency who have just left a place…..  The same picture we used in the case of  Titser ang babae applies, mutatis mutandis, to the other two utterances.  When the utterance completes, our fuzzy picture gets resolved, and a particular beautiful man (Brad Pitt in A River Runs Through It or even in The Tree Of Life) appears, or a particular woman (Marlene Dietrich, say) who has just left this particular room.  Brad Pitt pops into view.  Marlene Dietrich pops into view.

The equation makes sense now in these two latter cases because one particular gets identified with another particular when we utter the sentences.   ‘This particular thing (veiled at the start of the utterance) is identical with that particular thing (known to speaker and audience through the context, i.e., pragmatically). ‘

xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

∃x ∈ titser: x = ang babae.

∃x ∈ maganda: x =  si Brad Pitt.

∃x ∈ umalis: x = si Marlene Dietrich.

xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

We make sense of the claim that the canonical sentence in Tagalog has a predicate = topic structure when we regard not just titser, but also maganda and umalis as names of sets.  One member of each set equals an entity named in the topic that has been identified pragmatically.  This will also start to make sense of Naylor’s intitially counter-intuitive claim that in Tagalog what look like verbs are actually nouns, i.e., names.

To use an even less respectable conceit (‘conceit’ used here as in the sense it is applied to the technique used by English Metaphysical Poets), it is as if we identified an unknown star in the morning with an already identified Evening Star.  The ang phrase codes old information:  we already know the Evening Star is the planet Venus.  The predicate codes new information:  we now know, by the end of the sentence, which bright object showing up in the morning is in fact identical with the Evening Star is in fact identical with the planet Venus.  It is as if something like this were happening with every Predicate = Topic Tagalog sentence….

All right.  Enough of strained metaphors … although this one at least lets me picture the function of the Tagalog predicate as coding new information and the Tagalog ang phrase as coding old information.  And lets me picture ‘start of utterance’ (morning) with ‘completion of utterance’ (evening).

*****

When I first started suffering under the delusion that I had some grasp of how Tagalog works vs. English, I pictured the canonical Tagalog sentence as a weighing scale:  one puts the predicate on the left side of the scale, then places the topic, the ang phrase, at the right side of the scale so that now the two sides are completely balanced, are completely level.  I contrasted this with the standard English sentence, say “The man threw the ball” which is “transitive” — i.e., energy flows into the ball from the man, energy gets transmitted from the man to the ball.

This first picture contrasting with the second was my first Aha-Erlebnis regarding Tagalog.  Balance and equality vs. transmission.  This Aha-Erlebnis gained strength when I encountered Naylor’s claim that the canonical Tagalog sentence has a Predicate = Topic structure, though I did not completely understand what that equation meant in the cases of (ostensible) adjectives and verbs.  (I say ‘ostensible’ because Naylor persuasively argues that the ‘verbs’ at least are really nouns — on the syntactic level — in Tagalog.)  I submit that we can understand this this equality by thinking in terms of sets, i.e., of types.  The canonical Tagalog sentence works, as it moves from start to completion, first, by restricting the range of things possibly being talked about to members of a set, then by changing the status of one object of that set from ‘currently unidentified’ to ‘identified’  by equating it with an object known from the context by the time the utterance completes to be the object being talked about.  Typically, that object, coded by the topic, constitutes old information of some sort:  everyone has seen Brad Pitt enter the room, for example, or he has been talked about previously.  And typically, the predicate codes new information, or information that hits one with a renewed force that calls for a likewise renewed predication: Brad Pitt is beautiful.  ∃x ∈ maganda: x =  si Brad Pitt.  Maganda si Brad Pitt.

UPDATE (12/10/2011):  Beiged out a metaphor that is, while still useful to me as unfinished lumber, is likely to be confusing to anyone else.  Tried to clarify the concluding sentence in red.

UPDATE (12/14/2011)  Added the ∃x ∈ <<name of set>> statements.