Using the RM for ADTs

#31

David BL wrote:

Quote:

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.

Quote:

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'.

Quote:

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

#32

PS I just wrote

[...]

Quote:

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

#33

"none (Reinier Post)" <rp (AT) raampje (DOT) > wrote

Quote:

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.

Quote:

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

#34

On Jul 14, 6:52 am, rp (AT) raampje (DOT) (none) (Reinier Post) wrote:

Quote:

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

Quote:

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.

Interesting point.

Quote:

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.

#35

Brian Selzer wrote:

[...]

Quote:

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.

Quote:

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

#36

"none (Reinier Post)" <rp (AT) raampje (DOT) > wrote

Quote:

Brian Selzer wrote:

[...]

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?

Now you're just being contrary.

Quote:

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.

#37

David BL wrote:

[...]

Quote:

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?

Quote:

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

#38

On Jul 25, 5:55 am, rp (AT) raampje (DOT) (none) (Reinier Post) wrote:

Quote:

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

#39

David BL wrote:

Quote:

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

#40

Brian Selzer wrote:

Quote:

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