Personal tools

Relational algebra

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m (Just a thought: Mentioning also extensible record as a related concept)
m (Just a thought: extensible record and more generally, type arithmetic)
Line 23: Line 23:
 
* [[generalised algebraic datatype]]
 
* [[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?
 
* 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]]
+
* [[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):
 
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):

Revision as of 11:01, 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'

3 Practice

Thus, in contrast to direct SQL text manipulation, database managemant 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