* RWTH Aachen, Ahornstr. 55, 52056 Aachen, Germany
+ DFKI, Stuhlsatzenhausweg 3, 66123 Saarbrücken, Germany
This observation was the the main motivation for the first workshop KRDB'94 held in conjunction with the German National Conference on Artificial Intelligence KI'94. The goal of the workshop was to provide a platform where experts of both areas can meet and cross-fertilize their work. In particular, we hoped to obtain a collection of viewpoints on structured objects and reasoning services required by applications. The call for papers resulted in submissions from France, Italy, Switzerland, and Germany. With respect to the number of presentations it was the largest of the 18 workshops at the KI'94.
Connections between conceptual database models and concept languages have been investigated since the late eighties. As one result, reasoning techniques from knowledge representation became applicable to database tasks. For example, the problem whether there exists a database for a given entity relationship diagram can be solved by encoding the diagram into a set of statements in a concept language and then checking the encoding for satisfiability. Recently, this idea has been extended to other conceptual database models like semantic data models and object-oriented data models. The latter cannot be represented completely because methods have no counterpart in concept languages.
Another area of cross-fertilization is the determination of view types in object-oriented databases. Loosely speaking, views are predefined queries to a database. They are part of the database schema. To determine whether an answer object of the view satisfies the type restrictions of a method, one can classify the view definition against the type system. This task can be solved by using subsumption algorithms for suitable concept languages.
Concept languages have been proposed for semantic query optimization for object-oriented databases. Here, the predicative specification of a query is separated into two conjuncts, a ``structural part'' that can be expressed in a concept language, and the remaining ``dirty'' part. The structural parts of two queries can then be checked for subsumption, and this information can be used for optimization purposes.
Conversely, implementations of KR systems can profit from database technology. A common approach is to build hybrid systems with a database component where the instances of classes are stored. Under the additional assumption that all possible information about the instances is stored---the so-called Closed World Assumption, which is, however, not always justified in KR---the query mechanism of the database system can be used to compute inferences in the KR system.
A topic of common interest is the use of indexing techniques in knowledge and databases. Semantic indices based on class descriptions can be used to increase the performance of query answering, i.e., finding the set of individuals belonging to the class defined by the query. When a query is submitted then the most specific subsuming indices are used for optimization.
Maurizio Lenzerini from the University of Rome I, "La Sapienza", pointed out how inferences with concepts languages can be applied to database tasks that require schema level reasoning.
The first application he mentioned was the analysis of conceptual database models specified in some object-oriented or Entity-Relationship like language. He presented a concept language that is rich enough to capture very expressive data models containing, for instance, extended is-a-relations (like Student is subclass of all Persons who are not Professors) and cardinality restrictions (like a Student takes at most five Courses). In order to check whether a schema is free of contradictions, one translates it into concept language descriptions, and tests them for satisfiability. Since a database can only contain a finite number of instances, it is particularly interesting to test whether a description is satisfiable by a finite model. For such a task, standard techniques from logic are not applicable. However, there is an algorithm that is based on linear programming. Although the worst-case complexity of the satisfiability problem in the rich language is exponential, the algorithm runs in polynomial time when used for deciding the consistency of database schemas obeying some natural restrictions.
As a second application, Lenzerini proposed to represent so-called inter-schema knowledge between cooperative information systems. Assuming that the systems involved are described in an expressive entity relationship language, the problem is to relate the entities and relationships in one schema to those in another one. This can be done with the help of axioms stating that a complex description in terms of one schema is subsumed by a description in terms of the second schema. For example, one can say that the Students in system A are a subset of the Graduate-Students in system B. After a translation of the schemas into a concept language, inference techniques become available for consistency checks and for deriving consequences of the axioms.
Marc Scholl from the University of Ulm argued that the topic of views can link research in databases and knowledge representation. Views are prefabricated queries which are used to define more complex queries, to optimize queries by precomputing the answer to views, to enhance security and integrity of a database, and last, but not least, to integrate database schemas. Object-oriented databases, like the Cocoon system developed in Ulm, provide for schema languages that have many characteristics in common with concept languages. Views in such a system can be seen as new classes defined by the properties of their elements. To find the right place of a view class in the class hierarchy of a schema, Cocoon uses a procedure similar to subsumption algorithms for concept languages. Views can be specified by an arbitrary algebraic query expression, which is too expressive a language to keep subsumption decidable. The implemented procedure is incomplete for the full problem, but works well for most real cases.
The presentation of a data analysis practitioner surprised the audience. He reported that entity-relationship diagrams are not a suitable language for discussing a database schema with customers because database developers tend to prematurely translate them, at least mentally, to the relational level. Instead, a language only consisting of nodes and links was much more successful in his projects. The diagram is augmented afterwards by constraints. This techniques was motivated by the use of semantic networks for knowledge representation in AI.
The number of ideas and techniques was impressive, though sometimes being limited in its focus. People coming from KR learned that there is a multitude of practical applications that are strongly related to their work. In many cases, properties of an application make methods tractable that are intractable in the general case.
We plan to continue the workshop in 1995, and to establish it as a forum for information exchange. The current trend to distributed systems and world-wide communication creates new challenges for conceptual modeling and reasoning. We believe that the combination of KR and DB is a good answer to these challenges.