Personal tools

Relational algebra

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Adding reference to pointfree (in shorly describing Oliveira's mentioned paper))
(→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

The case of
Restrict
uses
Expr
. I think, the concept of
Expr
is an 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'
Retrieved from "http://www.haskell.org/haskellwiki/Relational_algebra"

Category: Theoretical foundations