Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
Home
Discussion Groups
Database Servers
DB2InformixIngresMS SQLOraclePervasive.SQLPostgreSQLProgressSybase
Desktop Databases
FileMakerFoxProMS AccessParadox
General
General DB TopicsDatabase Theory
Related Topics
Java Development.NET DevelopmentVB DevelopmentMore Topics ...

Database Forum / General DB Topics / DB Theory / January 2008

Tip: Looking for answers? Try searching our database.

Function

Thread view: 
Enable EMail Alerts  Start New Thread
Thread rating: 
mAsterdam - 14 Jan 2008 21:56 GMT
vldm10 wrote:
> David Cressey wrote:
>> vldm10 wrote:
>>>> David BL wrote:
>>>>> This however doesn't change the fact that most authors
>>>>> define a (mathematical) relation as a set
>>>>> of ordered tuples, which means a function is not a relation
>>>>> (assuming, as most do, that a function has
>>>>> a defined domain and codomain).
>>>> I don't understand how the conclusion follow from the premise.
>>> I am afraid that you don't understand above conclusion
>>>  because you don't understand what function is.
>> What makes you think that?
>
> Definition1    A function from A to B is a rule that assigns,
> to each member of set A, exactly one member of set B.
>
> Is this good or bad definition for a function?
> If you thing that this is good definition for a function then
> please explain why this is good definition,
> else please explain why it is not good definition.
> Your answer on my question will be also answer on your question.

This is getting silly. Did you even read the question?

How did you assess David's lack of understanding 'function'?
What gave you that impression?

This is not the first time that 'function' popped up as pivotal
to some misunderstandings in cdt - but I fail to see where
the unclarity is right now.

(cdt glossary:)

> [Function]
> For now we have to live with different meanings
> of _function_ when talking about databases:
> "The function of this function is to get the tuples from B
> that are functionally dependant on A."
>
> Three different contexts, but just about the same meaning:
>
> General
> A purpose or use.
> Math
> A binary mathematical relation with at most
> one b for each a in (a,b).
> Software
> A subroutine, procedure, or method.
>
> notes:
> every operator is a function
> every function is a relation
>
> Please be specific.

--
What you see depends on where you stand.
Jan Hidders - 15 Jan 2008 00:36 GMT
> vldm10 wrote:
>
[quoted text clipped - 44 lines]
>  > A binary mathematical relation with at most
>  > one b for each a in (a,b).

This "at most one b for each a in (a,b)" makes me cringe! Moreover, it
seems to describe partial functions, which is not what is usually
understood under "function". I would make that:

"A binary mathematical relation over two sets D and C that associates
with each element in D exactly one element in C."

You might even add something about calling D and C domain and codomain
respectively, although that might open up a whole new can of worms.

Of course, I'm still convinced that the c.d.t. glossary is a waste of
time, but there you go. ;-)

-- Jan Hidders
mAsterdam - 15 Jan 2008 14:20 GMT
[snip]
>> (cdt glossary:)
>>
>>  > [Function]
...
>>  > Math
>>  > A binary mathematical relation with at most
>>  > one b for each a in (a,b).
>
> This "at most one b for each a in (a,b)" makes me cringe!

Irritation about the status quo is a starting point
to many improvements. I am sure the "Software" subentry (you
snipped it) makes functional programming adepts curl
their toes as well - I'll keep it until somebody provides
a better text.

> Moreover, it
> seems to describe partial functions, which is not what is usually
> understood under "function". I would make that:
>
> "A binary mathematical relation over two sets D and C that associates
> with each element in D exactly one element in C."

I like it.
I'll post a proposal for replacement in my answer to Vladimir.
To the native english speakers: is 'that' correct in Jan's sentence?

> You might even add something about calling D and C domain and codomain
> respectively, although that might open up a whole new can of worms.

We could go fishing - we need some bait.
I'll add some politically correct lyrics.

> Of course, I'm still convinced that the c.d.t. glossary is a waste of
> time, but there you go. ;-)

Doesn't my appreciation count for anything? ;-)

Thank you for contributing :-)

