Abstract This work develops an approach to ef?cient reasoning in ?rst-order knowledge bases with incomplete information. We build on Levesque’s proper knowledge bases approach, which supports limited incomplete knowledge in the form of a possibly in?nite set of positive or negative ground facts. We propose a generalization which allows these facts to involve unknown individuals, as in the work on labeled null values in databases. Dealing with such unknown individuals has been shown to be a key feature in the database literature on data integration and data exchange. In this way, we obtain one of the most expressive ?rst-order open-world settings for which reasoning can still be done ef?ciently by evaluation, as in relational databases. We show the soundness of the reasoning procedure and its completeness for queries in a certain normal form.