a union is always a join!
paul c
It is inescapable that every relation is a join (eg., Heath's theorem).
So every relvar points to a join. If we can't 'delete' through a join,
we can't delete from any relvar (my father, who thought a disk buffer
was a polishing material could have concluded this - also, I surmise, we
can't logically express some number of otherwise possible relations
when we have some purpose besides defining a 'view').
The reason for every relation being a join has nothing to do with the
expression that forms a join 'view'. I think it's a consequence of
Codd's algebra that every relation that has more than one subset of
attributes is a join of two or more relations. By Heath, there will
always be two heading subsets (at least one of them having the same
heading as the relation) that will determine the other possible pairs of
heading subsets in a join. Because the join on all of a relation's
attributes with any subset of them is algebraically equal to the
relation, it looks to me that the number of possible and irreducible
join expressions is at least equal to the number of subsets of
attributes in a relation heading. (This is implicit. Explicit
constraints may have a number of expressions that are fewer and still
sufficient to express all the possible expressions.)
For the same reason, every 'insert' is through a join, even if the
'insert' is also to a 'view' formed by union. One can equally say that
some relations involve union, but this doesn't change the fact that they
are also joins, in other words, not all joins are algebraically equal to
some union or other, ie., if a relation is formed by join, it is not
always also a union.
If so, it should be far more productive to design a language based on
axioms that are universal, the theorems that are always true, rather
than on statements that are true only sometimes.
Brian Selzer
"paul c" <toledob...@oohay.ac> wrote in message
news:Pkv8l.42236$em5....@newsfe22.iad...
> Criticisms, please (preferably ones based on some formal logic or other).
>
I think your reasoning is circular: A relation is a join because it can be
joined to a projection of itself over a subset of its own heading?
rpost
>Criticisms, please (preferably ones based on some formal logic or other).
>
>It is inescapable that every relation is a join (eg., Heath's theorem).
As Brian writes, this is one step too far. Every relation can be
decomposed into smaller ones based on its nontrivial functional
dependencies, but if it hasn't any - and the resulting relations don't -
it is only a join of itself.
Perhaps by join you mean something like the AND in Darwen's 'A New
Relational Algebra' (thanks for giving its URL earlier), which has the
join and and union of relational algebra as special cases. We can also
decompose relations by writing them as the unions of other relations
(someone I know wrote a PhD thesis about it), but Heath isn't about that.
>So every relvar points to a join. If we can't 'delete' through a join,
>we can't delete from any relvar (my father, who thought a disk buffer
>was a polishing material could have concluded this - also, I surmise, we
>can't logically express some number of otherwise possible relations
>when we have some purpose besides defining a 'view').
I don't follow. If we know the dependencies,
some deletions are possible, while others aren't.
How is this relevant if you don't make a distinction between 'base'
and 'virtual' relations? (Or 'time varying' relations and views,
whatever.)
>The reason for every relation being a join has nothing to do with the
>expression that forms a join 'view'. I think it's a consequence of
>Codd's algebra that every relation that has more than one subset of
>attributes is a join of two or more relations.
If by 'subset of attributes' you mean 'key', you're right.
>By Heath, there will
>always be two heading subsets (at least one of them having the same
>heading as the relation) that will determine the other possible pairs of
>heading subsets in a join.
Heath has an 'if' clause; aren't you overlooking it?
>Because the join on all of a relation's
>attributes with any subset of them is algebraically equal to the
>relation, it looks to me that the number of possible and irreducible
>join expressions is at least equal to the number of subsets of
>attributes in a relation heading. (This is implicit. Explicit
>constraints may have a number of expressions that are fewer and still
>sufficient to express all the possible expressions.)
Yes, but what are trivial joins good for?
>For the same reason, every 'insert' is through a join, even if the
>'insert' is also to a 'view' formed by union.
An insert extends a relation vertically (it adds tuples); a relational
algebra join horizontally (it extends tuples with attributes and values),
but when projecting these attributes away again, hasn't added anything).
An insert can be expressed as a (relational algebra) union of the existing
relation with the inserted tuples, but no nontrivial r.a. union is a
r.a. join (and vice versa). Using the term 'join' for Darwen's AND
operator, which combines r.a. union and join, doesn't change this.
What are you trying to achieve?
>One can equally say that
>some relations involve union, but this doesn't change the fact that they
>are also joins, in other words, not all joins are algebraically equal to
>some union or other, ie., if a relation is formed by join, it is not
>always also a union.
In the relational algebra, a nontrivial union is never a join or vice versa.
What does combining them into "AND" buy you?
>If so, it should be far more productive to design a language based on
>axioms that are universal, the theorems that are always true, rather
>than on statements that are true only sometimes.
I don't see what this has to do with anything you wrote before.
--
Reinier
paul c
> paul c wrote:
>
>> Criticisms, please (preferably ones based on some formal logic or other).
>>
>> It is inescapable that every relation is a join (eg., Heath's theorem).
>
> As Brian writes, this is one step too far. Every relation can be
> decomposed into smaller ones based on its nontrivial functional
> dependencies, but if it hasn't any - and the resulting relations don't -
> it is only a join of itself.
All relations have at least n+1 fd's, even if trivial, where n is the number of attributes. All relations with at least one attribute (all but 'Dee') are a join of at least two (non-empty) relations.
> Perhaps by join you mean something like the AND in Darwen's 'A New
> Relational Algebra' (thanks for giving its URL earlier), which has the
> join and and union of relational algebra as special cases. We can also
> decompose relations by writing them as the unions of other relations
> (someone I know wrote a PhD thesis about it), but Heath isn't about that.
> ...
<AND> or the equivalent in another algebra is the only way to understand what join and union really mean, ie., are actually capable of being interpreted as. Some 'unions' can only be expressed as the union of themselves and an empty relation. I think it is helpful to understand union from some formal definition that acknowledges the logical possibility that two relations may not be 'union' compatible, eg., the '<OR>' operation or equivalent. Understanding relation structure based on empty relations seems as pointless/useless to me as understanding relational complement as being 'simple' complement. In fact, I'd rather call simple complement the vague complement and relative complement the exact complement. Why eschew a more precise interpretation when it's staring us in the face?
> algebra join horizontally (it extends tuples with attributes and values),
> but when projecting these attributes away again, hasn't added anything).
> An insert can be expressed as a (relational algebra) union of the existing
> relation with the inserted tuples, but no nontrivial r.a. union is a
> r.a. join (and vice versa). Using the term 'join' for Darwen's AND
> operator, which combines r.a. union and join, doesn't change this.
>
> What are you trying to achieve?
> ...
Originally, the most potent axioms for an implementation language that follows McGoveran's suggestions, ie., ones that recognize relation structure as opposed to how a relation value may have been arbitrarily formed. The way most people talk of Codd's algebra is simplistic because they have typically not tried to interpret it, probably have never even read it, for example, in the above, what do horizontal and vertical coordinates have to do with anything relational?. This is faux technocracy, usually involving what de Bono called porridge words which in this case are additional lingo to disguise a lack of basic understand (and which is how I believe Codd's algebra is usually 'taught', or thought to be 'taught'. But more to the point, I continue to be amazed that people claim they can 'insert' a tuple to a relvar but cannot 'delete' that very tuple! (vice-versa too.) I think when they say they can't delete, what they are really saying is that they can't delete a tuple that
is not in the join! The same goes for asserting and retracting a proposition in general. I've no doubt that it might be difficult to retract a proposition that one has never asserted! In a way, this is no surprise to me and I still don't know why people think it is a problem, when all human affairs contain much mumbo-jumbo that is logically make-believe. Now that you mention it, another goal would be to prevent geometric interpretations of the basic algebraic structures! Sounds like tables or arrays are getting mixed up with relations.
Brian Selzer
between your ears.
~(p /\ q) = ~p \/ ~q
So if ~(p /\ q), then which is false? p? q? both? All we can determine
for certain is that it is definitely not neither.
"paul c" <toledob...@oohay.ac> wrote in message
news:Gea9l.52558$u17...@newsfe20.iad...
rpost
>rpost wrote:
>> paul c wrote:
>>
>>> Criticisms, please (preferably ones based on some formal logic or other).
>>>
>>> It is inescapable that every relation is a join (eg., Heath's theorem).
>>
>> As Brian writes, this is one step too far. Every relation can be
>> decomposed into smaller ones based on its nontrivial functional
>> dependencies, but if it hasn't any - and the resulting relations don't -
>> it is only a join of itself.
>> ...
>
>All relations have at least n+1 fd's, even if trivial, where n is the
>number of attributes. All relations with at least one attribute (all
>but 'Dee') are a join of at least two (non-empty) relations.
Yes, trivial ones: one is the relation itself.
Nontrivial ones exist only when the relation has (nontrivial)
join dependencies, e.g. a (nontrivial) key.
>> Perhaps by join you mean something like the AND in Darwen's 'A New
>> Relational Algebra' (thanks for giving its URL earlier), which has the
>> join and and union of relational algebra as special cases. We can also
>> decompose relations by writing them as the unions of other relations
>> (someone I know wrote a PhD thesis about it), but Heath isn't about that.
>> ...
>
><AND> or the equivalent in another algebra is the only way to understand
>what join and union really mean, ie., are actually capable of being
>interpreted as.
I don't understand this, they are orthogonal operations, as I explained.
>Some 'unions' can only be expressed as the union of
>themselves and an empty relation.
I don't understand your interest in trivial unions or trivial joins.
>I think it is helpful to understand
>union from some formal definition that acknowledges the logical
>possibility that two relations may not be 'union' compatible, eg., the
>'<OR>' operation or equivalent.
The relational algebra union does so by not being defined for those
cases, but I agree with your and Darwen's sentiment that it is nicer to
extend operations to cover all cases when this can be usefully done,
in fact I've worked on a similar generalization of operations for a
different query language. But this doesn't change the fact that union
and join are fundamentally orthogonal, in the sense that one combines
relations vertically, the other horizontally.
So I do sympathize with his OR and NOT; but I also feel
the problems with them are more than 'computational issues'.
>Understanding relation structure based
>on empty relations seems as pointless/useless to me as understanding
>relational complement as being 'simple' complement. In fact, I'd rather
>call simple complement the vague complement and relative complement the
>exact complement. Why eschew a more precise interpretation when it's
>staring us in the face?
I'm trying to make sense of this by reading Darwen's NOT
for 'relational complement' and relational algebra's MINUS
for 'simple complement'. Is that what you mean?
In that case, I don't see what you mean by preciseness.
Darwen's AND, OR and NOT are more general operations than
those of the relational algebra, but they are not any more precise.
And the price he pays for allowing them is worse than computational:
the tuples of the relations we create with them can no longer all
be regarded as expressing positive facts. We now have to know how a
resulting relation was produced before we can interpret it.
We *lose* preciseness.
>> What are you trying to achieve?
>> ...
>
>Originally, the most potent axioms for an implementation language that
>follows McGoveran's suggestions, ie., ones that recognize relation
>structure as opposed to how a relation value may have been arbitrarily
>formed.
*Implementation* language?
Relational algebra (with possible extensions such as transitive
closure) already gives us both mathematical simplicity (the axiom aspect)
and implementation orientedness (it is targeted at optimization).
Darwen's algebra isn't any more axiomatic, it is *less* precise,
as we no longer know how to interpret the relations we produce.
and *not* implementation oriented, because NOT and OR cannot actually
be implemented as they are (try NOT-ing the table {A: 1, B: 1, C: 1},
where A, B, C can take arbitrary floating point values). I would
venture that the first thing any implementer will attempt to do
is rewrite all of Darwen's expressions back to relational algebra as
far as possible, and throw errors on the remainder. Then again, there
is no doubt a lot of theory on working with partly disjunctively or
negatively interpreted relations that I'm not aware of.
The same objection holds for treating selection as join with mathematical
relations (in Darwen's section 'Treating operators as relations'.)
A relation in a relational database is of a very different nature
than a mathematical relation such as PLUS. A database relation
consists of a posteriori knowledge, information about the world.
A mathematical relation is a priori: it reflects information
about mathematical constructs, not information about the world.
A database relation is established by someone or something who observes
facts in the world and makes sure the tuples of the relation reflect them.
The reason databases exist is that we want to store and then retrieve such
information. We typically want to be able to write a query that produces,
say, the relation reflecting the municipalities of the country with their
mayors. Typically, we want such a query to always produce the latest
known version of that information without having to specifically rewrite
it to make it do so; in which case the relation is 'time-varying', i.e.
its contents will need to be updated from time to time.
None of this is true for mathematical relations. They are invariant.
Most are infinite. It is indeed mathematically possible to express
arbitrary selection expressions in terms of relational joins, but
this only makes them hard to read and write, it obscures implementation
aspects such as performance, and I can't think of a benefit.
Nice as an academic exercise (look, ma, I removed a concept)
but not as an academic result (no useful purpose).
>The way most people talk of Codd's algebra is simplistic
>because they have typically not tried to interpret it, probably have
>never even read it, for example, in the above, what do horizontal and
>vertical coordinates have to do with anything relational?.
You know very well I wasn't talking about coordinates,
it was just a shorthand that is completely *obvious*
(considering that we usually visualize relations as tables)
and that I *carefully explained* just to be sure you would get it.
If you still didn't, I'm really sorry but I don't think it's my fault.
>This is faux
>technocracy, usually involving what de Bono called porridge words which
>in this case are additional lingo to disguise a lack of basic understand
Covering up a lack of reading comprehension with insults, as you have a
habit of doing, doesn't exactly help your credibility, mister. Do you
want help on understanding relational theory, or don't you?
>(and which is how I believe Codd's algebra is usually 'taught', or
>thought to be 'taught'. But more to the point, I continue to be amazed
>that people claim they can 'insert' a tuple to a relvar but cannot
>'delete' that very tuple! (vice-versa too.)
I can make sense of that remark in various ways so I'm not sure how
to respond. In relational algebra this is well possible, because of
the possible creation of symmetries that selections cannot 'break'.
Please clarify.
>I think when they say they
>can't delete, what they are really saying is that they can't delete a
>tuple that
> is not in the join! The same goes for asserting and retracting a
>proposition in general.
> I've no doubt that it might be difficult to
>retract a proposition that one has never asserted! In a way, this is no
>surprise to me and I still don't know why people think it is a problem,
I'm not sure what you mean. Maybe it depends on what kinds of facts a
database is assumed to contain; assuming that every tuple corresponds to
a fact and absence of a tuple to its negation really simplifies things,
but I don't know if you do. (Does make any sense as a reply?)
>when all human affairs contain much mumbo-jumbo that is logically
>make-believe. Now that you mention it, another goal would be to prevent
>geometric interpretations of the basic algebraic structures! Sounds
>like tables or arrays are getting mixed up with relations.
Yes, to you it does. You see a word, it triggers an association in your
mind, and you start blathering about the association instead of focusing
on trying to understand what is actually meant. You're in bad company
here, and I certainly won't exclude myself, but if you want to make
progress on this algebra stuff, a change of attitude is advisable.
---
Reinier
com...@hotmail.com
Reinier,
There are fundamentals of Date& Darwen's "algebra" A that you don't
understand.
Definitions:
AND is JOIN.
NOT R has exactly the tuples typed by R that are not in R.
R OR Q has exactly those tuples typed by R JOIN Q which
give a tuple from R when projected on R's attributes or give a tuple
from Q when projected on Q's attributes.
R MINUS (for permitted R and Q) is R AND NOT Q.
R MINUS (for permitted R and Q) Q is also R OR Q.
> Darwen's AND, OR and NOT are more general operations than
> those of the relational algebra, but they are not any more precise.
Agree.
> And the price he pays for allowing them is worse than computational:
> the tuples of the relations we create with them can no longer all
> be regarded as expressing positive facts.
Not so.
Queries are interpreted exactly the same as always.
Tuples that are present are true and those that are not present are
false.
> We now have to know how a
> resulting relation was produced before we can interpret it.
> We *lose* preciseness.
Not so.
Interpretation is the same as always.
I don't know what you think the problem is.
Try to give an example.
> Darwen's algebra isn't any more axiomatic, it is *less* precise,
...
> and *not* implementation oriented, because NOT and OR cannot actually
> be implemented as they are (try NOT-ing the table {A: 1, B: 1, C: 1},
> where A, B, C can take arbitrary floating point values).
Of course they can be implemented.
It's true that they denote large relations, but that's not necessarily
a problem.
First, you could allow only queries in NOT and OR that can be recast
using MINUS and UNION.
Second, you could allow non-query expressions but not queries in NOT
and OR.
Third, the cost of a query in NOT or OR is not necessarily
unacceptable.
It depends on the size of the attribute types rather than the number
of tuples in the relation,
but you could allow them and and still compute them (eg if the result
is small enough) (or in a lazy evaluation context).
The benefit is that NOT and OR can give clearer queries even if you
limit yourself to recastable queries
(they roughly mean "not" and "or" in the sense that
roughly JOIN means "and", MINUS means (limited) "and not" and UNION
means (limited) "or").
> I would
> venture that the first thing any implementer will attempt to do
> is rewrite all of Darwen's expressions back to relational algebra as
> far as possible, and throw errors on the remainder.
You use "venture", "attempt" and "as far as possible" but the
semantics are clear.
> Then again, there
> is no doubt a lot of theory on working with partly disjunctively or
> negatively interpreted relations that I'm not aware of.
Expressions in terms of NOT and OR are not interpreted differently.
Expressions that cannot be recast using MINUS and UNION instead of NOT
and OR
just might contain a lot of tuples.
> The same objection holds for treating selection as join with mathematical
> relations (in Darwen's section 'Treating operators as relations'.)
> A relation in a relational database is of a very different nature
> than a mathematical relation such as PLUS. A database relation
> consists of a posteriori knowledge, information about the world.
> A mathematical relation is a priori: it reflects information
> about mathematical constructs, not information about the world.
Not so.
You can either think of PLUS as a named relation value or as a
variable that doesn't happen to change.
Otherwise everything is as usual.
Eg R add C as A-B means R COMPOSE (PLUS rename ARG1 as C, ARG2 as B,
RESULT as A)
(you need a parameter naming convention if you want to mix named with
positional parameters).
In your informal terms, PLUS is information about the world; that info
just doesn't happen to change.
> Nice as an academic exercise (look, ma, I removed a concept)
> but not as an academic result (no useful purpose).
It is practical and not an exercise to simplify and generalize.
The basic consequence is that the difference between operators and
relations becomes only syntactic.
You can use a relation wherever you can use an operator and vice
versa.
This can be extended to include user-defined operations for which,
again,
the complexity for recastable queries is the same as the recast query,
and you need a policy for non-recastable queries (and further policies
for side-effects).
If the D&D presentation were more formal and complete this would be
more evident.
BTW, using NOT and OR is equivalent to using MINUS and UNION along
with a named single-attribute relation value
for each type each containing all that type's values.
Such a database has the same operation complexity as usual but some of
the leaves (the type-relations) are big.
So the cost of evaluating corresponding queries is the same.
Again, it is notationally more elegant and exactly as computationally
expensive
to allow the latter with the same recast-restrictions you would apply
to the former.
philip
com...@hotmail.com
> R MINUS (for permitted R and Q) Q is also R OR Q.
R UNION Q (for permitted R and Q) is R OR Q.
> Eg R add C as A-B means R COMPOSE (PLUS rename ARG1 as C, ARG2 as B,
> RESULT as A)
Eg R add A-B as C means R JOIN (PLUS rename ARG1 as C, ARG2 as B,
RESULT as A)
Eg R add A+B as C means R JOIN (PLUS rename ARG1 as A, ARG2 as B,
RESULT as C)
philip
paul c
>> I would
>> venture that the first thing any implementer will attempt to do
>> is rewrite all of Darwen's expressions back to relational algebra as
>> far as possible, and throw errors on the remainder.
>
> You use "venture", "attempt" and "as far as possible" but the
> semantics are clear.
Perhaps a neophyte would try that. If he did it a second time though, one would have to question his aptitude for such work, for that matter, any kind of mental work. Apart from predicting and validating results, the chief use of an underlying algebra to define a language is as a means to prove logical optimizations. (I have not seen any dbms that has the kind of exact and formal definitions as Tutorial D has, but even that could go further when it comes to constraints. Most dbms's seem to rely on informal definitions, if any.)
rpost
>Reinier,
>
>There are fundamentals of Date& Darwen's "algebra" A that you don't
>understand.
I understood the definitions (thanks for repeating them though)
but I did make a major mistake regarding OR.
>Definitions:
>AND is JOIN.
>NOT R has exactly the tuples typed by R that are not in R.
Note that 'the tuples typed by R' is a ambiguous.
I was going by Darwen's appendix "A New Relational Algebra",
which doesn't mention types. Therefore I was tempted to read
'the tuples typed by R' as the join of the single-attribute
projections of R. Let's call this operation RELDOM(R),
and define RELNOT(R) = RELDOM(R) MINUS R. RELDOM can
(obviously) be expressed in Codd's algebra, albeit not
with a fixed expression.
However, what you actually mean by 'the tuples typed by R' is
the join of the single-attribute relations with all possible
values for types of the attribute. This is also an operation,
let's call it DOM. Then we can define NOT(R) = DOM(R) MINUS R.
This 'absolute' NOT generally introduces domain values
that weren't in R, and when the domains are big or infinite,
produces very big / infinite relations. It's this NOT that
I have problems with.
>R OR Q has exactly those tuples typed by R JOIN Q which
>give a tuple from R when projected on R's attributes or give a tuple
>from Q when projected on Q's attributes.
Yes; and we can again introduce a relative variant RELOR
by using RELDOM(R JOIN Q) instead of DOM(R JOIN Q).
>> Darwen's AND, OR and NOT are more general operations than
>> those of the relational algebra, but they are not any more precise.
>
>Agree.
>
>> And the price he pays for allowing them is worse than computational:
>> the tuples of the relations we create with them can no longer all
>> be regarded as expressing positive facts.
>
>Not so.
>Queries are interpreted exactly the same as always.
>Tuples that are present are true and those that are not present are
>false.
Yes, but what I meant to say is that in general, the tuples
don't really express facts regarding those domain values,
they just help express information about other domain values.
But I wasn't thinking straight when I wrote that (as paul c
suggested): this is true for *any* operation with negation,
e.g. RELOR or MINUS. It is only more conspicuous in NOT and OR,
because they introduce domain values not in the original relation(s).
>> We *lose* preciseness.
>
>Not so.
OK.
>> Darwen's algebra is[...]
>> *not* implementation oriented, because NOT and OR cannot actually
>> be implemented as they are (try NOT-ing the table {A: 1, B: 1, C: 1},
>> where A, B, C can take arbitrary floating point values).
>
>Of course they can be implemented.
>It's true that they denote large relations, but that's not necessarily
>a problem.
It complicates the implementation: it is no longer possible to represent
all relations as finite collections of tuples.
>First, you could allow only queries in NOT and OR that can be recast
>using MINUS and UNION.
>Second, you could allow non-query expressions but not queries in NOT
>and OR.
Yes, that was my suggestion: rewrite to Codd's algebra
and reject the rest. Another idea is, of course, to use
RELNOT and RELOR instead.
>Third, the cost of a query in NOT or OR is not necessarily
>unacceptable.
>It depends on the size of the attribute types rather than the number
>of tuples in the relation,
Definitely. For Booleans or enums it's acceptable
to just complement literally.
>but you could allow them and and still compute them (eg if the result
>is small enough) (or in a lazy evaluation context).
Lazy evaluation doesn't help for NOT. I think you want to be smarter
anyway. But I notice there are several implementations already and I
haven't got a clue what they do.
>The benefit is that NOT and OR can give clearer queries even if you
>limit yourself to recastable queries
>(they roughly mean "not" and "or" in the sense that
>roughly JOIN means "and", MINUS means (limited) "and not" and UNION
>means (limited) "or").
Perhaps. I always liked how Codd's algebra separates 'horizontal'
operations (PROJECT, JOIN) from 'vertical' ones (MINUS, UNION,
INTERSECTION, quotient, selection). When I look at OR it doesn't
look like an operation I would use. But this may just be a matter
of getting used to it.
>> I would
>> venture that the first thing any implementer will attempt to do
>> is rewrite all of Darwen's expressions back to relational algebra as
>> far as possible, and throw errors on the remainder.
>
>You use "venture", "attempt" and "as far as possible" but the
>semantics are clear.
True.
[...]
>You can either think of PLUS as a named relation value or as a
>variable that doesn't happen to change.
>Otherwise everything is as usual.
Mathematically, yes. But the implementation has to treat PLUS,
and mathematical operations in general, differently from the
finite, extensionally defined, time-varying relations that
constitute the actual information stored in a relational database.
[...]
>In your informal terms, PLUS is information about the world; that info
>just doesn't happen to change.
No, it is not. The implementation can, and had better, take advantage
of the invariability of PLUS, and the typical computer hardware's
buil-in support for it. You really really don't want to implement it
as table lookup. Even for e.g. Boolean operators you probably want to
optimize differently than you they will be optimized when implemented
as table lookup.
>> Nice as an academic exercise (look, ma, I removed a concept)
>> but not as an academic result (no useful purpose).
>
>It is practical and not an exercise to simplify and generalize.
>The basic consequence is that the difference between operators and
>relations becomes only syntactic.
To the mathematician; not to the computer scientist.
>You can use a relation wherever you can use an operator and vice versa.
>This can be extended to include user-defined operations for which, again,
>the complexity for recastable queries is the same as the recast query,
>and you need a policy for non-recastable queries (and further policies
>for side-effects).
>If the D&D presentation were more formal and complete this would be
>more evident.
It is evident already, but I think this policy stuff is hard.
>BTW, using NOT and OR is equivalent to using MINUS and UNION along
>with a named single-attribute relation value
>for each type each containing all that type's values.
Yes (DOM above).
>Such a database has the same operation complexity as usual but some of
>the leaves (the type-relations) are big.
>So the cost of evaluating corresponding queries is the same.
>Again, it is notationally more elegant and exactly as computationally
>expensive
>to allow the latter with the same recast-restrictions you would apply
>to the former.
As I already said in my previous message, I see the elegance,
but at the same time I find elegance in Codd's use of two kinds
of operations. Obviously if you rewrite to Codd's algebra (or do
something equivalent to that) you're not going to lose efficiency
on the cases where this is possible. But just rejecting the rest
is only going to confuse the user. Why not be honest and admit
that we really expect, in our implementations, relational queries
to work on finite, typically small relations, that WORKS_IN is one
and PLUS is not, and that NOT doesn't do so?
>philip
--
Reinier
paul c
Nice to see somebody actually trying to read the Darwen & Date
definitions, though I think it's essential to recognize their intended
context which is pretty much limited to a formal basis for defining
their Tutorial D language and they have never suggested that an rdbms
should fully evaluate/materialize <NOT>. McGoveran goes much further
and I like his term - 'simple complement' better than 'absolute'
because there is not much that is absolute about <NOT>. His term
helps underline that A-algebra by itself is not enough to decide
certain (constrained) replacements of relations. A very elementary
one (I don't believe McGoveran has mentioned it publicly but it is a
favourite of mine) involves candidate keys - you can't necessarily
'insert' two tuples by 'deleting' them from the simple complement,
even though both are in the complement. In other words, the simple
complement is not subject to any constraints beyond the eligible
values of domains.
What you suggest is a 'relative' complement is not what I think
McGoveran had in mind, at least based on the very few public
statements he's made. From what I can make out, his point amounts to
saying that a relative complement is a constrained simple complement.
paul c
> ...
> As I already said in my previous message, I see the elegance,
> but at the same time I find elegance in Codd's use of two kinds
> of operations. Obviously if you rewrite to Codd's algebra (or do
> something equivalent to that) you're not going to lose efficiency
> on the cases where this is possible. But just rejecting the rest
> is only going to confuse the user. Why not be honest and admit
> that we really expect, in our implementations, relational queries
> to work on finite, typically small relations, that WORKS_IN is one
> and PLUS is not, and that NOT doesn't do so?
In the interest of keeping the pot stirred, here are some other
provocations (basically one of my same old tired recurring themes) .
As Fabian P and others have pointed out, a table (or should that be
R-table?) that involves nulls obviously involves more than one of
Codd's original relations. Given a smart enough implementation a
relation that is defined using <OR> could be replaced by two or more
relations (I seem to remember McGoveran stating similar somewhere or
other. I'm guessing that Codd wouldn't have agreed but my hunch is
that his objection would have been on practical, not theoretical
grounds, so perhaps he would not have objected if somebody had made a
practical implementation). As long as the closed-world-assumption is
followed, a relation that is produced using the <NOT> operator doesn't
generally need to be materialized because queries against it can be
transformed as queries against its own negation. I'd say the
importance of <NOT> has nothing to do with finiteness, rather that it
parallels boolean algebra's NOT and thus allows a algebra to define
retraction, aka 'deletion'.
<OR> is more interesting (to me) than <NOT>. Without <OR>, RT has no
way to 'add' a tuple to a relation variable. When one uses a
language's "INSERT" verb, it must effect the logical equivalent of
<OR>. Codd's unadorned relation is a conjunction of simple
propositions (by simple I mean each proposition contains no logical
connectors). If a relation variable has the 'quality' of being a
'view' (or 'green' as I like to joke), some people say to the effect
that the view is a conjunction of disjunctions (propositions involving
the logical connector 'OR'). Whereas if the relation variable is
'base', they say it is just a conjunction of simple propositions. For
years, I've been trying to understand how they can say this at the
same time as they say that users should preferably see no difference
between base and virtual/view relation variables (which I agree with,
just as I would agree that there should be no appreciable difference
between 'red' and 'green' relvars. Their argument then proceeds to
claim that 'inserts' to some union views are indeterminate while
'inserts' to an equal 'base' view aren't. I'd say that if they are
right, then we shouldn't be able to 'insert' to any variable unless it
points to an empty relation which would mean that no relation could
have more than one tuple - that bizarre situation would have exactly
one advantage - no questions about finiteness!
Brian Selzer
Paul,
I think you're on the right track if you can just separate what <OR> is from
what is an application of <OR>. Of course, this particular application of
<OR> is not limited to just INSERT, but also UPDATE and DELETE.
Relational Calculus, and therefore equivalent mechanisms such as Codd's or
D&D's algebras, is closely related to if not based upon first order
predicate logic. But while first order logic is fine for querying the
picture of the world that is represented by a given database value, it is
not sufficient for either the series of pictures represented by a succession
of database values, or the series of events that describe not just what is
changing between pairs of successive pictures, but exactly how what is
changing is different.
This is the way I see it: That which states what is the case is the
disjunction of all and only true propositions. Divide that into two parts:
one that states what has been the case (not necessarily what had been the
case--just that which obtained since the last change), and one that states
what is happening. Whenever nothing is happening, what has been the case
/is/ the case. For example, if Joe has been second in line at the bank and
nothing is happening, then Joe is still second in line. On the other hand,
if the person who has been first in line is now being served, then Joe is no
longer second in line but is instead first in line. The disjunction of the
two statements: "Joe has been second in line" and "Joe is no longer second
in line but is instead first in line" yields "Joe is first in line." In
symbols,
from p \/ (~p \/ q), derive (p \/ ~p) \/ q
since (p \/ ~p) is vacuously true, eliminate it and what is left is just q
Now let's apply that to relational theory: the database states what has been
the case; a transition states what is happening. The logical sum of these
two statements asserts what is the case, and is therefore what is becoming
the database: though there may be many databases that could be the database,
only one of them can actually be the database at a time.
So the application of <OR> to combine the statement of what has been the
case with the statement of what is happening is a fair description of a
database update, but it is not limited to just "INSERT." The disjunction, p
\/ ~p, when it appears in the logical sum of what has been the case and what
is happening can be thought of as the equivalent of a "DELETE," and the
disjunction, (p /\ q) \/ (p /\ ~q) \/ (p /\ r), the equivalent of an
"UPDATE;" only the disjunction, False \/ p, would be the equivalent of an
"INSERT."
Brian Selzer
"Brian Selzer" <br...@selzer-software.com> wrote in message
news:_zBql.17414$YU2....@nlpi066.nbdc.sbc.com...
Technically, (p \/ ~p) is not /vacuously/ true, it just conveys no
information. Still, such expressions must not appear as disjuncts in the
statement of what is the case.
Walter Mitty
>
>> that states what is happening. Whenever nothing is happening, what has
>> been the case /is/ the case. For example, if Joe has been second in line
Let's look at "whenever nothing is happening" in more detail. I submit
that, at a point in time where there are no transactions in progress, that
"nothing is happening". Further, I submit that, if serializability is the
criterion for concurrency management, then the DBMS ensures that the view
of the database is as if "nothing is happening", during a transaction,
except for the actions of that transaction. Every other transaction can be
seen as being completed "in the past" or beginning "in the future".
So, if the transactions can be serialized, each transaction sees the
database as if "nothing is happening". If you agree with all that, then
why isn't your point moot? If you don't agree, where don't you agree?
paul c
> "Brian Selzer" <br...@selzer-software.com> wrote in message
> news:wLsrl.14888$as4....@nlpi069.nbdc.sbc.com...
>
>>> that states what is happening. Whenever nothing is happening, what has
>>> been the case /is/ the case. For example, if Joe has been second in line
>
> Let's look at "whenever nothing is happening" in more detail. I submit
> that, at a point in time where there are no transactions in progress, that
> "nothing is happening". Further, I submit that, if serializability is the
> criterion for concurrency management, then the DBMS ensures that the view
> of the database is as if "nothing is happening", during a transaction,
> except for the actions of that transaction. Every other transaction can be
> seen as being completed "in the past" or beginning "in the future".
well put. What's more, IYAM, assuming a very strict implementation
such as two-phase lock protocol where a transaction ends when the
first "lock" is released (not that I advocate 2PL), nothing is
happening during any transaction and IYAM this would apply even for a
dbms with temporal support.
Brian Selzer
"Walter Mitty" <wam...@verizon.net> wrote in message
news:Ziyrl.1235$%u5....@nwrddc01.gnilink.net...
My point has little if anything at all to do with transactions and
concurrency control. Those belong to implementations. My point is that
relational calculus, or any equivalent mechanism such as relational algebra,
while necessary for describing database updates, is not sufficient for that
purpose because it can only apply to a single database, not two successive
databases. The mechanism of updating the database cannot be reduced to mere
algebraic expressions, but instead to asserting, in the context of what has
been the case, just what in the world is different and exactly how. Let me
explain.
The set of all state constraints, such as join dependencies and inclusion
dependencies, determines the set of all possible databases. Databases are
simply assertions that state just what things have been in the world and
exactly how those things relate to each other. Obviously, only one of those
assertions at a time can be assigned a positive truth value under an
interpretation. The [current] database is that one member that has been
assigned a positive truth value; the database is that one assertion that
states what has been the case. In the same way that databases are simply
assertions, transitions are simply assertions that state, in the context of
what has been the case, just what in the world is different and exactly how.
The set of all transition constraints describes the subset of possible
databases that are accessible from an arbitrary database. But more
importantly, when applied to the current database, it describes which
combinations of changes to what has been in the world are acceptable. For
example, a traffic light can only change from red to green, from green to
yellow, or from yellow to red; therefore, a change from green to red would
not be acceptable. If the traffic light has been green, no possible
database in which the traffic light is red would be accessible.
Given the assertion that states what has been the case (the database) and an
assertion that states just what in the world is different and exactly how (a
transition), the statement of what is the case can be calculated by
eliminating all instances of expressions that are true in all
interpretations from the logical sum of those two assertions. The result
states what is the case and therefore becomes the statement of what has been
the case (the database) until the next update.
I suppose that by now you're asking, why does this matter? Because <OR> is
just an operator of a relational algebra. The application of <OR> that Paul
referred to is a gross oversimplification of what actually has to occur
during a database update. While disjunction is a necessary part of the
calculation of what is the case, the remaining step of eliminating
expressions that are true in all interpretations cannot be ignored. It
should be easy to see that whenever there is a "DELETE,"
there will be expressions like (p \/ ~p) in the logical sum of the two
assertions. These are redundant because they are a consequence of just the
logic, and as a result they do not convey information.
Walter Mitty
So, what does "whenever nothing is happening" mean in the context of the
point you are making?
paul c
> "Walter Mitty" <wam...@verizon.net> wrote in message
> news:Ziyrl.1235$%u5....@nwrddc01.gnilink.net...
> I suppose that by now you're asking, why does this matter? Because <OR> is
> just an operator of a relational algebra. The application of <OR> that Paul
> referred to is a gross oversimplification of what actually has to occur
> during a database update. While disjunction is a necessary part of the
> calculation of what is the case, the remaining step of eliminating
> expressions that are true in all interpretations cannot be ignored. It
> should be easy to see that whenever there is a "DELETE,"
> there will be expressions like (p \/ ~p) in the logical sum of the two
> assertions. These are redundant because they are a consequence of just the
> logic, and as a result they do not convey information.
>
Walter, this is to you, I'm not going to argue with Brian S about
<OR>, which I consider to be a convenient trick to allow an
implementation to be defined on an algebra, one that parallels
boolean algebra, which is helpful for comprehension. All Brian S is
talking about is how the artifices of an implementation should be
interpreted (which I think is an application question).
Long before digital machines were invented, some mathematicians
decided that ordinary arithmetic would not be closed under division.
Whereas I'd say that closure of operations is very desireable for
auttomation, ie. for a machine, no matter whether it's a real or
virtual machine. While Codd talked a lot about exceptions and so may
not have agreed, and while McGoveran puts his argument in terms of
data independence, for me the controversy about updating views comes
down to whether one desires a logical machine to have closure under
union (and under negation).
Brian Selzer
In the context of the point I am making it introduces the null case: the
case where no database update is indicated because the things that have been
in the world are the things that are in the world and exactly how those
things have been related to each other is exactly how those things are
related to each other.
"What has been the case" encompasses the interval [Tn, Now), where Tn is the
instant of the last change. "What is the case" is the snapshot of the world
at the current instant. Whenever nothing is happening, "what has been the
case" will obtain at least until the succeeding instant, so nontemporal
queries against "what has been the case" must return exactly the same
results as the same queries against "what is the case." Whenever something
/is/ happening, on the other hand, at that instant "what has been the case"
becomes "what had been the case during [Tn, Tc)" where Tc is the instant of
what is happening, and since "What is the case" will obtain at least until
the succeding instant, notemporal queries against "what is the case" must
return exactly the same results as the same queries against a new instance
of "what has been the case" that encompasses the interval [Tc, Now).
A changing world can be described as a series of snapshots or as a series of
events. I prefer the latter because while the series of snapshots can be
derived from the series of events, the series of events cannot always be
derived from the series of snapshots. An expression that refers to one
individual at one time may refer to a completely different individual at
another. For example, "the person that is first in line" is definite in
that it refers to exactly one person at a time, but the statement "The
person that is first in line is wearing a red hat." could be true at
successive times even if "the person that is first in line" refers to Joe at
one time and to Mary at the next, provided both Joe and Mary are wearing red
hats. Similarly, "The person that is first in line is wearing a red hat."
could now be false because Mike, who is wearing a blue hat, is now first in
line, or because Joe just put on a blue hat. Since each event occurs in the
context of what has been the case, the confusion is eliminated because the
transition that describes the event asserts just what in the world is
different and exactly how. So it would be clear that Mike is now first in
line or that Joe just put on a blue hat.
Brian Selzer
> Brian Selzer wrote:
>> "Walter Mitty" <wam...@verizon.net> wrote in message
>> news:Ziyrl.1235$%u5....@nwrddc01.gnilink.net...
> ...
>> I suppose that by now you're asking, why does this matter? Because <OR>
>> is just an operator of a relational algebra. The application of <OR>
>> that Paul referred to is a gross oversimplification of what actually has
>> to occur during a database update. While disjunction is a necessary part
>> of the calculation of what is the case, the remaining step of eliminating
>> expressions that are true in all interpretations cannot be ignored. It
>> should be easy to see that whenever there is a "DELETE,"
>> there will be expressions like (p \/ ~p) in the logical sum of the two
>> assertions. These are redundant because they are a consequence of just
>> the logic, and as a result they do not convey information.
>
> Walter, this is to you, I'm not going to argue with Brian S about <OR>,
> which I consider to be a convenient trick to allow an implementation to be
> defined on an algebra, one that parallels boolean algebra, which is
> helpful for comprehension. All Brian S is talking about is how the
> artifices of an implementation should be interpreted (which I think is an
> application question).
>
You're missing the point. It's not about how it should be interpreted, but
just that it is subject to interpretation. Once you admit that data is
subject to interpretation and realize what interpretation involves, you'll
find that you can't accomplish what you're trying to do. But it's your own
time: how you waste it is really your own business.
>
> Long before digital machines were invented, some mathematicians decided
> that ordinary arithmetic would not be closed under division. Whereas I'd
> say that closure of operations is very desireable for auttomation, ie. for
> a machine, no matter whether it's a real or virtual machine. While Codd
> talked a lot about exceptions and so may not have agreed, and while
> McGoveran puts his argument in terms of data independence, for me the
> controversy about updating views comes down to whether one desires a
> logical machine to have closure under union (and under negation).
I'm not sure, but I think I said this before:
From p \/ q, can you infer p? Can you infer q? Can you infer p /\ q? No.
All that is certain is ~(~p /\ ~q).
How, then, can you determine which base relation or relations are the
ultimate target of an insert into a union view?
Walter Mitty
>> So, what does "whenever nothing is happening" mean in the context of the
>> point you are making?
>>
>
> of events. I prefer the latter because while the series of snapshots can
> be derived from the series of events, the series of events cannot always
> be derived from the series of snapshots.
So what?
Walter Mitty
> Brian Selzer wrote:
>> "Walter Mitty" <wam...@verizon.net> wrote in message
>> news:Ziyrl.1235$%u5....@nwrddc01.gnilink.net...
> ...
>> I suppose that by now you're asking, why does this matter? Because <OR>
>> is just an operator of a relational algebra. The application of <OR>
>> that Paul referred to is a gross oversimplification of what actually has
>> to occur during a database update. While disjunction is a necessary part
>> of the calculation of what is the case, the remaining step of eliminating
>> expressions that are true in all interpretations cannot be ignored. It
>> should be easy to see that whenever there is a "DELETE,"
>> there will be expressions like (p \/ ~p) in the logical sum of the two
>> assertions. These are redundant because they are a consequence of just
>> the logic, and as a result they do not convey information.
>
> Walter, this is to you, I'm not going to argue with Brian S about <OR>,
> which I consider to be a convenient trick to allow an implementation to be
> defined on an algebra, one that parallels boolean algebra, which is
> helpful for comprehension. All Brian S is talking about is how the
> artifices of an implementation should be interpreted (which I think is an
> application question).
>
I'm going to suggest that there are multiple layers of
representation/interpretation, and not just the two layers many of us are
accustomed to using in our discussions. I'm also going to suggest that what
Brain S. calls "oversimplification" is almost exactly what others call
"abstraction". I'm also going to suggest that without abstraction you don't
get any independence, and without independence, you don't get much of any
bang for the buck. That may be of zero theoretical importance, but it's of
interest to me.
>
> Long before digital machines were invented, some mathematicians decided
> that ordinary arithmetic would not be closed under division. Whereas I'd
> say that closure of operations is very desireable for auttomation, ie. for
> a machine, no matter whether it's a real or virtual machine. While Codd
> talked a lot about exceptions and so may not have agreed, and while
> McGoveran puts his argument in terms of data independence, for me the
> controversy about updating views comes down to whether one desires a
> logical machine to have closure under union (and under negation).
I'm afraid this is over my head. I appreciate the fact that you don't talk
down to me, and I'm not asking you to change that. But I need some
intermediate steps in the above chain of reasoning, simply due to my own
ignorance. I got the part about non closure under division. I didn't get
the connection between updating views and closure under union.
Closure under negation is problematic. For finite data sets, we can define
closure in a finite way. But our definition loses clarity when we try to
extrapolate from finite sets to infinite sets. Now most of us, when we
think about the data in a database, are content to think of this data as
being "a finite subset of an infinite reality". We usually call this subset
the "universe of discourse". There may be logical contradictions here, but I
don't detect them at my low level of thinking. But when you do negation,
the question of whether the universe of discourse is finite or infinite
becomes consequential.
Brian Selzer
So what? I had mentioned change in the preceding paragraph, so I thought I
should elaborate. Now let me elaborate further. Clearly the series of
events that describes the changing world contains more information than the
series of snapshots, and as a result, database update mechanisms based on it
promise both greater economy and precision since only what is different need
be stated and since exactly which set of differences that results in a
successor snapshot is clearly stated in each transition. In addition, more
granular transition constraints can be specified without resorting to the
introduction of superfluous temporal attributes or identity fields. What
has time to do with the requirement that a traffic light that is green can
only either remain green or become yellow?
I think that what is missing from commercial DBMSs is the ability to
declaratively specify constraints that limit the behavior of objects, and as
a consequence, those constraints and their enforcement have migrated into
application code. My goal is to describe a logical framework under which
all constraints can be specified declaratively--including transition
constraints. An implementation of such a framework would eliminate the need
for many triggered procedures and even some stored procedures, at least when
those procedures are used to maintain integrity. What follows is a rough
sketch of what I have in mind.
A database is an assertion that states what things have been in the world
and exactly how those things have been related to each other. A transition
is an assertion that in the context of a database states what in the world
is different and exactly how. Since both databases and transitions are just
assertions, and since databases can be represented as collections of
relations, it follows that transitions should also be able to be represented
as collections of relations. So during a database update, for each relation
schema in the database schema, there is one relation in the database and
three in the proposed transition: one that enumerates the tuples for things
that have been in the world but are no longer, one that enumerates the
tuples for things that are still in the world but differ in appearance, and
one that enumerates the tuples for things that have not been in the world
but now are. (Every tuple in the database maps to something in the world
because every tuple has a key value.) Since the resulting proposed relation
can be calculated from the corresponding relation in the database and three
relations in the proposed transition, it makes sense to materialize all of
those relations for all relation schemata as potential operands of
constraints defined using the relational calculus or something equivalent.
For example, if R{A, B, C} is a relation schema, then during a database
update the following relations would be materialized along with those for
every other relation schema for specifying declarative constraints
R{A, B, C}, the current relation
R-{A, B, C}, tuples about to be deleted
R%{A, B, C, A', B', C'}, tuples about to be updated
A', B' and C' contain new components values for A, B and C respectively
R+{A, B, C}, tuples about to be inserted
R'{A, B, C}, the proposed relation
State constraints would involve only the primed relations. Transition
constraints could be defined using just the primed and unadorned relations
for those relations with key values that are permanent identifiers, or using
the -, % and + relations together with the unadorned relations for those
with key values that are not.
So what? Context is critical. In order to support declarative
specification of transition constraints, it is necessary for the context of
both the proposed database and the current database to be the same. From a
series of snapshots it is not always possible to derive a series of events,
and as a consequence, the context of each snapshot is different. This
invalidates the result of a comparison of the proposed database to the
current database. From the series of events, on the other hand, it is
always possible to derive the series of snapshots, and since each snapshot
is derived from its predecessor, the context of that derivation can be the
context of both the proposed database and the current database during a
database update. So in effect, supporting declarative specification of
transition constraints is only always possible when the changing world is
described as a series of events.
Tegiri Nenashi
> Clearly the series of
> events that describes the changing world contains more information than the
> series of snapshots, and as a result, database update mechanisms based on it
> promise both greater economy and precision since only what is different need
> be stated and since exactly which set of differences that results in a
> successor snapshot is clearly stated in each transition. In addition, more
> granular transition constraints can be specified without resorting to the
> introduction of superfluous temporal attributes or identity fields. What
> has time to do with the requirement that a traffic light that is green can
> only either remain green or become yellow?
A simple Traffic Lights database design
table TrafficLights (
streetCrossId integer,
state {red,yellow,green}
)
has no concept of light switching ordering. However, as soon as we
have time added it becomes temporal database, and everything becomes
more complicated, including queries! Yet, the constraint is
expressible (although as quite unwieldy SQL assertion).
> I think that what is missing from commercial DBMSs is the ability to
> declaratively specify constraints that limit the behavior of objects, and as
> a consequence, those constraints and their enforcement have migrated into
> application code.
Perhaps there are other reasons why constraint enforcement migrated
into application code? Such as application programmers' ignorance of
database fundamentals, client-server latency, and, most important,
weak support from RDBMS vendors?
> My goal is to describe a logical framework under which
> all constraints can be specified declaratively--including transition
> constraints.
Transition constraints are more complicated than state constraints.
Think of simple inequality x < 10. How many transition constraints
would it take to represent it? Assuming domain of integers we would
allow transitions 1->2, 1->3, 1->4, 2->3, ... and reject 1->11, 3-
>12, ... How would you express functional dependency as a transition
constraint, without explicitly enumerating all legitimate state
transitions?
I'd suggest that state constraints are much more common than
transition constraints, therefore having transition constraints as a
foundation seems to be a wrong idea. It requires quite a lot of effort
and sophistication to develop something workable along this ideas --
we are looking into fields that study dynamics, in general, and
differential equations, in particular.
Your criticism of algebraic foundation for constraint system might get
some ground if you focus on (un)expressiveness and (im)maturity of
underlying algebraic system...
Brian Selzer
"Tegiri Nenashi" <Tegiri...@gmail.com> wrote in message
news:ab49ab5f-a8e6-4b2a...@a12g2000yqm.googlegroups.com...
During a database update, assuming that streetCrossIds are permanent
identifiers, the relations,
TrafficLights- {streetCrossId, state},
TrafficLights% {streetCrossId, state, streetCrossId', state'}, and
TrafficLights+ {streetCrossId, state}
would be populated with tuples representing those traffic lights that have
been removed from service, those traffic lights whose state is now
different, and those traffic lights that have been placed into service
respectively.
Wouldn't it be simpler to write something like
NOT EXISTS TrafficLights%
(TrafficLights%.state = green AND TrafficLights%.state' = red)
This expression would return false if the state of any traffic light is
switching from green to red.
> > I think that what is missing from commercial DBMSs is the ability to
> > declaratively specify constraints that limit the behavior of objects,
> > and as
> > a consequence, those constraints and their enforcement have migrated
> > into
> > application code.
>
> Perhaps there are other reasons why constraint enforcement migrated
> into application code? Such as application programmers' ignorance of
> database fundamentals, client-server latency, and, most important,
> weak support from RDBMS vendors?
>
I don't deny those other reasons, but I don't think they're the whole story.
> > My goal is to describe a logical framework under which
> > all constraints can be specified declaratively--including transition
> > constraints.
>
> Transition constraints are more complicated than state constraints.
> Think of simple inequality x < 10. How many transition constraints
> would it take to represent it? Assuming domain of integers we would
> allow transitions 1->2, 1->3, 1->4, 2->3, ... and reject 1->11, 3-
> >12, ... How would you express functional dependency as a transition
> constraint, without explicitly enumerating all legitimate state
> transitions?
>
In the framework I sketched, state constraints such as functional
dependencies would be defined using just the primed relations--that is, the
proposed relations. This does not differ significantly from how state
constraints are specified now. I did not intend to reinvent the wheel, just
augment what is already there to also allow the specification of declarative
transition constraints.
> I'd suggest that state constraints are much more common than
> transition constraints, therefore having transition constraints as a
> foundation seems to be a wrong idea. It requires quite a lot of effort
> and sophistication to develop something workable along this ideas --
> we are looking into fields that study dynamics, in general, and
> differential equations, in particular.
I think you've misinterpreted my intent. I did not intend that state
constraints be rewritten as transition constraints. I intend instead that
both state constraints and transition constraints can be specified
declaratively.
> Your criticism of algebraic foundation for constraint system might get
> some ground if you focus on (un)expressiveness and (im)maturity of
> underlying algebraic system...
The algebra is perfectly suited for what it was intended to do. I don't
object to its use as a foundation for a constraint system. In fact, since
it is equivalent to relational calculus, it could in fact be an integral
component. What I object to is trying to cast it as an update mechanism,
which is clearly beyond not just its intended purpose, but also its
capabilities.
paul c
> ... I'm also going to suggest that what
> Brain S. calls "oversimplification" is almost exactly what others call
> "abstraction". I'm also going to suggest that without abstraction you don't
> get any independence, and without independence, you don't get much of any
> bang for the buck. That may be of zero theoretical importance, but it's of
> interest to me.
> ...
Walter, I'm with the many people who think phyaical and logical
independence are of high importance, both theoretically and
practically. But I'd say many of the nuances and implications of
those haven't been explored much in print. Brain S as you call him
regularly enters the realm of mysticism. I point this out not to
correct him, but to warn newcomers here that he is not exactly
swimming in the main stream of relational theory (to be fair, not many
are, because the theory is often confused with past practice). I have
a number of mystic acquaintances and I like them all, partly because
they don't involve themselves in db theory and there is much in life
for which mysticism offers the only comfortable clues.
But here we must remember one of Codd's first precepts - all meaning
in an rdb is expressed through the values of attributes of relations.
With care in their expression, some constraints can stand in effect
(eg. intensions) for such relations, but many programmers who come to
this field are incapable of removing their past experience from the
topic, which is one of the reasons we see the word 'interpretation'
mentioned so often here (basically what Edward de Bono called a
porridge word). It seems that Brian S doesn't want to use attributes
to express time values or state successions. I doubt if Codd would
have gone along with that (but being smarter than I he wouldn't have
bothered arguing about it either).
...
>
> I'm afraid this is over my head. I appreciate the fact that you don't talk
> down to me, and I'm not asking you to change that. But I need some
> intermediate steps in the above chain of reasoning, simply due to my own
> ignorance. I got the part about non closure under division. I didn't get
> the connection between updating views and closure under union.
> ...
If I can understand it, it can't be very deep. There used to be many
posters here who could think better than I but most of them seem to
have gone away. If we can't insert to all possible unions, then
sooner or later some expression will be interrupted by an exception.
Big names like Darwen and Date don't need to worry about this much
because of their choice of implementation language style. But imagine
a language that implicitly asserts what we think of as persistent
updates in the course of making queries. Such a language would be
impossible because nested expressions could fail at any time depending
on data. So I say a more universal definition of an rdb needs to
avoid the possibility of some (single) relations being thought of as
conjuntions of disjunctions. Much better to think of them as
conjunctions of simple propositions. But I warn you - this is coming
from somebody who doesn't even think persistence is necessary to have
a relational engine!
(Brian S's association P V ^P with deletion is a bizarre example of
mixing up programming operators with db values and with formal
language definitions/operators.)
When it comes to assuming logical independence when inserting to
union, I think it's enough to imagine relations A, B and C, where C is
a union of A and B. Then allow any of the three to be base (aka
'real') and any of the three to be a view (aka 'virtual'), then ask
whether there is only one way to update one of the three so that no
matter what, a user ignorant of the 'independent' qualities of tables
will see the same result.
> Closure under negation is problematic. For finite data sets, we can define
> closure in a finite way. But our definition loses clarity when we try to
> extrapolate from finite sets to infinite sets. Now most of us, when we
> think about the data in a database, are content to think of this data as
> being "a finite subset of an infinite reality". We usually call this subset
> the "universe of discourse". There may be logical contradictions here, but I
> don't detect them at my low level of thinking. But when you do negation,
> the question of whether the universe of discourse is finite or infinite
> becomes consequential.
>
Infinity is not a problem because when we implement on a digital
machine, all stored values are finite. It's true that materializing
some negations is intractable. This is where an algebraic foundation
rather than a programming or mystical foundation for definitions comes
to our aid. But people who talk of infinity here might as well talk
about the effect of gravitons on dbs, for all it matters.
paul c
...
> Infinity is not a problem because when we implement on a digital
Maybe I should have qualified 'values' to be ones that aren't allowed
to be treated in an approximate way by the operators allowed, such as
many floating point value representations.
paul c
...
> ... It's true that materializing some
> negations is intractable. ...
ie., their extensions
Brian Selzer
> Walter Mitty wrote:
>
>> ... I'm also going to suggest that what
>> Brain S. calls "oversimplification" is almost exactly what others call
>> "abstraction". I'm also going to suggest that without abstraction you
>> don't
>> get any independence, and without independence, you don't get much of any
>> bang for the buck. That may be of zero theoretical importance, but it's
>> of
>> interest to me.
>> ...
>
> Walter, I'm with the many people who think phyaical and logical
> independence are of high importance, both theoretically and practically.
> But I'd say many of the nuances and implications of those haven't been
> explored much in print. Brain S as you call him regularly enters the
> realm of mysticism. I point this out not to correct him, but to warn
> newcomers here that he is not exactly swimming in the main stream of
> relational theory (to be fair, not many are, because the theory is often
> confused with past practice). I have a number of mystic acquaintances and
> I like them all, partly because they don't involve themselves in db theory
> and there is much in life for which mysticism offers the only comfortable
> clues.
>
Mysticism. If accepting that the universe of discourse contains things and
that at different times a thing can differ in appearance yet still be the
same thing means that I'm a mystic, then I'm guilty as charged. If
acknowledging that under an interpretation values are mappings from language
terms such as constant symbols to things in the universe of discourse means
that I'm a mystic, then I'm guilty as charged. If recognizing that there is
equivalence between a tuple in a relation and an atomic formula in a first
order language means that I'm a mystic, then I'm guilty as charged. If
allowing that there is an equivalence between a key value in a tuple and a
term in a first order language means that I'm a mystic, then I'm guilty as
charged.
>
> But here we must remember one of Codd's first precepts - all meaning in an
> rdb is expressed through the values of attributes of relations. With care
> in their expression, some constraints can stand in effect (eg. intensions)
> for such relations, but many programmers who come to this field are
> incapable of removing their past experience from the topic, which is one
> of the reasons we see the word 'interpretation' mentioned so often here
> (basically what Edward de Bono called a porridge word). It seems that
> Brian S doesn't want to use attributes to express time values or state
> successions. I doubt if Codd would have gone along with that (but being
> smarter than I he wouldn't have bothered arguing about it either).
>
You should have gone into politics, given how adroitly you twist what people
say to suit your own ends.
Tegiri Nenashi
a database update, assuming that streetCrossIds are permanent
> identifiers, the relations,
>
> TrafficLights- {streetCrossId, state},
> TrafficLights% {streetCrossId, state, streetCrossId', state'}, and
> TrafficLights+ {streetCrossId, state}
>
> would be populated with tuples representing those traffic lights that have
> been removed from service, those traffic lights whose state is now
> different, and those traffic lights that have been placed into service
> respectively.
This is not a good example of database update. Why do we care what
state traffic light was during maintenance upgrade? I suspect they
turn it out before actually unplugging the electrics and removing
other mechanical artifacts. Moreover, the state is probably a
calculated value, function of time and perhaps some other conditions.
Any other realistic example of transition constraint?
> I think you've misinterpreted my intent. I did not intend that state
> constraints be rewritten as transition constraints. I intend instead that
> both state constraints and transition constraints can be specified
> declaratively.
Good luck with that. For transition constraints you'd have to summon
automata theory? That is not one of the prettiest subjects of computer
science...
Walter Mitty
What difference does it make whether it's the same thing or a different
thing?
vld...@yahoo.com
> Moreover, the state is probably a
> calculated value, function of time and perhaps some other conditions.
If you are interested you can find the definition of a state of an
entity or relationship in my paper about new data model. I posted it a
few days ago on this user group, under topic:
A new db model/design
or you can go directly to my web site:
www.dbdesign11.com
It is definition 4.2.4.1 in the paper Database Design and Data Model
Founded on Concept and Knowledge construct. You can find there
examples about the states. I applied the idea about the states in very
complex DB projects and m-n relationships.
Vladimir Odrljin
Walter Mitty
> Walter Mitty wrote:
>
>> ... I'm also going to suggest that what
>> Brain S. calls "oversimplification" is almost exactly what others call
>> "abstraction". I'm also going to suggest that without abstraction you
>> don't
>> get any independence, and without independence, you don't get much of any
>> bang for the buck. That may be of zero theoretical importance, but it's
>> of
>> interest to me.
>> ...
>
> Walter, I'm with the many people who think phyaical and logical
> independence are of high importance, both theoretically and practically.
> But I'd say many of the nuances and implications of those haven't been
> explored much in print. Brain S as you call him regularly enters the
> realm of mysticism.
"Brain S" was a typo. No intentional irony here.
Brian Selzer
> On Mar 8, 3:45 pm, "Brian Selzer" <br...@selzer-software.com>
> > During a database update, assuming that streetCrossIds are permanent
> > identifiers, the relations,
> >
> > TrafficLights- {streetCrossId, state},
> > TrafficLights% {streetCrossId, state, streetCrossId', state'}, and
> > TrafficLights+ {streetCrossId, state}
> >
> > would be populated with tuples representing those traffic lights that
> > have
> > been removed from service, those traffic lights whose state is now
> > different, and those traffic lights that have been placed into service
> > respectively.
>
> This is not a good example of database update. Why do we care what
> state traffic light was during maintenance upgrade? I suspect they
> turn it out before actually unplugging the electrics and removing
> other mechanical artifacts. Moreover, the state is probably a
> calculated value, function of time and perhaps some other conditions.
If the state of a traffic light were always a function of time, then the
constraint could possibly be written as a state constraint, but not all
traffic lights follow a regular schedule. Some depend upon traffic
conditions, others allow for manual intervention. (Those buttons you push to
get the walk signal come to mind.)
What I thought was obvious apparently isn't: a traffic light that is being
removed from service would have to be switched off and dismantled for parts
or relegated to the trash heap; a traffic light that is being placed into
service would have to be assembled, installed and switched on, and so would
also have to have an intial state; a traffic light that is neither being
removed from nor placed into service must have been and must still be in
service, though its state may or may not have changed. So the transition
constraint,
NOT EXISTS TrafficLights%
(TrafficLights%.state = green AND TrafficLights%.state' = red)
would apply only to traffic lights that have been and still are in service.
> Any other realistic example of transition constraint?
The transition constraint,
NOT EXISTS TrafficLights+
(TrafficLights+.state != red)
would require that whenever a traffic light is placed into service that its
initial state be red.
> > I think you've misinterpreted my intent. I did not intend that state
> > constraints be rewritten as transition constraints. I intend instead
> > that
> > both state constraints and transition constraints can be specified
> > declaratively.
>
> Good luck with that. For transition constraints you'd have to summon
> automata theory? That is not one of the prettiest subjects of computer
> science...
I don't think we need to summon automata theory. A transition only ever
involves two states: that which has obtained up to but not including the
instant of change and that which obtains at that instant. How those states
and the transition fits into an abstract state machine is incidental. For
any implementation to support transition constraints, however, requires both
a syntactic and semantic definition of what constitutes a state and what
constitutes a transition.
A state is simply a database--a collection of relations that together
represent and by extension assert just what things have been in the world
and exactly how those things have been related to each other. A transition
is also a collection of relations, specifically three relations for each
relation in the database, that together represent and by extension assert
what in the world is different and exactly how, or more specifically, that
which has been in the world but no longer is, that which is still in the
world but appears different, and that which hadn't been in the world but now
is.
For example, if there are just relations P{A, B, C}, Q{A, D} and R{A, E} in
the database, then a proposed transition will consist of the following
relations
P-{A, B, C} -- tuples to be "deleted" from P
P%{A, B, C, A', B', C'} -- tuples in P to be "updated" with new components
P+{A, B, C} -- tuples to be "inserted" into p
Q-{A, D} -- tuples to be "deleted" from Q
Q%{A, D, A', D'} -- tuples in Q to be "updated" with new components
Q+{A, D} -- tuples to be "inserted" into Q
R-{A, E} -- tuples to be "deleted" from R
R%{A, E, A', E'} -- tuples in R to be "updated" with new components
R+{A, E} -- tuples to be "inserted" into R
One or more or even all of these relations may contain tuples during a
database update. Just not none. The proposed relations are:
P'{A, B, C} =
(P MINUS (P- UNION P%{A, B, C}))
UNION (P%{A', B', C'} RENAME {A' AS A, B' AS B, C' AS C'})
UNION P+
Q'{A, D} =
(Q MINUS (Q- UNION Q%{A, D}))
UNION (Q%{A', D'} RENAME {A' AS A, D' AS D})
UNION Q+
R'{A, E} =
(R MINUS (R- UNION R%{A, E}))
UNION (R%{A', E'} RENAME {A' AS A, E' AS E})
UNION R+
During a database update, and only during a database update, the relations
P, P-, P%, P+, P', Q, Q-, Q%, Q+, Q', R, R-, R%, R+, R'
contain the current database (P, Q, R),
the transition (P-, P%, P+, Q-, Q%, Q+, R-, R%, R+),
and the proposed database (P', Q', R').
Since constraints only need to be checked during a database update, they can
reference any of the above relations because it is only during a database
update that they are all populated with data.
Brian Selzer
If an employee worked 50 hours on a project and his labor rate is $20 per
hour, then it cost $1000 to have him work on the project, right? WRONG!
The employee's labor rate /is/ $20 per hour, but that doesn't mean that it
/had been/ $20 per hour during the time that he worked on the project. At
that time his labor rate might have been $18 per hour or may even have
changed part way through the project. So the record of cost must not
contain just which project, which employee and how many hours, but also at
which labor rate or rates the work was performed. But the employee is still
the same employee even though his labor rate changed from $18 to $20. Other
cost records may exist for projects that he worked on after the rate
increase, and one should expect that a query of which projects he worked on
would return all of the projects, regardless of the labor rate.
So something can appear different at different times yet still be the same
thing.
This poses a problem because keys are not necessarily permanent identifiers.
(I'm having trouble articulating my thought here because there is more than
one usage of the term, "key." I'm disinclined from using "key value"
because under an interpretation, a key value is a mapping to a particular
thing in the universe, that thing being the output of the valuation function
for the set of symbols for the components in a tuple of the set of
attributes that is the candidate key, and it's possible for that same set of
symbols to map to different things at different times, or for different sets
of symbols to map to the same thing at different times. But it's unwieldy
to say "sets of symbols for the components in a tuple of the set of
attributes that is the candidate key" instead of just "keys.") The problem
stems from how things in the universe of discourse are identified, and that
the scope of the definition of a candidate key is any database and not all
databases. While a key may uniquely identify something in the context of
its containing database, that doesn't necessarily mean that that same key
uniquely identifies that same something at all databases in which it
appears.
paul c
I wish, at least once, you would give an answer that was shorter than
the question.
com...@hotmail.com
> On Feb 18, 12:14 pm, rp...@pcwin518.campus.tue.nl (rpost) wrote:
There are some fundamentals of the relational model that you also
don't
understand.
> Yes, but what I meant to say is that in general, the tuples
> don't really express facts regarding those domain values,
> they just help express information about other domain values.
Tuples do not express facts about domain values. They contain domain
values.
A relation has an associated "external predicate" which is a
parameterized
statement about the modelled world. Eg "My dog named NAME has N
fleas".
Eg "N cats have M kittens".
All the statements you get by substituting the values from the tuples
that are
in the relation for the corresponding parameters are true. All the
statements
you get by substituting the value from the tuples that are not in the
relation
but are typed by it are false. You do not have any choice about it. A
relation
makes a statement for every tuple that is typed by it, not just the
ones in
the relation.
> this is true for *any* operation with negation,
> e.g. RELOR or MINUS. It is only more conspicuous in NOT and OR,
> because they introduce domain values not in the original relation(s).
Everything R says is true, NOT R says is false, and everything R says
is false
NOT R says is true. They both use every possible tuple that is typed
by the
relation. You just don't have to write down the false ones.
This is fundamental. So make sure every thing you ever say about
relations is
consistent with this.
> When I look at OR it doesn't
> look like an operation I would use. But this may just be a matter
> of getting used to it.
If relation R's predicate is R and relation S's predicate is S then:
(R JOIN S)'s predicate is (R and S) (so it has the tuples for which
that's true).
Eg "My dog is named NAME and has N fleas and (the same number) N cats
have M kittens".
(R PROJECT A)'s predicate is (there exists an A such that R) (so it
has the
tuples for which that's true). Eg "There exists a NAME and an N such
that my
dog is named NAME and has N fleas" (ie "My dog has fleas").
(R MINUS T)'s predicate is (R and not T) (so it has the tuples for
which that's
true) (but they have to use the same attributes). Eg "My dog is named
NAME
and has N fleas and it's not the case that my friend NAME ate N
apples".
(R UNION T)'s predicate is (R or T) (so it has the tuples for which
that's true)
(but they have to use the same attributes). Eg "My dog is named NAME
and
has N fleas or my friend NAME ate N apples". But if you wanted to put
'or'
between any predicates use (R OR S): Eg "My dog is named NAME and has
N
fleas or I have (the same number) N cats and M kittens".
> I always liked how Codd's algebra separates 'horizontal'
> operations (PROJECT, JOIN) from 'vertical' ones (MINUS, UNION,
> INTERSECTION, quotient, selection).
But this is just coincidental. If (for instance) you PROJECT away
some
attributes, it is because you want a result that can be described via
"there
exists" as above. It doesn't matter that you didn't know it could be
described
that way, that you were unable to use that to actually write the right
thing,
and were instead organizing yourself around these other vague notions
instead.
> >The benefit is that NOT and OR can give clearer queries even if you
> >limit yourself to recastable queries
> Perhaps.
> >The basic consequence is that the difference between operators and
> >relations becomes only syntactic.
>
> To the mathematician; not to the computer scientist.
Suppose I want the NAMES, N and M for which
R and not (S or T).
Why shouldn't I be able to write
R AND NOT(S OR T)
instead of something with MINUS, UNION, LEFT JOIN, etc? You are
making
me be a mathematician instead of a computer scientist, and in a case
where the computer could have done the work.
Why can't I use a relation as a boolean-result-operator (ie predicate)
or as a
function-operator (called using a superkey) as in:
// Numbers of cats and their numbers of kittens
// with the same number of kittens as Frank has fleas.
S where R(Frank NAME, M as N)
S where N=R(Frank as Name)
or write
A join (PLUS where P1=5)
An operator is a relation.
> Therefore I was tempted to read
> 'the tuples typed by R' as the join of the single-attribute
> projections of R. Let's call this operation RELDOM(R),
> and define RELNOT(R) = RELDOM(R) MINUS R. RELDOM can
> (obviously) be expressed in Codd's algebra, albeit not
> with a fixed expression.
> Yes; and we can again introduce a relative variant RELOR
> by using RELDOM(R JOIN Q) instead of DOM(R JOIN Q).
You can define them but I don't know what you think they mean or could
be
useful for (I think you don't know what they mean, and thus couldn't
use
them for anything). NOT and OR have simple interpretations; these do
not.
Can you give me a reference for McGoveran vis a vis these?
> It complicates the implementation: it is no longer possible to represent
> all relations as finite collections of tuples.
> But the implementation has to treat PLUS,
> and mathematical operations in general, differently from the
> finite, extensionally defined, time-varying relations that
> constitute the actual information stored in a relational database.
> Lazy evaluation doesn't help for NOT.
You are confused if you think the implementation or representation
has
anything to do with what the meaning of relations or queries are. The
user
knows what the values of the relations mean. They are implemented
somehow. It doesn't matter how. It does not matter to the user
whether
they would be big or infinite if written out.
If I allow you to use NOT and OR according to some policy, then you
can use
it according to that policy. One example policy I gave was, you can
use them
all you want eg to make updates but when you actually ask for the
tuples of a
relation (expression) it has to be one that could have been expressed
without
them. In practice every query is going to be able to be expressed
without them
because why would you have wanted one of these enormous relations?
The implementation is trivial. When the user assigns an expression and
it has
NOT or OR, just remember the expression instead of evaluating it. Use
in
other expressions. Evaluate when you have to. Object when you can't.
That's it.
We have not introduced infinite relations. All we have is relations
that would be
really big were we to enumerate their tuples, that we are not
enumerating. But
that is also why if we do have infinite relations, they're not a
problem eiher.
So don't confuse behaviour issues and implementation issues.
philip
On Feb 18, 12:14 pm, rp...@pcwin518.campus.tue.nl (rpost) wrote:
> philip wrote:
> >Reinier,
>
> >There are fundamentals of Date& Darwen's "algebra" A that you don't
> >understand.
>
> I understood the definitions (thanks for repeating them though)
> but I did make a major mistake regarding OR.
>
> >Definitions:
> >AND is JOIN.
> >NOT R has exactly the tuples typed by R that are not in R.
>
> Note that 'the tuples typed by R' is a ambiguous.
>
> I was going by Darwen's appendix "A New Relational Algebra",
> which doesn't mention types. Therefore I was tempted to read
> 'the tuples typed by R' as the join of the single-attribute
> projections of R. Let's call this operation RELDOM(R),
> and define RELNOT(R) = RELDOM(R) MINUS R. RELDOM can
> (obviously) be expressed in Codd's algebra, albeit not
> with a fixed expression.
>
> However, what you actually mean by 'the tuples typed by R' is
> the join of the single-attribute relations with all possible
> values for types of the attribute. This is also an operation,
> let's call it DOM. Then we can define NOT(R) = DOM(R) MINUS R.
> This 'absolute' NOT generally introduces domain values
> that weren't in R, and when the domains are big or infinite,
> produces very big / infinite relations. It's this NOT that
> I have problems with.
>
> >R OR Q has exactly those tuples typed by R JOIN Q which
> >give a tuple from R when projected on R's attributes or give a tuple
> >from Q when projected on Q's attributes.
>
> Yes; and we can again introduce a relative variant RELOR
> by using RELDOM(R JOIN Q) instead of DOM(R JOIN Q).
>
> >> Darwen's AND, OR and NOT are more general operations than
> >> those of the relational algebra, but they are not any more precise.
>
> >Agree.
>
> >> And the price he pays for allowing them is worse than computational:
> >> the tuples of the relations we create with them can no longer all
> >> be regarded as expressing positive facts.
>
> >Not so.
> >Queries are interpreted exactly the same as always.
> >Tuples that are present are true and those that are not present are
> >false.
>
> Yes, but what I meant to say is that in general, the tuples
> don't really express facts regarding those domain values,
> they just help express information about other domain values.
>
> But I wasn't thinking straight when I wrote that (as paul c
> suggested): this is true for *any* operation with negation,
> e.g. RELOR or MINUS. It is only more conspicuous in NOT and OR,
> because they introduce domain values not in the original relation(s).
>
> >> We *lose* preciseness.
>
> >Not so.
>
> OK.
>
> >> Darwen's algebra is[...]
> >> *not* implementation oriented, because NOT and OR cannot actually
> >> be implemented as they are (try NOT-ing the table {A: 1, B: 1, C: 1},
> >> where A, B, C can take arbitrary floating point values).
>
> >Of course they can be implemented.
> >It's true that they denote large relations, but that's not necessarily
> >a problem.
>
> It complicates the implementation: it is no longer possible to represent
> all relations as finite collections of tuples.
>
> >First, you could allow only queries in NOT and OR that can be recast
> >using MINUS and UNION.
> >Second, you could allow non-query expressions but not queries in NOT
> >and OR.
>
> Yes, that was my suggestion: rewrite to Codd's algebra
> and reject the rest. Another idea is, of course, to use
> RELNOT and RELOR instead.
>
> >Third, the cost of a query in NOT or OR is not necessarily
> >unacceptable.
> >It depends on the size of the attribute types rather than the number
> >of tuples in the relation,
>
> Definitely. For Booleans or enums it's acceptable
> to just complement literally.
>
> >but you could allow them and and still compute them (eg if the result
> >is small enough) (or in a lazy evaluation context).
>
> Lazy evaluation doesn't help for NOT. I think you want to be smarter
> anyway. But I notice there are several implementations already and I
> haven't got a clue what they do.
>
> >The benefit is that NOT and OR can give clearer queries even if you
> >limit yourself to recastable queries
> >(they roughly mean "not" and "or" in the sense that
> >roughly JOIN means "and", MINUS means (limited) "and not" and UNION
> >means (limited) "or").
>
> Perhaps. I always liked how Codd's algebra separates 'horizontal'
> operations (PROJECT, JOIN) from 'vertical' ones (MINUS, UNION,
> INTERSECTION, quotient, selection). When I look at OR it doesn't
> look like an operation I would use. But this may just be a matter
> of getting used to it.
>
> >> I would
> >> venture that the first thing any implementer will attempt to do
> >> is rewrite all of Darwen's expressions back to relational algebra as
> >> far as possible, and throw errors on the remainder.
>
> >You use "venture", "attempt" and "as far as possible" but the
> >semantics are clear.
>
> True.
>
> [...]
>
> >You can either think of PLUS as a named relation value or as a
> >variable that doesn't happen to change.
> >Otherwise everything is as usual.
>
> Mathematically, yes. But the implementation has to treat PLUS,
> and mathematical operations in general, differently from the
> finite, extensionally defined, time-varying relations that
> constitute the actual information stored in a relational database.
>
> [...]
>
> >In your informal terms, PLUS is information about the world; that info
> >just doesn't happen to change.
>
> No, it is not. The implementation can, and had better, take advantage
> of the invariability of PLUS, and the typical computer hardware's
> buil-in support for it. You really really don't want to implement it
> as table lookup. Even for e.g. Boolean operators you probably want to
> optimize differently than you they will be optimized when implemented
> as table lookup.
>
> >> Nice as an academic exercise (look, ma, I removed a concept)
> >> but not as an academic result (no useful purpose).
>
> >It is practical and not an exercise to simplify and generalize.
> >The basic consequence is that the difference between operators and
> >relations becomes only syntactic.
>
> To the mathematician; not to the computer scientist.
>
> >You can use a relation wherever you can use an operator and vice versa.
> >This can be extended to include user-defined operations for which, again,
> >the complexity for recastable queries is the same as the recast query,
> >and you need a policy for non-recastable queries (and further policies
> >for side-effects).
> >If the D&D presentation were more formal and complete this would be
> >more evident.
>
> It is evident already, but I think this policy stuff is hard.
>
> >BTW, using NOT and OR is equivalent to using MINUS and UNION along
> >with a named single-attribute relation value
> >for each type each containing all that type's values.
>
> Yes (DOM above).
>
> >Such a database has the same operation complexity as usual but some of
> >the leaves (the type-relations) are big.
> >So the cost of evaluating corresponding queries is the same.
> >Again, it is notationally more elegant and exactly as computationally
> >expensive
> >to allow the latter with the same recast-restrictions you would apply
> >to the former.
>
> As I already said in my previous message, I see the elegance,
> but at the same time I find elegance in Codd's use of two kinds
> of operations. Obviously if you rewrite to Codd's algebra (or do
> something equivalent to that) you're not going to lose efficiency
> on the cases where this is possible. But just rejecting the rest
> is only going to confuse the user. Why not be honest and admit
> that we really expect, in our implementations, relational queries
> to work on finite, typically small relations, that WORKS_IN is one
> and PLUS is not, and that NOT doesn't do so?
>
> >philip
>
> --
> Reinier
Brian Selzer
Ask me a question that has a simple answer, and I'll simply answer it.
paul c
That's a cute riposte in that it grants my wish as far as my last
question is concerned. But how about the simple answer to Walter M's
question (which is "none", ie., the attributes that are chosen for
relations determine the consequences)? The example of the employee
whose hourly cost changes is bogus because it confuses employee cost
with project hourly costs, obviously the latter would be an attribute
of some project relation in any workable system.
One of the flaws of the mystic persuasion as far as db's are concerned
and as we see it in your posts, is that it denies, in what usually
appears to me to be in a willful and haphazard way, that mechanical
db's, so far in history, don't actually relect reality, only an
abstraction of reality. This has got to be understood in any mention
of 'interpretation'. At some point maybe you will come to see that.
I wouldn't criticize if you could describe a formal model that could
embody the very extraneous notions you bring up, but the usual
assumption of any reader here is that the RM is the starting point but
your starting point doesn't which makes it very hard for any reader to
guess what the dickens your context is. Nothing wrong with additional
abstractions beyond Codd's, as long as the perpretators recognize that
they need to explain them to the rest of us.
Walter Mitty
> One of the flaws of the mystic persuasion as far as db's are concerned and
> as we see it in your posts, is that it denies, in what usually appears to
> me to be in a willful and haphazard way, that mechanical db's, so far in
> history, don't actually relect reality, only an abstraction of reality.
> This has got to be understood in any mention of 'interpretation'.
Bingo!
Brian Selzer
As my voluminous reply indicated, I don't think that it is "none."
> The example of the employee whose hourly cost changes is bogus because it
> confuses employee cost with project hourly costs, obviously the latter
> would be an attribute of some project relation in any workable system.
>
But it is clear that at each interval during which the employee was working
on the project, the employee's hourly cost and the project's hourly cost (at
least as far as the employee was concerned) were identical. That fact
cannot be denied even though the database doesn't maintain an explicit
record of the employee's rate changes.
>
> One of the flaws of the mystic persuasion as far as db's are concerned and
> as we see it in your posts, is that it denies, in what usually appears to
> me to be in a willful and haphazard way, that mechanical db's, so far in
> history, don't actually relect reality, only an abstraction of reality.
> This has got to be understood in any mention of 'interpretation'. At some
> point maybe you will come to see that.
Abstraction is a good thing. I don't deny it. The universe of discourse,
or as Codd put it, "the micro-world that the database is supposed to
represent," for most if not all databases is itself an abstraction of just a
subset of reality. But what you appear to be trying to do is apply
mechanisms that only work for static mathematical objects to things that can
change over time. That's not abstraction: that's just illogical.
There is a huge difference between a relation for an operator defined on a
domain of mathematical objects and a relation defined on a domain of things
that that can change over time. In particular, there can only ever be one
extension of the relation for the operator, whereas there are as many
possible extensions of the other as there are legal combinations of tuples.
The relation for the operator is true at all possible worlds at all times
under all interpretations, so the mechanism of its interpretation is moot
since the outcome is always the same. But for things that can change over
time, the mechanism of interpretation becomes critical because whether or
not a tuple appears in a relation depends solely upon whether the assertion
it represents has been assigned a positive truth value under an
interpretation.
> I wouldn't criticize if you could describe a formal model that could
> embody the very extraneous notions you bring up, but the usual assumption
> of any reader here is that the RM is the starting point but your starting
> point doesn't which makes it very hard for any reader to guess what the
> dickens your context is. Nothing wrong with additional abstractions
> beyond Codd's, as long as the perpretators recognize that they need to
> explain them to the rest of us.
There really isn't room here for a detailed explanation, but perhaps what
follows will at least clarify what my context is.
The way I see it, the Relational Model is equivalent to a formal logical
system based on a first-order modal tense logic. Modal because the set of
all domain constraints, relation constraints and database constraints
together specifies the set of all possible databases, which is the
equivalent of the set of all possible worlds, and tense because a database
is the equivalent of an assertion that states not just what is the case but
rather what has been the case since the last update, and a transition is the
equivalent of an assertion that states in the context of what has been the
case (or more precisely, what had been the case during the interval from the
last update up to this point) what is different and exactly how.
The simple terms of a formal language of that system include, like any
formal first-order language, a set of individual names, a set of individual
variables, and a set of relation names of various degrees. An atomic
formula is of the form P(x1,...,xn) where P is a relation name and
(x1,...,xn) are a set of zero or more individual variables. Complex
formulae are formed by combining atomic formulae with logical operators,
connectives and quantifiers. Constraints are sentences (closed formulae)
that together specify which models are legal under the intended
interpretation. A model is an extension of each formula in each possible
world, a mapping of each term to something in the universe of discourse, and
a mapping of each formula in each extension to a truth value, which as a
consequence states which member of the set of all possible worlds is the
actual world. Constraints fall into four categories: a set of named
constraints partitions the set of individual names; another set of
constraints specifies the set of all legal extensions for each formula; a
third set specifies the legal combinations of extensions that together
constitute the set of all possible worlds, and a fourth set defines which
possible worlds are accessible from another. Under the Unique Name and
Closed World Assumptions, these sets of constraints are the equivalents of
domain definitions, relation constraints, database constraints and
transition constraints in the Relational Model.
If you're interested in other abstractions beyond Codd's, you might want to
investigate Edward Zalta's theory of abstract objects. In particular, his
paper "The Modal Object Calculus and its Interpretation," published in
/Advances in Intensional Logic/, 1996, describes in detail the mechanism of
interpretation--including the assignment of meaning to terms in the formal
language and the assignment of truth values to formulae.
Walter Mitty
>
> "Walter Mitty" <wam...@verizon.net> wrote in message
> news:apltl.2309$%u5....@nwrddc01.gnilink.net...
>>
>> "Brian Selzer" <br...@selzer-software.com> wrote in message
>> news:eY2tl.9205$%54....@nlpi070.nbdc.sbc.com...
Walter Mitty
Actually, the floating point arithmetic treats values as producing an exact
result under all the operators involved. At least, so it seems to me from
looking at the FP operators of several computers. The problem is that the
exact result isn't "exactly right" in terms of what we construe exact
rightness to mean. In most cases, that is because what we give the
arithmetic unit as inputs are only approximations to the real values we
would like to give.
Walter Mitty
Don't you think Heraclitus said all of this much more clearly, some 2500
years ago?
http://www.spaceandmotion.com/philosophy-metaphysics-heraclitus.htm
paul c
> ...
>
> Don't you think Heraclitus said all of this much more clearly, some 2500
> years ago?
>
> http://www.spaceandmotion.com/philosophy-metaphysics-heraclitus.htm
Sounds like he was a fine old abstracter (abstractionist?). Seems
Abelson and company were hip too:
M
(Even while it changes, it stands still.)
Heraclitus
(also):
Plus ça change, plus c'est la même chose.
Alphonse Karr
(both from the esteemed sicp book)
I gather the temporal db people, whatever their arguments, at least
agree on choosing their desired abstractions up front, not plopping
multiple interpretations onto the basic Codd model with extraneous
lingo like 'tense' and 'modal' in today's popular but despicable
faux-technocratic way. (The general public has allowed the technocrats
to usurp their own name, just like the once-respectable word
'propaganda' in the 1930's. An honest db technocrat ought never
venture into metaphysics.).
Brian Selzer
Is this the new liberalism: express a position that is counter to
consensus--regardless if it or the consensus is correct--and endure not just
scorn and ridicule, but even to being cast as morally reprehensible. I
guess it would be too much to ask for a rational argument, if it were even
possible for you to formulate one, since ad hominem attacks are usually
either petty acknowlegements that there is no counterargument or hide an
inability or an unwillingness to comprehend what is under discussion.
Brian Selzer
No. I'm saying that the tuple in one database that maps to a particular
thing in the universe of discourse can be a different set of components from
the tuple in the succeeding database that maps to that same thing. In fact,
any or even all of the components can be different--including key
components.
Brian Selzer
I'm not sure what you're driving at. I'm not trying to answer philisophical
questions about change, nor do I seek to wax metaphysical. I merely accept
that it is not only the micro-world that a database is supposed to represent
that can vary over time, but also the things in that micro-world.
Walter Mitty
Now we're even!
Brian Selzer
Perhaps I wasn't making myself clear. You asked what difference does it
make whether it's the same thing or a different thing. Well, I think it's
important to know whether what I am talking about now is the same thing that
I had been talking about up to now. For instance, if the nurse is about to
administer a dose of morphine to a patient, and the nurse just administered
a dose of morphine to a patient, don't you think it is important to know
whether or not they are the same patient--especially if an overdose could
kill him? The identity relation has to take into account every past,
present and possible property exemplified by each thing that can change over
time, and that includes not just the properties that they actually exemplify
now but also the properties that they exemplified at every time at which
they appeared in the past and the properties that they exemplify at every
possible world at which they appear. Unfortunately, how something is
identified at one time may be different from how it is identified at
another, and as a consequence, identical tuples from successive databases
may map to different things in the universe of discourse.
Walter Mitty
> My point has little if anything at all to do with transactions and
> concurrency control. Those belong to implementations. My point is that
> relational calculus, or any equivalent mechanism such as relational
> algebra, while necessary for describing database updates, is not
> sufficient for that purpose because it can only apply to a single
> database, not two successive databases. The mechanism of updating the
> database cannot be reduced to mere algebraic expressions, but instead to
> asserting, in the context of what has been the case, just what in the
> world is different and exactly how. Let me explain.
I finally figured out that this is where the discussion branched off into
what some of us consider mysticism.
I disagree with the last sentence. In particular, the phrase "just what in
the world is different" implies, if I read it correctly, that a database
update has to be mapped into a "real world update". However, this mapping
is not presupposed by either the relational calculus or the relational
algebra. A database update is simply the difference between the ex ante
state of the database and the ex post state of the database. It is not an
assertion about what in the world is different, except in the eye of the
beholder.
The mathematics of relational calculus and relational algebra are fully
capable, AFAIK, of describing the difference between two states of a
database.
Walter Mitty
> This is really very simple, if you choose to actually use the mass of
> tissue between your ears.
Walter Mitty
paul c
If the algebra isn't capable of that, the RM is in trouble! (Heh, I
could predict in advance one mystic response, ie., there could be many
possible such 'differences', but as I might've hinted, I don't think
the mystics are really talking about the RM, though at least the late
lamented Dawn had the grace to state her PICK bias up-front.)
Regarding transactions and concurrency control 'belonging' to
implementations, it is more that most people are blinded by past
practice, failing to see that Codd's 'keys' might offer a theoretical
way to describe those aspects. Maybe if those same people asked what
are the requirements for transactions and concurrency from an
application viewpoint, they would see their way to a more logical,
verifiable basis for implementations. Eg., what is the difference
between an application data model in a single-user system versus in a
multi-user system? I guess that most people think none but my
attitude is that this is myopic, which rhymes with mystic. Can't
count how many requirements meetings I went to where nobody wanted to
talk about concurrency models, usually they just tossed around various
porridge phrases like isolation levels and picked the first one that
sounded presentable to the ignorami.
Brian Selzer
This was not an ad hominem attack, but merely a goad, and it prefaced an
argument that for anyone with even a rudimentary understanding of logic
clearly parallels the problem of updating a union view.
Brian Selzer
>
> "Brian Selzer" <br...@selzer-software.com> wrote in message
> news:pi_rl.24249$ZP4....@nlpi067.nbdc.sbc.com...
>
>> My point has little if anything at all to do with transactions and
>> concurrency control. Those belong to implementations. My point is that
>> relational calculus, or any equivalent mechanism such as relational
>> algebra, while necessary for describing database updates, is not
>> sufficient for that purpose because it can only apply to a single
>> database, not two successive databases. The mechanism of updating the
>> database cannot be reduced to mere algebraic expressions, but instead to
>> asserting, in the context of what has been the case, just what in the
>> world is different and exactly how. Let me explain.
>
> I finally figured out that this is where the discussion branched off into
> what some of us consider mysticism.
>
> I disagree with the last sentence. In particular, the phrase "just what
> in
> the world is different" implies, if I read it correctly, that a database
> update has to be mapped into a "real world update".
I don't agree with that characterization. A world is just a snapshot of the
universe of discourse. The universe of discourse is only an abstraction of
at most a subset of reality--if that--and is limited to just what is
interesting, so the context of "just what in the world is different" is
definitely not "the real world."
<snipped the remainder of your argument because it is based on a false
premise>
Brian Selzer
Do you deny that the set of all domain constraints, relation constraints and
database constraints together specify the set of all legal databases? If
not then how can you support your statement that 'modal' is extraneous
lingo? Correct me if I'm wrong, but didn't Codd use the phrase
"time-varying relation" to describe the information carrying structures of
the Relational Model? Do you deny that there can be different databases at
different times? If not then how can you support your statement that
'tense' is extraneous lingo? You appear to be ignorant of what a modal
logic is or what a tense logic is, otherwise you would understand that my
usage of the terms is anything but extraneous. I guess that would account
for the content of your posts, your inability to recognize that neither the
algebra nor the calculus were designed for nor are they sufficient for
expressing database updates because database updates cannot be described
using just first order predicate logic. There is an implicit tense
component to a database update--the notion of before and after...of order,
that is alien to first order predicate logic, but not to tense logics.
Brian Selzer
The algebra is capable of that if and only if each and every tuple has a key
that permanently identifies the thing in the universe of discourse that the
tuple maps to. But since that isn't a requirement of the RM, the RM must be
in trouble! If different keys at different states map to the same thing in
the universe of discourse, or if the same key at different states maps to
different things in the universe of discourse, then how is it possible to
describe exactly what is different between two states of a database.
For your information, I haven't read in any of Codd's writings that he
bought into D&D's inserts, updates and deletes are shortcuts for assignments
paradigm. And that makes sense since a set of inserts, updates and deletes
specifies exactly which possible set of differences constitutes what is
different, whereas that can't always be determined from just an assignment.
<snip>
Brian Selzer
As an exercise, try to write a set-based update trigger (a statement trigger
in Oracle) on a table with only a composite natural key. You'll find that
when a column in the key may be the target of an update, that you can't just
join deleted to inserted (old to new in Oracle) to determine exactly what is
different. (That's one of the main reasons Oracle and many other
implementations support row triggers.)
Walter Mitty
>
> As an exercise, try to write a set-based update trigger (a statement
> trigger in Oracle) on a table with only a composite natural key. You'll
> find that when a column in the key may be the target of an update, that
> you can't just join deleted to inserted (old to new in Oracle) to
> determine exactly what is different. (That's one of the main reasons
> Oracle and many other implementations support row triggers.)
>
>
The idea behind entity keys is that they are immutable. When analyzing the
universe of discourse into entities, it's important to discover a reliable
identifier for each entity. In practice, it's sometimes necessary to
synthesize identifiers, because the identifiers in common use are
unsuitable. An example might be the use of common names for people at the
time when information systems were first being computerized.
Foreign keys are immutable during the period of time that they refer to the
same thing, for the same reason that entity keys are immutable. It follows
that foreign keys should not have to be updated as a cascade from the update
of the entity keys they refer to. An update to a foreign key that
represents negation of the old relationship and assertion of a new one ought
to be expressble as a delete followed by an insert. I could be wrong on
this, as I haven't completed the exercise you proposed.
The tables I have built with only composite natural keys have all been
relationship tables, and not entity tables. In these cases, the composite
key that identifies rows in the relationship table are also foreign keys
that reference entities.
By the way, are you claiming that all attributes are mutable?
paul c
> "Brian Selzer" <br...@selzer-software.com> wrote in message
> news:c4Fvl.26433$ZP4....@nlpi067.nbdc.sbc.com...
>
>> As an exercise, try to write a set-based update trigger (a statement
>> trigger in Oracle) on a table with only a composite natural key. You'll
>> find that when a column in the key may be the target of an update, that
>> you can't just join deleted to inserted (old to new in Oracle) to
>> determine exactly what is different. (That's one of the main reasons
>> Oracle and many other implementations support row triggers.)
>>
>>
>
> The idea behind entity keys is that they are immutable. When analyzing the
> universe of discourse into entities, it's important to discover a reliable
> identifier for each entity. In practice, it's sometimes necessary to
> synthesize identifiers, because the identifiers in common use are
> unsuitable. An example might be the use of common names for people at the
> time when information systems were first being computerized.
Walter, please don't fall for a mystic trap/trick question. It is
pointless to respond to a puzzle that mentions 'natural' keys which
are a myth like the Emperor's New Clothes, some people don't see them
and some people dream they see them. Any answer you give will be
rejected in a picayune way for not using 'natural' keys, those being
recognizable only by mystics and not the rest of us. The keys that
are chosen by a design are all that matters. This means that
'synthetic' keys is a pointless term as well. The chosen keys will be
as 'common' as the application needs them to be. There are some old
posts from Bob B about this pointing out that a useful key will become
'familiar' very quickly, ie., immediately, even if it wasn't before an
app goes into play.
Another trap here is Oracle - what's it got to do with db theory?
I've never seen any Oracle documentation of its features/ops that used
only algebra or calculus for definitions. What I've seen pretends that
casual explanation is as good as a formal definition.
I think it might be more useful to ask whether there is a
difference/delta set or relation that obeys all the constraints of the
target variable.
Brian Selzer
An instance of a relationship isn't any less a thing than an instance of an
entity, so I think we should try to avoid all of the baggage associated with
the terms "entity" and "relationship."
> By the way, are you claiming that all attributes are mutable?
>
I'm claiming that whether an attribute is mutable or not is orthogonal to
the Relational Model. What about a relation for which the entire heading is
the key? Shouldn't it still be possible to issue an update?
Tegiri Nenashi
> "Walter Mitty" <wami...@verizon.net> wrote in message
Consider R at two time moments R(t') and R(t"). Define
Delta_i = R(t")-R(t')
Delta_d = R(t')-R(t")
Those are informally insertions and deletions when one ignores keys.
Now suppose we have a key, that is empty relation K. Consider
projections of Delta_i and Delta_d onto K:
Delta_i v K
Delta_i v K
These relations have the same header so their intersection
(Delta_i v K) ^ (Delta_i v K)
is a set of keys that "stays the same", that is update. Morale: you
can't possibly define what update is without a key. Exercise: prove
that updates are "well defined" regardless of the key choice.
Brian Selzer
"Tegiri Nenashi" <Tegiri...@gmail.com> wrote in message
news:f578bb12-97bd-4280...@u18g2000pro.googlegroups.com...
I disagree. Your argument rests on the premise that keys permanently
identify things in the universe of discourse. But by definition, all that
is required is that no two tuples in the same relation in the same database
have the same key components. What that means is that what identifies
something in the universe of discourse at t' could identify something
totally different at t''.
In other words, just because keys are the same at different times doesn't
necessarily mean that they map to the same thing in the universe of
discourse, and similarly, just because keys are different at different times
doesn't necessarily mean that they don't map to the same thing in the
universe of discourse.
> Morale: you
> can't possibly define what update is without a key.
Yes, you can: Consider the equivalence between the two D expressions from
/TTM Third Edition/ pages 112-113:
UPDATE r (Ai := X, Aj := Y)
where i != j is equivalent to
( ( EXTEND r ADD ( X AS Bi, Y AS Bj ) )
{ ALL BUT Ai, Aj } RENAME { Bi AS Bk, Bj AS Aj, Bk AS Ai}
Now let's look a bit more closely at this expression. The first part
( ( EXTEND r ADD ( X AS Bi, Y AS Bj ) )
results in a relation in which each tuple contains both the old components
and the new components, and from that relation it is possible to determine
exactly what is different--tuple, by tuple. But then that /stated/
correlation is projected away by
{ ALL BUT Ai, Aj } RENAME { Bi AS Bk, Bj AS Aj, Bk AS Ai},
so clearly, information is lost when translating an update into an
assignment. Now if we could just shift constraint enforcement to just
before that information is projected away, then we could specify transition
constraints declaratively.
> Exercise: prove
> that updates are "well defined" regardless of the key choice.
I think I just did.
Walter Mitty
"Brian Selzer" <br...@selzer-software.com> wrote in message news:Sy0wl.22503
> I disagree. Your argument rests on the premise that keys permanently
> identify things in the universe of discourse. But by definition, all that
> is required is that no two tuples in the same relation in the same
> database have the same key components. What that means is that what
> identifies something in the universe of discourse at t' could identify
> something totally different at t''.
>
> In other words, just because keys are the same at different times doesn't
> necessarily mean that they map to the same thing in the universe of
> discourse, and similarly, just because keys are different at different
> times doesn't necessarily mean that they don't map to the same thing in
> the universe of discourse.
>
This is why I brought Heraclitus into the discussion.
Incidentally, I disagree with both you and Heraclitus.
Without immutable identifiers, the universe of discourse cannot be
adequately described by data.
If the universe of discourse cannot be adequately described by data, then
the connection between
the universe of discourse and any database becomes haphazard, at best.
Every universe of discourse that I've dealt with in connection with
databases has held to
the assumption that identifiers are immutable. This, as you said, is
orthogonal to the
Relational Model, but it's an important feature of a universe of discourse,
from the point of view of the semantics of the data.
The question of whether the universe of discourse is a description of a part
of
the real world, on the one hand, or an illusion on the other hand,
is a question that I leave to mystics and thinkers like Heraclitus.
Tegiri Nenashi
> Your argument rests on the premise that keys permanently
> identify things in the universe of discourse. But by definition, all that
> is required is that no two tuples in the same relation in the same database
> have the same key components. What that means is that what identifies
> something in the universe of discourse at t' could identify something
> totally different at t''.
Well, there is no such thing as well defined update operation.
Because, it depends on the key. Example
delete {(p=1,q=a)}
insert {(p=1,q=b)}
with key {p} is equivalent to
update where p = 1 set q = b
Therefore, the update relative to key {p,q} is different from update
relative to key {p}. My take is that update is nothing more than
syntactic shorthand for combination of insert and delete.
> In other words, just because keys are the same at different times doesn't
> necessarily mean that they map to the same thing in the universe of
> discourse, and similarly, just because keys are different at different times
> doesn't necessarily mean that they don't map to the same thing in the
> universe of discourse.
Keys were the only option to try to define update formally. Again, if
not through keys, how do you formally define update?
> > Morale: you
> > can't possibly define what update is without a key.
>
> Yes, you can: Consider the equivalence between the two D expressions from
> /TTM Third Edition/ pages 112-113:
>
> UPDATE r (Ai := X, Aj := Y)
>
> where i != j is equivalent to
>
> ( ( EXTEND r ADD ( X AS Bi, Y AS Bj ) )
> { ALL BUT Ai, Aj } RENAME { Bi AS Bk, Bj AS Aj, Bk AS Ai}
>
> Now let's look a bit more closely at this expression. The first part
>
> ( ( EXTEND r ADD ( X AS Bi, Y AS Bj ) )
>
> results in a relation in which each tuple contains both the old components
> and the new components, and from that relation it is possible to determine
> exactly what is different--tuple, by tuple. But then that /stated/
> correlation is projected away by
>
> { ALL BUT Ai, Aj } RENAME { Bi AS Bk, Bj AS Aj, Bk AS Ai},
>
> so clearly, information is lost when translating an update into an
> assignment. Now if we could just shift constraint enforcement to just
> before that information is projected away, then we could specify transition
> constraints declaratively.
I'm not sure what relational assignment is to form an opinion if it
adequately preserves information to be leveraged in transition
constraints. It is obvious that transition constraint is nothing more
than algebraic-relational expression that includes two variables: the
state of relation before update R(t_1) and the state after R(t_2).
paul c
>>> Morale: you
>>> can't possibly define what update is without a key.
>> Yes, you can: Consider the equivalence between the two D expressions from
>> /TTM Third Edition/ pages 112-113:
>>
>> UPDATE r (Ai := X, Aj := Y)
>>
>> where i != j is equivalent to
>>
>> ( ( EXTEND r ADD ( X AS Bi, Y AS Bj ) )
>> { ALL BUT Ai, Aj } RENAME { Bi AS Bk, Bj AS Aj, Bk AS Ai}
Right. So-called "UPDATE" is a language device and when defined
algebraically doesn't need to depend on keys. (The exact quote can be
found at the bottom of page 24 at
http://www.dcs.warwick.ac.uk/~hugh/TTM/CHAP05.pdf )
>> Now let's look a bit more closely at this expression. The first part
>>
>> ( ( EXTEND r ADD ( X AS Bi, Y AS Bj ) )
>>
>> results in a relation in which each tuple contains both the old components
>> and the new components, and from that relation it is possible to determine
>> exactly what is different--tuple, by tuple. But then that /stated/
>> correlation is projected away by
>>
>> { ALL BUT Ai, Aj } RENAME { Bi AS Bk, Bj AS Aj, Bk AS Ai},
>>
>> so clearly, information is lost when translating an update into an
>> assignment. Now if we could just shift constraint enforcement to just
>> before that information is projected away, then we could specify transition
>> constraints declaratively.
> ...
To be precise, this particular language definition (Tutorial D)
"loses" information. That doesn't prevent some other language or
environment definition from presenting the un-renamed, un-projected
relation value to some declarative expression, ie., the algebra
doesn't prevent such a language.
> I'm not sure what relational assignment is to form an opinion if it
> adequately preserves information to be leveraged in transition
> constraints. It is obvious that transition constraint is nothing more
> than algebraic-relational expression that includes two variables: the
> state of relation before update R(t_1) and the state after R(t_2).
If you're saying you're not sure what relational assignment is, it is
the assignment of a relation value to a variable, aka pointer, ie., it
is a language device. Don't confuse relational assignment with any
of the relational operators, which involve no notion of pointers. I
wish people would clarify whether they are talking about the RM or
about some language or other.
Notions of 'before' and 'after' don't matter to an algebra, only two
possible relation values, as the Tutorial D definition hints at -
nothing prevents a language from having a notation that presents a
single relation value with tuples that have two values for each
attribute.
br...@selzer-software.com
> On Mar 17, 10:31 pm, "Brian Selzer" <br...@selzer-software.com> wrote:
>
> > Your argument rests on the premise that keys permanently
> > identify things in the universe of discourse. But by definition, all that
> > is required is that no two tuples in the same relation in the same database
> > have the same key components. What that means is that what identifies
> > something in the universe of discourse at t' could identify something
> > totally different at t''.
>
> Well, there is no such thing as well defined update operation.
> Because, it depends on the key. Example
>
> delete {(p=1,q=a)}
> insert {(p=1,q=b)}
>
> with key {p} is equivalent to
>
> update where p = 1 set q = b
>
> Therefore, the update relative to key {p,q} is different from update
> relative to key {p}. My take is that update is nothing more than
> syntactic shorthand for combination of insert and delete.
>
I don't think so. I think that the delete/insert pair states that
there is a different thing with key p = 1, whereas the update states
that the thing with key p = 1 merely appears different. In other
words, the delete/insert pair describes two distinct things, whereas
the update describes two distinct appearances of the same thing. The
delete/insert pair,
delete {(p=1,q=a)}
insert {(p=1,q=a)}
states that there are two distinct things with exactly the same
components, just during adjacent intervals.
> > In other words, just because keys are the same at different times doesn't
> > necessarily mean that they map to the same thing in the universe of
> > discourse, and similarly, just because keys are different at different times
> > doesn't necessarily mean that they don't map to the same thing in the
> > universe of discourse.
>
> Keys were the only option to try to define update formally. Again, if
> not through keys, how do you formally define update?
>
I just don't agree with you on this. I presented an alternative
definition that is independent of keys.
>
> > > Morale: you
> > > can't possibly define what update is without a key.
>
> > Yes, you can: Consider the equivalence between the two D expressions from
> > /TTM Third Edition/ pages 112-113:
>
> > UPDATE r (Ai := X, Aj := Y)
>
> > where i != j is equivalent to
>
> > ( ( EXTEND r ADD ( X AS Bi, Y AS Bj ) )
> > { ALL BUT Ai, Aj } RENAME { Bi AS Bk, Bj AS Aj, Bk AS Ai}
>
> > Now let's look a bit more closely at this expression. The first part
>
> > ( ( EXTEND r ADD ( X AS Bi, Y AS Bj ) )
>
> > results in a relation in which each tuple contains both the old components
> > and the new components, and from that relation it is possible to determine
> > exactly what is different--tuple, by tuple. But then that /stated/
> > correlation is projected away by
>
> > { ALL BUT Ai, Aj } RENAME { Bi AS Bk, Bj AS Aj, Bk AS Ai},
>
> > so clearly, information is lost when translating an update into an
> > assignment. Now if we could just shift constraint enforcement to just
> > before that information is projected away, then we could specify transition
> > constraints declaratively.
>
> I'm not sure what relational assignment is to form an opinion if it
> adequately preserves information to be leveraged in transition
> constraints. It is obvious that transition constraint is nothing more
> than algebraic-relational expression that includes two variables: the
> state of relation before update R(t_1) and the state after R(t_2).- Hide quoted text -
Unfortunately, it just isn't that simple. Since the key components
that identify something can be different at different times yet still
identify that same something, there can be more than one transition
that yields a resulting state. For example, if the guy that had up to
this point been first in line at the bank was wearing a blue hat, and
if the guy that is now first in line is wearing a red hat, then one
possibility is that there is a different guy that is first in line,
the guy wearing the red hat, but another possibility is that the guy
that had up to this point been first in line is still first in line
but just put on a red hat. So which is it? If the transition
consisted of a delete/insert pair, then it's clear that it's the first
possibility, but if the transition consists of an update, then it's
clearly the second.
> - Show quoted text -
Tegiri Nenashi
> I think that the delete/insert pair states that
> there is a different thing with key p = 1, whereas the update states
> that the thing with key p = 1 merely appears different. In other
> words, the delete/insert pair describes two distinct things, whereas
> the update describes two distinct appearances of the same thing. The
> delete/insert pair,
>
> delete {(p=1,q=a)}
> insert {(p=1,q=a)}
>
> states that there are two distinct things with exactly the same
> components, just during adjacent intervals.
Why do you need to identify "things"? Unless you made a typo, please
also note, that I'm not allowing arbitrary deletions and insertions.
Insertions and deletions in my understanding are just differences
between old and new state, and vise versa. Therefore, deleting and
inserting the same relation {(p=1,q=a)} doesn't make any sense.
> Unfortunately, it just isn't that simple. Since the key components
> that identify something can be different at different times yet still
> identify that same something, there can be more than one transition
> that yields a resulting state. For example, if the guy that had up to
> this point been first in line at the bank was wearing a blue hat, and
> if the guy that is now first in line is wearing a red hat, then one
> possibility is that there is a different guy that is first in line,
> the guy wearing the red hat, but another possibility is that the guy
> that had up to this point been first in line is still first in line
> but just put on a red hat. So which is it? If the transition
> consisted of a delete/insert pair, then it's clear that it's the first
> possibility, but if the transition consists of an update, then it's
> clearly the second.
This "real life" example is not helping. I doubt customer hat is of
any concern to the bank business (unless it is ski hood), much less to
the general public.
Tegiri Nenashi
> If you're saying you're not sure what relational assignment is, it is
> the assignment of a relation value to a variable, aka pointer, ie., it
> is a language device. Don't confuse relational assignment with any
> of the relational operators, which involve no notion of pointers. I
> wish people would clarify whether they are talking about the RM or
> about some language or other.
I don't think assignment concept, in general, and relational
assignment, in particular, is useful anywhere beyond programming
environment. We have relation as function of time, and describe
relation evolution in terms of transitional constraints. This is in
the same spirit as dynamical systems are defined with differential
equations. I see no assignment concept in the latter, this is why I
assume it is not important in relational theory as well.
Kevin Kirkpatrick
> "Tegiri Nenashi" <TegiriNena...@gmail.com> wrote in message
>
> news:28078b81-9b60-412d...@l16g2000yqo.googlegroups.com...
>
>
>
>
>
> > On Mar 8, 3:45 pm, "Brian Selzer" <br...@selzer-software.com>
> > > During a database update, assuming that streetCrossIds are permanent
> > > identifiers, the relations,
>
> > > TrafficLights- {streetCrossId, state},
> > > TrafficLights% {streetCrossId, state, streetCrossId', state'}, and
> > > TrafficLights+ {streetCrossId, state}
>
> > > would be populated with tuples representing those traffic lights that
> > > have
> > > been removed from service, those traffic lights whose state is now
> > > different, and those traffic lights that have been placed into service
> > > respectively.
>
> > This is not a good example of database update. Why do we care what
> > state traffic light was during maintenance upgrade? I suspect they
> > turn it out before actually unplugging the electrics and removing
> > other mechanical artifacts. Moreover, the state is probably a
> > calculated value, function of time and perhaps some other conditions.
>
> If the state of a traffic light were always a function of time, then the
> constraint could possibly be written as a state constraint, but not all
> traffic lights follow a regular schedule. Some depend upon traffic
> conditions, others allow for manual intervention. (Those buttons you push to
> get the walk signal come to mind.)
>
> What I thought was obvious apparently isn't: a traffic light that is being
> removed from service would have to be switched off and dismantled for parts
> or relegated to the trash heap; a traffic light that is being placed into
> service would have to be assembled, installed and switched on, and so would
> also have to have an intial state; a traffic light that is neither being
> removed from nor placed into service must have been and must still be in
> service, though its state may or may not have changed. So the transition
> constraint,
>
> NOT EXISTS TrafficLights%
> (TrafficLights%.state = green AND TrafficLights%.state' = red)
>
> would apply only to traffic lights that have been and still are in service.
>
> > Any other realistic example of transition constraint?
>
> The transition constraint,
>
> NOT EXISTS TrafficLights+
> (TrafficLights+.state != red)
>
> would require that whenever a traffic light is placed into service that its
> initial state be red.
>
> > > I think you've misinterpreted my intent. I did not intend that state
> > > constraints be rewritten as transition constraints. I intend instead
> > > that
> > > both state constraints and transition constraints can be specified
> > > declaratively.
>
> > Good luck with that. For transition constraints you'd have to summon
> > automata theory? That is not one of the prettiest subjects of computer
> > science...
>
> I don't think we need to summon automata theory. A transition only ever
> involves two states: that which has obtained up to but not including the
> instant of change and that which obtains at that instant. How those states
> and the transition fits into an abstract state machine is incidental. For
> any implementation to support transition constraints, however, requires both
> a syntactic and semantic definition of what constitutes a state and what
> constitutes a transition.
>
> A state is simply a database--a collection of relations that together
> represent and by extension assert just what things have been in the world
> and exactly how those things have been related to each other. A transition
> is also a collection of relations, specifically three relations for each
> relation in the database, that together represent and by extension assert
> what in the world is different and exactly how, or more specifically, that
> which has been in the world but no longer is, that which is still in the
> world but appears different, and that which hadn't been in the world but now
> is.
>
> For example, if there are just relations P{A, B, C}, Q{A, D} and R{A, E} in
> the database, then a proposed transition will consist of the following
> relations
>
> P-{A, B, C} -- tuples to be "deleted" from P
> P%{A, B, C, A', B', C'} -- tuples in P to be "updated" with new components
> P+{A, B, C} -- tuples to be "inserted" into p
> Q-{A, D} -- tuples to be "deleted" from Q
> Q%{A, D, A', D'} -- tuples in Q to be "updated" with new components
> Q+{A, D} -- tuples to be "inserted" into Q
> R-{A, E} -- tuples to be "deleted" from R
> R%{A, E, A', E'} -- tuples in R to be "updated" with new components
> R+{A, E} -- tuples to be "inserted" into R
>
> One or more or even all of these relations may contain tuples during a
> database update. Just not none. The proposed relations are:
>
> P'{A, B, C} =
> (P MINUS (P- UNION P%{A, B, C}))
> UNION (P%{A', B', C'} RENAME {A' AS A, B' AS B, C' AS C'})
> UNION P+
> Q'{A, D} =
> (Q MINUS (Q- UNION Q%{A, D}))
> UNION (Q%{A', D'} RENAME {A' AS A, D' AS D})
> UNION Q+
> R'{A, E} =
> (R MINUS (R- UNION R%{A, E}))
> UNION (R%{A', E'} RENAME {A' AS A, E' AS E})
> UNION R+
>
> During a database update, and only during a database update, the relations
>
> P, P-, P%, P+, P', Q, Q-, Q%, Q+, Q', R, R-, R%, R+, R'
>
> contain the current database (P, Q, R),
> the transition (P-, P%, P+, Q-, Q%, Q+, R-, R%, R+),
> and the proposed database (P', Q', R').
>
> Since constraints only need to be checked during a database update, they can
> reference any of the above relations because it is only during a database
> update that they are all populated with data.
Brian,
I have a major objection to your "transition-constraints".
It is my understanding that databases are models of the real world,
and database values are collections of assertions (tuples) that fit
the database model (relations). At any given time, a database value
may contain assertions which are factually incorrect. When this is
detected, database users need to correct the database value by
updating/inserting/deleting appropritate tuples. Modifying a database
value from V1 to V2 is ONLY asserting that V1 is incorrect, and V2 is
correct. Nothing more.
Modifying a database value from V1 to V2 is NOT the same as
1) asserting that V1 was a fully correct description of the real world
at some earlier time,
2) V2 is a correct description of the real world at present, and
3) that the real-world transitioned directly from state V1 to V2 (e.g.
no other database value V3 exists such that V3 correctly described the
real world after V1 and before V2).
However (and please identify/correct the straw-man here if it is one),
it seems like this is precisely how you think a modification of a
database value from V1 to V2 should be interpretted. I'll try to use
your example to illuminate how absurd this is:
Let us assume that we need to model the predicate "The traffic light
at <cross_road> is <color>". I'll leave aside any attempt to find any
use for such a predicate, but let's assume this is all the information
our client cares to store about traffic lights at cross-roads.
We model the predicate with the aformentioned TrafficLight relation.
At 1:00 p.m., database user Alice asserts "The traffic light at <1st
and Elm> is <Green>"
The database receives :
UPDATE TrafficLights
SET color = 'Green'
WHERE crossroad='1st and Elm';
5 minutes later database user Bob asserts, "The traffic light at <1st
and Elm> is <Red>"
The database receives:
UPDATE TrafficLights
SET color = 'Red'
WHERE crossroad='1st and Elm';
Nobody has asserted any proposition that fits "The traffic light at
<crossroad> transitioned directly from <color1> to <color2>".
Specifically, Bob is NOT asserting "The traffic light at 1st and Elm
transitioned directly from green to red".
Perhaps
1) the light had always been red, but Alice is color-blind and mis-
reported it as 'Green', or
2) between when Alice and Bob reported its state, it was yellow (but
nobody noticed).
3) the light was green or yellow when Bob saw it, but he clicked the
wrong dropdown item and asserted 'Red'
Since our databse does not model the real world in a way that allows
us to infer 1, 2 or 3 (or any other plausible alternative), it cannot
use your "transition constraints" to assume and prevent #3.
Now, consider an alternative: the client actually *cares* about real-
world transitions of traffic lights and wants them to be modeled
explicitly. Peraps the client is a traffic department's QC division,
and needs to model the predicate, "The traffic light at <crossroad> is
transitioning too quickly from <original_color> to <final_color>".
This might be modeled with relation QuickLights {crossroad,
original_color, final_color}.
For this model, it may make sense to have constraints about real-world
state-transitions, perhaps with a foreign-key of QuickLights
{original_color,final_color} to
ValidLightTransitions {
{original_color='Green', final_color='Yellow'},
{original_color='Yellow', final_color='Red'},
{original_color='Red', final_color='Green'}}
Unlike in the first example, this "state-transition-constraint" makes
sense because now our database is modeling real-world state-
transitions; and can thus (rightly) forbid Bob from asserting: "The
traffic light at <1st and Elm> is transitioning too quickly from
<Green> to <Red>".
Thanks,
Kevin
Brian Selzer
"Kevin Kirkpatrick" <kvnkr...@gmail.com> wrote in message
news:20aa4363-4618-492f...@a12g2000yqm.googlegroups.com...
<big snip>
>
> Brian,
>
> I have a major objection to your "transition-constraints".
>
> It is my understanding that databases are models of the real world,
> and database values are collections of assertions (tuples) that fit
> the database model (relations). At any given time, a database value
> may contain assertions which are factually incorrect. When this is
> detected, database users need to correct the database value by
> updating/inserting/deleting appropritate tuples. Modifying a database
> value from V1 to V2 is ONLY asserting that V1 is incorrect, and V2 is
> correct. Nothing more.
>
> Modifying a database value from V1 to V2 is NOT the same as
> 1) asserting that V1 was a fully correct description of the real world
> at some earlier time,
> 2) V2 is a correct description of the real world at present, and
> 3) that the real-world transitioned directly from state V1 to V2 (e.g.
> no other database value V3 exists such that V3 correctly described the
> real world after V1 and before V2).
>
> However (and please identify/correct the straw-man here if it is one),
> it seems like this is precisely how you think a modification of a
> database value from V1 to V2 should be interpretted.
Not exactly. (1) The universe of discourse is not nor have I even sought to
imply that it is "the real world." The universe of discourse is just an
abstraction that might reflect some aspect of the real world, or might be
completely contrived. That said, under the Closed World Assumption, what is
not stated by the database is not true, and under the Domain Closure
Assumption, only those terms that appear in positive formulae denote (map to
things in the universe of discourse). So under those assumptions, a
database is a complete description of just a picture of the universe of
discourse. In particular, during a transition, V1 is a complete description
of what had since the last transition and up to now been the case /with
respect to the universe of discourse./ (2) Also during a transition and in
the same way that V1 is complete, V2 is a complete description of what is
now the case /again with respect to the universe of discourse./ (3) V1 is
what had been the case during the the half-closed interval [T1, T2), where
T1 is the point in time of the last transition and T2 is the time of the
present transition; V2 is what will have been the case during the half-open
interval [T2, now), once the transition is complete. There is no overlap;
there are no gaps; therefore, there cannot be a V3 between V1 and V2.
So what you're saying is that (1) we shouldn't specify constraints that can
keep garbage out of the database because the users that supply information
are unreliable witnesses; that (2) we shouldn't specify constraints that can
keep garbage out of the database because the users that supply information
are unreliable witnesses; and that (3) we shouldn't specify constraints that
can keep garbage out of the database because the users that supply
information are unreliable witnesses.
By your reasoning, there's just no point in defining /any/ constraints at
all.
<snip>
Brian Selzer
"Tegiri Nenashi" <Tegiri...@gmail.com> wrote in message
news:557d6f32-dccf-4512...@w35g2000prg.googlegroups.com...
> On Mar 18, 6:25 pm, br...@selzer-software.com wrote:
> > I think that the delete/insert pair states that
> > there is a different thing with key p = 1, whereas the update states
> > that the thing with key p = 1 merely appears different. In other
> > words, the delete/insert pair describes two distinct things, whereas
> > the update describes two distinct appearances of the same thing. The
> > delete/insert pair,
> >
> > delete {(p=1,q=a)}
> > insert {(p=1,q=a)}
> >
> > states that there are two distinct things with exactly the same
> > components, just during adjacent intervals.
>
> Why do you need to identify "things"?
Because things are what is in the universe of discourse. (I didn't want to
use the term "object" because it carries a lot of baggage that would
distract from the point I'm trying to make. Apart from "object," "thing" is
perhaps the most generic term for what can be discussed.)
> Unless you made a typo, please
> also note, that I'm not allowing arbitrary deletions and insertions.
> Insertions and deletions in my understanding are just differences
> between old and new state, and vise versa. Therefore, deleting and
> inserting the same relation {(p=1,q=a)} doesn't make any sense.
I didn't make a typo. I think that your characterization of insertions and
deletions is incorrect. There are things in the universe of discourse that
can appear different at different times. Twenty years ago I was fifty
pounds lighter than I am now, but that doesn't mean that wasn't me. Each
thing that persists travels a path through time, interacting along the way
with various other things, and thus identity for things that persist must
take into account the entirety of those paths, not just what appears in
arbitrary or even adjacent snapshots of the universe along the way;
therefore what serves to identify something can be different at different
times, and similarly, what serves to identify something at one time may
serve to identify something else at a different time. Whenever an employee
forgets his badge, he is issued one of five temporary badges, so more than
one of those temporary badges could serve to identify the same employee at
different times, and also each of those temporary badges could serve to
identify several different employees at different times. Consequently, one
cannot logically conclude that whenever identifiers at different times are
identical, the things that they identify are also identical, and therefore
the fact that a particular tuple appears in successive states does not imply
that the things referenced by the tuple at each state are identical.
Clearly deletions and insertions are not just differences between states--at
least not algebraic differences. Once one admits that there are things in
the universe of discourse that can appear different at different times, the
semantics of insert, update and delete become clear: insert describes the
beginning of the path that something travels through time, updates describe
milestones along the path that mark changes in appearance, and delete
describes the end of the path. So a transition consisting of a delete and
an insert that has no apparent effect on the database makes perfect sense
because it describes the end of one thing and the beginning of another.
<snip>
Walter Mitty
> least not algebraic differences. Once one admits that there are things in
> the universe of discourse that can appear different at different times,
> the semantics of insert, update and delete become clear: insert describes
> the beginning of the path that something travels through time, updates
> describe milestones along the path that mark changes in appearance, and
> delete describes the end of the path. So a transition consisting of a
> delete and an insert that has no apparent effect on the database makes
> perfect sense because it describes the end of one thing and the beginning
> of another.
This is mysticism.
Brian Selzer
What is your definition of mysticism? According to Webster, mysticism is
either
1: the experience of mystical union or direct communion with ultimate
reality reported by mystics
2: the belief that direct knowledge of God, spiritual truth, or ultimate
reality can be attained through subjective experience (as intuition or
insight)
3a : vague speculation : a belief without sound basis b : a theory
postulating the possibility of direct and intuitive acquisition of ineffable
knowledge or power
My argument has nothing to do with a mystical union or direct communication
with ultimate reality, does not even refer to God, spiritual truth or
ultimate reality, nor does it concern the acquisition of ineffable knowledge
or power. I don't think there is anything vague about my argument, and it
is based upon the premise that there are things in the universe of discourse
that can appear different at different times. I personally think that
premise is reasonable. If you don't, then I would like to hear your
argument.
paul c
(Pardon me for jumping in, ha ha, I should know better than to fall
for these flights of fancy, I guess I'm just a sucker for alternative
interpretations of the RM but I don't feel too guilty about that when
even the big guns are still debating some nuances.)
Come on, this is a very unreasonable thing to ask of Walter (or any of
the few posters here nowadays), given what you wrote. Eg., things
that appear different from what they are, not to mention time travel!
Give us a break. Suggest you stick to what is defineable as far as
a convention machine is concerned, eg., ask how the information
principle has got anything to do with these musings. Then you might
find a better reception. You keep saying "I think" without
demonstration, looks like you really mean "I want to believe".
Basically this means that you must convince people who are familiar
with such machines how whatever you advocate is possible using machine
language. D&D did this and you need to if want other people to dig
whatever you're talking about. You don't need to quote assembly
language to do this, just offer some classical paralles which are
known to be implementable.
Webster looks like it's gone downhill since I gave my old copy away,
what the hell is "ultimate reality"? Sounds like a TV show. Anyway,
you didn't mention #3a, the obvious link being vague speculation with
overtones of #1 and #2, plus possibly whatever #3b et cetera mention.
Do us a favour and look up 'mumbo-jumbo' in Webster's.
Bob Badour
Not that that would have anything to do with "ultimate reality" or anything.
Brian Selzer
I thought that distortion, misdirection and obfuscation were the tools of
propagandists and politicians, but even the propaganda arm of the Dimocrat
party--the mainstream media--has enough integrity to merely take literal
quotes out of context, rather than twist and distort what had been said to
the point of being unrecognizable. I never said that things could appear
different than what they are. That is more than even distortion to the
point of being mutilation.
<snipped the remainder of your inane and perverse rant>
Tegiri Nenashi
Ok, after tuple has been inserted into the table, did it get recorded
in the database? If it was, then we have two distinct database states,
and this insertion is visible to an observer (err, database user). If
this insertion was not committed, but immediately rolled back, then no
other transaction can possibly notice this change. For all practical
purposes the insertion and deletion of the "same thing" is NOOP.
Brian Selzer
I just want to point out that transactions differ from transitions in that
they are an implementation mechanism, along with isolation levels and the
notions of being committed or being rolled back. If a database user's
transaction is executing at a READ UNCOMMITTED isolation level, then yes,
the insertion would be visible, but then, that is a known consequence of the
READ UNCOMMITTED isolation level. At the SERIALIZABLE isolation level, all
other transactions that might possibly affect the result of a query are
blocked until the result is produced, so the insertion wouldn't be visible.
But more importantly, delete refers to tuples that are in the database, not
tuples that are being inserted, so a transition that consists of a delete
and an insert of a particular tuple is not a NOOP, but rather an assertion
that describes the end of the interval during which one thing persisted and
the beginning of the interval that a different thing persists. Bottom line:
you can't delete what isn't already there, nor can you insert what is
already there.
Walter Mitty
Actually, definition 3b (above) is pretty much on target with regard to this
discussion.
Consider the last few exchanges between Brian and Tegiri.
Tegiri opined as to how an update is essentially the same thing as a delete
followed by an insert. An eminently reasonable proposition,
given that any delta in a database that can be caused by an update can also
be caused by a suitable delete followed by a suitable insert.
As a side note, the constraints on the database might be violated between
the delete and the insert, but that's a digression.
Tegiri also offered up the delete and insert that exactly reverse each other
as an exceptional case, because the delta in the database, in this case, is
no diefference at all.
Brian jumped in on this case, and offered the opinion that a delete followed
by an insert represnts the destruction of a thing in the UofD followed by
the creation of a new thing in the UofD. In the case of an insert that ia
followed by a reversing insert, it means, according to Brian, that
something in the UofD has been destroyed, and replaced by an exact replica.
This reminds me of an old Steve Wright joke, but that's another digression.
In any event, the idea that something real can happen in the UofD and the
resulting difference in the database is no difference at all, fits awfully
well with "ineffable knowledge, intuitively acquired". If you look at a
database at one time, and then look at the database a little while later,
and there's no difference, how do you know that everything in the UofD
hasn't been destroyed, and replaced by an exact replica? You don't,
according to Brian.
If Brian knows such a thing, it doesn't come from studying the data. It
comes from ineffable knowledge, intuitively acquired. It's mystic crystal
revelation, and the mind's true liberation.
Walter Mitty
Actually, definition 3b (above) is pretty much on target with regard to this
discussion.
Consider the last few exchanges between Brian and Tegiri.
Tegiri opined as to how an update is essentially the same thing as a delete
followed by an insert. An eminently reasonable proposition,
given that any delta in a database that can be caused by an update can also
be caused by a suitable delete followed by a suitable insert.
As a side note, the constraints on the database might be violated between
the delete and the insert, but that's a digression.
Tegiri also offered up the delete and insert that exactly reverse each other
as an exceptional case, because the delta in the database, in this case, is
no diefference at all.
Brian jumped in on this case, and offered the opinion that a delete followed
paul c
...
>
> Actually, definition 3b (above) is pretty much on target with regard to this
> discussion.
> If Brian knows such a thing, it doesn't come from studying the data. It
> comes from ineffable knowledge, intuitively acquired. It's mystic crystal
> revelation, and the mind's true liberation.
Looks like the dimensions a relation has depends on one's sign.
rpost
>>> The mathematics of relational calculus and relational algebra are fully
>>> capable, AFAIK, of describing the difference between two states of a
>>> database.
[...]
>The algebra is capable of that if and only if each and every tuple has a key
>that permanently identifies the thing in the universe of discourse that the
>tuple maps to.
No, the algebra can describe the difference between database states
without any assumption on how these states are interpreted.
And as Walter Mitty already wrote, it is not in fact necessary that
databases are inpeepreted in such a way that tuples are about "things"
in the universe of discourse.
I think you are overstating your point, which was, if I understand
you correctly, that while relational algebra and calculus may be used
to express the contents of a database change, they do not express the
fact that the contents change; and this does need to be expressed in
some way when reasoning about database updates.
>But since that isn't a requirement of the RM, the RM must be
>in trouble! If different keys at different states map to the same thing in
>the universe of discourse, or if the same key at different states maps to
>different things in the universe of discourse, then how is it possible to
>describe exactly what is different between two states of a database.
It is really simple. However, you are right in that mutability of
keys and other aspects of the relationship between database contents
and its interpretation will fall outside the scope of that description.
--
Reinier
rpost
>> don't really express facts regarding those domain values,
>> they just help express information about other domain values.
>
>Tuples do not express facts about domain values. They contain domain
>values.
Duh.
True, I didn't express myself clearly enough.
But I don't need your lecturing. My point is that in a relational
database, the tuples of a relation often correspond not just to the
propositions of an associated predicate, but to observations; explicitly
asserted, rather than derived information. To propositional logic,
it's all the same, of course.
--
Reinier
Kevin Kirkpatrick
Fair enough, my statement could have been more precise; "Databases are
models of aspects of the real world; scoped by what is called the
domain of discourse."
> That said, under the Closed World Assumption, what is
> not stated by the database is not true, and under the Domain Closure
> Assumption, only those terms that appear in positive formulae denote (map to
> things in the universe of discourse).
Nope. The CWA says, that which the database doesn't affirm, it
denies. It doesn't say, "that which the database doesn't affirm, is
not true / factually false". I mean, if I create a database of US
states, enter the states to the best of my recollection, and leave
Hawaii out, Hawaii will continue to be a member of the US of A,
right? And if, the next day, I see a map and realize my mistake, and
INSERT 'Hawaii', I'm not claiming that the United States just annexed
a new territory, am I?
Sorry if this comes across as sophomoric, but without getting
agreement on such simple ideas, I can't figure out if we're just
talking past each other, or if you're some sort of weird crackpot.
> So under those assumptions, a
> database is a complete description of just a picture of the universe of
> discourse.
It's a description of the U-of-D based on human input, poor memory,
imperfect sensory data, etc., and thus subject to revision and
corrections. Do you believe that claims about the real-world stored
in databases are supernaturally inerrant?
> In particular, during a transition, V1 is a complete description
> of what had since the last transition and up to now been the case /with
> respect to the universe of discourse./
You start working at a new company, and their HR person enters some
information about you into the database, giving V1. You query the
database later that day and discover that according to V1, you were
born in 1917 (not 1971). In this hypothetical, what is V1 a
"complete description" of? If the HR person gets your frantic call,
apologizes, and updates the year-of-birth to 1971, (giving database
value V2), what real-world transition occured between V1 and V2?
Birthdays can't just change by 62 years in the real world - in light
of this, what role do you think transition-constraints should have
played in this situation? Would they have helped?
<snip>
>
> So what you're saying is that (1) we shouldn't specify constraints that can
> keep garbage out of the database because the users that supply information
> are unreliable witnesses; that (2) we shouldn't specify constraints that can
> keep garbage out of the database because the users that supply information
> are unreliable witnesses; and that (3) we shouldn't specify constraints that
> can keep garbage out of the database because the users that supply
> information are unreliable witnesses.
>
> By your reasoning, there's just no point in defining /any/ constraints at
> all.
>
Wow, sorry, but that is just obtuse. Constraints are *great* for
keeping garbage out. For instance, "The traffic light at <1st and
Elm> is <Blue>" should be excluded. "The traffic light at <1st and
1st> is <Blue>" should be excluded. These are garbage because they
describe impossible states of affairs. That's what constraints do:
they take your model of the universe of discourse, and prevent the
entry of claims about the real world which are nonsensical,
impossible, or leave some internal contradiction within the
database.
Your "transition constraints" don't do this. They don't constrain the
data at all; they constrain the means with which bad/incorrect/out-
dated data can be corrected. When can this possibly be useful?
User:"The database value V1 is incorrect, it should be V2".
TransCon: "Error... if V1 was correct, then V2 is impossible".
User: "Um, but V1 wasn't correct. It's incorrect, that's why I'm
changing it to V2"
TransCon: "Error... if V1 was correct, then V2 is impossible".
(and so on)
com...@hotmail.com
> >> Yes, but what I meant to say is that in general, the tuples
> >> don't really express facts regarding those domain values,
> >> they just help express information about other domain values.
>
> >Tuples do not express facts about domain values. They contain domain
> >values.
>
> Duh.
>
> True, I didn't express myself clearly enough.
>
> But I don't need your lecturing.
Of course I know you know tuples contain domain values.
What you didn't seem to know is that they do not express
information about domain values, since you wrote the
opposite. I'm only being precise and basic to justify my
points clearly. I guess you think I'm too basic. But I think
that many things you write contradict basics, and that thus
basics are relevant to my reply.
> My point is that in a relational
> the tuples of a relation often correspond not just to the
> propositions of an associated predicate, but to observations; explicitly
> asserted, rather than derived information. To propositional logic,
> it's all the same, of course.
Along the way you have said (along with a lot of other stuff
I contradict) that there is a distinction relevant to the user
between relations that observe changing things, those that
observe unchanging things and those that derive from
these; and that it is relevant to the user how any of these
are implemented. And I have said that there isn't. Other
than what the observing (changing and constant) relations
represent, to the *user* it's all the same. And treating them
them the same eases programming.
philip
paul c
I just want to comment on one point, users can think whatever they
want (when they away from the desk as it were), but when they are
operating the db, the only view they should take is that of the
intentions of the data design. If the design doesn't concern itself
with recording changes (as opposed to the result of recording
changes), eg., if the design doesn't handle 'before' and 'after', then
a user who concerns himself with that is a mystic!
Obviously a data design is just a mechanical reflection of one or more
chosen abstractions of reality. All mystics should make a vow to
remember daily what McCarthy said about submarines trying to swim.
Mystics are like Chickenman, they turn up all the time, no matter
where you go. It is a shame that they have started to breed with
technocrats, now neither label has any meaning.
rpost
>points clearly. I guess you think I'm too basic. But I think
>that many things you write contradict basics, and that thus
>basics are relevant to my reply.
Absolutely, and it is appreciated, but sometimes you stop there
and do not address the actual issue.
[...]
>Along the way you have said (along with a lot of other stuff
>I contradict) that there is a distinction relevant to the user
>between relations that observe changing things, those that
>observe unchanging things and those that derive from
>these;
Not quite. The distinction is between a priori knowledge
and a posteriori knowledge. Usually, relations that represent
the former are immutable, relations that represent the latter aren't.
One working with a database must understand how its relations
are to be interpreted, and this distinction is important in that.
It is good database design practice to try and keep them apart,
by keeping derived information out of the base relations,
putting it into queries and views. Of course this distinction
can also be made even when D&D's algebra is used. You deny
that the user needs to be aware of it.
>and that it is relevant to the user how any of these
>are implemented.
That, too, e.g. performance characteristics of operations
may be important.
>And I have said that there isn't. Other
>than what the observing (changing and constant) relations
>represent, to the *user* it's all the same. And treating them
>them the same eases programming.
It eases programming until you wonder
why the program doesn't work.
>philip
--
Reinier
rpost
>I just want to comment on one point, users can think whatever they
>want (when they away from the desk as it were), but when they are
>operating the db, the only view they should take is that of the
>intentions of the data design. If the design doesn't concern itself
>with recording changes (as opposed to the result of recording
>changes), eg., if the design doesn't handle 'before' and 'after', then
>a user who concerns himself with that is a mystic!
You are confusing two things.
1) The fact that updates to relational databases are possible,
that users need to be aware of what updates are possible and
what they will mean when they happen. This is just a matter of
understanding the intentions of the data design, as you put it.
2) The fact that a database may explicitly store information about
past states of affairs, by design, and that it is impossible to
obtain, from the *present* database state, information about
a past state of affairs if that information isn't retained by design.
This is obvious, and it's not what the disagreement is about.
>Obviously a data design is just a mechanical reflection of one or more
>chosen abstractions of reality. All mystics should make a vow to
>remember daily what McCarthy said about submarines trying to swim.
Obviously, windmills are a technological innovation that helped upset
the social order of the feudal world. Don Quixote may have been crazy,
but his windmills and his fight were real.
Your mystics are figments of your imagination.
--
Reinier
Jan Hidders
Oh dear. I'm afraid I only remember what E. W. Dijkstra said about
submarines and swimming. ;-)
-- Jan Hidders
paul c
...
>> Obviously a data design is just a mechanical reflection of one or more
>> chosen abstractions of reality. All mystics should make a vow to
>> remember daily whatMcCarthysaid about submarines trying to swim.
>
> Oh dear. I'm afraid I only remember what E. W. Dijkstra said about
> submarines and swimming. ;-)
>
> -- Jan Hidders
Sorry if I got the source wrong, Jan. Oh well, they were both smart
guys and I'd guess would have agreed no matter who said it.
paul c
...
> Obviously, windmills are a technological innovation that helped upset
> the social order of the feudal world. Don Quixote may have been crazy,
> but his windmills and his fight were real.
> Your mystics are figments of your imagination.
>
Yeah, sure. That's what they said to the very few who first
recognized the intruders in Invasion of the Body Snatchers and to the
boy in The Emperor's New Clothes who just couldn't see things that
weren't there.
I can't help it if English is my first language.
rpost
>I can't help it if English is my first language.
Dan is onze conversatie hiermee beeindigd.
Een prettige dag,
--
Reinier
Brian Selzer
<snip>
> Tegiri opined as to how an update is essentially the same thing as a
> delete
> followed by an insert. An eminently reasonable proposition,
> given that any delta in a database that can be caused by an update can
> also
> be caused by a suitable delete followed by a suitable insert.
If a user issues an insert, isn't it reasonable to assume that it concerns
something that isn't already represented in the database? If a user issues
a delete, isn't it reasonable to assume that it concerns something that
shouldn't still be represented in the database? If a user issues an update,
isn't it reasonable to assume that it concerns something that should still
be represented in the database? If those assumptions are reasonable, then
the assumption that an update is essentially the same thing as a delete
followed by an insert isn't.
The assumption that an update is essentially the same thing as a delete
followed by an insert effectively denies that there is a connection between
a database and the universe of discourse. And that is just absurd.
<snip>
Walter Mitty
It's exactly the opposite, Brian. The assertion that a given state of the
database makes different assertions about the UofD depending on how the
database got to that state is what breaks the connection between the
database and the UofD. It's the current state of the database, and not the
history of the database, that makes assertions about the UofD.
This is the nub of the debate between you and me. Let's let it rest here.
I'm not going to change your mind. And you're not going to change my mind,
or the minds of most of the participants.
paul c
...
> If a user issues an insert, isn't it reasonable to assume that it concerns
It's not "reasonable to assume" anything that doesn't obey the
Information Principle.
> ... the assumption that an update is essentially the same thing as a delete
> followed by an insert isn't.
>
There is no such assumption, it is a fact - you yourself posted the TD
definition that REMOVE's the 'deleted' attribute values.
You are just playing with words.
Brian Selzer
From an epistemic perspective, the Closed World Assumption relegates
everything that is knowable to being either known to be true or known to be
false. Whether that knowledge is faulty is a separate issue.
> I mean, if I create a database of US
> states, enter the states to the best of my recollection, and leave
> Hawaii out, Hawaii will continue to be a member of the US of A,
> right? And if, the next day, I see a map and realize my mistake, and
> INSERT 'Hawaii', I'm not claiming that the United States just annexed
> a new territory, am I?
>
No, you're not. You're issuing a correction. There is a significant
difference between a correction and a transition. A correction rewrites
history: it restates what has been the case since the last transition (or
perhaps even before that). A transition, on the other hand, writes history:
it marks the end of the interval associated with what had up to now been the
case and the start of the interval assocated with what is now the case. So
if there is a difference between a correction and a transition, how can the
one distinguish between them? It's quite simple, really: if all and only
corrections were to require explanation, then whenever an explanation is
supplied, what was just issued was a correction instead of a transition.
Define an attribute or set of attributes or even a set of relations to
record explanations, depending on how much detail you need, and then require
that whenever a correction is issued, an explanation must be supplied.
Constraints can then be defined so that they target just transitions and not
corrections, or different constraints can be defined that target just
corrections.
<snip>
Brian Selzer
You're being short-sighted. A relational database that states not just what
has been the case since the last update, but what has ever been the case is
called a historical database. It is a simple matter to define a set of
views on the historical database that represents just what has been the case
since the last update: restrict each relation to just those tuples that have
indefinite intervals, and then project away the interval attributes.
Moreover, every delete, insert or update that target those views maps to an
update, an update and an insert, or an insert against the historical base
relations, given the point in time that the delete, insert or update occurs.
So in effect, it can easily be argued that a database that is not historical
is essentially just a view on one that is.