Affordable Access

Publisher Website

On the Power of Rule-Based Query Languages for Nested Data Models

Authors
Journal
The Journal of Logic Programming
0743-1066
Publisher
Elsevier
Volume
21
Issue
3
Identifiers
DOI: 10.1016/s0743-1066(14)80009-5
Disciplines
  • Computer Science
  • Logic
  • Mathematics

Abstract

A number of algebras, calculi, and rule-based query languages have been developed in recent years to meet the challenges of modern applications. Of these, rule-based languages are of interest to researchers in the areas of both databases and logic programming. This paper analyzes the “power” of a certain class of rule-based languages, called value-based languages. By “power” we mean data complexity. The main result of the paper is the establishment of both the upper and lower bounds of the data complexity of the finite versions of three (value-based) logic programming languages: ELPS, COL, and LDL. An interesting consequence of our analysis is a new technique to extend a given total order on a set to its power set using positive rules only (including for built-in predicates).

There are no comments yet on this publication. Be the first to share your thoughts.