# Relational algebra

### From HaskellWiki

(Difference between revisions)

EndreyMark (Talk | contribs) (Adding reference to pointfree (in shorly describing Oliveira's mentioned paper)) |
EndreyMark (Talk | contribs) (→Just a thought: : an early, immature thought of mine to represent relational algebra expressions) |
||

Line 1: | Line 1: | ||

__TOC__ | __TOC__ | ||

+ | |||

+ | == Pointfree == | ||

José Nuno Oliveira: [http://www.di.uminho.pt/~jno/ps/_.pdf First Steps in Pointfree Functional Dependency Theory]. A concise and deep approach, it is [[pointfree]]. See also [http://www.di.uminho.pt/~jno/html/ the author's homepage] and also [http://www.di.uminho.pt/~jno/html/jnopub.html his many other papers] -- many materials related to in this topic can be found. | José Nuno Oliveira: [http://www.di.uminho.pt/~jno/ps/_.pdf First Steps in Pointfree Functional Dependency Theory]. A concise and deep approach, it is [[pointfree]]. See also [http://www.di.uminho.pt/~jno/html/ the author's homepage] and also [http://www.di.uminho.pt/~jno/html/jnopub.html his many other papers] -- many materials related to in this topic can be found. | ||

+ | |||

+ | == Just a thought == | ||

+ | |||

+ | An early, immature thought of mine to represent relational algebra expressions: | ||

+ | <haskell> | ||

+ | data Query :: * -> * -> * where | ||

+ | Identity :: Scheme a => Query a a | ||

+ | Restrict :: (Scheme a, Scheme b) => Expr b Bool -> Query a b -> Query a b | ||

+ | Project :: (Scheme a, Scheme b, Scheme b', Sub b' b) => b' -> Query a b -> Query a b' | ||

+ | Rename :: (Scheme a, Scheme b, Scheme b', Iso b b') => Query a b -> Query a b' | ||

+ | Product :: (Scheme a, Scheme b1, Scheme b2, Scheme b, Sum b1 b2 b) => | ||

+ | Query a b1 -> Query a b2 -> Query a b | ||

+ | Union :: (Scheme a, Scheme b, Id b) => Query a b -> Query a b -> Query a b | ||

+ | Difference :: (Scheme a, Scheme b, Id b) => Query a b -> Query a b -> Query a b | ||

+ | |||

+ | </haskell> | ||

+ | ... using the concepts / ideas of | ||

+ | * [[generalised algebraic datatype]] | ||

+ | * a sort of differential approach (I think I took it from [[Zipper]]). | ||

+ | |||

+ | The case of <hask>Restrict</hask> uses <hask>Expr</hask>. I think, the concept of <hask>Expr</hask> is an ''inside'' approach (making the relational algebra -- regarded as an embedded language -- richer, more autonome from the host language, but also more restricted): | ||

+ | |||

+ | <haskell> | ||

+ | data Expr :: * -> * -> * where | ||

+ | Constant :: (Scheme sch, Literal a) => a -> Expr sch a | ||

+ | Attribute :: (Scheme sch, Match attr a, Context attr sch) => attr -> Expr sch a | ||

+ | Not :: Scheme sch => Expr sch Bool -> Expr sch Bool | ||

+ | And :: Scheme sch => Expr sch Bool -> Expr sch Bool -> Expr sch Bool | ||

+ | Or :: Scheme sch => Expr sch Bool -> Expr sch Bool -> Expr sch Bool | ||

+ | Equal :: (Scheme sch, Eq a) => Expr sch a -> Expr sch a -> Expr sch Bool | ||

+ | Less :: (Scheme sch, Ord a) => Expr sch a -> Expr sch a -> Expr sch Bool | ||

+ | </haskell> | ||

+ | |||

+ | Maybe an ''outside'' approach (exploiting the host language more, thus enjoying more generality) would be also appropriate: | ||

+ | |||

+ | <haskell> | ||

+ | data Query :: * -> * -> * where | ||

+ | ... | ||

+ | Restrict :: (Scheme a, Scheme b, Record br, On b br) => (br -> Bool) -> Query a b -> Query a b | ||

+ | ... | ||

+ | Rename :: (Scheme a, Scheme b, Scheme b', Iso b b') => (b -> b') -> Query a b -> Query a b' | ||

+ | </haskell> | ||

[[Category:Theoretical foundations]] | [[Category:Theoretical foundations]] |

## Revision as of 10:19, 17 June 2006

## Contents |

## 1 Pointfree

José Nuno Oliveira: First Steps in Pointfree Functional Dependency Theory. A concise and deep approach, it is pointfree. See also the author's homepage and also his many other papers -- many materials related to in this topic can be found.

## 2 Just a thought

An early, immature thought of mine to represent relational algebra expressions:

data Query :: * -> * -> * where Identity :: Scheme a => Query a a Restrict :: (Scheme a, Scheme b) => Expr b Bool -> Query a b -> Query a b Project :: (Scheme a, Scheme b, Scheme b', Sub b' b) => b' -> Query a b -> Query a b' Rename :: (Scheme a, Scheme b, Scheme b', Iso b b') => Query a b -> Query a b' Product :: (Scheme a, Scheme b1, Scheme b2, Scheme b, Sum b1 b2 b) => Query a b1 -> Query a b2 -> Query a b Union :: (Scheme a, Scheme b, Id b) => Query a b -> Query a b -> Query a b Difference :: (Scheme a, Scheme b, Id b) => Query a b -> Query a b -> Query a b

... using the concepts / ideas of

- generalised algebraic datatype
- a sort of differential approach (I think I took it from Zipper).

Restrict

Expr

Expr

*inside*approach (making the relational algebra -- regarded as an embedded language -- richer, more autonome from the host language, but also more restricted):

data Expr :: * -> * -> * where Constant :: (Scheme sch, Literal a) => a -> Expr sch a Attribute :: (Scheme sch, Match attr a, Context attr sch) => attr -> Expr sch a Not :: Scheme sch => Expr sch Bool -> Expr sch Bool And :: Scheme sch => Expr sch Bool -> Expr sch Bool -> Expr sch Bool Or :: Scheme sch => Expr sch Bool -> Expr sch Bool -> Expr sch Bool Equal :: (Scheme sch, Eq a) => Expr sch a -> Expr sch a -> Expr sch Bool Less :: (Scheme sch, Ord a) => Expr sch a -> Expr sch a -> Expr sch Bool

Maybe an *outside* approach (exploiting the host language more, thus enjoying more generality) would be also appropriate:

data Query :: * -> * -> * where ... Restrict :: (Scheme a, Scheme b, Record br, On b br) => (br -> Bool) -> Query a b -> Query a b ... Rename :: (Scheme a, Scheme b, Scheme b', Iso b b') => (b -> b') -> Query a b -> Query a b'