Re: Using the RM for ADTs
- From: "Brian Selzer" <brian@xxxxxxxxxxxxxxxxxxx>
- Date: Thu, 2 Jul 2009 17:23:11 -0400
"Cimode" <cimode@xxxxxxxxxxx> wrote in message
news:429001d6-ac23-42bb-8e2e-db6bb1f48c96@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On 2 juil, 11:28, David BL <davi...@xxxxxxxxxxxx> 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.
.
- Follow-Ups:
- Re: Using the RM for ADTs
- From: David BL
- Re: Using the RM for ADTs
- References:
- Using the RM for ADTs
- From: David BL
- Re: Using the RM for ADTs
- From: Cimode
- Using the RM for ADTs
- Prev by Date: Re: Natural keys vs Aritficial Keys
- Next by Date: identifying entities across database updates (was: Is a function a relation?)
- Previous by thread: Re: Using the RM for ADTs
- Next by thread: Re: Using the RM for ADTs
- Index(es):
Relevant Pages
|
Loading
