Re: no names allowed, we serve types only

From: David BL <>
Date: Thu, 18 Feb 2010 01:00:38 -0800 (PST)
Message-ID: <>

On Feb 17, 7:29 pm, David BL <> wrote:
> I wonder whether there are practical economies for avoiding formalised
> types in a database schema language. A database schema is no longer
> a type definition but instead just a set definition. D&Ds concept of
> subtyping by constaint maps to nothing more revolutionary than
> subsetting through set comprehension. A relation value can represent
> the equivalent of a tuple type and a power set over a relation value
> (i.e. a set of tuples) provides the equivalent of a relation type (as
> a set of relations). Set comprehension allows arbitrary database
> constraints to be imposed.

I've jumped in and had a go at defining a typeless language that can specify a database schema in a set theoretic way...




denote the union over each element of S (S is a set of sets)



denote the set of all subsets of X.

Function graphs



denote the set of function graphs with domain D and codomain C. i.e.

  { G | G is a subset of D x C where

        for each x in D exists unique y in C
        such that (x,y) in G


Let G be in functiongraphs(D,C). Then

  dom(G) denotes D
  range(G) denotes { y in C | (x,y) in G }

If (x,y) in G then G(x) denotes y.

Note that given G there are many codomains C satisfying G in functiongraphs(D,C). Therefore we cannot define codomain(G).

If D,C are sets then functiongraphs(D,C) is necessarily a set according to the axioms of ZFC. We cannot avoid codomains by defining functionsgraphs(D) over all possible codomains because that is not a set under ZFC.

Function graph projection

Let G be a function graph with domain D and let D' be a subset of D. Then


denotes the projection of G onto domain D'. i.e.

  proj(G,D') =
    { (x,y) in G | x in D' }




denote the set of functions with domain D and codomain C. i.e.

  functions(D,C) = { (D,C,G) | G in functiongraphs(D,C) }

Let f = (D,C,G) and (x,y) in G. Then

  dom(f) denotes D

  codom(f) denotes C
  range(f) denotes range(G)
  graph(f) denotes G and

  f(x) denotes y.

Function projection

Let f = (D,C,G) be a function and D' be a subset of D. Then


denotes the projection of f onto domain D', keeping the same codomain.  i.e.

  proj(f,D') = (D', C, proj(G,D'))


Let A be a functiongraph representing a set of attributes, where for each (N,D) in A, N represents an attribute name and D represents an attribute domain (a set). Note that the attribute names are necessarily distinct by definition of a functiongraph.



denotes the set of tuples where each tuple is formally a function graph that maps attribute names into elements of their respective domains i.e.

  { t in functiongraphs(dom(A),union(range(A))) |

      for each (N,D) in A, t(N) in D }

Note that tuples are function graphs not functions because we don't want to say two tuples are distinct just because of differing attribute domains.






Key constraints

Let A be a given functiongraph representing a set of attributes. Let K be a given subset of powerset(dom(A)) (i.e. sets of sets of attribute names). Then



  { r in relations(A) |
    for all k in K,

      for all t1, t2 in r,
        proj(t1,k) = proj(t2,k) => t1 = t2


A database value is a tuple that maps relation name to relation value.

  mydatabaseschema =


    ) Received on Thu Feb 18 2010 - 10:00:38 CET

Original text of this message