Evaluating Datalog via tree automata and cycluits

DOI10.1007/S00224-018-9901-2zbMATH Open1430.68078arXiv1808.04663OpenAlexW3104480332WikidataQ128626663 ScholiaQ128626663MaRDI QIDQ2322722FDOQ2322722

Authors: Antoine Amarilli, Pierre Bourhis, Mikaël Monet, Pierre Senellart 

Publication date: 5 September 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We show that clique-frontier-guarded Datalog with stratified negation (CFG-Datalog) enjoys bilinear-time evaluation on structures of bounded treewidth for programs of bounded rule size. Such programs capture in particular conjunctive queries with simplicial decompositions of bounded width, guarded negation fragment queries of bounded CQ-rank, or two-way regular path queries. Our result is shown by translating to alternating two-way automata, whose semantics is defined via cyclic provenance circuits (cycluits) that can be tractably evaluated.

Full work available at URL: https://arxiv.org/abs/1808.04663

Recommendations

• Combined tractability of query evaluation via tree automata and cycluits
• Monadic Datalog over finite structures of bounded treewidth
• When is the evaluation of conjunctive queries tractable?
• scientific article; zbMATH DE number 2080462
• Query evaluation via tree-decompositions

zbMATH Keywords

provenanceautomatadatabase theorycircuitsDatalog

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Database theory (68P15) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Datalog LITE
• Incomplete Information in Relational Databases
• Title not available (Why is that?)
• Depth-First Search and Linear Graph Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Decomposition by clique separators
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A lattice-theoretical fixpoint theorem and its applications
• Finding and counting given length cycles
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The implication problem for functional and inclusion dependencies
• Query evaluation via tree-decompositions
• The Implication Problem for Functional and Inclusion Dependencies is Undecidable
• Graph minors. II. Algorithmic aspects of tree-width
• Cyclic Boolean circuits
• Hypertree decompositions and tractable queries
• Optimal decomposition by clique separators
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Graph minors. III. Planar tree-width
• Treewidth computations. I: Upper bounds
• Finding Regular Simple Paths in Graph Databases
• Degrees of acyclicity for hypergraphs and relational database schemes
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• State-complexity of finite-state devices, state compressibility and incompressibility
• An introduction to clique minimal separator decomposition
• Monadic Datalog over finite structures of bounded treewidth
• Programming Techniques: Regular expression search algorithm
• Analysis of cyclic combinational circuits
• Simplicial decompositions of graphs: A survey of applications
• Rewriting Guarded Negation Queries
• An indexing framework for queries on probabilistic graphs
• Combined tractability of query evaluation via tree automata and cycluits
• Provenance circuits for trees and treelike instances
• The semijoin algebra and the guarded fragment
• Two-Way Tree Automata Solving Pushdown Games
• A Step Up in Expressiveness of Decidable Fixpoint Logics
• Monadic Datalog Containment
• Games and model checking for guarded logics
• Guarded fixed point logics and the monadic theory of countable trees.
• Guarded negation
• Title not available (Why is that?)
• Effective interpolation and preservation in guarded logics
• Monadic Datalog, tree validity, and limited access containment

Cited In (4)

• Title not available (Why is that?)
• Monadic Datalog over finite structures of bounded treewidth
• Memory-saving evaluation plans for Datalog
• Combined tractability of query evaluation via tree automata and cycluits

Uses Software

• ComputeTW
• Datalog LITE

This page was built for publication: Evaluating Datalog via tree automata and cycluits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2322722)