Re: Using the RM for ADTs

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.

>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