-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Ferry Table Algebra
--   
--   The Ferry 2.0 Table Algebra library
--   
--   The table algebra [2] is an intermediate language used by Ferry 2.0
--   [3] and DSH [4]. It forms the input for the pathfinder [1] optimiser
--   that can translate it into SQL. The library exposes a monadic
--   interface to construct algebraic plans, it automatically performs
--   common sub-tree elimination so that the resulting plan is as small as
--   possible and the optimiser can do it's work better. XML rendering is
--   present and needed for interfacing with DSH-Pathfinder, and for
--   debugging plans with the standalone Pathfinder.
--   
--   <ol>
--   
--   <li><a>http://www-db.informatik.uni-tuebingen.de/research/pathfinder</a></li>
--   
--   <li><a>http://dbworld.informatik.uni-tuebingen.de/projects/pathfinder/wiki/Logical_Algebra</a></li>
--   
--   <li><a>http://www-db.informatik.uni-tuebingen.de/research/ferry</a></li>
--   
--   <li><a>http://www-db.informatik.uni-tuebingen.de/files/publications/ferryhaskell.pdf</a></li>
--   </ol>
@package TableAlgebra
@version 0.1.5


-- | This package provides a convenient interface to construct Table
--   Algebra plans that can be dealt with by Pathfinder
--   (http:<i></i>www-db.informatik.uni-tuebingen.de<i>research</i>pathfinder).
--   A describtion of the algebra can be found at:
--   http:<i></i>dbworld.informatik.uni-tuebingen.de<i>projects</i>pathfinder<i>wiki</i>Logical_Algebra
--   This module only provides a subset of the complete algebra.
module Database.Ferry.Algebra

-- | An algebraic plan is the result of constructing a graph. | The pair
--   consists of the mapping from nodes to their respective ids | and the
--   algres from the top node.
type AlgPlan = (Map Algebra AlgNode, AlgRes)
transform :: (Bool, AlgPlan) -> Doc

-- | Union between two plans
union :: AlgNode -> AlgNode -> GraphM AlgNode
emptyPlan :: SubPlan

-- | Attach a column <a>ResAttrName</a> of type <a>ATy</a> with value
--   <a>AVal</a> in all rows to table <a>AlgNode</a>
attach :: ResAttrName -> ATy -> AVal -> AlgNode -> GraphM AlgNode

-- | Project/rename certain column out of a plan
proj :: ProjInf -> AlgNode -> GraphM AlgNode

-- | Get the current loop table
getLoop :: GraphM AlgNode
subPlan :: Int -> AlgRes -> SubPlan

-- | Similar to rowrank but this will assign a emph{unique} number to every
--   row (even if two rows are equal)
rownum :: AttrName -> [AttrName] -> Maybe AttrName -> AlgNode -> GraphM AlgNode

-- | Same as rownum but columns can be assigned an ordering direction
rownum' :: AttrName -> [(AttrName, SortDir)] -> Maybe AttrName -> AlgNode -> GraphM AlgNode

-- | Join two plans where the columns n1 of table 1 and columns n2 of table
--   2 are equal.
eqJoin :: String -> String -> AlgNode -> AlgNode -> GraphM AlgNode

-- | Assign a number to each row in column <a>ResAttrName</a> incrementing
--   sorted by <a>SortInf</a>. The numbering is not dense!
rank :: ResAttrName -> SortInf -> AlgNode -> GraphM AlgNode

-- | The same as eqJoin but with multiple columns.
eqTJoin :: [(String, String)] -> ProjInf -> AlgNode -> AlgNode -> GraphM AlgNode

-- | Remove duplicate rows
distinct :: AlgNode -> GraphM AlgNode

-- | Same as rank but provides a dense numbering.
rowrank :: ResAttrName -> SortInf -> AlgNode -> GraphM AlgNode

-- | Cast column <a>AttrName</a> to type <a>ATy</a> and give it the name
--   <a>ResAttrName</a> afterwards.
cast :: AttrName -> ResAttrName -> ATy -> AlgNode -> GraphM AlgNode

-- | Compute the difference between two plans.
difference :: AlgNode -> AlgNode -> GraphM AlgNode

-- | Apply aggregate functions to a plan
aggr :: [(AggrType, ResAttrName, Maybe AttrName)] -> Maybe PartAttrName -> AlgNode -> GraphM AlgNode

-- | Select rows where the column <a>SelAttrName</a> contains True.
select :: SelAttrName -> AlgNode -> GraphM AlgNode

