Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The usual technique of hashing any sequence is combining the values (or hashes thereof) of its elements in some mathematical way. I don't think a tree would be any different in this respect. </p> <p>For example, here is the hash function for tuples in Python (taken from Objects/tupleobject.c in the source of Python 2.6):</p> <pre><code>static long tuplehash(PyTupleObject *v) { register long x, y; register Py_ssize_t len = Py_SIZE(v); register PyObject **p; long mult = 1000003L; x = 0x345678L; p = v-&gt;ob_item; while (--len &gt;= 0) { y = PyObject_Hash(*p++); if (y == -1) return -1; x = (x ^ y) * mult; /* the cast might truncate len; that doesn't change hash stability */ mult += (long)(82520L + len + len); } x += 97531L; if (x == -1) x = -2; return x; } </code></pre> <p>It's a relatively complex combination with constants experimentally chosen for best results for tuples of typical lengths. What I'm trying to show with this code snippet is that the issue is very complex and very heuristic, and the quality of the results probably depend on the more specific aspects of your data - i.e. domain knowledge may help you reach better results. However, for good-enough results you shouldn't look too far. I would guess that taking this algorithm and combining all the nodes of the tree instead of all the tuple elements, plus adding their position into play will give you a pretty good algorithm.</p> <p>One option of taking the position into account is the node's position in an inorder walk of the tree.</p>
    singulars
    1. This table or related slice is empty.
    1. POHashing a Tree Structure
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USEli Bendersky
    1. USEli Bendersky
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    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. VTUpMod
    1. COYou make a good point in general. However, trees are slightly different to sequences in that they contain greater structure - a tree cannot simply be represent by a sequence (unless you specifically know it is a binary/ternary/etc. tree). Might be able to adapt the algorithm easily enough however...
      singulars
      1. PO
      1. USNoldorin
    2. COA tree *can* be represented as a sequence. I showed in my answer and example of how.
      singulars
      1. PO
      1. USP Shved
    3. COThe "position" incorporates the path information. For example, for every node assign a position value of 0 for the node itself and 1..n for each of its n children from left to right. When you visit child number i in your traversal, you include i in the hash. When you visit the node itself, include 0 and the node's hash contents. The choice of the constants 0, 1, ..., n was arbitrary and should instead be chosen based on domain-specific knowledge, e.g. maybe "0-mississippi", "1-mississippi", etc. will work better.
      singulars
      1. PO
      1. USJames K Polk
 

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