Re: Using the RM for ADTs

On Jul 14, 6:52 am, rp_at_raampje.(none) (Reinier Post) wrote:
> 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

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

> 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.
Received on Tue Jul 14 2009 - 04:12:03 CEST