Mr. Scott wrote:
....
Tempts me to use a new term (at least I'm guessing it's new) - exclusion
dependency, even if there is nothing new about what it connotes. I
think it is hard to separate the influence of the typical dbms product
that doesn't allow one to express all the possibilities that an algebra
allows (maybe easier for me being quite ignorant of most products). This
makes talk of theory harder so most people end up habitually confusing
various product documentation with theory. Personally, given that any
dbms is likely to have a number of practical limitations, I don't see
why a dbms couldn't allow restricted use of negation so that a foreign
'reference'/exclusion dependency might be read as "A{attr} = A{attr} AND
(NOT B{attr})", which is basically of the same form as any inclusion
dependency or what I call a reference. (Any dbms that has a 'delete'
operator already supports similar negation implictly.) When people talk
of referential integrity I suspect that they are usually talking about
such an equation. Also suspect that we have a number of qualified names
for that basic form (of which 'primary key' was apparently the first)
simply because using the terms in a dbms' language makes it easy for
implementers to physically optimize. IMHO the implementation artifacts
don't really contribute to, nor involve, any essential theory except for
the usually ignored theory of optimization.

(I once read an interview of Codd where he more or less acknowledged
that in his first two papers he was struggling to find the best terms to
use. Eg., he said that the American 'normalization' of relations with
China inspired him to use same term. I've read where CJ Date hadn't
heard of this, but I recall the interview, probably from a magazine
called 'DBMS' around 1994.)

Sampo Syreeni wrote:
He was dealing with structured data all along. What he excluded was two
things i) unnecessary structure, ii) hidden structure.

I've seen that term being used, although far less commonly than is the
case for inclusion. There is not a whole lot of theory on that sort of
thing. (Which is why I forgot referential integrity can take that form
as well; Thanks, Mr. Scott!)

I've never seen a real life schema where this sort of constraint was
being enforced. Quite possibly because people don't come to think of
the logical presence, and thus the necessity of the constraint. The
main context in which I have in fact seen these used is a theoretical,
data modelling one. There the commonest case is to enforce the
distinction between plain and disjoint union types.

In practical, relational use that however mostly translates into a
data model which places the separate pieces of a disjoint union into
separate tables, and so makes the enforcement implicit. (Cf.
dependency preservation and all that.) The other kind of union then
tends to yield tables with lots of correlatedly null columns, or a
constellation of tables with a shared key (often a surrogate/OID/
whatever in case the participants in the union are different enough;
unsurprisingly the pattern often also leads to redundant columns as
well).

Well, not quite the same form because it's more general. But no, there
is no reason why that sort of functionality couldn't be available. And
in fact, even SQL supports it nowadays, via assertions, eventhough
just about nobody implements that part of the standard.

That's really quite a shame. Every single form of dependency I can
think of could be asserted that way, and the wider use of assertions
instead of more specialised forms of integrity constraint would
basically for RDBMS vendors to treat constraints in a fully
declarative, generalized, high level fashion. And if you then think
about it, solving that problem would also pretty much solve the
problem of incremental maintenance of materialized views, and vice
versa.

Quite so. More specifically, if you special case for just a few forms
of constraints (or other functionality at that), you can then special
case your underlying implementation to deal particularly well with
those special cases. That can considerably simplify implementation and
lead to substantially higher performance in those cases which fit into
your defined interface. Just like in our original example here:
foreign keys as a concept have been heavily optimized by always
demanding that the target is a candidate key and unconditionally
creating a a unique index for it.

That optimization comes at the price of generality. So when we think
about the relational model in all, such solutions don't really fit in
too well. I mean, from the very start relational data management has
been about making the model and its support machinery completely
general and declarative. No difference between fields at the logical
level. No difference between entities and relationships. No difference
in the level at which data reside, unlike in hierarchical databases.
No difference between pointers and the data pointed to, because
pointers are explicitly forbidden. No difference between table and
view. And so on.

Thus what the relational model would like is purely declarative,
algebraically complete assertions as the means of guaranteeing
integrity. Not specialized mechanisms like foreign keys -- those
belong in the same era as pointers to data do.

In this regard, there is a slight complication, though. If you think
about foreign keys, they have one extra aspect in addition to the
inclusion dependency they declare has to hold. That is the procedural
rule used to deal with impending violation.

