Topics in Knowledge Bases: Epistemic Ontologies and Secrecy-preserving Reasoning

Thumbnail Image
Tao, Jia
Major Professor
Vasant Honavar
Giora Slutzki
Committee Member
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Organizational Unit
Computer Science

Computer Science—the theory, representation, processing, communication and use of information—is fundamentally transforming every aspect of human endeavor. The Department of Computer Science at Iowa State University advances computational and information sciences through; 1. educational and research programs within and beyond the university; 2. active engagement to help define national and international research, and 3. educational agendas, and sustained commitment to graduating leaders for academia, industry and government.

The Computer Science Department was officially established in 1969, with Robert Stewart serving as the founding Department Chair. Faculty were composed of joint appointments with Mathematics, Statistics, and Electrical Engineering. In 1969, the building which now houses the Computer Science department, then simply called the Computer Science building, was completed. Later it was named Atanasoff Hall. Throughout the 1980s to present, the department expanded and developed its teaching and research agendas to cover many areas of computing.

Dates of Existence

Related Units

Journal Issue
Is Version Of

Applications of ontologies/knowledge bases (KBs) in many domains (healthcare, national security, intelligence) have become increasingly important. In this dissertation, we focus on developing techniques for answering queries posed to KBs under the open world assumption (OWA).

In the first part of this dissertation, we study the problem of query answering in KBs that contain epistemic information, i.e., knowledge of different experts. We study ALCKm, which extends the description logic ALC by adding modal operators of the basic multi-modal logic Km. We develop a sound and complete tableau algorithm for answering ALCKm queries w.r.t. an ALCKm knowledge base with an acyclic TBox. We then consider answering ALCKm queries w.r.t. an ALCKm knowledge base in which the epistemic operators correspond to those of classical multi-modal logic S4m and provide a sound and complete tableau algorithm. Both algorithms can be implemented in PSpace.

In the second part, we study problems that allow autonomous entities or organizations (collectively called querying agents) to be able to selectively share information. In this scenario, the KB must make sure its answers are informative but do not disclose sensitive information. Most of the work in this area has focused on access control mechanisms that prohibit access to sensitive information (secrets). However, such an approach can be too restrictive in that it prohibits the use of sensitive information in answering queries against knowledge bases even when it is possible to do so without compromising secrets. We investigate techniques for secrecy-preserving query answering (SPQA) against KBs under the OWA. We consider two scenarios of increasing difficulty: (a) a KB queried by a single agent; and (b) a KB queried by multiple agents where the secrecy policies can differ across the different agents and the agents can selectively communicate the answers that they receive from the KB with each other subject to the applicable answer sharing policies. We consider classes of KBs that are of interest from the standpoint of practical applications (e.g., description logics and Horn KBs). Given a KB and secrets that need to be protected against the querying agent(s), the SPQA problem aims at designing a secrecy-preserving reasoner that answers queries without compromising secrecy under OWA. Whenever truthfully answering a query risks compromising secrets, the reasoner is allowed to hide the answer to the query by feigning ignorance, i.e., answering the query as "Unknown". Under the OWA, the querying agent is not able to infer whether an "Unknown" answer to a query is obtained because of the incomplete information in the KB or because secrecy protection mechanism is being applied. In each scenario, we provide a general framework for the problem. In the single-agent case, we apply the general framework to the description logic EL and provide algorithms for answering queries as informatively as possible without compromising secrecy. In the multiagent case, we extend the general framework for the single-agent case. To model the communication between querying agents, we use a communication graph, a directed acyclic graph (DAG) with self-loops, where each node represents an agent and each edge represents the possibility of information sharing in the direction of the edge. We discuss the relationship between secrecy-preserving reasoners and envelopes (used to protect secrets) and present a special case of the communication graph that helps construct tight envelopes in the sense that removing any information from them will leave some secrets vulnerable. To illustrate our general idea of constructing envelopes, Horn KBs are considered.

Subject Categories
Sun Jan 01 00:00:00 UTC 2012