--
What you see depends on where you stand.
Marshall - 15 Jan 2008 14:55 GMT
> [snip]
>
[quoted text clipped - 24 lines]
> I'll post a proposal for replacement in my answer to Vladimir.
> To the native english speakers: is 'that' correct in Jan's sentence?

Yes.

There are different kinds of things that variously get called
functions:

 total functions, partial functions, multifunctions, aggregate
functions

Often "function" by itself means "total function" but sometimes it
doesn't.

It seems the difference between a total function and a partial
function is
just in what we want to call the domain. Division over the domain
(integer, integer) is partial; division over the domain (integer,
nonzero integer)
is total. What's up with that?

Some things out there produce more than one result, or a stream of
results. Sometimes these are called multifunctions and sometimes
generators.

Then we have things like sum() avg() etc. Aggregate functions.

Marshall
Sampo Syreeni - 15 Jan 2008 15:44 GMT
> Often "function" by itself means "total function" but sometimes it
> doesn't.

The standard reading of "function" implies "total". The only time
somebody qualifies it explicitly is when the context includes all these
"non-function functions" as well.

> It seems the difference between a total function and a partial
> function is just in what we want to call the domain.

Yes. The concept of partial functions only exists because in the context
of relative mathematical properties, natural extensions and restrictions
relate partial functions defined on supersets to actual functions on
subsets. And of course because functionality is quite a useful and
restrictive property of a general relation as well.

> Division over the domain (integer, integer) is partial; division over
> the domain (integer, nonzero integer) is total.

...which is an example of restriction of course.

Really, the weird part about this thread, to me, is how much time is
being spent on how various people construct relations, functions and the
like. In today's math it's much more common to go with the axiomatic
method and simply talk about the properties any such constructs possess.
Under that sort of treatment, most of the fuzziness goes away because
you can show that the various constructive versions are isomorphic to
each other; from the viewpoint of behavior, properties and logic, they
are all just models of the same basic mathematical intuition. Such a
viewpoint saves you a whole lot of quibbling.
Signature

Sampo Syreeni, aka decoy - mailto:decoy@iki.fi, tel:+358-50-5756111
student/math+cs/helsinki university, http://www.iki.fi/~decoy/front
openpgp: 050985C2/025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2

Kira Yamato - 15 Jan 2008 16:04 GMT
> [...]
> Really, the weird part about this thread, to me, is how much time is
[quoted text clipped - 7 lines]
> mathematical intuition. Such a viewpoint saves you a whole lot of
> quibbling.

But any serious students of mathematics has gone through at least one
exercise of rigorously defining what a function is.

You never want to be vague when it comes to math.  Vagueness will lead
to contradictions.

Signature

-kira

David Cressey - 15 Jan 2008 17:46 GMT
> Really, the weird part about this thread, to me, is how much time is
> being spent on how various people construct relations, functions and the
> like...
> ...Such a
> viewpoint saves you a whole lot of quibbling.

Perhaps reduction of quibbling is not a particular goal of some
contributors!?
mAsterdam - 15 Jan 2008 18:15 GMT
Marshall schreef:
>>> ..."A binary mathematical relation over two sets D and
>>> C that associates with each element in D exactly
[quoted text clipped - 4 lines]
>
> Yes....

Thank you.

--
What you see depends on where you stand.
Jan Hidders - 15 Jan 2008 22:04 GMT
> > Of course, I'm still convinced that the c.d.t. glossary is a waste of
> > time, but there you go. ;-)
>
> Doesn't my appreciation count for anything? ;-)

It does. It does. :-)

-- Jan Hidders
vldm10 - 15 Jan 2008 05:40 GMT
> vldm10 wrote:
>
[quoted text clipped - 55 lines]
> --
> What you see depends on where you stand.

I think it will be good to have two definitions for the functions in
your glossary.
Definition1    A function from A to B is a rule that assigns, to each
member of set A, exactly one member of set B.

And second definition is similar to Jan's suggestion, but slightly
changed:
Definition2
A function from A to B is a relation between A and B that associates
each element of A with exactly one element of B.

First definition says that a function do something. You can call it
intutive definition of a function. Here the function in fact is a
procedure as you mentioned.
Second definition is set theoretic.
mAsterdam - 15 Jan 2008 14:26 GMT
> I think it will be good to have two definitions for the functions in
> your glossary.
[quoted text clipped - 11 lines]
> procedure as you mentioned.
> Second definition is set theoretic.

