Does a normalized design lead to complex queries?

Suppose we have to design a database for a recruitment agency. There
will be a table "candidates" with fields "candidateid","last
name","first name" ; the languages mastered by a candidate as
well as the skills are separated into different tables. Eg. The skills
are stored in the table "skills" with fields "skillid",
"skillname","candidateid" where skillid is the primary
autoincrement key. The language table is defined in a similar way. A
candidate having two skills will lead to two records in the table
"skills"; similarly a candidate mastering 3 languages will lead to
3 records in the table "languages".
Retrieving candidates with skills with skillname="php" and
skillname="asp" as well as languagename="EN" and
languagename="FR" can be done as follows:
SELECT DISTINCT c.name FROM candidates c, skills s, languages l WHERE
l.candidateid=c.candidateid AND s.candidateid=c.candidateid AND
(s.skillname='php' OR s.skillname='asp') AND (l.languagename='FR' OR
l.languagename='EN')
GROUP BY c.name HAVING (count(DISTINCT s.skillid)=2 AND count(DISTINCT
l.languageid)=2)
This already rather complex query (for a non-expert as myself) is
probably the disadvantage of a normalized design.
The problem that bothers me most is the following: what happens if I
want to built a search tool to find candidates using a flexible search
interface; in this interface the user could type "meta queries"
such as: find me the candidates that (master php AND (asp OR net)) AND
(that master French OR (Dutch AND German))
This query looks quite simple but how to translate this to one query
for the normalized database?
Do I first have to do the following conversion:
find me the candidates that (master (php AND asp) OR (php AND net)) AND
(that master French OR (Dutch AND German))
becoming
find me the candidates that (master (php AND asp)) AND (that master
French)
OR
find me the candidates that (master (php AND asp)) AND (that master
Dutch AND German)
OR
find me the candidates that (master (php AND net)) AND (that master
French)
OR
find me the candidates that (master (php AND net)) AND (that master
Dutch AND German)
Next I assume the three ORs have to be combined via UNION statements?
This seems quite complicated so I was wondering if there is no easier
way to create an SQL query starting from the "meta query" above?