Narrow Results

Datalog programs, are a special case of logic programs without function symbols. Detection of boundedness permits Datalog programs to be optimized by the elimination of recursion. To determine whether a predicate is bounded in a Datalog program is known to be undecidable. However, previous work (Cosmadakis et al., 20th ACM Symposium on the Theory of Computing, 1988) has show that for monadic Datalog, this problem is decidable, with upper and lower bounds of EXPSPACE and PSPACE respectively for linear monadic programs. We establish that predicate boundedness for linear monadic programs is in fact in PSPACE, yielding a tight bound for this problem.^a

We consider similarity-based relational databases that allow to retrieve approximate data, find data within a given range of distance or similarity, and support imprecise queries. We focus on the recently introduced relational algebra with similarities on -relations, which are annotated with multi-dimensional similarity values with each dimension referring to a single attribute. The codomains of the annotated relations are De Morgan frames, and the annotations express the relevance of the tuples as answers to a similarity-based query. In this paper, we study Datalog programs on -relations, with and without negation. We describe the least-fixpoint algorithm for safe and rectified Datalog programs on -relations with finite support but without negative literals in the body. We further describe the perfect-minimal-fixpoint algorithm of a Datalog program on -relations with finite support and negative literals in the body when rules are safe, rectified and stratified. We introduce the idea of controlling the calculation of the annotations such that the tuples that enter an IDB relation last will be announced less desirable than those that enter first. For this we define a damping function that augments/diminishes the individual annotations that contribute to the final annotations of tuples. With a damping function, for instance, long chains of inferences may be made significantly less desirable or even totally undesirable.

A logical database schema, e.g. a relational one, is the implementation of a specification, e.g. an entity-relationship diagram. Upcoming new data models require a cost-effective method for mapping from one data model to the other. We present an approach where the mapping process is divided into three parts. The first part reformulates the source and target data models into a so-called meta model. The second part classifies the input schema into the meta model, yielding a data model-independent representation. The third part synthesizes the output schema in terms of the target data model. The meta model, the data models as well as the schemas are all represented in the logic-based formalism of O-Telos. Its ability to quantify across data model concepts is the key to classifying schema elements independently of their data model. A prototype has been implemented on top of the deductive object base manager ConceptBase for the mapping of relational schemas to entity-relationship diagrams. From this, a C++-based tool has been derived as part of a commercial CASE environment for database applications.