Publications of Anna Formica

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  ALL, with author Formica A., in the category IASI Research Reports (or show them all):


IASI Research Report n. 469  (Previous    Next)  

Anna Formica

Finite satisfiability of integrity constraints in object-oriented database schemas

ABSTRACT
Checking satisfiability of database constraints is a fundamental problem in database design. In addition, database constraints have to be not only satisfiable but also finitely satisfiable. This problem is generally addressed by using theorem provers that, being developed for first order logic formulas, are based on semidecidable procedures. Furthermore, even in simple cases, theorem provers are quite inefficient in dealing with comparison operators, such as for instance the equality. In this paper, a decidable, sound, and complete method for checking finite satisfiability of a specific class of integrity constraints for Object-Oriented databases, including the equality constraints, is presented. The method, that is based on a graph-theoretic approach, has exponential complexity in the worst case, rarely occurring in practice.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -