Database Forum / General DB Topics / DB Theory / January 2008
Function
|
|
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
|
|
|