Using the RM for ADTs
David BL
database. Circuits are abstract mathematical objects (i.e. "values")
independent of physical layout. There is no requirement to label
individual components (e.g. all 1 ohm resistors are
indistinguishable), nor any requirement to label circuit nodes.
The reason for recording circuit values in a physical database is
outside the scope of this discussion.
Two circuits are equivalent if they are isomorphic. A model for a
circuit value must define exactly when circuits are identical. Failure
to do so would mean for example that a set of circuit values is ill-
defined (e.g. one cannot determine the cardinality of the set).
In principle a very large circuit can consist of thousands of
components, wired up in a complex network. Recursive types cannot
eliminate the need for abstract identifiers.
One approach is to use abstract identifiers for the circuit nodes, and
use relations such as:
resistor(N1,N2,R) :- there is a resistor of value R
connected between nodes N1,N2.
This raises the question of whether the following symmetry
resistor(N1,N2,R) <=> resistor(N2,N1,R)
should be an integrity constraint. If so then in the logical model
information is represented twice and it complicates updates. If not
then there are potential surprises when using the relation. Do we
take the union of the resistors connected from N1 to N2, and N2 to
N1?
Two or more resistors connected in parallel between a given pair of
nodes are always equivalent to some single resistor value, so in
theory we could make {N1,N2} the key. If we want to model resistors
in parallel then even if the key is {N1,N2,R} there cannot be multiple
resistors of the same value. To model that we could instead use:
resistor'(N1,N2,R,M) :- there are M resistors
of value R connected (in parallel) between
nodes N1,N2.
I find it curious that we would only tend to record the tuples where
M>0. Normally under a closed world assumption one expects the set of
tuples for a given relation to be uniquely defined. However in this
case, under CWA, a tuple with M=0 can be removed without changing the
circuit value. Note as well that a similar issue would occur in the
relation
resistor''(N1,N2,C) :- there is a resistor with
conductance C (in siemens) connected between
nodes N1,N2.
because resistors with zero conductance are equivalent to no resistor
at all. I find this interesting because it complicates the definition
of circuit identity. One could apply the integrity constraint C>0,
however that somehow seems artificial in a logical model, and more
like a rule an implementation would impose.
I'd like to know whether circuit identity can be implicit in the
database schema by treating abstract identifiers specially. If there's
still ambiguity in the model then a comparison operator must be
separately and explicitly defined. Is that acceptable given that
C.Date says the relations *are* the logical model?
Tuples have a well defined definition of equality (they must have the
same attribute names and values), and so also for relations which are
sets of tuples. One can't mess with these definitions! It follows
that a tuple with relation valued attributes cannot really be used to
define a possrep for a circuit if it fails to define logical
equivalence as we would like. The missing concept seems to be
encapsulation in the sense used for an ADT defined in terms of a
private implementation.
Cimode
The definition of an entity relation according to its properties or to
a specific context is not a relational definition.
Brian Selzer
"Cimode" <cim...@hotmail.com> wrote in message
news:429001d6-ac23-42bb...@b9g2000yqm.googlegroups.com...
What identifies a resistor is an unordered pair of nodes and a resistance,
so the relation representing resistors could reflect that--e.g.
resistor{Nodes,R} where Nodes is a set of nodes. At first I thought that if
the domain of nodes is a total order, then a constraint can be specified
that forces N1 < N2. But that introduces unnecessary structure that might
complicate the algorithm for determining whether two circuits are
isomorphic.
Incidentally, most resistors are labeled with color bands that are read from
left to right, or with verbiage indicating the resistance, precision and
power rating. When resistors are inserted into a board so that the bands or
verbiage are not oriented as expected, automated optical inspectors might
reject the board, even though the circuit would work regardless of the
orientation of the resistor.
I think it might be simpler to assign artificial identifiers to the
components instead of the nodes. It is certainly more intuitive. Each
component has a finite number of leads, and each lead can connect with zero
or more components, possibly other leads on the same component. For
example, a NOR gate becomes an inverter if you tie the inputs together. The
circuits can then be represented entirely as a set of unordered pairs:
{{component, lead}, {component, lead}}
And then isomorphism between circuits can be determined by substituting the
symbols for the components--something like how alpha conversion works in the
lambda calculus. Treat each set of pairs as a function where the artificial
identifiers for each component are bound variables in the function, then if
the functions are equivalent modulo alpha conversion, then the circuits are
equivalent whenever the component properties are identical.
I think that for components with two leads that can operate in either
orientation, if the lead identifiers were also treated like bound variables,
along with the component identifiers, then circuits would still be
considered equivalent even if one or more of the components that can be
reversed are.
David BL
> I think it might be simpler to assign artificial identifiers to the
> components instead of the nodes. It is certainly more intuitive. Each
> component has a finite number of leads, and each lead can connect with zero
> or more components, possibly other leads on the same component. For
> example, a NOR gate becomes an inverter if you tie the inputs together. The
> circuits can then be represented entirely as a set of unordered pairs:
>
> {{component, lead}, {component, lead}}
Consider a node to which n components are connected and n is large.
Using pairwise connections can either be exceedingly arbitrary (by
only representing n-1 pairs) or it makes for enormous redundancy (by
representing all n(n-1)/2 pairs).
I think this is much worse that the symmetry problem with resistors.
Note that netlists used by circuit simulation programs like SPICE tend
to use something similar to what I discussed - i.e. for each component
list all the nodes to which it is connected. One difference is that
they require component labels as well as node labels.
> I think that for components with two leads that can operate in either
> orientation, if the lead identifiers were also treated like bound variables,
> along with the component identifiers, then circuits would still be
> considered equivalent even if one or more of the components that can be
> reversed are.
You might to be onto something there. I've also been thinking that the
concept of bound variables could be relevant. I came at this by
thinking about the idea of instantiating circuit values within
containing circuits. To achieve circuit reuse I was thinking that
circuit values must be named (so they can be referenced by name in
order to be instantiated within another circuit).
> The definition of an entity relation according to its properties or to
> a specific context is not a relational definition.
You're repeating Cimode?
Brian Selzer
"David BL" <dav...@iinet.net.au> wrote in message
news:767b6704-2690-47d2...@l35g2000pra.googlegroups.com...
> On Jul 3, 5:23 am, "Brian Selzer" <br...@selzer-software.com> wrote:
>
>> I think it might be simpler to assign artificial identifiers to the
>> components instead of the nodes. It is certainly more intuitive. Each
>> component has a finite number of leads, and each lead can connect with
>> zero
>> or more components, possibly other leads on the same component. For
>> example, a NOR gate becomes an inverter if you tie the inputs together.
>> The
>> circuits can then be represented entirely as a set of unordered pairs:
>>
>> {{component, lead}, {component, lead}}
>
> Consider a node to which n components are connected and n is large.
> Using pairwise connections can either be exceedingly arbitrary (by
> only representing n-1 pairs) or it makes for enormous redundancy (by
> representing all n(n-1)/2 pairs).
>
> I think this is much worse that the symmetry problem with resistors.
I see your point, but I still think that assigning components artificial
identifiers is better: the unordered pairs could be replaced with or
preprocessed into a single set per node prior to the determination of
isomorphism. For example,
{resistor1:lead1,capacitor2:lead1,transistor1:lead2}
discribes a node that connects a resistor and a capacitor to the base of a
transistor.
The above contains the same information as the unordered pairs
{{resistor1:lead1,capacitor2:lead1},
{resistor1:lead1,transistor1:lead2}}
without either the arbitrariness or the redundancy you seek to avoid.
> Note that netlists used by circuit simulation programs like SPICE tend
> to use something similar to what I discussed - i.e. for each component
> list all the nodes to which it is connected. One difference is that
> they require component labels as well as node labels.
>
>
>> I think that for components with two leads that can operate in either
>> orientation, if the lead identifiers were also treated like bound
>> variables,
>> along with the component identifiers, then circuits would still be
>> considered equivalent even if one or more of the components that can be
>> reversed are.
>
> You might to be onto something there. I've also been thinking that the
> concept of bound variables could be relevant. I came at this by
> thinking about the idea of instantiating circuit values within
> containing circuits. To achieve circuit reuse I was thinking that
> circuit values must be named (so they can be referenced by name in
> order to be instantiated within another circuit).
>
>
>> The definition of an entity relation according to its properties or to
>> a specific context is not a relational definition.
>
> You're repeating Cimode?
I don't know what happened. I thought I replied to your post, but I must
have replied to his instead. I was as surprised as you to see that.
David BL
> "David BL" <davi...@iinet.net.au> wrote in message
> > Consider a node to which n components are connected and n is large.
> > Using pairwise connections can either be exceedingly arbitrary (by
> > only representing n-1 pairs) or it makes for enormous redundancy (by
> > representing all n(n-1)/2 pairs).
>
> > I think this is much worse that the symmetry problem with resistors.
>
> I see your point, but I still think that assigning components artificial
> identifiers is better: the unordered pairs could be replaced with or
> preprocessed into a single set per node prior to the determination of
> isomorphism. For example,
>
> {resistor1:lead1,capacitor2:lead1,transistor1:lead2}
>
> discribes a node that connects a resistor and a capacitor to the base of a
> transistor.
>
> The above contains the same information as the unordered pairs
>
> {{resistor1:lead1,capacitor2:lead1},
> {resistor1:lead1,transistor1:lead2}}
>
> without either the arbitrariness or the redundancy you seek to avoid.
I cannot tell which approach is better. Anyway, the point I find
interesting is that in both cases nesting can ensure the schema meets
the given requirements for logical equivalence of circuit values.
Brian Selzer
I think that this is the perfect counterexample to some of the myths that
are perpetuated here on cdt. It illustrates valid uses of both artificial
identifiers and nesting. I think one would be hard pressed to come up with
a solution that doesn't involve the use of artificial identifiers. The
nesting can, of course, be dispensed with through the introduction of
additional artificial identifiers.
Roy Hann
I think it is a perfect example of wondering why chisels don't make
good screwdrivers.
--
Roy
David BL
> Brian Selzer wrote:
>
> > I think that this is the perfect counterexample to some of the myths that
> > are perpetuated here on cdt. It illustrates valid uses of both artificial
> > identifiers and nesting. I think one would be hard pressed to come up with
> > a solution that doesn't involve the use of artificial identifiers. The
> > nesting can, of course, be dispensed with through the introduction of
> > additional artificial identifiers.
>
> I think it is a perfect example of wondering why chisels don't make
> good screwdrivers.
Are you suggesting the RM is poorly suited to representing circuit
values? I think this is an important question. I don't see much
evidence that the RM is particularly useful here.
For example, to perform a nodal analysis one may associate a voltage
with each labelled node and use Kirchoff's voltage and current laws to
create a large system of simultaneous equations. This in turn may
require sparse matrix techniques for efficient computation. I don't
see anything in the RA that will help do numerical analysis.
In fact I'm not entirely sure why one would want to use the RA at
all. Is it useful to find all the resistors connected to a 5pF
capacitor? If pattern matching is useful I expect the RA isn't as
appropriate as some kind of graph based unification technique.
Nevertheless, complex circuits may contain millions of components and
as data it needs to be managed - i.e. there needs to be a DBMS
providing persistence, multi-user support, data entry validation etc.
Brian Selzer
"Roy Hann" <spec...@processed.almost.meat> wrote in message
news:qeedncJlvtaULszX...@pipex.net...
I don't understand why you scoff:
Here is a case in which what defines something is how it stands in relation
to other things rather than just a collection of properties. A typical
circuit template may call for several 1K resistors, but apart from the
resistance, precision and power rating, what defines each include the nodes
that its leads are connected to. This is also a case in which what defines
something is a collection of other things rather than just a collection of
properties. Each node in a circuit template is defined entirely by the
component leads that it connects. In a circuit template, resistors and
capacitors or just components in general are not physical objects--neither
are nodes, yet despite their lack of substance, it is intuitively obvious
that each component or node should still be distinguishable from all other
components and nodes in the same template; however, the expression of that
intuition in a first-order language without assigning arbitrary names
(artifical identifiers) to each component or to each node is anything but
obvious.
But what I find most interesting is the compactness and lack of redundancy
in the design above where each node is modeled as a single collection of two
or more component leads as opposed to the one where each node is modeled as
one or more uniform pairs of component leads. Of course the former would
require a constraint that guarantees that the collections be pairwise
disjoint.
David BL
> Here is a case in which what defines something is how it stands in relation
> to other things rather than just a collection of properties.
This idea is fundamental to the axiomatic approach to mathematics.
One can draw a parallel with the natural numbers which can be defined
using the Peano axioms. This treats the natural numbers as an
abstract set. As such one could use abstract identifiers for each of
the elements, and define them though their relation to each other.
ISTM that we don't use abstract identifiers for the natural numbers
because we don't need to. We can instead encode them using a physical
representation that maps to the number of successor operations from 0.
Evidently "tricks" like this cannot be used in more complicated
examples.
> ...,it is intuitively obvious
> that each component or node should still be distinguishable from all other
> components and nodes in the same template;
I disagree. Circuits may contain a lot of self-symmetry. One can
investigate this mathematically by considering the group of
automorphisms in the obvious way.
As an example, consider a circuit consisting of 12 x 1 ohm resistors
and 8 nodes wired up in the manner of a 3-dimensional cube. All the
resistors are indistinguishable and all the nodes are
indistinguishable, even in the context of the circuit that they appear
in.
Some circuits have more symmetry than others. For example, one can
partially break the symmetry by changing only one of the resistors.
This affects the group of automorphisms.
Brian Selzer
They are not indistinguishable. Just pick an arbitrary component lead, and
the rest can be described in terms of it because each has different paths to
it.
David BL
> "David BL" <davi...@iinet.net.au> wrote in message
> > As an example, consider a circuit consisting of 12 x 1 ohm resistors
> > and 8 nodes wired up in the manner of a 3-dimensional cube. All the
> > resistors are indistinguishable and all the nodes are
> > indistinguishable, even in the context of the circuit that they appear
> > in.
>
> They are not indistinguishable. Just pick an arbitrary component lead, and
> the rest can be described in terms of it because each has different paths to
> it.
Well, obviously some things won't be indistinguishable anymore after
you "just pick" one. Picking one means distinguishing it from all
others.
Note that distinguishing one of the nodes is insufficient to break all
symmetry. Call it "top". This immediately distinguishes a node on
the opposite corner (call it "bottom"). However there remains 3-way
symmetry in the nodes adjacent to "top", and a further 2-way symmetry
from any one of these nodes to the next three adjacent nodes as we
proceed towards the bottom of this lattice structure.
In your case picking a component lead can be regarded as picking an
ordered pair of adjacent nodes. That still leaves a 2-way symmetry as
described above.
Brian Selzer
I wasn't denying that there is symmetry, nor that it poses problems for
identification. What I'm arguing is that despite the symmetry, there are
still 8 nodes and 12 resistors in the cube example, which means that there
must be a means to distinguish between the nodes and the resistors, for
things that are indistinguishable are the same thing: that is the essence of
identity. The nodes and components in a circuit template can be thought of
as verticies and hyperedges in a connected hypergraph. Certainly each
vertex can be distinguished from all other verticies and each hyperedge can
be distinguished from all other hyperedges in the same hypergraph, can't
they?
Walter Mitty
"Brian Selzer" <br...@selzer-software.com> wrote in message
news:s4m5m.9183$Jb1...@flpi144.ffdc.sbc.com...
> ... there must be a means to distinguish between the nodes and the
> is the essence of identity.
It does my soul good to hear you say that, Brian. It seems like you're half
way to adopting a common sense understanding of what identity is.
Dare I hope for the other half?
Brian Selzer
"Walter Mitty" <wam...@verizon.net> wrote in message
news:qrq5m.1699$P5....@nwrddc02.gnilink.net...
If the 'other half' involves conflating identification with identity or
taking things out of context, then don't hold your breath.
David BL
>
> I wasn't denying that there is symmetry, nor that it poses problems for
> identification. What I'm arguing is that despite the symmetry, there are
> still 8 nodes and 12 resistors in the cube example, which means that there
> must be a means to distinguish between the nodes and the resistors, for
> things that are indistinguishable are the same thing: that is the essence of
> identity. The nodes and components in a circuit template can be thought of
> as verticies and hyperedges in a connected hypergraph. Certainly each
> vertex can be distinguished from all other verticies and each hyperedge can
> be distinguished from all other hyperedges in the same hypergraph, can't
> they?
Ok, I understand what you're saying now.
I think it is useful to distinguish two mutually exclusive sets:
S1: The set of all circuit values where nodes and components have
been uniquely identified. The labels are regarded as part of the
circuit value.
S2: The set of equivalence classes over S1 according to the
equivalence relation defined by isomorphism
It turns out that it is difficult to represent elements of S2 other
than by using some arbitrary representative taken from S1. That is
why abstract identifiers necessarily appear in the model.
All nodes and components have unique identity in an element of S1.
However this doesn't apply to an element of S2 when there is self
symmetry in the sense of a nontrivial automorphism.
BTW I find it very interesting that the graph isomorphism problem is
NP but has not yet been proven P nor NPC. In fact it is suspected
that it is neither!
Walter Mitty
Forget it.
I'm guessing that, at the database level, I probably do conflate
identification with identity. And I'm not interested in the philosophical
level on this score.
The closest I get to ontology is entity-relationship modeling.
As far as taking things out of context goes, I'd have to say that you are a
past master at that. Or let me correct that. You repeatedly come to the
conclusion that everybody else is out of step with you. So you have your
own context. Have fun!
Brian Selzer
Just a thought. It might be worthwhile to think of components recursively.
Supposing that identifiers are assigned to simple components and their
leads, then nodes are completely defined as collections of component leads.
Define a component as one of the following:
1. A simple component.
2. A collection of components connected by a node.
Note that a simple component can have 2 or more leads and that a node may
only connect one component. For example, a quad, 2-input OR gate that has
14 leads (Vcc, gnd, 8 inputs and 4 outputs), can be transformed into a
single 5 input OR gate by connecting the outputs of two of the OR gates to
the inputs of a third OR gate, and connecting the output of the third OR
gate to an input of the fourth OR gate. Each of the three connections is a
node consisting of two leads of the same component.
Thinking of components recursively may simplify the pattern matching
because each component can then be represented as either a function
of 2 or more variables for simple components, or a composition of
functions that share variables. For example, suppose that d1(a,b) and
d2(c,d) represent simple components (diodes), then d2(c,d) is d2(c,b)
by alpha conversion so that or1(a,c,b) can be d1(a,b).d2(c,b), where
the node that connects d1 and d2 is represented by the variable b.
Brian Selzer
>
> "Brian Selzer" <br...@selzer-software.com> wrote in message
> news:h3u5m.6348$vO4....@flpi145.ffdc.sbc.com...
>>
>> "Walter Mitty" <wam...@verizon.net> wrote in message
>> news:qrq5m.1699$P5....@nwrddc02.gnilink.net...
>>>
>>> "Brian Selzer" <br...@selzer-software.com> wrote in message
>>> news:s4m5m.9183$Jb1...@flpi144.ffdc.sbc.com...
>>>> ... there must be a means to distinguish between the nodes and the
>>>> resistors, for things that are indistinguishable are the same thing:
>>>> that is the essence of identity.
>>>
>>> It does my soul good to hear you say that, Brian. It seems like you're
>>> half way to adopting a common sense understanding of what identity is.
>>>
>>> Dare I hope for the other half?
>>
>> If the 'other half' involves conflating identification with identity or
>> taking things out of context, then don't hold your breath.
>
> Forget it.
>
> I'm guessing that, at the database level, I probably do conflate
> identification with identity. And I'm not interested in the philosophical
> level on this score.
It's not a question of philosophy. Identity and identification are
completely different concepts. In particular, identity involves all
properties while identification involves just those properties that serve to
distinguish one object from another. There can be many sets of properties
that identify something at any given time, but only something that has all
the same properties at all times can be considered identical.
> The closest I get to ontology is entity-relationship modeling.
What does ontology to do with identity and identification? Or taking things
out of context?
> As far as taking things out of context goes, I'd have to say that you are
> a past master at that. Or let me correct that. You repeatedly come to
> the conclusion that everybody else is out of step with you. So you have
> your own context. Have fun!
I have never come to the conclusion that everybody else is out of step with
me. I have read numerous academic papers that at least in part support the
positions I take, and I have in the past cited some of them here, so I don't
consider myself out of step. On the other hand, I should point out that
while I am willing to think outside the box, some here on c.d.t. aren't,
whether out of an irrational fear or an unthinking zeal I can't really say.
paul c
...
> I'm guessing that, at the database level, I probably do conflate
Walter, where's the conflation? The two words involve the same notion.
(it is probably impossible to talk intelligibly about this with anybody
who believes that a tuple can somehow have different values at different
times.)
Bob Badour
> Walter Mitty wrote:
> ...
>
> (it is probably impossible to talk intelligibly about this with anybody
> who believes that a tuple can somehow have different values at different
> times.)
Now, THAT is a very astute observation. Bravo!
Brian Selzer
"paul c" <toledob...@oohay.ac> wrote in message
news:4jK5m.34258$Db2.18180@edtnps83...
> Walter Mitty wrote:
> ...
>> I'm guessing that, at the database level, I probably do conflate
>> identification with identity. ...
>
> Walter, where's the conflation? The two words involve the same notion.
>
No. They don't. What identifies something is the minimal set of properties
that serves to distinguish it from everything else in the same context.
Things that are identical have exactly the same properties in every possible
context.
>
> (it is probably impossible to talk intelligibly about this with anybody
> who believes that a tuple can somehow have different values at different
> times.)
I never said that a value can have different values at different times.
That is just ludicrous.
Do you really think that by repeatedly attacking my credibility by
misrepresenting my position will in any way bolster your own credibility?
It does just the opposite: it emphasizes the feebleness of your own argument
that you have to resort to the tactics of sleazy liberal
politicians--misrepresentation, misdirection, obfuscation, and outright
deception.
Walter Mitty
At the risk of repeating myself, forget it.
But thanks anyway.
Bob Badour
> Walter Mitty wrote:
> ...
>
> (it is probably impossible to talk intelligibly about this with anybody
> who believes that a tuple can somehow have different values at different
> times.)
You know, that reminds me of a joke:
2 + 2 = 5
for sufficiently large values of 2.
David BL
> Just a thought. It might be worthwhile to think of components recursively.
> Supposing that identifiers are assigned to simple components and their
> leads, then nodes are completely defined as collections of component leads.
> Define a component as one of the following:
>
> 1. A simple component.
> 2. A collection of components connected by a node.
>
> Note that a simple component can have 2 or more leads and that a node may
> only connect one component. For example, a quad, 2-input OR gate that has
> 14 leads (Vcc, gnd, 8 inputs and 4 outputs), can be transformed into a
> single 5 input OR gate by connecting the outputs of two of the OR gates to
> the inputs of a third OR gate, and connecting the output of the third OR
> gate to an input of the fourth OR gate. Each of the three connections is a
> node consisting of two leads of the same component.
>
> Thinking of components recursively may simplify the pattern matching
> because each component can then be represented as either a function
> of 2 or more variables for simple components, or a composition of
> functions that share variables. For example, suppose that d1(a,b) and
> d2(c,d) represent simple components (diodes), then d2(c,d) is d2(c,b)
> by alpha conversion so that or1(a,c,b) can be d1(a,b).d2(c,b), where
> the node that connects d1 and d2 is represented by the variable b.
To get reuse one needs to use DAG structures, not trees. For example,
circuit values could be named in a flat namespace using a relation,
allowing for arbitrary reuse between those circuits with the
constraint that there are no cycles. A circuit "instantiates" another
circuit by name. The most useful circuits tend to instantiated within
many other circuits.
A circuit could distinguish between its external and internal nodes,
allowing the system to have stronger integrity constraints.
Brian Selzer
This assumes that the circuits being "instantiated" are known ahead of time.
How is that knowledge arrived at? Where does it come from?
David BL
> This assumes that the circuits being "instantiated" are known ahead of time.
> How is that knowledge arrived at? Where does it come from?
Circuit designers. In practise tremendous data compression is
possible. For example a 32 bit ripple carry adder can be built from
32 full adders, where each full adder is made from 2 XOR, 2 AND and 1
OR gate, and each of these gates involves a particular configuration
of transistors.
Brian Selzer
I'm sorry. I thought you were looking for a more general solution that
facilitates the detection of circuits that are structurally equivalent but
whose components or nodes just have different identifiers.
David BL
> "David BL" <davi...@iinet.net.au> wrote in message
> > Circuit designers. In practise tremendous data compression is
> > possible. For example a 32 bit ripple carry adder can be built from
> > 32 full adders, where each full adder is made from 2 XOR, 2 AND and 1
> > OR gate, and each of these gates involves a particular configuration
> > of transistors.
>
> I'm sorry. I thought you were looking for a more general solution that
> facilitates the detection of circuits that are structurally equivalent but
> whose components or nodes just have different identifiers.
The model should support that, but in practise I don't think that's a
particularly important reason why one would be interested in abstract
identifies and symmetry.
I don't think it makes much sense to ever allow users to see abstract
identifiers. In fact I think of abstract identifiers as only
supporting comparison and a special function to allocate new values.
So there isn't an operator that allows for conversion to or from a
human readable string representation.
Not surprisingly in the applications where they appear necessary or
useful, it seems that the user is more likely to want to view and edit
the data in some graphical way (e.g. trisurfaces, CAD drawings, or
circuit schematics). When "objects" are rendered on the screen in
some "virtual world" they have identity in the mind of the user
without having an explicit human readable name. That's a rather
different view of data than the one emphasised by conventional use of
the RM (i.e. sets of facts about things where each fact is
*independently* verifiable by a domain expert). As you have noted
yourself, sometimes things are only identified by their relation to
other things.
Note with regard to a special function to allocate new abstract
identifiers: This obviously cannot be regarded as a mathematical
function that returns a result that is determined by the input
parameters. In that sense it is not what D&D call an "operator".
I find it interesting that when thinking about automorphisms in
circuits, we can see some correlation between:
a) stronger integrity constraints
b) larger equivalence classes
c) less degrees of freedom
For example modelling the symmetry of resistors seems like a good
idea. In terms of a GUI it means that the diagram doesn't need to
distinguish the two leads of a resistor. There are also less degrees
of freedom at the time of data entry of circuit values.
none Reinier Post
>It's not a question of philosophy. Identity and identification are
>completely different concepts. In particular, identity involves all
>properties while identification involves just those properties that serve to
>distinguish one object from another. There can be many sets of properties
>that identify something at any given time, but only something that has all
>the same properties at all times can be considered identical.
It's only completely different if you postulate an absolute object
universe in which every object absolutely exists. You have not
demonstrate the need for this postulate. Just considering identity
and identifiability to be the same thing, namely, a property of terms
used in a given a conceptual model, makes a lot more sense to me.
The difference you refer to just the difference between identity in
two conceptual models to me. Except that according to you, one is
The Absolute Object Model, which will always remain elusive
(we'll never agree on all the details).
Of course our conceptual models do have a correspondence with reality,
but I don't think it's best expressed in terms of Absolute Real Objects.
>> The closest I get to ontology is entity-relationship modeling.
>
>What does ontology to do with identity and identification? Or taking things
>out of context?
E/R expresses identity ('identifiability' if you prefer) explicitly.
>[...] I have read numerous academic papers that at least in part support the
>positions I take, and I have in the past cited some of them here, so I don't
>consider myself out of step.
I think you're correct. E.g. the Tractatus Logico-Philosophicus
(which I haven't read, but I browsed it for this discussion)
seems to agree with you both in viewpoint and in terminology.
It particular it uses the term 'object' in the same way,
as far as I can see.
--
Reinier
none Reinier Post
>I think it is useful to distinguish two mutually exclusive sets:
>
>S1: The set of all circuit values where nodes and components have
>been uniquely identified. The labels are regarded as part of the
>circuit value.
This is, of course, easy to represent.
I think we can generalise this to the task of representing
directed graphs in which the nodes can be uniquely identified by
their attributes (e.g. by position or by explicit identification labels).
This is easily represented in a relational schema, as long as the
set of possible attributes and their sets of domain values are fixed.
You'd need a stronger query language than first order logic
to test for isomotphism, but that is nothing new.
>S2: The set of equivalence classes over S1 according to the
>equivalence relation defined by isomorphism
>
>It turns out that it is difficult to represent elements of S2 other
>than by using some arbitrary representative taken from S1. That is
>why abstract identifiers necessarily appear in the model.
>
>All nodes and components have unique identity in an element of S1.
>However this doesn't apply to an element of S2 when there is self
>symmetry in the sense of a nontrivial automorphism.
Here you're asking, I think, for the following: a relational schema
in which all values are attribute values of circuit elements,
or perhaps elementary values such as booleans or integers,
and all possible circuits are database values, such that no two
different database values represent isomorphic circuits.
This can again be generalized to the task of representing
equivalence classes of directed graphs, in which this time
neither the nodes nor the edges are guaranteed to be identifiable
by their attributes, while attribute values are the only values
allowed.
This is possible, but not with a fixed schema.
And it is extremely impractical. E.g. it will not be possible
to ever issue a database that breaks a symmetry:
the query language doesn't allow it. This can be remedied by
making the query language so powerful that it can create a copy
of the whole database with the insert already performed and delete
the original, but that would be ridiculously expensive.
Another option is to allow nondeterministic database updates
That might actually work well. But what does it buy us?
Testing isomorphism will still be just as expensive;
we've only moved the expense 'to the implementation'.
>BTW I find it very interesting that the graph isomorphism problem is
>NP but has not yet been proven P nor NPC. In fact it is suspected
>that it is neither!
Quite. Our set-based abstraction suggests that deduplication
and sorting are implementation details; often they are, but not always.
--
Reinier
none Reinier Post
[...]
>This is possible, but not with a fixed schema.
>And it is extremely impractical. E.g. it will not be possible
>to ever issue a database that breaks a symmetry:
update --^
Sorry.
--
Reinier
Brian Selzer
"none (Reinier Post)" <rp@raampje.> wrote in message
news:4a5badd3$0$8677$703f...@news.kpn.nl...
> Brian Selzer wrote:
>
>>It's not a question of philosophy. Identity and identification are
>>completely different concepts. In particular, identity involves all
>>properties while identification involves just those properties that serve
>>to
>>distinguish one object from another. There can be many sets of properties
>>that identify something at any given time, but only something that has all
>>the same properties at all times can be considered identical.
>
> It's only completely different if you postulate an absolute object
> universe in which every object absolutely exists. You have not
> demonstrate the need for this postulate. Just considering identity
> and identifiability to be the same thing, namely, a property of terms
> used in a given a conceptual model, makes a lot more sense to me.
> The difference you refer to just the difference between identity in
> two conceptual models to me. Except that according to you, one is
> The Absolute Object Model, which will always remain elusive
> (we'll never agree on all the details).
I think we have our wires crossed here. I don't postulate an absolute
object universe in which every object absolutely exists. I postulate a
fixed universe that contains everything that CAN be discussed. For a fixed
domain, individual quantifiers range over everything that can possibly be,
not just everything that actually is. Existence--that is, actual
existence--is a property that everything that has become actual but hasn't
yet become history has.
David BL
> David BL wrote:
> >I think it is useful to distinguish two mutually exclusive sets:
>
> >S1: The set of all circuit values where nodes and components have
> >been uniquely identified. The labels are regarded as part of the
> >circuit value.
>
> This is, of course, easy to represent.
>
> I think we can generalise this to the task of representing
> directed graphs in which the nodes can be uniquely identified by
> their attributes (e.g. by position or by explicit identification labels).
> This is easily represented in a relational schema, as long as the
> set of possible attributes and their sets of domain values are fixed.
> You'd need a stronger query language than first order logic
> to test for isomotphism, but that is nothing new.
I would like to confirm my understanding here: FOL restricts
quantification to be over elements in the domain of discourse, whereas
SOL also allows for quantification over sets. In particular testing
for existence of an isomorphism is quantification over a set because a
function is basically a set of pairs.
On a somewhat unrelated note, Ron Fagin has been mention occasionally
on cdt. He proved in his PhD thesis that existential second order
logic corresponds to the computational complexity class NP. I've just
come across this:
http://www.almaden.ibm.com/cs/people/fagin/genspec.pdf
Interesting point.
none Reinier Post
[...]
>I think we have our wires crossed here. I don't postulate an absolute
>object universe in which every object absolutely exists. I postulate a
>fixed universe that contains everything that CAN be discussed.
OK. My mistake.
>For a fixed
>domain, individual quantifiers range over everything that can possibly be,
>not just everything that actually is. Existence--that is, actual
>existence--is a property that everything that has become actual but hasn't
>yet become history has.
So you can quantify over all green 20x50 windows that didn't magically
appear just above my head yesterday between 22:50 and 22:53 GMT, right?
And over all green 20x50 windows that didn't appear *in any way*
just above my head yesterday between 22:50 and 22:53 GMT, right?
Are they the same set?
I'm sorry, I find this pointless, even as a thought exercise.
--
Reinier
Brian Selzer
"none (Reinier Post)" <rp@raampje.> wrote in message
Now you're just being contrary.
> I'm sorry, I find this pointless, even as a thought exercise.
Perhaps before you dismiss it altogether, you should look into the
consequences of *not* assuming a fixed domain. I think then you'll get the
point.
none Reinier Post
[...]
>I would like to confirm my understanding here: FOL restricts
>quantification to be over elements in the domain of discourse, whereas
>SOL also allows for quantification over sets. In particular testing
>for existence of an isomorphism is quantification over a set because a
>function is basically a set of pairs.
I'm not aware that SQL allows anything like this.
Can you give me an example?
>On a somewhat unrelated note, Ron Fagin has been mention occasionally
>on cdt. He proved in his PhD thesis that existential second order
>logic corresponds to the computational complexity class NP. I've just
>come across this:
>
>http://www.almaden.ibm.com/cs/people/fagin/genspec.pdf
I never read this, it looks interesting.
--
Reinier
David BL
> David BL wrote:
>
> [...]
>
> >I would like to confirm my understanding here: FOL restricts
> >quantification to be over elements in the domain of discourse, whereas
> >SOL also allows for quantification over sets. In particular testing
> >for existence of an isomorphism is quantification over a set because a
> >function is basically a set of pairs.
>
> I'm not aware that SQL allows anything like this.
> Can you give me an example?
SOL = second order logic
none Reinier Post
>> I'm not aware that SQL allows anything like this.
>> Can you give me an example?
>
>SOL = second order logic
Sorry, capital O and Q look frightfully similar in the font I'm using.
--
Reinier
none Reinier Post
>Perhaps before you dismiss it altogether, you should look into the
>consequences of *not* assuming a fixed domain. I think then you'll get the
>point.
I'm perfectly happy using the relational model,
which makes no such assumption at all.
It is unclear to me what consequences you are thinking of.
--
Reinier