Description: At the present time, deductive, nonmonotonic, and other non-standard databases are not generally available in commercial products. One impediment to their more widespread adoption is that most database application programmers are familiar with relational database programming, but are less or even totally unfamiliar with programming in a logic-based or other non-standard paradigms. If one looks at the design of most deductive-style databases such as NAIL!, LDL, CORAL, XSB, etc. they can usually act as a frontend to a more traditional relational database, but you cannot have the relational system act as a front end to them. However, if you could it might make it easier to deploy a deductive database system as then only the designer of the database needs understand the non-standard knowledge system and the application programmers can use the SQL they know and love. From a theoretical standpoint, such systems are still expressive: we can view the nonstandard knowledge system as an oracle set and consider the power of SQL (at least as strong as first-order) reductions to it. Unless the non-standard system is quite weak, this will generally be stronger than the relational system by itself. There are also many potential applications to such systems as you could for instance add tables for fuzzy or rule-based informations to the relational database that could be used to limit the scope of queries and potentially improve the speed of their evaluation. As my master's I intend to develop an interface system whereby non-standard knowledge systems can make their resources available as a backend to a more traditional relational database. The particular deliverable I will work towards is an XSB system [X02] backend for the Oracle system.

Schedule:

Deliverables:

1. The goal of the first couple deliverables is to become familiar with some nonstandard knowledge representation systems. Write a program that calculates the stable models semantics of a propositional logic program stored in a file.

2. Write a program that uses XSB's tabling features.

3. Create random Smodels knowledge-bases and use system to generate stable models. See if any threshold phenomena hold.

4. Suggest some designs for interface and try to implement some of it for an Oracle database. (Say using triggers.)

5. First semester report on project of length between 10-20 pages

References:

[AHV95] Foundations of Databases. Abiteboul, Hull, Vianu. Addison Wessley. 1995.

[EN00] Fundamentals of Database Systems 3rd. Ed. ElMasri and Navathe. Addison-Wesley. 2000.

[JM94] Jaffar and Mahar. Constraint Logic Programming: A survey. Journal of Logic Programming. pp503-581. 1994.

[SN97] I.Niemela and P. Simons. Smodels - an implementation of the stable model and well-founded semantics for normal logic programs. In Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning, volume 1265 of Lecture Notes in Artificial Intelligence, pages 420-429, Dagstuhl, Germany, July 1997.

[S00] P. Simons. Extending and Implementing the Stable Model Semantics. Doctoral dissertation. Research Report 58, Helsinki University of Technology, Helsinki, Finland, April 2000.