Another difference I see with Jan's is a sense of direction.

How about this:
cdt glossary proposal:

>> [Codomain]
>> See function, math context.
[quoted text clipped - 44 lines]
>>     every operator is a function
>>     every function is a relation

--
What you see depends on where you stand.
Kira Yamato - 15 Jan 2008 15:52 GMT
>> I think it will be good to have two definitions for the functions in
>> your glossary.
[quoted text clipped - 24 lines]
>>> that for each tuple (A1, A2, ...An, ...Am) in R,
>>> An is an element of Sn.

This is not good enough.  It is possible that a value exists in the
domain Sn yet the relation has no corresponding tuple which holds that
value for An.

>>> 2. A domain is a set of values: for example
>>> "integers between 0 and 255",
>>> "character strings less than 10 characters long",
>>> "dates".
>>> Sometimes used synonymously with type.

This seems right.  A domain is just a set of values.  In relational
algebra, this set is required to be non-empty since attributes are
non-null.

>>> 3. Domain of a function. See function, math context.

On the other hand, mathematics does not require a domain to be non-empty.

>>> [Function]
>>> For now we have to live with different meanings
>>> of _function_ when talking about databases:
>>> "The function of this function is to get the tuples from B
>>> that are functionally dependant on A."

No, there is always just one meaning of function in database.

>>> Three different contexts, but just about the same meaning:
>>>
[quoted text clipped - 5 lines]
>>> with each element in D exactly one element in C.
>>> Set D is called the domain of the function, C its codomain.

Essentially correct, although to be rigorous you need to define how
such binary relation can define the meaning of "associating each
element in D exactly one element in C."

Not all binary relation has this property.

>>> 3. Software
>>> A subroutine, procedure, or method.

Yea.  It's really an abused use of the term in software design.  
Subroutines in software has no clear domain since same input arguments
can product different outputs.

>>> In both the math and software context, there is a sense of
>>> direction from domain (input) to codomain (output).
[quoted text clipped - 5 lines]
>>>
>>> Where x is input in the "f-machine" and f(x) is output.

Fair.

>>> notes:
>>>     every operator is a function
>>>     every function is a relation

Yes.

Signature

-kira

mAsterdam - 15 Jan 2008 16:26 GMT
Kira Yamato schreef:
> mAsterdam said:
>
[quoted text clipped - 28 lines]
>
> This is not good enough.  

Could you provide a better text?

> It is possible that a value exists in the
> domain Sn yet the relation has no corresponding tuple which holds that
> value for An.

Does the current text forbid that?

>>>> 2. A domain is a set of values: for example
>>>> "integers between 0 and 255",
[quoted text clipped - 5 lines]
> algebra, this set is required to be non-empty since attributes are
> non-null.

It is worm season, it seems :-)

>>>> 3. Domain of a function. See function, math context.
>
[quoted text clipped - 7 lines]
>
> No, there is always just one meaning of function in database.

Would s/meanings/uses/ take away your objection?
If not, which one meaning?

>>>> Three different contexts, but just about the same meaning:
>>>>
[quoted text clipped - 11 lines]
>
> Not all binary relation has this property.

IMHO this goes way beyond the glossaries purpose.
However, if you have a simple replacement that would cover this it
would be welcome.

>>>> 3. Software
>>>> A subroutine, procedure, or method.
>
> Yea.  It's really an abused use of the term in software design.  
> Subroutines in software has no clear domain since same input arguments
> can product different outputs.

I'll keep this for now. Let's hope somebody gets irritated enough to
write a better piece.

>>>> In both the math and software context, there is a sense of
>>>> direction from domain (input) to codomain (output).
[quoted text clipped - 13 lines]
>
> Yes.

Thank you for your comments.

--
What you see depends on where you stand.
Kira Yamato - 15 Jan 2008 19:14 GMT
> Kira Yamato schreef:
>> mAsterdam said:
[quoted text clipped - 14 lines]
>
> Could you provide a better text?

A domain is simply a set of values.

