QUERYING WEAK INSTANCES UNDER EXTENSION CHASE SEMANTICS: A COMPLETE SOLUTION
Authors:
D. Laurent a;
V. Phan Luong b;
N. Spyratos c
| Affiliations: | a LI, Universit F. Rabelais de Tours, 3, place Jean Jaur s, F-41000 Blois, France. |
b LIM, ESA 6077, C.M.I., Universit de Provence, 39, Joliot-Curie, F-13453 Cedex 13, France. |
|
c LRI, Universit de Paris-Sud, Orsay Cedex, F-91405, France. |
DOI:
10.1080/0020716031000079509
Publication Frequency:
12 issues per year
Published in:
International Journal of Computer Mathematics,
Volume
80,
Issue
5
May
2003
, pages 591
- 613
Subjects:
Analysis - Mathematics;
Bioinformatics;
Computer Mathematics;
Discrete Mathematics;
Mathematical Finance;
Mathematical Logic;
Mathematical Numerical Analysis;
Systems & Computer Architecture;
Number of References: 36
Formats available:
PDF
(English)
View Article:
View Article (PDF)
Abstract
The problem of computing windows using relational expressions has been solved only in certain cases in which the chase semantics and the extension chase semantics of the database coincide. However, the general problem of computing windows under either chase semantics or extension chase semantics, but without restrictions, remained an open problem. In this paper we present a complete solution of the general problem, under extension chase semantics. Our solution is complete in the sense that it does not require any assumption on the database scheme or on the database state. It follows that our approach subsumes previous approaches, and we exhibit cases in which our approach correctly computes the windows, while previous approaches fail to do so. Moreover, the efficiency of our approach lies in the fact that it uses only those relation schemes and only those functional dependencies that are necessary in the computation of windows. The main technique employed by our approach is a least fixpoint construction using the notion of cover (a cover being a set of relation schemes satisfying certain properties). The proposed technique can be implemented using relational algebra plus recursion.
|
| Keywords: Relational Databases; Functional Dependencies; Incomplete Information; Deductive Databases; Universal Scheme Interfaces |
| view references (36) |

Download Citation

F. Rabelais de Tours, 3, place Jean Jaur
CiteULike
Del.icio.us
BibSonomy
Connotea