Database theory column

ABSTRACT

The study of database logic programs, popularly known as Datalog programs, is one of the principal research themes in database theory today. Datalog is the simplest formalism available for describing rule-based programming and, thus, of interest to the larger computer science community. A key optimization problem is to estimate the depth of recursion of a database logic program, as a function of the size of its input database. Deciding bounded recursion for a given program, i.e., determining whether its depth of recursion is bounded by a constant independent of the input, turns out to be a basic and surprisingly subtle task. In the first database theory column, we review the progress made on understanding bounded recursion and list some of the outstanding open questions. For the readers, who are not familiar with the terminology, we include the relevant definitions.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

  H. Information Systems
  H.1 MODELS AND PRINCIPLES

General Terms:
Theory