>> It is possible that a value exists in the domain Sn yet the relation
>> has no corresponding tuple which holds that value for An.
>
> Does the current text forbid that?

In your original definition, you require a tuple in R that holds that
value in order for that value to be in Sn.

I'm saying that this requirement is not needed.

>>>>> 2. A domain is a set of values: for example
>>>>> "integers between 0 and 255",
[quoted text clipped - 7 lines]
>
> It is worm season, it seems :-)

Yea.  Some relational algebra textbooks make a big case of why
attributes should not be null.

>>>>> 3. Domain of a function. See function, math context.
>>
[quoted text clipped - 10 lines]
> Would s/meanings/uses/ take away your objection?
> If not, which one meaning?

Perhaps s/meanings/definition/ is better.

>>>>> Three different contexts, but just about the same meaning:
>>>>>
[quoted text clipped - 15 lines]
> However, if you have a simple replacement that would cover this it
> would be welcome.

It is over the top for practical uses.  I was just being pedantic.  :)

> [...]

Signature

-kira

mAsterdam - 15 Jan 2008 19:42 GMT
Kira Yamato schreef:
> ...A domain is simply a set of values.

Ok,

>> [Domain]
>> 1. Set of values.
>>    Sometimes used synonymously with type.
>>
>> 2. Domain of a function. See function, math context.

>>>>>> [Function]
>>>>>> For now we have to live with different meanings
[quoted text clipped - 8 lines]
>
> Perhaps s/meanings/definition/ is better.

The next question is: where are those definitions?
I'll use 'uses' for now.

>>>>>> A binary mathematical relation over two sets D and C that
>>>>>> associates with each element in D exactly one element in C.
[quoted text clipped - 11 lines]
>
> It is over the top for practical uses.  I was just being pedantic.  :)

Ok.

I'll post the glossary in a new thread next.

--
What you see depends on where you stand.
Bob Badour - 15 Jan 2008 18:22 GMT
>>> I think it will be good to have two definitions for the functions in
>>> your glossary.
[quoted text clipped - 38 lines]
> algebra, this set is required to be non-empty since attributes are
> non-null.

Theoretically, the universal subtype has an empty set of values and the
union of all operations.

>>>> 3. Domain of a function. See function, math context.
>
[quoted text clipped - 7 lines]
>
> No, there is always just one meaning of function in database.

I got "and", "but", and "or". They'll get you pretty far. (Apologies to
our European friends and the younger crowd in the audience for the
inside joke.)

>>>> Three different contexts, but just about the same meaning:
>>>>
[quoted text clipped - 18 lines]
> Subroutines in software has no clear domain since same input arguments
> can product different outputs.

If one considers internal state an input, I am not entirely sure what
you said is true.

>>>> In both the math and software context, there is a sense of
>>>> direction from domain (input) to codomain (output).
[quoted text clipped - 13 lines]
>
> Yes.

Technically, in the standard vocabularies, every operator is a symbol
not a function.
Kira Yamato - 15 Jan 2008 19:25 GMT
>>>> [...]
>>>>>
[quoted text clipped - 10 lines]
> Theoretically, the universal subtype has an empty set of values and the
> union of all operations.

Can you explain a bit more what you mean here?

What is the universal subtype?  If it is an empty set, where is it used?

Can this type be an attribute in a relation?  I would think not, since
relational algebra requires all values in the tuples be non-null.

What do you mean by union of all operations?

>>>>> 3. Domain of a function. See function, math context.
>>
[quoted text clipped - 11 lines]
> our European friends and the younger crowd in the audience for the
> inside joke.)

Hmm...  Apparently, I'm an outsider.  :)

>>>>> Three different contexts, but just about the same meaning:
>>>>>
[quoted text clipped - 21 lines]
> If one considers internal state an input, I am not entirely sure what
> you said is true.

Well if you go that far, then since all Turing machines are
deterministic, hence it's just one big function.

>>>>> In both the math and software context, there is a sense of
>>>>> direction from domain (input) to codomain (output).
[quoted text clipped - 16 lines]
> Technically, in the standard vocabularies, every operator is a symbol
> not a function.

But every operator is also a function though.

