Implementing a tag search with operands

Question

I've been trying to implement a tag based search where users may type a string of tags using the operators & | and ! along with the ability to group search terms [i.e. (X&Y)|!Z]. My plan is to then be able to translate there short string into a full SQL query that may search for objects which have been linked with particular tags.

object    >--<    tags
object -< bond >- tags

 -----------    -----------------------    ------
| object    |  | bond                  |  | tag  |
 -----------    ---- -------- ---------    ------ 
| Id | Name |  | Id | textId | tagName |  | Name |
 ---- ------    ---- -------- ---------    ------ 
| 1  | A    |  | 1  | 1      | V       |  | V    |
| 2  | B    |  | 2  | 1      | W       |  | W    |
| 3  | C    |  | 3  | 1      | X       |  | X    |
 ---- ------   | 4  | 2      | Z       |  | Y    |
               | 5  | 3      | V       |  | Z    |
               | 6  | 3      | W       |   ------
               | 7  | 3      | X       |
               | 8  | 3      | Y       |
                ---- -------- ---------

SEARCH: 
    (X&Y)|Z

QUERY:{
    SELECT *
    FROM object
    WHERE object.id = bond.textId
    AND (
        (bond.tagName = 'X' AND bond.tagName = 'Y')
        OR bond.tagName = 'Z'
    )

RETURN: 
    2 | B
    3 | C

I have written the following to compile the query http://jsfiddle.net/wP7JR/1/

and the following to test my query http://sqlfiddle.com/#!2/139ca/3/0

However, I notice a few problems and am looking for guidance:

• First and foremost, I have been searching and searching for resources which discuss this problem, solutions to this problem and so on. However, my biggest problem is I do not know what the best search is... I'm sure there's a name for this type of problem, there always is.

• Secondly, My SQL is clearly amateur and wrong since a search for tagName <> 'Y' I would want to return objects 1 and 2 but instead I receive 1, 2 and 3 since there are bonds where object 3 is not linked to Y.

• My search for (tagName = 'X' & tagName = 'Y') returns nothing and I know the reason for this is that there are no occurances of objects where tag X and Y are linked at the same time...

So, hence forth, I'm looking for a bit of guidance to resolving my problem.

Thinks to search for, similar problems, solutions(?), alternative solutions(? If my one is not an optimal way of solving this problem).

Thanks

Answer 1

I think that you could accomplish a solution to your problem implementing a Binary Expression Tree, and then given that structure you could start creating your SQL begining from the most-left node (in fact, you have to use inorder, post-order or pre-order according to your expression format).

Other solution, a little bit more complex, could be working with lexers and parsers, generating your own grammar.. read this

As your other questions, you'll first have to define what operator '&' would do.. tagname = 'X' & tagname = 'Y' means that item have at least these two tags and not that item could have X or Y tag.