Access Restriction

Author Demolombe, Robert
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1992
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Relational model
Abstract A domain-independent formula of first-order predicate calculus is a formula whose evaluation in a given interpretation does not change when we add a new constant to the interpretation domain. The formulas used to express queries, integrity constraints or deductive rules in the database field that have an intuitive meaning are domain independent. That is the reason why this class is of great interest in practice. Unfortunately, this class is not decidable, and the problem is to characterize new subclasses, as large as possible, which are decidable. A syntactic characterization of a class of formulas, the Evaluable formulas, which are proved to be domain independent are provided. This class is defined only for function-free formulas. It is also proved that the class of evaluable formulas contains the other classes of syntactically characterized domain-independent formulas usually found in the literature, namely, range-separable formulas and range-restricted formulas. Finally, it is shown that the expressive power of evaluable formulas is the same as that of domain-independent formulas. That is, each domain-independent formula admits an equivalent evaluable one. An important advantage of this characterization is that, to check if a formula is evaluable, it is not necessary to transform it to a normal form, as is the case for range-restricted formulas.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1992-01-02
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 39
Issue Number 1
Page Count 24
Starting Page 71
Ending Page 94

Open content in new tab

   Open content in new tab
Source: ACM Digital Library