Efficient Reasoning in Proper Knowledge Bases with Unknown Individuals
Giuseppe De Giacomo, Yves Lesperance and Hector Levesque
This work develops an approach to efficient reasoning in first-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 infinite set of positive or negative ground facts. We propose a generalization of proper knowledge bases that allows the known positive and negative 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 data integration and data exchange, where recent advances are based on computing certain answers to conjunctive queries over databases with labeled nulls. In this way we obtain one of the most expressive first-order open-world settings for which reasoning can still be done efficiently by evaluation, as in relational databases. We show soundness of the reasoning procedure and completeness for queries in Levesque's Normal Form.