# 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)

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

Original text of this message