Knowledgebase Transformations

AbstractWe propose a language that expresses uniformly queries and updates on knowledgebases consisting of finite sets of relational structures. The language contains an operator that “inserts” arbitrary first-order sentences into a knowledgebase. The semantics of the insertion is based on the notion ofupdateformalized by Katsuno and Mendelzon in the context of belief revision theory. Our language can express, among other things, hypothetical queries and queries on recursively indefinite databases. The expressive power of our language lies between existential second-order and general second-order queries. The data complexity is in general within polynomial space, although it can be lowered toco-NPand to polynomial time by restricting the form of queries and updates