For example, take the addition operator on a set of integers Z.  Then
for every pair of values x1, x2 in Z there exists a value y in Z such
that
    x1 + x2 = y.
So, I can define the function
    f : Z x Z --> Z
by the formula
    f(a, b) = a + b.

This is certainly a function.  So, every operator is indeed a function also.

Signature

-kira

Marshall - 15 Jan 2008 20:48 GMT
> >> This seems right.  A domain is just a set of values.  In relational
> >> algebra, this set is required to be non-empty since attributes are
[quoted text clipped - 6 lines]
>
> What is the universal subtype?

In type systems with subtyping, a universal subtype is the type that
is a subtype of all types. In lattice terms, it is "bottom".

> If it is an empty set, where is it used?
>
> Can this type be an attribute in a relation?  I would think not, since
> relational algebra requires all values in the tuples be non-null.

A type that includes at attribute of type bottom may exist,
but it cannot be instantiated. In relational terms, a relation whose
type includes an attribute of type bottom is necessarily an
empty relation.

Marshall
Bob Badour - 16 Jan 2008 01:56 GMT
>>>>> [...]
>>>>>
[quoted text clipped - 12 lines]
>
> Can you explain a bit more what you mean here?

I suspect _Third Manifesto_ mentions the universal subtype. Or see
Marshall's reply.

> What is the universal subtype?  If it is an empty set, where is it used?

You know what it means to be universal, right? You know what a subtype
is, right?

The universal subtype is not an empty set. It has an empty set of values
and the union of all operations.

> Can this type be an attribute in a relation?  I would think not, since
> relational algebra requires all values in the tuples be non-null.

Yes, as Marshall observed, it can be an attribute in an empty relation.

> What do you mean by union of all operations?

You know what a set is, right? You know what a union of sets is, right?
If a data type has a set of values and a set of operations defined on
those values, the universal subtype's set of operations is the union of
the sets of operations for all of its supertypes, which is all data
types because it is a universal subtype.

>>>>>> 3. Domain of a function. See function, math context.
>>>
[quoted text clipped - 14 lines]
>
> Hmm...  Apparently, I'm an outsider.  :)

http://www.youtube.com/watch?v=7TQByv_xkuc

It was one of the first primers on boolean logic operations I recall seeing.

>>>>>> Three different contexts, but just about the same meaning:
>>>>>>
[quoted text clipped - 47 lines]
>
> But every operator is also a function though.

No, in the standard vocabularies, every operator is only a symbol. The
symbol can stand for a function, but 'operator' signifies the symbol and
not the function.

[snip]
vldm10 - 20 Jan 2008 03:24 GMT
> > I think it will be good to have two definitions for the functions in
> > your glossary.
[quoted text clipped - 72 lines]
>
> - Show quoted text -

It will be good to say something about some specifics that hold true
for a function but doesn't hold for the relations in general.

1)   The rule "f pairs each x with just one y"
For example if one step on a scale then the scale will show just one
number. The scale will not show two or three numbers in same time. We
have here the law:  weight = gravity x mass or y = gx. Because "f-
machine" compute y, we can say that y is an extrinsic property of the
person who step on the scale.
Another example for above rule is a sequence of procedures:

----- > f1----- > f2 ------ >  ...

The sequence is very important for the structural programming and for
some other sciences.

For presenting function as "f-machine" we can use:
Definition1    A function from A to B is a rule that assigns, to each
member of set A, exactly one member of set B.
Counter - example: In a theatre we can imagine a function from the set
of visitors to the set of seats in the theatre. However we can't say
what is the rule here. This is weak side of Definition1. We can use
set-theoretic Definition2, formally it is OK for this example, but
still we don't know what the rule here is. As far as I know there is
no good definition for the algorithm; usually the algorithm is defined
as the fixed set of rules.

2) Construction of a relation
(i) For example the following relation R ( identifier1, A1, A2)  -
where identifier1 get values from a procedure P, and D1, D2 are
domains for A1, A2 - can't be constructed as the product of P x D1 x
D2
because P is not set, it is the procedure. So to construct a relation
we must have ready all sets.
(ii) The pair primary key - foreign key, can find each other by
matching. However m-n relationship need some third agent, usually a
data entry person, who will pair every pair, it can be the millions of
these pairs. On the other hand if we have a function, then for every x
the function will compute the corresponding y.

