Foundations of Secure Deductive Databases

Piero A. Bonatti, Sarit Kraus, V. S. Subrahmanian

Research output: Contribution to journalArticlepeer-review

82 Scopus citations


In this paper, we develop a formal logical foundation for secure deductive databases. This logical foundation is based on an extended logic involving several modal operators. We develop two models of interaction between the user and the database called “yes-no" dialogs, and “yes-no-don’t know" dialogs. Both dialog frameworks allow the database to lie to the user. We develop an algorithm for answering queries using yes-no dialogs and prove that secure query processing using yes-no dialogs is NP-complete. Consequently, the degree of computational intractability of query processing with yes-no dialogs is no worse than for ordinary databases. Furthermore, the algorithm is maximally cooperative to user in the sense that lying is resorted to only when absolutely necessary. For Horn databases, we show that secure query processing can be achieved in linear time - hence, this is no more intractable than the situation in ordinary databases. Finally, we identify necessary and sufficient conditions for the database to be able to preserve security. Similar results are also obtained for yes-no-don’t know dialogs.

Original languageEnglish (US)
Pages (from-to)406-422
Number of pages17
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number3
StatePublished - Jun 1995
Externally publishedYes


  • Deductive databases
  • com-
  • logic programming
  • puter security
  • secure databases

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Foundations of Secure Deductive Databases'. Together they form a unique fingerprint.

Cite this