On Formal IS-A definition

#41

"Erwin" <e.smout (AT) myonline (DOT) be> wrote

On 6 mei, 22:02, "Mr. Scott" <do_not_re... (AT) noone (DOT) com> wrote:

Quote:

"Erwin" <e.sm... (AT) myonline (DOT) be> wrote in message

news:88f215e4-8651-44cb-8d58-07b8dbea4a08 (AT) 37g2000yqm (DOT) googlegroups.com...
On 6 mei, 14:51, Erwin <e.sm... (AT) myonline (DOT) be> wrote:

On 6 mei, 14:14, "Mr. Scott" <do_not_re... (AT) noone (DOT) com> wrote:

QUOTE"Erwin" <e.sm... (AT) myonline (DOT) be> wrote in message

news:9fc21a72-6865-4a73-9183-a897275b6fdf (AT) 37g2000yqm (DOT) googlegroups.com...
On 6 mei, 09:00, "Mr. Scott" <do_not_re... (AT) noone (DOT) com> wrote:

"Tegiri Nenashi" <tegirinena... (AT) gmail (DOT) com> wrote in message

news:0b2f71d0-34b5-4661-a8f6-21a40cdb9989 (AT) n37g2000prc (DOT) googlegroups.com...

Given the two relations R and S, the R is a subtype of S or simply
"R
is an S" (was this the source of Reinier blunder?-) iff the two
conditions hold:

1. R ^ S = R (where the ^ is natural join operation). This can be
expressed succinctly as R < S with generalized subset constraint
"<".

The immediate consequence is that the attributes of S are the
subset
of attributes R (formally: R ^ [] < S ^ [] where the "[]" is the
relation with empty set of attributes and empty set of tuples, aka
DUM). Then, one may add second requirement that

2. Attributes of S form a key in relation R.

My question is if the condition #2 is really necessary. Consider
the
two relations:

Animals = [Name]
bear
sheep
wolf
;

Carnivores1 = [Name FavoritePrey]
bear deer
wolf sheep
;

They satisfy both conditions so that informally we say
"Carnivores1"
IS-A "Animals".

Contrast this with

Animals = [Name]
bear
sheep
wolf
;

Carnivores2 = [Name Prey]
bear deer
wolf sheep
wolf deer
;

I suggest that we still have "Carnivores2" IS-A "Animals". Do you
agree?

There is a problem here. Which scheme is better?

Employees{taxid,name,startdate} KEY{taxid},
ContractEmployees{taxid,name,startdate,enddate} KEY{taxid},
ContractEmployees[taxid,name,startdate] is a subset of
Employees[taxid,name,startdate]

or

Employees{taxid,name,startdate} KEY{taxid},
ContractEmployees{taxid,enddate} KEY{taxid},
ContractEmployees[taxid] is a subset of Employees[taxid]

Clearly the second scheme is equivalent to the first with respect to
information content, so if a ContractEmployee is an Employee in the
first
scheme, then it must also be in the second, but in the second
scheme,
the
set of attributes for Employees is not a subset of the set of
attributes
for
ContractEmployees. I think the effect of the foreign key constraint,
namely, that the components of the referenced tuple are effectively
'included' with the referencing tuple, must be taken into account.-
Tekst
uit oorspronkelijk bericht niet weergeven -

- Tekst uit oorspronkelijk bericht weergeven -

The first is a violation of BCNF.

QUOTE

No, it's not. Both schemes are in BCNF.

snip>- Tekst uit oorspronkelijk bericht niet weergeven -

- Tekst uit oorspronkelijk bericht weergeven -

OK. Your example was this :

Employees{taxid,name,startdate} KEY{taxid},
ContractEmployees{taxid,name,startdate,enddate} KEY{taxid},
ContractEmployees[taxid,name,startdate] is a subset of
Employees[taxid,name,startdate]

This tells me that within the Employees relvar, the FD
taxid->{name,startdate} holds.

And within ContractEmployees, the FD taxid->{name,startdate,enddate}
holds.
And the subset constraint tells me that the name and startdate
associated with any given ContractEmployees.taxid must be equal to the
name and startdate associated with the corresponding Employees.taxid.

Meaning that those two attributes are redundant in ContractEmployees.

Not a violation of BCNF ? My foot.- Tekst uit oorspronkelijk bericht
niet
weergeven -

- Tekst uit oorspronkelijk bericht weergeven -

QUOTE
Or let me put it differently.

If it is indeed true that the given example satisfies BCNF, then I
must conclude that normalization as the-formal-method-as-we-know-it,
fails to detect and eliminate this kind of redundancy.

