Somebody willing to select the users from Texas and Alabama would think like state = Texas and state = Alabama and would get zero users selected, because nobody lives in Texas and Alabama.
The previous example illustrates the issues with Boolean expressions mentioned by @user1757436.
IT people understand and love Boolean algebra, and think that everybody else also does. This is why there were so many attempts to publish such UIs.
There is also a skill that we IT-related people have, and that normal people don't, which is the ability to formulate an abstract expression from the top of our heads based on its expected result. Like, a computer program, or a complex Boolean expression.
To skip the issues mentioned above, I'd pose the user an incremental UI, one that worked more like the mind.
For example allow the user the user select DiCaprio and get a lot of films, and the same ol' search form to refine or enlarge the search.
The user's second step could be to realize that she was not very sure if it was DiCaprio or Alain Delon, so she would add all Delon's films, getting instant feedback.
Next, noticing that the current (rather contrived, for the benefit of the example) selection includes too many films, she'd filter it by selecting only horror films.
If the list is still too long she could refine it by choosing only a range of years.
At every stage she'd see the results (instantly, aren't we in 2012?) and a text in English describing the search criteria, like Horror films featuring DiCaprio or Delon, released between 1964 and 2008.
The "we are in 2012" comment means that, in 1998, a database search and the transmission of the results involved a significant amount of resources, while today it does not.
See for example Google, that shows the results almost as you type.
In brief, don't make the users write Boolean expressions, show the results instantly, and let them know what are they looking for.