Consulta avanzada (?) Y/O

Tengo que decir que estoy perplejo. No puedo pensar en ninguna solución que venga incluso cerca. Intentaría buscar una solución en estas direcciones:

• Funciones agregadas definidas por el usuario. Tal vez puedas hacer una función que tome como argumento la expresión deseada (en una sintaxis simplificada) y las filas para una sola persona. Luego, la función analiza la expresión y la compara con las filas. Hmm... ¿Quizás MySQL incluye alguna función agregada de concatenación y una función de coincidencia de expresiones regulares? Esta podría ser una solución entonces (aunque probablemente no muy rápida).
• Funciones analíticas. No pretendo entenderlos, pero por lo que sé sobre ellos, creo que generalmente van en esta dirección. Aunque no sé si habrá una función que se adapte a esta necesidad.

Añadido: ¡Ah, creo que lo tengo! Aunque creo que el rendimiento será miserable. ¡Pero esto funcionará! Por ejemplo, si tiene el requisito de buscar 1 AND 2 AND (3 OR 4) entonces escribirías:

SELECT
    *
FROM
    Persons A
WHERE
    EXISTS (Select * from PersonCriteria B WHERE A.PersonID=B.PersonID AND CriteriaID=1)
    AND
    EXISTS (Select * from PersonCriteria B WHERE A.PersonID=B.PersonID AND CriteriaID=2)
    AND
    (
        EXISTS (Select * from PersonCriteria B WHERE A.PersonID=B.PersonID AND CriteriaID=3)
        OR
        EXISTS (Select * from PersonCriteria B WHERE A.PersonID=B.PersonID AND CriteriaID=4)
    )

Añadido 2: Aquí hay otro, aunque es probable que el rendimiento sea aún peor:

SELECT p.* FROM Person p
    JOIN (select PersonID from PersonCriteria WHERE CriteriaID=1) c1 ON p.PersonID=c1.PersonID
    JOIN (select PersonID from PersonCriteria WHERE CriteriaID=2) c2 ON p.PersonID=c2.PersonID
    JOIN (select PersonID from PersonCriteria WHERE CriteriaID IN (3,4)) c3 ON p.PersonID=c3.PersonID

Agregado 3: Esta es una variación del No. 2, ¡pero en realidad podría tener la posibilidad de tener un rendimiento decente!

SELECT p.* FROM
    Person p
    JOIN PersonCriteria c1 on (p.PersonID=c1.PersonID AND c1.CriteriaID=1)
    JOIN PersonCriteria c2 on (p.PersonID=c2.PersonID AND c2.CriteriaID=2)
    JOIN PersonCriteria c3 on (p.PersonID=c3.PersonID AND c3.CriteriaID IN (3,4))

Si agrega un índice a PersonCriteria en las columnas (PersonID,CriteriaID) (¡exactamente en este orden!), entonces creo que es lo más rápido que obtendrá en cualquier caso.