Semantics and expressive power of nondeterministic constructs in deductive databases

被引：11
作者：
Giannotti, F
Pedreschi, D
Zaniolo, C
机构：
[1] CNR, CNUCE Inst, I-56125 Pisa, Italy
[2] Univ Pisa, Dipartimento Informat, I-56125 Pisa, Italy
[3] Univ Calif Los Angeles, Dept Comp Sci, Los Angeles, CA 90095 USA
来源：
JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2001年 / 62卷 / 01期
基金：
美国国家科学基金会;
关键词：
deductive databases; logic-based languages; nondeterminism; expressive power; operational semantics; declarative semantics; fixpoint;
D O I：
10.1006/jcss.1999.1699
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Nondeterministic extensions are needed in logic-based languages, such as first-order relational languages and Datalog, to enhance their expressive power and support the efficient formulation of low-complexity problems and database queries. In this paper, we study the semantics and expressive power of the various nondeterministic constructs proposed in the past, including various versions of the choice operator and the witness operator. The paper develops a model-theoretic semantics, a fixpoint semantics, and an operational semantics for these constructs, and characterizes their power of expressing deterministic and nondeterministic queries. The paper presents various soundness and completeness results and establishes an expressiveness hierarchy that correlates the various operators with each other and with other constructs such as negation and fixpoint. (C) 2001 Academic Press.
引用
收藏
页码：15 / 42
页数：28
相关论文
共 33 条
  • [1] Abiteboul S., 1989, Proceedings. Fourth Annual Symposium on Logic in Computer Science (Cat. No.89CH2753-2), P71, DOI 10.1109/LICS.1989.39160
  • [2] Abiteboul S., 1991, Annals of Mathematics and Artificial Intelligence, V3, P151, DOI 10.1007/BF01530924
  • [3] ABITEBOUL S, 1990, PROCEEDINGS OF THE NINTH ACM SIGACT-SIGMOD-SIGART SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, P218, DOI 10.1145/298514.298575
  • [4] ABITEBOUL S, 1990, J COMPUT SYSTEM SCI, V41
  • [5] Abiteboul S., 1995, Foundations of databases, V1st
  • [6] REASONING ABOUT TERMINATION OF PURE PROLOG PROGRAMS
    APT, KR
    PEDRESCHI, D
    [J]. INFORMATION AND COMPUTATION, 1993, 106 (01) : 109 - 157
  • [7] STRUCTURE AND COMPLEXITY OF RELATIONAL QUERIES
    CHANDRA, A
    HAREL, D
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1982, 25 (01) : 99 - 128
  • [8] Chandra A., 1985, J LOGIC PROGRAM, V1, P1
  • [9] Chimenti D., 1990, IEEE Transactions on Knowledge and Data Engineering, V2, P76, DOI 10.1109/69.50907
  • [10] Codd E.F., 1972, COURANT COMPUTER SCI, P33
1234