And if normalization as a formal method fails to detect and eliminate
this kind of redundancy, then it is pretty darn useless and we can
just as well stop teaching it.

QUOTE

Well that argument is just plain stupid. Should you stop wearing your
seatbelt just because some collisions are so severe that people are
seriously injured or die even though they are wearing one?- Tekst uit
oorspronkelijk bericht niet weergeven -

- Tekst uit oorspronkelijk bericht weergeven -

<<QUOTE

Normalization was invented with the specific purpose of eliminating
redundancies such as that from the example you gave.

If BCNF still allows designs that contain/involve such reduncancies,
then the only possible conclusion is that normalization has failed to
achieve its stated goal. And please don't give me the argument that
normalization was already known not to be able to eliminate all
redundancies. The known situations in which this occurred are way
more "exotic" than what you presented as an example here, and that
remains true even if I cannot give a precise, formal and scientific
definition of what "exotic" means in this phrase.

And if we must acknowledge that BCNF has failed to achieve its stated
goal, then it must be either ditched or improved. In either case,
BCNF as we know it right now can be stopped talking about. Just like
2NF and 4NF can be stopped talking about because they are irrelevant
intermediate steps toward the normal forms that are (usually
considered as being) way more important.

Quote:

QUOTE

There are normal forms that involve inclusion dependencies as well as
functional dependencies. BCNF is not one of them.

#42

"Tegiri Nenashi" <tegirinenashi (AT) gmail (DOT) com> wrote

On May 5, 11:00 pm, "Mr. Scott" <do_not_re... (AT) noone (DOT) com> wrote:

Quote:

"Tegiri Nenashi" <tegirinena... (AT) gmail (DOT) com> wrote in message

news:0b2f71d0-34b5-4661-a8f6-21a40cdb9989 (AT) n37g2000prc (DOT) googlegroups.com...

Given the two relations R and S, the R is a subtype of S or simply "R
is an S" (was this the source of Reinier blunder?-) iff the two
conditions hold:

1. R ^ S = R (where the ^ is natural join operation). This can be
expressed succinctly as R < S with generalized subset constraint "<".

The immediate consequence is that the attributes of S are the subset
of attributes R (formally: R ^ [] < S ^ [] where the "[]" is the
relation with empty set of attributes and empty set of tuples, aka
DUM). Then, one may add second requirement that

2. Attributes of S form a key in relation R.

My question is if the condition #2 is really necessary. Consider the
two relations:

Animals = [Name]
bear
sheep
wolf
;

Carnivores1 = [Name FavoritePrey]
bear deer
wolf sheep
;

They satisfy both conditions so that informally we say "Carnivores1"
IS-A "Animals".

Contrast this with

Animals = [Name]
bear
sheep
wolf
;

Carnivores2 = [Name Prey]
bear deer
wolf sheep
wolf deer
;

I suggest that we still have "Carnivores2" IS-A "Animals". Do you
agree?

There is a problem here. Which scheme is better?

Employees{taxid,name,startdate} KEY{taxid},
ContractEmployees{taxid,name,startdate,enddate} KEY{taxid},
ContractEmployees[taxid,name,startdate] is a subset of
Employees[taxid,name,startdate]

or

Employees{taxid,name,startdate} KEY{taxid},
ContractEmployees{taxid,enddate} KEY{taxid},
ContractEmployees[taxid] is a subset of Employees[taxid]

Clearly the second scheme is equivalent to the first with respect to
information content, so if a ContractEmployee is an Employee in the first
scheme, then it must also be in the second, but in the second scheme, the
set of attributes for Employees is not a subset of the set of attributes
for
ContractEmployees. I think the effect of the foreign key constraint,
namely, that the components of the referenced tuple are effectively
'included' with the referencing tuple, must be taken into account.

<<QUOTE
I'd suggest different naming in the second case. The relation with
attributes {taxid,enddate} is called Terminations, and a Termination
IS not-An Employee. ContractEmployees relation is a view, which is a
join of Employees with Terminations.

Quote:

QUOTE

I think you missed my point. The foreign key constraint, by its very
nature, has the effect of extending each row in the foreign key table to
include all of the components in the corresponding row in the primary key
table. There can't be a row in the foreign key table unless there is a
corresponding row in the primary key table.

#43

On May 7, 9:20 am, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:

Quote:

David BL wrote:
On May 6, 9:10 pm, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:

