RULE-BASED LANGUAGES

The paper presents a survey of the main formal rule-based languages an d semantics. Both procedural (fixpoint) and declarative (model-theoret ic) semantics are defined and discussed, including inflationary and no ninflationary fixpoint semantics, and the semi-positive, stratified an d well-founded semantics. The relative expressive power and complexity of the various languages are provided. Nondeterministic rule-based la nguages are also discussed, and it is shown how nondeterminism can cir cumvent some difficulties concerning the expressive power of the deter ministic languages. Finally, languages with value invention (in the sp irit of object-creation in oodbs) are presented and issues of expressi ve power specific to such languages are discussed.