MySQL 9.0.0
Source Code Documentation
OnlineCycleFinder Class Reference

A fast online cycle finder, based on [Pea03]. More...

#include <online_cycle_finder.h>

Public Member Functions

 OnlineCycleFinder (MEM_ROOT *mem_root, int num_vertices)
 
bool EdgeWouldCreateCycle (int a_idx, int b_idx)
 
bool AddEdge (int a_idx, int b_idx)
 
void DeleteEdge (int a_idx, int b_idx)
 
Bounds_checked_array< int > order () const
 

Private Member Functions

bool DepthFirstSearch (int node_idx, int upper_bound, int node_idx_to_avoid)
 
void MoveAllMarked (int start_pos, int new_pos)
 
void Allocate (int node_idx, int index_in_order)
 

Private Attributes

Bounds_checked_array< int > m_order
 
Bounds_checked_array< int > m_position_of_node
 
Bounds_checked_array< bool > m_visited
 
Mem_root_array< int > m_to_shift
 
mem_root_unordered_multimap< int, int > m_edges
 

Detailed Description

A fast online cycle finder, based on [Pea03].

It keeps a DAG in memory, built up incrementally, and is able to reject adding edges that would create cycles (or, equivalently, test if adding an edge would create a cycle). The amortized cost of checking ϴ(E) insertions is O(V).

The basic working of the algorithm is to keep a list of all vertices, topologically sorted given the order so far. When inserting a new edge, we can quickly identify any vertices that would need to be moved in the topological sort (they are the ones stored between the two endpoints), run a DFS, and see if moving them would cause a contradiction (and thus, a cycle). See EdgeWouldCreateCycle() or the paper for more details.

Note that confusingly enough, when used from the graph simplification algorithm, the vertices in this graph represent hyperedges (joins) in the join hypergraph, not the vertices (tables) themselves. The edges in this graph are happens-before relations between those joins.

[Pea03] Pearce et al: “Online Cycle Detection and Difference Propagation for Pointer Analysis”, section 3.2.

Constructor & Destructor Documentation

◆ OnlineCycleFinder()

OnlineCycleFinder::OnlineCycleFinder ( MEM_ROOT mem_root,
int  num_vertices 
)

Member Function Documentation

◆ AddEdge()

bool OnlineCycleFinder::AddEdge ( int  a_idx,
int  b_idx 
)

◆ Allocate()

void OnlineCycleFinder::Allocate ( int  node_idx,
int  index_in_order 
)
inlineprivate

◆ DeleteEdge()

void OnlineCycleFinder::DeleteEdge ( int  a_idx,
int  b_idx 
)

◆ DepthFirstSearch()

bool OnlineCycleFinder::DepthFirstSearch ( int  node_idx,
int  upper_bound,
int  node_idx_to_avoid 
)
private

◆ EdgeWouldCreateCycle()

bool OnlineCycleFinder::EdgeWouldCreateCycle ( int  a_idx,
int  b_idx 
)

◆ MoveAllMarked()

void OnlineCycleFinder::MoveAllMarked ( int  start_pos,
int  new_pos 
)
private

◆ order()

Bounds_checked_array< int > OnlineCycleFinder::order ( ) const
inline

Member Data Documentation

◆ m_edges

mem_root_unordered_multimap<int, int> OnlineCycleFinder::m_edges
private

◆ m_order

Bounds_checked_array<int> OnlineCycleFinder::m_order
private

◆ m_position_of_node

Bounds_checked_array<int> OnlineCycleFinder::m_position_of_node
private

◆ m_to_shift

Mem_root_array<int> OnlineCycleFinder::m_to_shift
private

◆ m_visited

Bounds_checked_array<bool> OnlineCycleFinder::m_visited
private

The documentation for this class was generated from the following files: