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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Evaluating conjunctive queries and solving constraint satisfaction problemsare fundamental problems in database theory and artificial intelligence,respectively. These problems are NP-hard, so that several research efforts havebeen made in the literature for identifying tractable classes, known as islandsof tractability, as well as for devising clever heuristics for solvingefficiently real-world instances. Many heuristic approaches are based onenforcing on the given instance a property called local consistency, where (indatabase terms) each tuple in every query atom matches at least one tuple inevery other query atom. Interestingly, it turns out that, for many well-knownclasses of queries, such as for the acyclic queries, enforcing localconsistency is even sufficient to solve the given instance correctly. However,the precise power of such a procedure was unclear, but for some very restrictedcases. The paper provides full answers to the long-standing questions about theprecise power of algorithms based on enforcing local consistency. The classesof instances where enforcing local consistency turns out to be a correctquery-answering procedure are however not efficiently recognizable. In fact,the paper finally focuses on certain subclasses defined in terms of the novelnotion of greedy tree projections. These latter classes are shown to beefficiently recognizable and strictly larger than most islands of tractabilityknown so far, both in the general case of tree projections and for specificstructural decomposition methods.

Tree Projections and Structural Decomposition Methods: The Power of Local Consistency and Larger Islands of Tractability