Conference turris::languages

120.0. "Some tedious albegra!" by DUBSWS::D_OSULLIVAN (Bovine TD) Fri Nov 28 1986 10:05

I'm putting this in here as an afterthought.  I'm dealing with it in relation
    to Rdb.  It does bring up points related to languages however, so
       someone here may be interested.  You won't be surprised to 
          hear that its origins are in the olive groves of 
    			Academia!
    
    			\Dermot/
Dear Mr. O'Sullivan,

A brief note to elucidate my comment that a logic using Tables 
(flat-files) as operands and containing only three operators 
SELECT+ PROJECT+ JOIN is not "relationally complete".  My 
contention was that you needed at least five appropriate 
operators to achieve this.

Two points of clarification are required.  One, the 
interpretation of the operators;  two, the significance of the 
phrase "relationally complete".

My interpretation of the operators is that they were used as 
operators within the context of relational algebra independent of 
any particular compter language.  In this sense SELECT and 
PROJECT are monadic operators and JOIN is a dyadic operator.  
This is how you very appropriately and effectively presented 
them.  I take the point that the JOIN presented was the eqi-join, 
and that JOIN using any of the other comparators (e.g unequal 
join) should be presumed.  Even presuming this I believe my 
contention holds.

The phrase "relationally complete" is used in the context of the 
relational calculus.  In general terms a logic that is 
relationally complete would enable one to extract from a set of 
tables any information that was implicit in them and that could 
be expressed as a sentence within first-order predicate logic.  
For example, given a database of four tables; one for teachers, 
one for pupils, one for subjects and one showing what teachers 
taught (over several years) what subjects to what pupils for how 
long; sentences (expressions) of the following kind could be 
expressed and resolved:

	"What male teachers taught a continental language to a 
female pupil at least as long as the least time for which any 
female teacher taught such a language to a male pupil."

The first three tables are qite easy to sketch in one's mind; the 
fourth table would have headings such as 

	TH   SH   PH   Quantity (Time)

Appropriate attributes are assumed in the other threee tables.  A 
technical definition of the term "relationally complete", is 
given in a basic article in the literature, viz. E. F. Codd, 
"Relational Completeness of DB Sublanguages", in DB Systems, 
Prentice-Hall (1972).  This article also showed that any 
statement in "relational calculus" in this sense can be converted 
into a semantically equivalent algebraic expression, using a 
relational algebra of eight basic operators.  Although these 
operators are basic in the sense of mapping fundamental 
intuitional monoadic and dyadic operations on one/two tables, 
three of them can be reduced to a combination of the other five.  
The eight operators in question are

	Monadic:  SELECT;  PROJECT
	
	Dyadic:   JOIN; UNION; INTERSECT; MINUS; TIMES; DIVIDEBY

Hence my contention boils down to claiming that all the operators 
of relational algebra and hence any statement within the 
relational calculus can be expressed using the two monadic 
operators and three dyadic operators (e.g. UNION, MINUS, TIMES).  
This can be shown using some quite clear but slightly tedious 
algebra.  My contention that it needs at least three dyadic as 
well as two monadic operators, remains to be disproved.  I would 
be happy though surprised to see this done.  Indeed I think it 
would create quite a stir in relational data base theory.

I recognise that a specific computer language which has only 
these three verbs might very well provide some of the additional 
functionality required by using adverbs (e.g. MISSING) as 
conditioners to verbs.  You will realise however that this 
approach raises questions about the independence of the logical 
scope of the verb and its adverbs, which do not arise in a 
language which provides seperate operators for these functions.  
It could also have implications for efficiency of operation in 
situations where several sequences of operations were logically 
equivalent but operationally distinct (e.g. a commutitative set 
of operators).  Unless one knew a particular language quite well 
it might be difficult to clarify these questions.

I apologise if my way of expressing this contention seemed too 
abrasive to you.  Time pressures on these occasions tends to make 
for over-sharp articulation of points of view.

I look forward to any views you might have on these or related 
topics.

Yours Sincerely    etc.

P.S.	To illustrate the way in which the algebra works suppose 
we want to get the names of the teachers who (over the period 
recorded by the tables) taught all pupils; we could express this 
in relational algebra by the expression

	((TSP [TH, PH] DIVIDEBY P[PH]) JOIN T) [TNAME]

where the tables were named T; S; P and TSP respectively, where 
TH, PH were attributes providing unique identifiers for teachers 
and pupils respectively and where TNAME was an attribute of the 
teacher table giving names of teachers.