DATALOG EXTENSIONS FOR DATABASE QUERIES AND UPDATES

被引：105
作者：
ABITEBOUL, S [1 ]
VIANU, V [1 ]
机构：
[1] UNIV CALIF SAN DIEGO,DEPT CSE,LA JOLLA,CA 92093
来源：
JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1991年 / 43卷 / 01期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1016/0022-0000(91)90032-Z
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Deterministic and non-deterministic extensions of Datalog with fixpoint semantics are proposed, and their expressive power characterized. It is argued that fixpoint semantics provides an elegant way to overcome the limited expressive power available with purely declarative semantics. The Datalog extensions range from complete languages to languages capturing interesting complexity classes of queries and updates: PTIME and PSPACE in the non-deterministic case, and the fixpoint queries and while queries in the deterministic case. The connection between the Datalog extensions and explicitly procedural languages, as well as fixpoint extensions of first-order logic, is also investigated. In particular, a new family of non-deterministic fixpoint extensions of first-order logic is considered. © 1991.
引用
收藏
页码：62 / 124
页数：63
相关论文
共 50 条
  • [1] ABITEBHOUL S, 1988, 1988 P INT C DAT THE, P1
  • [2] ABITEBOUL S, 1989, FOURTH ANNUAL SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, P71
  • [3] PROCEDURAL LANGUAGES FOR DATABASE QUERIES AND UPDATES
    ABITEBOUL, S
    VIANU, V
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1990, 41 (02) : 181 - 229
  • [4] ABITEBOUL S, IN PRESS ANN MATH AR
  • [5] ABITEBOUL S, 1990, 1990 P ACM SIGACT SI, P218
  • [6] ABITEBOUL S, 1988, 7TH P ACM S PRINC DA, P240
  • [7] ABITEBOUL S, 1988, INRIA846 TECHN REP
  • [8] ABITEBOUL S, IN PRESS THEORET COM
  • [9] ABITEBOUS S, 1987, 1987 P ACM SIGACT SI, P260
  • [10] Aho Alfred V., 1979, 6TH P ACM S PRINC PR, P110
12345