How do I structure a SELECT query for the following...

Question

Hoping that someone here will be able to provide some mysql advice...

I am working on a categorical searchtag system. I have tables like the following:

EXERCISES
    exerciseID
    exerciseTitle

SEARCHTAGS
    searchtagID
    parentID ( -> searchtagID)
    searchtag

EXERCISESEARCHTAGS
    exerciseID (Foreign key -> EXERCISES)
    searchtagID (Foreign key -> SEARCHTAGS)

Searchtags can be arranged in an arbitrarily deep tree. So for example I might have a tree of searchtags that looks like this...

Body Parts
    Head
    Neck
    Arm
        Shoulder
        Elbow
    Leg
        Hip
        Knee
Muscles
    Pecs
    Biceps
    Triceps

Now...

I want to select all of the searchtags in ONE branch of the tree that reference at least ONE record in the subset of records referenced by a SINGLE searchtag in a DIFFERENT branch of the tree.

For example, let's say the searchtag "Arm" points to a subset of exercises. If any of the exercises in that subset are also referenced by searchtags from the "Muscles" branch of SEARCHTAGS, I would like to select for them. So my query could potentially return "Biceps," "Triceps".

Two questions:

1) What would the SELECT query for something like this look like? (If such a thing is even possible without creating a lot of slow down. I'm not sure where to start...)

2) Is there anything I should do to tweak my datastructure to ensure this query will continue to run fast - even as the tables get big?

Thanks in advance for your help, it's much appreciated.

Answer 1

An idea: consider using a cache table that saves all ancestor relationships in your searchtags:

CREATE TABLE SEARCHTAGRELATIONS (
    parentID INT,
    descendantID INT
);

Also include the tag itself as parent and descendant (so, for searchtag with id 1, the relations table includes a row with (1,1).

That way, you get rid of the parent/descendant relationships and can join a flat table. Assuming "Muscles" has the ID 5,

SELECT descendantID FROM SEARCHTAGRELATIONS WHERE parentID=5

returns all searchtags contained in muscles.

Answer 2

Alternatively, use modified preorder tree traversal, also known as the nested set model. It requires two fields (left and right) instead of one (parent id), and makes certain operations harder, but makes selecting whole branches much easier.