Answering queries posed over knowledge bases is a central problem in knowledge representation and database theory. In the database area, checking query containment is an important query optimization and schema integration technique (Aho, Sagiv, and Ullman 1979; Johnson and Klug 1984). In knowledge representation it has been used for object classification, schema integration, service discovery, and more. In the presence of a knowledge base, the problem of query containment is strictly related to that of query answering; indeed, the two are reducible to each other (Call, Gottlob, and Kifer 2008b); we focus on the latter, and our results immediately extend to the former. A practically relevant instance of the query containment problem was first studied in (Johnson and Klug 1984) for functional and inclusion dependencies, and later, for instance, in (Cal-vanese, Giacomo, and Lenzerini 1998).
展开▼