If one is interested specifically in subtypes of supertypes, a proper
subset of a type with a proper superset of operations is a proper
subtype of that type. Thus, circle values are a subtype of ellipse
values and ellipse variables are a subtype of circle variables.

There is no subtype relationship between ellipse variables and circle
variables (in either direction).

Consider a procedure in an imperative language that is passed a
reference to a circle variable. Most generally the variable can be
used as an "in-out" parameter, meaning that the variable is both read
and written by the procedure. An ellipse variable can only be
substituted for out-parameters.

Ellipse variables are a proper subset of the variables where one might
store a circle,

Elements of sets are values, never variables. You cannot talk about
subset relationships between sets of variables because there is no
such thing as a set of variables.

Quote:

It has a proper superset of the operations permitted for
circle variables allowing one to also store a non-circular ellipse values.

Saying that one cannot apply circle value operations to ellipse
variables demonstrates nothing more than a confusion between values and
variables. One can apply all circle variable operations to ellipse
variables.

It's not clear to me what is meant exactly by an "operation" that acts
on variables instead of values. I would rather use the term
"procedure" to avoid confusion with operators in algebraic systems.
Even so, I'll drop the scare quotes below...

Why for instance, can't there be an operation that acts on a circle
variable to return the radius of the circle value that it currently
holds? I presume you would say it is not a valid operation on a
variable because otherwise that operation cannot generally be applied
to ellipse variables contradicting your last sentence just quoted.

Are you saying that a circle value has a radius, whereas a circle
variable does not? Well yes I agree. However, I find it strange to
say that there is a dereference operator to read the current value in
a circle variable, but you prohibit the operator defined as the
composition

GetRadius o Dereference.

#44

David BL wrote:

Quote:

On May 7, 9:20 am, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:

David BL wrote:

On May 6, 9:10 pm, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:

If one is interested specifically in subtypes of supertypes, a proper
subset of a type with a proper superset of operations is a proper
subtype of that type. Thus, circle values are a subtype of ellipse
values and ellipse variables are a subtype of circle variables.

There is no subtype relationship between ellipse variables and circle
variables (in either direction).

Consider a procedure in an imperative language that is passed a
reference to a circle variable. Most generally the variable can be
used as an "in-out" parameter, meaning that the variable is both read
and written by the procedure. An ellipse variable can only be
substituted for out-parameters.

Ellipse variables are a proper subset of the variables where one might
store a circle,

Elements of sets are values, never variables.

I am unfamiliar with any restrictions on what goes in sets.

Quote:

You cannot talk about
subset relationships between sets of variables because there is no
such thing as a set of variables.

Of course there is. Suppose I have a set of 3 variables and a dog { a,
b, c, Rosie } ...

Quote:

It has a proper superset of the operations permitted for
circle variables allowing one to also store a non-circular ellipse values.

Saying that one cannot apply circle value operations to ellipse
variables demonstrates nothing more than a confusion between values and
variables. One can apply all circle variable operations to ellipse
variables.

It's not clear to me what is meant exactly by an "operation" that acts
on variables instead of values. I would rather use the term
"procedure" to avoid confusion with operators in algebraic systems.

Operation is well-defined both for procedural and declarative languages.
Operators are symbols that denote operations per the ISO/IEC 2382
standard vocabularies.

#45

On May 6, 4:12*pm, Erwin <e.sm... (AT) myonline (DOT) be> wrote:

Quote:

OK. *Now I see what you meant by "that typo of mine". *It wasn't a
typo. *I deliberately used the term "relation algebra" to denote any
algebra that operates on relations. *I did try to follow the link you
gave, but it produced an http 404, or some such.

Google newsgroup reader decided to break URL with a new line.

Quote:

I know an algebra is nothing more than just a set of operators, so I
understand that anyone can define any algebra he(/she) likes (I also
understand why it takes an extremely bright mind to define one that
turns out to be useful), I am even aware of the consequences to the
extent that I have written myself in several places that "there is no
such thing as _the_ relational algebra", but I do not know how many
relation(al) algebras have been defined, let alone that I would know
the details of all of them.

The two similarly sounded algebras is an unfortunate artifact. Names
stick, no matter how awkward they are. A better name for De Morgan's
Relation Algebra is "The Algebra of Binary Relations", while Codd's
Relational Algebra should be called "The Algebra of Relations with
Named Attributes".

Quote:

I was implying that relation algebras are perfect abstractions for
modeling graphs. Relational model? Hardly.

Are you suggesting that even with generalized transitive closure being
included in the RM, there are still certain graph things that are
impossible to do with the RM ?

IIRC it has been demonstrated that RA amended with TC is Turing
complete.

