Database Forum / General DB Topics / DB Theory / June 2008
POOD and the Unique Name Assumption
|
|
Thread rating:  |
Brian Selzer - 09 Jun 2008 14:02 GMT Does the Unique Name Assumption apply only to individuals, or does it apply also to relations? Under an interpretation where constant symbols are mapped to individuals and predicate symbols are mapped to relations, if a and b are constant symbols and P and Q predicate symbols and if neither aPb nor aQb fail to denote, can aPb ever mean exactly the same thing as aQb?
And if the Unique Name Assumption does apply also to relations, then what impact does that have on POOD?
Marshall - 10 Jun 2008 07:28 GMT > Does the Unique Name Assumption apply only to individuals, or does it apply > also to relations? Under an interpretation where constant symbols are [quoted text clipped - 4 lines] > And if the Unique Name Assumption does apply also to relations, then what > impact does that have on POOD? I guess I don't really know what this "Unique Name Assumption" is. But ordinarily, the mapping from names to things being named is a function, but not necessarily the reverse.
As to whether aPb can ever mean the same thing as aQb:
2+0 = 2-0
Marshall
Brian Selzer - 11 Jun 2008 01:05 GMT >> Does the Unique Name Assumption apply only to individuals, or does it >> apply [quoted text clipped - 8 lines] > > I guess I don't really know what this "Unique Name Assumption" is. The Unique Name Assumption ensures that whenever two names are different, the objects they represent must also be different.
> But ordinarily, the mapping from names to things being named > is a function, but not necessarily the reverse. > > As to whether aPb can ever mean the same thing as aQb: > > 2+0 = 2-0 The /result/ of 2+0 is the same as the /result/ of 2-0, but is the meaning of an expression the same as the result of the expression? It seems to me that how one arrives at a result can be just as important as the result. For example, if a man turns left onto the sidewalk in front of his house and then proceeds around the block, he will end up at the exact same place as if he had turned right onto the sidewalk and then proceeded around the block.
> Marshall Marshall - 11 Jun 2008 18:29 GMT > >> Does the Unique Name Assumption apply only to individuals, or does it > >> apply [quoted text clipped - 11 lines] > The Unique Name Assumption ensures that whenever two names are different, > the objects they represent must also be different. What is motivation for such an assumption? It doesn't seem to hold in any formal system I can think of.
> > But ordinarily, the mapping from names to things being named > > is a function, but not necessarily the reverse. [quoted text clipped - 9 lines] > then proceeds around the block, he will end up at the exact same place as if > he had turned right onto the sidewalk and then proceeded around the block. Sure.
"2+0" != "2-0"
However
2+0 = 2-0
It seems straightforward enough. "2+0" and "2-0" are two different names, expressions specifically, for the same thing.
Marshall
Bob Badour - 11 Jun 2008 20:33 GMT >>>>Does the Unique Name Assumption apply only to individuals, or does it >>>>apply [quoted text clipped - 39 lines] > It seems straightforward enough. "2+0" and "2-0" are two > different names, expressions specifically, for the same thing. The unique name assumption sounds like asking for aliasing errors.
Brian Selzer - 12 Jun 2008 12:21 GMT >>>>>Does the Unique Name Assumption apply only to individuals, or does it >>>>>apply [quoted text clipped - 49 lines] > > The unique name assumption sounds like asking for aliasing errors. The unique name assumption is concerned with how first order language elements are mapped to objects in the Universe of Discourse. How could forcing that mapping to be bijective cause aliasing errors?
Marshall - 14 Jun 2008 08:25 GMT > >>>>I guess I don't really know what this "Unique Name Assumption" is. > [quoted text clipped - 7 lines] > elements are mapped to objects in the Universe of Discourse. How could > forcing that mapping to be bijective cause aliasing errors? Well, to be pedantic (and who doesn't love an opportunity for that?) I'd have to say here we're talking about *anti* aliasing errors.
You said specifically "language elements." So that definitely means things like variable names, and not values from the domain of discourse. Yes?
So under the UNA, an expression like
AxEy:x=y
will be false, but ordinarily it would be true. So ... that's going to be weird.
In fact, it occurs to me that the UNA can be expressed with a rewrite rule with an inequality and an implication. Thus:
AxEy:x=y
with the UNA assumed is the same as
AxEy:x!=y -> x=y
without the UNA assumed.
This makes it clear that the UNA makes first order languages less expressive.
Marshall
Brian Selzer - 14 Jun 2008 21:35 GMT >> >>>>I guess I don't really know what this "Unique Name Assumption" is. >> [quoted text clipped - 16 lines] > things > like variable names, and not values from the domain of discourse. Yes? No. Not all language elements can map to objects in the Universe. Certainly not variable names. There are two sets of symbols in a first order language whose members can: the set of constant symbols, each of which maps to an individual, and the set of predicate symbols, each of which maps to a relation. There is also a set of individual variables, but variables do not map directly to individuals in the universe. They are placeholders for that which does.
Incidentally, Date refers to the Unique Name Assumption in the chapter on Logic-Based Databases in /An Introduction to Database Systems/ (page 792 in the Eighth Edition). Of course in the same paragraph he also mentions the Domain Closure axiom, but his interpretation of Reiter appears to be flawed in the same way as his interpretation of the unique name assumption:
3. The "unique name" axiom, which states that every constant is distinguishable from all of the others (i.e., it has a unique name).
4. The "domain closure" axiom, which states that no constants exist other than those in the database domains.
Is problematic because not all of the members of a domain necessarily denote, nor do their referents necessarily exist. For example, suppose that you have a part number A-12349-0 that today happens to be the next internal part number to be used. It currently doesn't refer to any particular assembly, because it hasn't yet been assigned to one. Depending on decisions made today, it could end up referring to one of several assemblies whose design has been quoted. So if quote 103256 is won, and the paperwork reaches engineering first, then A-12349-0 would refer to the assembly quoted on quote 103256, but if the paperwork for quote 103847 reaches engineering first, then A-12349-0 would refer to the assembly quoted on quote 103847. Reiter, in "Equality and Domain Closure in First-Order Databases" (JACM, April 1980), writes,
3. Closed Databases
Let {c1, ..., cp} be all of the distinct constant signs occuring in the formulas of a database DB. These are finite in number since there are just finitely many formulas in DB. Then the following is the /domain closure axiom/ for DB:
(x) x = c1 \/ ... \/ x = cp. ["(x)" is Reiter's notation for "forall x"]
If DB contains its domain closure axiom, then DB is called a /closed database/. In effect a closed database DB restricts the universe of discourse to just those individuals denoted by the constant signs of DB. As far as DB is concerned, no other individuals exist.
Date mistakenly equates membership in a database domain with "occuring in the formulas of a database," and as my example shows, just because a constant appears in a domain doesn't mean that it denotes--that is, that it references an individual that either exists or existed. Equally flawed is his take on the "unique name" axiom: Of course every constant should be distinguishable from all other constants, but that isn't what the "unique name" axiom is about. Completely missing is the idea that whenever two symbols are distinguishable, their referents in the Universe of Discourse must also be distinguishable.
> So under the UNA, an expression like > > AxEy:x=y > > will be false, but ordinarily it would be true. So ... that's going to > be weird. So under the UNA, an expression like
AxEy:x=y
would be true.
<snip>
Brian Selzer - 12 Jun 2008 01:55 GMT >> >> Does the Unique Name Assumption apply only to individuals, or does it >> >> apply [quoted text clipped - 18 lines] > What is motivation for such an assumption? It doesn't seem to hold in > any formal system I can think of. The Unique Name assumption, when combined with the Closed World and Domain Closure assumptions provides the basis for answering negative queries and queries that involve counts. For example, if you issue a query like
"How many widgets are blue?"
against a relation containing widget names and colors, but widget names do not follow the unique name assumption, then more than one widget name could reference the same widget, and thus even though the names are unique, the number of widgets could be completely different than the number of widget names. Consequently, you can't rely on the answer without the Unique Name Assumption. A query like,
"How many widgets are not blue?"
can be answered only when all three assumptions are in effect. The Domain Closure Assumption and Closed World Assumptions make it possible to determine which widget names denote and which widget names that denote are associated with a color that is not blue, but it is only under the Unique Name Assumption that the actual count of widgets that are not blue can be calculated.
>> > But ordinarily, the mapping from names to things being named >> > is a function, but not necessarily the reverse. [quoted text clipped - 27 lines] > > Marshall
|
|
|