Proposition 30. There are CQs Q and sets of IDs C such that NQI(Q, C, S, V) can not be described by a first-order query over V. More generally, there are CQs Q and sets of IDs C such that NQI(Q, C, S, C, V) is PTime-hard in **data** complexity (that is, as V varies over instances).