Role of determinism in query languages for data bases (Q1112628): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Structure and complexity of relational queries / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Expressing program looping in regular dynamic logic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The comparison of the expressive power of first-order dynamic logics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3957927 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:12, 19 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Role of determinism in query languages for data bases |
scientific article |
Statements
Role of determinism in query languages for data bases (English)
0 references
1987
0 references
The idea of using a predicate logic as a query language for data bases belongs to \textit{E. F. Codd} and has existed for a long time. Relatively recently \textit{A. Chandra} and \textit{D. Harel} [J. Comput. Syst. Sci. 25, 99-128 (1982; Zbl 0511.68073)], considered a hierarchy of more powerful languages for data bases. Languages of various dynamic logics can be used as such languages as well. A natural requirement of such languages - the existence of an algorithm for determination of the truth of a given formula on a given data base - does not allow the use of certain powerful logics, for example a recursively enumerable logic. It is interesting in this connection to compare the expressive power of the languages of regular (DL) and deterministic regular (DDL) logics as query languages for data bases [see definitions in (*)\ \textit{M. A. Tajtslin}, Sib. Mat. Zh. 24, No.3(139), 184-192 (1983; Zbl 0518.03002)]. This is equivalent to a comparison of DDL and DL on the class of finite structures. The problem of the relation of the expressive power of DDL and DL is found in many works [\textit{A. R. Meyer} and \textit{K. Winklmann}, Theor. Comput. Sci. 18, 301-323 (1982; Zbl 0478.68031), et al.]. The answer was obtained by \textit{A. P. Stolboushkin} and \textit{M. A. Tajtslin} [ibid. 27, 197-209 (1983; Zbl 0536.03015)], as well as by \textit{P. Bernau}, \textit{J. Y. Halpern} and \textit{J. Tiuryn} [(**)\ Lect. Notes Comput. Sci. 140, 48-60 (1982; Zbl 0494.68032)]. However, in these works DDL and DL differ on classes of infinite structures. Our goal is to show that DL and DDL differ on the class of finite structures. In this connection we shall use techniques from (**). In addition, we assume familiarity with (*), in order not to repeat the definitions of DL and DDL. We note that in (*) DL is denoted by L(RG,0) and DDL by L(RD,0).
0 references
predicate logic as query language for data bases
0 references
regular logics
0 references
deterministic regular logic
0 references
dynamic logics
0 references
class of finite structures
0 references