Database.Algebra.Dag

The DAG data structure

data AlgebraDag a

Instances

ToJSON a => ToJSON (AlgebraDag a)

(FromJSON a, Operator a) => FromJSON (AlgebraDag a)

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

Methods

opChildren :: a -> [AlgNode]

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

nodeMap :: AlgebraDag a -> NodeMap a

Return the nodemap of a DAG

rootNodes :: AlgebraDag a -> [AlgNode]

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

refCountMap :: AlgebraDag a -> NodeMap Int

A map storing the number of parents for each node.

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

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!

emptyDag :: AlgebraDag a

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.

addRootNodes :: Operator a => AlgebraDag a -> [AlgNode] -> AlgebraDag a

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]

Return the list of parents of a node.

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

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

hasPath :: AlgNode -> AlgNode -> AlgebraDag a -> Bool

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

reachableNodesFrom :: AlgNode -> AlgebraDag a -> Set AlgNode

Return all nodes that are reachable from one node.

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

Returns the operator for a node.

DAG modification functions

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

Insert a new node into the DAG.

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

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

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

'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

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

collect :: Operator o => Set AlgNode -> AlgebraDag o -> AlgebraDag o