Re: Using the RM for ADTs

"Cimode" <cimode_at_hotmail.com> wrote in message news:429001d6-ac23-42bb-8e2e-db6bb1f48c96_at_b9g2000yqm.googlegroups.com... On 2 juil, 11:28, David BL <davi..._at_iinet.net.au> wrote:
> 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 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?

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.

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

The definition of an entity relation according to its properties or to a specific context is not a relational definition. Received on Thu Jul 02 2009 - 23:23:11 CEST