Re: Signing relational databases

On Apr 20, 12:27 pm, Jonathan Leffler <jleff..._at_earthlink.net> wrote:
> Julien Lafaye wrote:
> > Marshall wrote:
>
> >> I don't see any obvious reason why a digital signature algorithm
> >> should
> >> much care what the payload is. If not, then the question devolves to
> >> what format to represent a database in, and what cryptographic hash
> >> to use. Any reason not to just export the database in some native
> >> text format?
>
> > My problem with that but perhaps it would seem like a researcher problem is
> > the following. A relational table should be invariant to a reordering of
> > the tuples and/or the attributes. The signature algorithm should reflect
> > this and I was wondering whether such an algorithm exists.
>
> It seems to me improbable that such an algorithm exists (or even could
> exist). Hash functions are intentionally very sensitive to the order in
> which the data is presented (so as to detect any changes in the input
> data). Using orthodox technology, then, you would be dependent on some
> specific order for both the tuples within a relation and the attributes
> within a tuple, not to mention some sequence for the relations in the
> database.

Assuming the attributes of a given relation are uniquely named, a total ordering on the attributes can be defined. Assuming a total ordering exists on the domains, it is possible to define a total ordering on the tuples by ordering on each attribute in turn.

We can totally order the relations by their name, and therefore all relations can be written to a stream in a way that is invariant to any physically stored order of relations, attributes and tuples. Received on Fri Apr 20 2007 - 09:38:03 CEST