Knowledgebase Transformations

✍ Scribed by Gösta Grahne; Alberto O. Mendelzon; Peter Z. Revesz

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 825 KB
• Volume: 54
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1997.1454

✦ Synopsis

We 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 of update formalized 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 to co-NP and to polynomial time by restricting the form of queries and updates. ] 1997 Academic Press

Example 1.1. Suppose two robot vehicles V and W are orbiting Venus. We have received the message ``I have landed,'' but due to noise we could not determine whether article no.