3) Codomain
The functions don't have so strict codomain as a relation. The
codomain of function can be a superset of the range of the function.
For example Bourbaki aproach to the function is based on the set of
all functions from A to B. Here it is better to work with a codomain
than with the range of the functions.

This is longer text, but the function is really basic thing. In fact I
am surprise that people who are good at this field didn't write
anything.
mAsterdam - 20 Jan 2008 11:17 GMT
>>> I think it will be good to have two definitions for the functions in
>>> your glossary.
[quoted text clipped - 13 lines]
>> How about this:
>> cdt glossary proposal:
[snipped changed entries]
>>>> [Function]
>>>> For now we have to live with different meanings
[quoted text clipped - 20 lines]
>>>>     every operator is a function
>>>>     every function is a relation

Thank you for the f-machine. It simplifies and clarifies.

> It will be good to say something about some specifics that hold true
> for a function but doesn't hold for the relations in general.

There is a 'sense of direction' in the [Function] entry.

> 1)   The rule "f pairs each x with just one y"
> For example if one step on a scale then the scale will show just one
[quoted text clipped - 8 lines]
> The sequence is very important for the structural programming and for
> some other sciences.

This however, IMO complicates without need:
'extrinsic'?
'sequence of procedures'?
'structural programming'?

> For presenting function as "f-machine" we can use:
> Definition1    A function from A to B is a rule that assigns, to each
[quoted text clipped - 6 lines]
> no good definition for the algorithm; usually the algorithm is defined
> as the fixed set of rules.

I do not understand what you are saying here.
Maybe it is a language thing.

> 2) Construction of a relation
> (i) For example the following relation R ( identifier1, A1, A2)  -
[quoted text clipped - 17 lines]
>
> This is longer text,

That's not really a problem. As it is, it is not ready for inclusion.
I can't simply copy and paste it and say: this text improved (which I
could with the f-machine). Did you read the 'How to contribute' part?

> but the function is really basic thing. In fact I
> am surprise that people who are good at this field didn't write
> anything.

Many are not interested.
Maybe it is good enough for the ones who are.

Bob Badour would prefer something different for
>>>>     every operator is a function
if he'd care.

--
What you see depends on where you stand.
vldm10 - 20 Jan 2008 19:27 GMT
> This however, IMO complicates without need:
> 'extrinsic'?
> 'sequence of procedures'?
> 'structural programming'?

My intention here was to explain why function is not same as relation,
and I separated some important characteristics of the functions in
three groups.
There is old definition of the function introduced by Leibniz, and
modern definition, defined by the group of mathematicians which wrote
under name Bourbaki. The Bourbaki definition became the first to
define function in terms of a set of ordered pairs. In Bourbaki
definition there is also part which define some additional conditions.
Now, there are discussants in this group, who insist that function is
just a kind of relation. Although the concept of relation is
important, insisting only on this concept can cause a misunderstanding
of the function.
In first part I wrote about importance of the rule: "f pairs each x
with just one y"
For example almost all laws in physics are in the form of a function,
satisfying this simple rule. Very important structures as the
sequences are implied by this rule (and not only by this rule).  So I
don't think that this should go in the glossary, but it should be
clarified, because it is about basic things.

> > For presenting function as "f-machine" we can use:
> > Definition1    A function from A to B is a rule that assigns, to each
[quoted text clipped - 9 lines]
> I do not understand what you are saying here.
> Maybe it is a language thing.

This about "f-machine" should be supported by some background and it
is Definition1. If you note this definition doesn't have term
relation. Definition1 "smells" on a computation process. The counter-
example shows a weak side of Definition1. This can open a discussion
about the problems related to a definition of computable or algorithm,
what is not necessary for one glossary. Rather this is just one
interesting counter-example.

As conclusion, in my opinion you can add Bourbaki definition
(Definition2) now or later.  So your glossary can cover "computable"
approach and also the set abstract approach. It will be OK and enough,
although there are some other approaches as the category theory for
example.

Vladimir Odrljin
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2009 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.