On the Expressive Power of Datalog: Tools and a Case Study

We study here the language Datalog(≠), which is the query language obtained from Datalog by allowing equalities and inequalities in the bodies of the rules. We view Datalog(≠) as a fragment of an infinitary logic L ω and show that L ω can be characterized in terms of certain two-person pebble games....

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 1995-08, Vol.51 (1), p.110-134
Main Authors: Kolaitis, P.G., Vardi, M.Y.
Format: Article
Language:English
Subjects:
Applied sciences
Artificial intelligence
Computer science
control theory
systems
Exact sciences and technology
Information systems. Data bases
Memory organisation. Data processing
Problem solving, game playing
Programming languages
Software
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study here the language Datalog(≠), which is the query language obtained from Datalog by allowing equalities and inequalities in the bodies of the rules. We view Datalog(≠) as a fragment of an infinitary logic L ω and show that L ω can be characterized in terms of certain two-person pebble games. This characterization provides us with tools for investigating the expressive power of Datalog(≠). As a case study, we classify the expressibility of fixed subgraph homeomorphism queries on directed graphs. S. Fortune, J. Hopcroft, and J. Wyllie ( Theoret. Comput. Sci. 10 (1980), 111-121) classified the computational complexity of these queries by establishing two dichotomies, which are proper only if P ≠ NP. Without using any complexity-theoretic assumptions, we show here that the two dichotomies are indeed proper in terms of expressibility in Datalog(≠).
ISSN:0022-0000
1090-2724
DOI:10.1006/jcss.1995.1055