Databases
StackOverflow2013
Postsdbo
POTree matching algorithm?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POTree matching algorithm?
    primarykey
    data
    text
    <p>I am working on a <a href="http://en.wikipedia.org/wiki/Tree_structure" rel="nofollow noreferrer">tree</a> library, and part of the required functionality, is to be able to search a node for child nodes that match a pattern.</p> <p>A 'pattern' is a specification (or criteria) that lays out the structure, as well as attributes of nodes in the subtree(s) to be matched.</p> <p>For example, suppose a tree represents data regarding a particular species of bird. Further assume that the nodes of such a tree have the following attributes:</p> <ul> <li>location</li> <li>sex</li> <li>wingspan</li> <li>weight</li> <li>brood_size</li> </ul> <p>Given a parent node, I would like to issue a search in plain English thus:</p> <blockquote> <p>"Fetch me all male birds that are descendants of this bird, and live in XXX city and have a weight > 100g. Any such bird found should also have at least 2 brothers and one sister, and must itself have at least one child"</p> </blockquote> <p><strong>&lt; note ></strong></p> <p>Just to clarify, I do not expect to be able to query using plain English as I have done above. I only used the "plain English query" to illustrate the type of matching I would like to be performing on the tree. I fully expect to use symbols for the matching (as opposed to plain text) in practice.</p> <p><strong>&lt; /note ></strong></p> <p>I am thinking of possibly using a regex type pattern matching to match trees. One way would be to have a string representation of each node, so I could use a normal regex - but this is likely of be quite inefficient, as there will be a lot of repeated data - i.e. string representation of child nodes will be supersets of their parent representation, which will be supersets of their parents representational string, and so on, recursively, up the tree - this could very easily become unwieldy for event modestly sized trees - there has to be a better way.</p> <p>Is anyone aware of an algorithm that will allow me to select nodes (subtrees) in a node, based on a pattern?</p> <p>Although I asked for a general algorithm, I am implementing this in Python. any snippets that further illustrate such an algorithm (if one can indeed be written), would be immensely useful.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USmorpheous
    1. USmorpheous
    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. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POTree matching algorithm?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POTree matching algorithm?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POTree matching algorithm?
      1. USguidoism
      1. VTFavorite
    1. COYou're probably far better off using a recursive list, which you'd actually be doing anyway just with an intermediate list ➔ string ➔ regexp ➔ list that probably is not worth the overhead. A more concrete example would help get you a better answer.
      singulars
      1. POTree matching algorithm?
      1. USmsw
    2. COYou have *2* problems: a) how to represent a tree pattern match as a formal interpretable entity and b) Converting an free-text English query into such a pattern. a) is well known; see my answer for one option. b) is still a topic of research; I doubt you want try that on your own.
      singulars
      1. POTree matching algorithm?
      1. USIra Baxter
    3. CO@Ira: just to be clear, I only used the "plain English query" to illustrate the type of matching I would like to be performing on the tree. I expect to use symbols for the matching (as opposed to plain text) in practice - I think I will edit my post to clarify that
      singulars
      1. POTree matching algorithm?
      1. USmorpheous
 

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