Roughly there are two general approaches to this, and SQL allows a
limited form of both wrt foreign keys: 1) deny and roll back the
transaction if a violation is about to happen, or the hazier, far more
complicated option of 2) making it so that the update takes effect,
and then using whatever means to automatically propagate the logical
consequences of the update to once again make the integrity to fully
and globally check out.

As I said, even SQL has the latter in the limited form of "on delete
cascade". But in the fully general form, those operational semantics
would be exceedingly complex, and evenmore complex to specify exactly
if full generality was to be expected. So in that sense, we do have
some very serious theory going on in here, and the kind of theory that
hasn't been fully fleshed out yet even in the best of DB literature.
--
Sampo

On Oct 22, 7:34 am, Sampo Syreeni <de... (AT) iki (DOT) fi> wrote:
I agree that it is possible to enforce such join semantics with
domains but I'm not sure it is entirely appropriate. I say that
because to the greatest extent the RM is orthogonal to domains.
To quote CJ Date "Databases In Depth" Chapter 2 Summary:

"It's a very common misconception that the relational model deals
only with rather simple types: numbers, strings, perhaps dates
and times, and not much else. In this chapter, I've tried to show
that this is indeed a misconception. Rather, relations can have
attributes of /any type whatsoever/ -- the relational model
nowhere predicates what those types must be, and in fact they
can be as complex as we like ... In other words, the question as
to what types are supported is orthogonal to the question of
support for the relational model itself. Or (less precisely but
more catchily): /types are orthogonal to tables/."

To put this another way, the RM should be just as complete and
effective for a universe with a single domain as it is for a
universe with a rich domain set (such as you propose to handle
my GenericID join constraint example). And placing constraints
on /relational expressions/ seems as fundamental to the RM as
placing constraints on /relational values/.

By pushing such expression constraints off to domains, we are
admitting that the RM itself has no support for constraining
relational expressions and I'm not prepared to admit that
limitation. Especially since it does provide support for
constraining the values of relational variables.

I will also note that both Codd and Date proposed RM mechanisms
to operate the other way around ie to allow designers to force
cross-domain operations. Codd with "Domain Check Overrides" and
date with the THE_ operators that provide type coercion.

I think there are other views, see above. And I don't think either
of the views is accurate in this case and certainly may not apply
to every case one can imagine. In short, we should not let our lack
of imagination guide our design principles.

It's not for us to wonder such whys because our imagination is
usually quite limited. For example, GenericID seems an entirely
reasonable thing to me if I labelled every item I sent out (even
the coupons) with a barcode and have other relations expressing
facts about those barcodes apart from what they label. But
arguing about such specific design semantics I think is irrelevant
to basic questions of what constraint capabilities the relational
model supports.

Anyhow, the question here is not one of our imagination but rather
simply this: if it makes sense for the RM to support constraints
on relational /values/ (taken on by variables) why does it not
make sense to support constraints on relational /expressions/?
That is a question of general principle not specific design.

Frankly I don't understand the point of the above paragraph at
all. Also I don't see how entity integrity enters into this at
all; I'm assuming we follow the sage advice of having no NULLs
to begin with; so entity integrity is non-issue.

I don't think I'm talking about "physical level" types (posreps)
at all. And again, I'm not convinced of your conclusion that the
responsibility of constraining /relational/ expressions should be
shoved off to domains.

Consider Date's point that RM is orthogonal to type support.
Then what argument from principle do you have for prohibiting
the RM from defining constraints on relational expressions by
pushing that responsibility off to domain support? How would
we express the constraints in a universe with one domain?

Thanks!

KHD

Keith H Duggar wrote:

Domains, however, define what is or is not joinable because natural join
applies the equality comparison to attributes with like names, and
domains define equality comparisons.

On Oct 24, 3:13 pm, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:
Domains also define a set of permissible values for attributes.
However, that doesn't stop RM from adding additional constraints
to limit those values further. Why should relational operations
be any different in this respect from relational variables? Ie
why shouldn't the RM allow us to further constrain what domains
permit for both values AND operations?

KHD

Keith H Duggar wrote:

You asked about semantic joinability. Semantically, the join works if
like-named attributes have an equality comparison defined and not if
they don't.


Because the RM doesn't have anything much to say about domains. Domains
are a separate--albeit vitally important--concern.

Bob Badour wrote:
....
In RT, how could they not define equality?

Bob Badour wrote:
None in theory, I thought you were talking about attributes in the same
domain.

paul c wrote:

What reason would one have to define an equality comparison to compare
employee ids with department ids or with names? Or charge with current
or potential? Or age with price?