FOUNDATIONS OF SECURE DEDUCTIVE DATABASES

In this paper, we develop a formal logical foundation for secure deduc tive databases. This logical foundation is based on an extended logic involving several modal operators. We develop two models of interactio n between the user and the database called ''yes-no'' dialogs, and ''y es-no-don't know'' dialogs. Both dialog frameworks allow the database to lie to the user. We develop an algorithm for answering queries usin g yes-no dialogs and prove that secure query processing using yes-no d ialogs is NP-complete. Consequently, the degree of computational intra ctability of query processing with yes-no dialogs is no worse than for ordinary databases. Furthermore, the algorithm is maximally cooperati ve to user in the sense that lying is resorted to only when absolutely necessary. For Horn databases, we show that secure query processing c an be achieved in linear time - hence, this is no more intractable tha n the situation in ordinary databases. Finally, we identify necessary and sufficient conditions for the database to be able to preserve secu rity. Similar results are also obtained for yes-no-don't know dialogs.