Note that if you build it they will come, i.e. you will get the most ridiculously contorted tag queries being run on a regular basis. Hopefully it won't make the database crap itself if just OR and AND are allowed. Or even just AND.
I seem to get everything wrong when it comes to databases, but I would expect OR to be pretty easy. You just get the list of the first category (which we do all the time), do it again for the next (equally easy), and remove duplicates (I'm not sure how easy that would be, but I would think at worst it's O(n.log(n)). It's AND that's difficult because you have to compare everything in two categories (which is probably O(n^2)). With OR, you can do one at a time.