# Relational algebra

### From HaskellWiki

EndreyMark (Talk | contribs) (Link to paper: José Nuno Oliveira: First Steps in Pointfree Functional Dependency Theory. mainly it was that forced me to create page for relational algebra) |
EndreyMark (Talk | contribs) (→Other links: The λ Abroad. A Functional Approach To Software Components by Daniel Johannes Pieter Leijen) |
||

(9 intermediate revisions by 3 users not shown) | |||

Line 1: | Line 1: | ||

− | + | __NOTOC__ | |

− | José Nuno Oliveira: [http://www.di.uminho.pt/~jno/ps/_.pdf First Steps in Pointfree Functional Dependency Theory]. See also [http://www.di.uminho.pt/~jno/html/ | + | {{Foundations infobox}} |

+ | ==Definition== | ||

+ | Relational algebra is an offshoot of first-order logic and is a set of relations closed under operators. | ||

+ | |||

+ | |||

+ | == 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. | ||

+ | |||

+ | == 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]]). Can <hask>Query</hask> be regarded as an [[arrow]], and if so, is it worth of doing so? | ||

+ | * [[extensible record]] and more generally, [[type arithmetic]] | ||

+ | |||

+ | 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> | ||

+ | |||

+ | == Practice == | ||

+ | |||

+ | Thus, in contrast to direct SQL text manipulation, [[Libraries and tools/Database interfaces|database management]] systems can be approached also in declarative, type safe ways. More specifically, they may be implemented as domain specific embedded languages -- using e.g. Haskell for their host language. See the examples of | ||

+ | * [[Libraries and tools/Database interfaces/HaskellDB|HaskellDB]] | ||

+ | * [[Libraries and tools/Database interfaces/CoddFish|CoddFish]] | ||

+ | |||

+ | ==Other links== | ||

+ | * [http://en.wikipedia.org/wiki/Relational_algebra Wikipedia entry for relational algebra] | ||

+ | * [http://research.microsoft.com/users/daan/download/papers/phd-thesis.pdf The λ Abroad. A Functional Approach To Software Components] by Daniel Johannes Pieter Leijen | ||

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

## Revision as of 21:00, 7 August 2007

## 1 Definition

Relational algebra is an offshoot of first-order logic and is a set of relations closed under operators.

## 2 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.

## 3 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). Can be regarded as an arrow, and if so, is it worth of doing so?Query
- extensible record and more generally, type arithmetic

*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'

## 4 Practice

Thus, in contrast to direct SQL text manipulation, database management systems can be approached also in declarative, type safe ways. More specifically, they may be implemented as domain specific embedded languages -- using e.g. Haskell for their host language. See the examples of

## 5 Other links

- Wikipedia entry for relational algebra
- The λ Abroad. A Functional Approach To Software Components by Daniel Johannes Pieter Leijen