Using the RM for ADTs

From: David BL <>
Date: Thu, 2 Jul 2009 02:28:54 -0700 (PDT)
Message-ID: <>

Consider a requirement to record electronic circuits in a relational 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 illdefined  (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. Received on Thu Jul 02 2009 - 11:28:54 CEST

Original text of this message