We show how deductive databases may be protected against unauthorized retrieval and update requests issued by authenticated users. To achieve this protection, a deductive database is expressed in an equivalent form that is guaranteed to permit only authorized actions. When a user poses a query Q on the protected form of a database, the user sees the subset of the answers for Q that they are permitted to know are true in the database; when a user’s update request is received, a minimal set of authorized changes the user is permitted to make to the database is performed. The authorized retrieval and update requests are specified using a security theory that is expressed in normal clause logic. The approach has a number of attractive technical results associated with it, and can be used to protect the information in any deductive database that is expressed in normal clause logic.