Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>There are a few methods that each may be faster depending on your structure, but in general what youre going to want is a traversal.</p> <p>A depth first search, goes through each possible route, keeping track of nodes that have already been visited. It's a recursive function, because at each node you have to branch and try each child node of it. There's no faster method if you dont know which way to look for the object you just have to try each way! You definitely need to keep track of where you have already been because it would be wasteful otherwise. It should require on the order of the number of nodes to do a full traversal. </p> <p>A breadth first search is similar but visits each child of the node before "moving on" and as such builds up layers of distance from the chosen root. This can be faster if the destination is expected to be close to the root node. It would be slower if it is expected to be all the way down a path, because it forces you to traverse every possible edge.</p> <p>Youre right about maybe keeping a list of known root nodes, the tradeoff there is that you basically have to do the search whenever you alter the graph. If you are altering the graph rarely this is acceptable, but if you alter the graph more frequently than you need to generate this information, then of course it is too costly. </p> <p>EDIT: Info Update. It sounds like we are actually looking for a path between two arbitrary nodes, the root/leaf semantic keeps getting switched. The DepthFirstSearch (DFS) starts at one node, and then for each unvisited child, recurse. Break if you find the target node. Due to the way recursion evaluates, this will traverse all the way down the 'left' path, then enumerate nodes at this distance before ever getting to the 'right' path. This is time costly and inefficient if the target node is potentially the first child on the right. BreadthFirst walks in steps, covering all children before moving forward. Because your graph is bottom heavy like a tree, both will be approximately the same execution time.</p> <p>When the graph is bottom heavy you might be interested in a reverse traversal. Start at the target node and walk upwards, because there are relatively fewer nodes in this direction. So long as the nodes in general have more parents than children, this direction will be much faster. You can also combine the approaches, stepping one up and one down , then comparing lists of nodes, and meeting somewhere in the middle. (this combination might seem the fastest if you ignore that twice as much work is done at each step).</p> <p>However, since you said that your graph is stored as a list of lists of children, you have no real way of traversing the graph backwards. A node does not know what its parents are. This is a problem. To fix it you have to get a node to know what its parents are by adding that data on graph update, or by creating a duplicate of the whole structure (which you have said is too large). It will need the whole structure to be rewritten, which sounds probably out of the question due to it being a large database at this point. There's a lot of work to do. <a href="http://en.wikipedia.org/wiki/Graph_(data_structure)" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Graph_(data_structure)</a></p>
    singulars
    1. This table or related slice is empty.
    1. POIs there an effient way of determining whether a leaf node is reachable from another arbitrary node in a Directed Acyclic Graph?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USKarl
    1. USKarl
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POIs there an effient way of determining whether a leaf node is reachable from another arbitrary node in a Directed Acyclic Graph?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COWell, we need to read this information about 3 times as often (very rough guesstimate) as the graph changes, but since as I just edited, the graph's more bottom heavy and I'm looking for nodes at the top.
      singulars
      1. PO
      1. USDavy8
    2. COThis is getting more and more complicated. Are you starting from a leaf and looking for a root, or are you starting from a root and looking for a leaf? The procedures will be different, and youve asked both... are we looking for a path between two arbitrary nodes? That might be a clearer solution.
      singulars
      1. PO
      1. USKarl
    3. COSorry for the confusion, I'm starting from an arbitrary node and looking for all roots (don't care about the path)
      singulars
      1. PO
      1. USDavy8
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload