algebra-dag-0.1.0.0: Infrastructure for DAG-shaped relational algebra plans

Database.Algebra.Dag

Synopsis

# The DAG data structure

class (Ord a, Show a) => Operator a where Source

Methods

opChildren :: a -> [AlgNode] Source

replaceOpChild :: a -> AlgNode -> AlgNode -> a Source

Return the nodemap of a DAG

rootNodes :: AlgebraDag a -> [AlgNode] Source

Return the (possibly modified) list of root nodes from a DAG

A map storing the number of parents for each node.

mkDag :: Operator a => NodeMap a -> [AlgNode] -> AlgebraDag a Source

Create a DAG from a node map of algebra operators and a list of root nodes. Nodes which are not reachable from the root nodes provided will be pruned!

Construct an empty DAG with no root nodes. Beware: before any collections are performed, root nodes must be added. Otherwise, all nodes will be considered unreachable.

Add a list of root nodes to a DAG, all of which must be present in the DAG. The node map is normalized by removing all nodes which are not reachable from the root nodes. FIXME re-use graph, opmap etc, only remove pruned nodes.

# Query functions for topological and operator information

parents :: AlgNode -> AlgebraDag a -> [AlgNode] Source

Return the list of parents of a node.

topsort :: Operator a => AlgebraDag a -> [AlgNode] Source

Return a topological ordering of all nodes which are reachable from the root nodes.

Tests wether there is a path from the first to the second node.

Return all nodes that are reachable from one node.

operator :: Operator a => AlgNode -> AlgebraDag a -> a Source

Returns the operator for a node.

# DAG modification functions

insert :: Operator a => a -> AlgebraDag a -> (AlgNode, AlgebraDag a) Source

Insert a new node into the DAG.

insertNoShare :: Operator a => a -> AlgebraDag a -> (AlgNode, AlgebraDag a) Source

Insert an operator without checking if an equivalent operator is already present.

replaceChild :: Operator a => AlgNode -> AlgNode -> AlgNode -> AlgebraDag a -> AlgebraDag a Source

'replaceChild n old new' replaces all links from node n to node old with links to node new.

replaceRoot :: Operator a => AlgebraDag a -> AlgNode -> AlgNode -> AlgebraDag a Source

Replace an entry in the list of root nodes with a new node. The root node must be present in the DAG.