PROGRAMMING WITH NONDETERMINISM IN DEDUCTIVE DATABASES

While non-determinism has long been established as a key concept in lo gic programming, its importance in the context of deductive databases was recognized only recently. This paper provides an overview of recen t results on this topic with the aim of providing an introduction to t he theory and practice of non-determinism in deductive databases. In p articular we (i) recall the main results linking non-deterministic con structs in database languages to the theory of data complexity and the expressibility hierarchy of query languages; (ii) provide a reasoned introduction to effective programming with non-deterministic construct s; (iii) compare the usage of non-deterministic constructs in language s such as LDL++ to that of traditional logic programming languages; (i v) discuss the link between the semantics of logic programs with non-d eterministic constructs and the stable-model semantics of logic progra ms with negation.