Quote:

Again, my impression is that transitive closure doesn't fit into
relational model.

I have seen the comment that "TC was added to the RA in an ad-hoc
fashion after the unanswerability of some queries with Codd's algebra
was proved.". *I think I also understand how the formulation/
definition of the generalized version of TC was much the same kind of
response when it was proved that even with "regular" TC, queries such
as "how many distinct paths exist between a and b" were still
unanswerable. *But does that warrant the conclusion that "(G)TC
doesn't fit" ? *I'm hesitant to answer that with a "yes".

My idea is simple. If TC genesis is [De Morgan's] Relation Algebra,
why not to bring *all its operations* into Codd's Relational Algebra,
and not just one? Merging the two algebras together, so to speak.

#46

On May 7, 9:36 pm, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:

Quote:

David BL wrote:
On May 7, 9:20 am, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:

David BL wrote:

On May 6, 9:10 pm, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:

If one is interested specifically in subtypes of supertypes, a proper
subset of a type with a proper superset of operations is a proper
subtype of that type. Thus, circle values are a subtype of ellipse
values and ellipse variables are a subtype of circle variables.

There is no subtype relationship between ellipse variables and circle
variables (in either direction).

Consider a procedure in an imperative language that is passed a
reference to a circle variable. Most generally the variable can be
used as an "in-out" parameter, meaning that the variable is both read
and written by the procedure. An ellipse variable can only be
substituted for out-parameters.

Ellipse variables are a proper subset of the variables where one might
store a circle,

Elements of sets are values, never variables.

I am unfamiliar with any restrictions on what goes in sets.

Values are immutable. Variables accessed by imperative programs are
usually mutable. Sets are values. If a set contained a variable then
it wouldn't be immutable.

You appear to use what is called "Naive Set Theory" which is an
informal theory of sets that only uses natural language to describe
what they are. It suffers for example from Russell's paradox.

In modern axiomatizations of set theory such as ZFC, elements of sets
must be sets.
The axioms imply the existence of the empty set, and the axioms of
pairing, union, infinity and power set etc allow for bigger sets to be
constructed from smaller ones. The purpose of the axioms is to ensure
mathematicians agree on what is and isn't a set. For example there is
no axiom that allows for "the set of all sets", and indeed that can be
*proven* to not be a set by using the axiom of comprehension to yield
Russell's paradox as a proof by contradiction.

In practise mathematicians find it convenient to allow for ur-
elements, which are elements of sets that are not sets. However that
is only meant to be a convenience, and not a suggestion for example
that you can pretend that the collection of books on your bookshelf
comprise a mathematical set as defined in modern set theory.

Quote:

You cannot talk about
subset relationships between sets of variables because there is no
such thing as a set of variables.

Of course there is. Suppose I have a set of 3 variables and a dog { a,
b, c, Rosie } ...

No, that is not allowed. A dog is not a value. A variable is not a
value.

In logic, a *term* is defined recursively and may contain function
symbols and variables. For example in the term

s(10,x)

s is a function symbol with arity 2, 10 is a function symbol with
arity 0 (i.e. a "constant symbol") and x is a variable.

A variable in logic must not be confused with a variable in imperative
programs. The purpose of the former is essentially to allow for
quantification, and that's what distinguishes FOL from the much
simpler propositional logic.

Logicians have a formalised concept of giving meaning to terms - i.e.
so that a term denotes a value parameterised in the variables. An
interpretation must specify a set called the domain of discourse over
which variables range over, and the interpretation of each function
symbol is a function of the same arity, defined on tuples over the
domain of discourse.

For example, the domain of discourse might be the integers, and
interpreation of the term s(10,x) may be the set {10,x} for some given
value of the variable x which is assumed to range over the integers.
In that case it would be the case that {10,x} is a subset of the
integers for each value of x. But that shouldn't be interpreted to
mean that sets may contain variables!

Quote:

It has a proper superset of the operations permitted for
circle variables allowing one to also store a non-circular ellipse values.

Saying that one cannot apply circle value operations to ellipse
variables demonstrates nothing more than a confusion between values and
variables. One can apply all circle variable operations to ellipse
variables.

It's not clear to me what is meant exactly by an "operation" that acts
on variables instead of values. I would rather use the term
"procedure" to avoid confusion with operators in algebraic systems.

Operation is well-defined both for procedural and declarative languages.
Operators are symbols that denote operations per the ISO/IEC 2382
standard vocabularies.

Yes I agree that an operator is a symbol. What exactly does it mean
to "denote an operation"? So what does "operation" mean?

I think logicians treat "operator" and "function symbol" as synonyms.
I don't know about the word "operation". Do they use it to mean
"function"?

I'm not sure what these terms are assumed to mean in imperative
languages. I would rather new terms be used rather than hijack the
ones used by logicians. For example I think it's important to
distinguish between procedures and mathematical functions. Using
"operator" to mean a symbol that may denote either seems like it will
create a lot of confusion to me.

#47

Quote:

I am unfamiliar with any restrictions on what goes in sets.

Quote:

Values are immutable.

If I may be so bold as to interject my two cents : I suspect you two
are talking past one another.

It is true that mathematical set theory has no constraint on what type
of thing can or cannot be member of a set. It is also true that the
application of mathematical set theory in the context of relational
data management, talks about sets of values exclusively, thus in a
sense indeed limits sets to contain values exclusively.

I've never seen any theoretical stuff that tried, e.g., to define a
program as a set of variables and then exploit the properties/axioms/
postulates of set theory to deduce therefrom some kind of "set-
theoretical theory of programming". But of course that may just as
well me due to my limited and unidirectional vision.

Exchanging arguments without agreeing on the premisses is not a
fruitful debate. Regardless whether those arguments are detailed
reasonings or dense and almost cryptic oneliners.

#48

David BL wrote:

Quote:

On May 7, 9:36 pm, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:

David BL wrote:

On May 7, 9:20 am, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:

David BL wrote:

On May 6, 9:10 pm, Bob Badour <bbad... (AT) pei (DOT) sympatico.ca> wrote:

If one is interested specifically in subtypes of supertypes, a proper
subset of a type with a proper superset of operations is a proper
subtype of that type. Thus, circle values are a subtype of ellipse
values and ellipse variables are a subtype of circle variables.

There is no subtype relationship between ellipse variables and circle
variables (in either direction).

Consider a procedure in an imperative language that is passed a
reference to a circle variable. Most generally the variable can be
used as an "in-out" parameter, meaning that the variable is both read
and written by the procedure. An ellipse variable can only be
substituted for out-parameters.

Ellipse variables are a proper subset of the variables where one might
store a circle,

Elements of sets are values, never variables.

I am unfamiliar with any restrictions on what goes in sets.

Values are immutable. Variables accessed by imperative programs are
usually mutable.

None of which has anything to do with what one may compose a set with.

<irrelevent philosophical dead-ends snipped>

Quote:

You cannot talk about
subset relationships between sets of variables because there is no
such thing as a set of variables.

Of course there is. Suppose I have a set of 3 variables and a dog { a,
b, c, Rosie } ...

No, that is not allowed. A dog is not a value.

You must have some set telling me what I may or may not have a set of.
My set of three variables and a dog is a perfectly valid set just as
Socrates is a perfectly valid element of a set of men.

Watch! I can even apply set algebra to my set. Suppose I have another
set: the set of smells like skunk. I can interset the two sets to yield
a third set: { Rosie }

So there!

<more irrelevancies snipped>

Quote:

It has a proper superset of the operations permitted for
circle variables allowing one to also store a non-circular ellipse values.

Saying that one cannot apply circle value operations to ellipse
variables demonstrates nothing more than a confusion between values and
variables. One can apply all circle variable operations to ellipse
variables.

It's not clear to me what is meant exactly by an "operation" that acts
on variables instead of values. I would rather use the term
"procedure" to avoid confusion with operators in algebraic systems.

Operation is well-defined both for procedural and declarative languages.
Operators are symbols that denote operations per the ISO/IEC 2382
standard vocabularies.

Yes I agree that an operator is a symbol. What exactly does it mean
to "denote an operation"? So what does "operation" mean?

I suggest you check the standard vocabularies where the standard
definition is given.

#49

Erwin wrote:

Quote:

I am unfamiliar with any restrictions on what goes in sets.

Values are immutable.

If I may be so bold as to interject my two cents : I suspect you two
are talking past one another.

No, BL is trying to make shit up as he goes along.

#50

On May 8, 7:11*am, David BL <davi... (AT) iinet (DOT) net.au> wrote:

Quote:

Values are immutable. *Variables accessed by imperative programs are
usually mutable. *Sets are values. *If a set contained a variable then
it wouldn't be immutable.

We can generalize values and variables to elements of domains, where a
value is any element of a domain while a variable is an element of a
domain for which a homomorphism to another domain is defined.
Assigning to a variable would reduce to modification of the
homomorphism, so sets containing variables would not be modified by
assignment to a variable.