-- | Get's the nth element(s) of a (partitioned) table.
posSelect :: Int -> SortInf -> Maybe AttrName -> AlgNode -> GraphM AlgNode

-- | Construct a database table node The first argument is the
--   emph{qualified} name of the database table. The second describes the
--   columns in alphabetical order. The third argument describes the
--   database keys (one table key can span over multiple columns).
dbTable :: String -> Columns -> KeyInfos -> GraphM AlgNode

-- | Negate the boolen value in column n and store it in column r
notC :: AttrName -> AttrName -> AlgNode -> GraphM AlgNode

-- | Make cross product from two plans
cross :: AlgNode -> AlgNode -> GraphM AlgNode

-- | Apply an operator to the element in <a>LeftAttrName</a> and
--   <a>RightAttrName</a>, store the result in <a>ResAttrName</a>
oper :: String -> ResAttrName -> LeftAttrName -> RightAttrName -> AlgNode -> GraphM AlgNode

-- | Construct an empty table node with
emptyTable :: SchemaInfos -> GraphM AlgNode

-- | Evaluate the graph construction computation with the current
--   environment extended with a binding n to v.
withBinding :: String -> AlgRes -> GraphM a -> GraphM a

-- | Evaluate the graph construction computation with a differnt gamma, |
--   and loop table. Return within he current computational context.
withContext :: Gam -> AlgNode -> GraphM a -> GraphM a

-- | Get the current variable environment
getGamma :: GraphM Gam
getPlan :: Int -> SubPlan -> AlgRes

-- | Lookup a variable in the environment
fromGam :: String -> GraphM AlgRes

-- | Create an algebraic nat value
nat :: Integer -> AVal

-- | Create an algebraic int value
int :: Integer -> AVal

-- | Create an algebraic boolean value
bool :: Bool -> AVal

-- | Create an algebraic double value
double :: Double -> AVal

-- | Create an algebraic string value
string :: String -> AVal
natT :: ATy
intT :: ATy
surT :: ATy
boolT :: ATy
doubleT :: ATy

-- | Types of algebraic values
stringT :: ATy

-- | Sorting rows in a direction
data SortDir
Asc :: SortDir
Desc :: SortDir
data AggrType
Avg :: AggrType
Max :: AggrType
Min :: AggrType
Sum :: AggrType
Count :: AggrType
All :: AggrType
Prod :: AggrType
Dist :: AggrType
newtype SubPlan
SubPlan :: (Map Int AlgRes) -> SubPlan

-- | An algebraic solution is a triple consisting of the node id, a
--   description of the database columns and all subplans
type AlgRes = (AlgNode, Columns, SubPlan)

-- | The column data type is used to represent the table structure while
--   compiling ferry core into an algebraic plan The col column contains
--   the column number and the type of its contents The NCol column is used
--   to group columns that together form an element of a record , its
--   string argument is used to represent the field name.
data Column
Col :: Int -> ATy -> Column
NCol :: String -> Columns -> Column

-- | One table can have multiple columns
type Columns = [Column]

-- | Algebraic types At this level we do not have any structural types
--   anymore those are represented by columns. ASur is used for surrogate
--   values that occur for nested lists.
data ATy
AInt :: ATy
AStr :: ATy
ABool :: ATy
ADec :: ATy
ADouble :: ATy
ANat :: ATy
ASur :: ATy

-- | Schema information, represents a table structure, the first element of
--   the tuple is the column name the second its type.
type SchemaInfos = [(AttrName, ATy)]

-- | Multiple keys
type KeyInfos = [KeyInfo]
type AlgNode = Int

-- | Graphs are constructed in a monadic environment. | The graph
--   constructed has to be a DAG. | The reader monad provides access to the
--   variable environment Gamma and the loop table | The variable
--   environment is a mapping from variable names to graphnodes that
--   represent | their compiled form. | The state monad gives access to a
--   supply of fresh variables, and maintains a map from | nodes to node
--   ids. When a node is inserted and an equal node (equal means, equal
--   node | and equal child nodes) already exists in the map the node id
--   for that already existing | node is returned. This allows maximal
--   sharing.
type GraphM = ReaderT (Gam, AlgNode) (State (Int, Map Algebra AlgNode))

-- | Variable environemtn mapping from variables to compiled nodes.
type Gam = [(String, AlgRes)]

-- | Shorthand for the initial loop condition used by Ferry.
initLoop :: Algebra

-- | Evaluate the monadic graph into an algebraic plan, given a loop
--   relation.
runGraph :: Algebra -> GraphM AlgRes -> AlgPlan