Re: no names allowed, we serve types only

From: David BL <davidbl_at_iinet.net.au>
Date: Thu, 18 Feb 2010 01:00:38 -0800 (PST)
Message-ID: <1315eb13-4a81-49b5-ac2b-0254213db256_at_u15g2000prd.googlegroups.com>

On Feb 17, 7:29 pm, David BL <davi..._at_iinet.net.au> 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...

Sets

---

Let

   union(S)

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

Let

  powerset(X)

denote the set of all subsets of X.

Function graphs

---

Let

  functiongraphs(D,C)

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

  proj(G,D')

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

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

Functions

---

Let

  functions(D,C)

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

  proj(f,D')

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

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

Tuples

---

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.

Then

  tuples(A)

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.

  tuples(A)
=
  { 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.

Relations

---

Let

  relations(A)

denote

  powerset(tuples(A))

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

  relations(A,K)

denotes

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

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

  }

Example

---

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

  mydatabaseschema =
    tuples
    (

      {
        (
          employee,
          relations
          (
            {
              (name,string),
              (birthdate,date)
            },
            {
              {name}
            }
          )
        }
      )

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