English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of conjunctive query evaluation relative to a class ofqueries; this problem is formulated here as the relational homomorphism problemrelative to a class of structures A, wherein each instance must be a pair ofstructures such that the first structure is an element of A. We present acomprehensive complexity classification of these problems, which strongly linksgraph-theoretic properties of A to the complexity of the correspondinghomomorphism problem. In particular, we define a binary relation on graphclasses, which is a preorder, and completely describe the resulting hierarchygiven by this relation. This relation is defined in terms of a notion which wecall graph deconstruction and which is a variant of the well-known notion oftree decomposition. We then use this hierarchy of graph classes to infer acomplexity hierarchy of homomorphism problems which is comprehensive up to acomputationally very weak notion of reduction, namely, a parameterized versionof quantifier-free first-order reduction. In doing so, we obtain asignificantly refined complexity classification of homomorphism problems, aswell as a unifying, modular, and conceptually clean treatment of existingcomplexity classifications. We then present and develop the theory ofEhrenfeucht-Fraisse-style pebble games which solve the homomorphism problemswhere the cores of the structures in A have bounded tree depth. Finally, we useour framework to classify the complexity of model checking existentialsentences having bounded quantifier rank.

One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries