|go ahead... be a heretic|
Is [there] some sort of structure which maps a collection of cases to a collection of SQL labels?
I think you have a very flexible, structured tool available, one that lets you create the exact results you're looking for. Specifically, your database.
Determine an initial set of queries and their most common variations. Create a set of tables that express these variations well, and then use queries, views, stored procs, or whatever you want to provide a run time interface that lets the user:
As you can probably tell, this requires multiple tables. However, they will likely be very tiny tables, so there should be few performance concerns.
Maintenance should be simplified because it then becomes a data editing task, rather than a source modification. If your DBA creates a view to replace a complex WHERE clause, then you should be able to incorporate using a simple UPDATE query. If your end-user's new query turns out to be an alternate ORDER BY clause, you INSERT it into the appropriate detail table. If you model this properly, your Perl code should be very simple and basic.
In short, consider treating this as a data problem, not a language/module problem.