For instance, I use parent tasks as "Projects" (in GTD terminology) and subtasks for my "Next Action" list. If I set a parent task to "Someday" status, I shouldn't have to manually change the subtasks to "Waiting" or "Someday" status. It'd be much better to save a custom search, showing only the "Next Action" tasks which either have no parent, or whose parent is not in "Someday" status.
Alternatively, I'd like to do a search on all tasks with context "Project", which have no unchecked subtasks with status "Next Action", so I could see at a glance which projects I needed to make a Next Action for.
I hope the usefulness of this feature is clear.
As to the interface, it'd probably be easiest if for each criterion, there were a radio button, and you could pick between "Parent", "Subtask", and "This Task", to choose which one it applied to.
From a database standpoint, a simple LEFT JOIN in your MySQL query (or whatever you use) would probably do the trick.