Cover Image

Resilience for Regular Path Queries: Towards a Complexity Classification

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Amarilli, Antoine, Gatterbauer, Wolfgang, Makhija, Neha, Monet, Mikaël, Muñoz, Martín
Format:	Preprint
Published:	2024
Subjects:	Databases
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries
by: Makhija, Neha, et al.
Published: (2021)

Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation
by: Makhija, Neha, et al.
Published: (2024)

Ranked Enumeration for MSO on Trees via Knowledge Compilation
by: Amarilli, Antoine, et al.
Published: (2023)

A Principled Solution to the Disjunction Problem of Diagrammatic Query Representations
by: Gatterbauer, Wolfgang
Published: (2024)

A Comprehensive Tutorial on over 100 Years of Diagrammatic Representations of Logical Statements and Relational Queries
by: Gatterbauer, Wolfgang
Published: (2024)

Discovering Dichotomies for Problems in Database Theory
by: Makhija, Neha
Published: (2023)

Ranked Enumeration for Database Queries
by: Tziavelis, Nikolaos, et al.
Published: (2024)

Database Research needs an Abstract Relational Query Language
by: Gatterbauer, Wolfgang, et al.
Published: (2025)

On The Reasonable Effectiveness of Relational Diagrams: Explaining Relational Query Patterns and the Pattern Expressiveness of Relational Languages
by: Gatterbauer, Wolfgang, et al.
Published: (2024)

Tractable Circuits in Database Theory
by: Amarilli, Antoine, et al.
Published: (2024)

A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automata
by: Amarilli, Antoine, et al.
Published: (2024)

Approximating Queries on Probabilistic Graphs
by: Amarilli, Antoine, et al.
Published: (2023)

On the Complexity of Language Membership for Probabilistic Words
by: Amarilli, Antoine, et al.
Published: (2025)

The Non-Cancelling Intersections Conjecture
by: Amarilli, Antoine, et al.
Published: (2024)

The S-Hamiltonian Cycle Problem
by: Amarilli, Antoine, et al.
Published: (2026)

Towards Agentic Schema Refinement
by: Rissaki, Agapi, et al.
Published: (2024)

Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases
by: Karmakar, Pratik, et al.
Published: (2024)

Locality Testing for NFAs is PSPACE-complete
by: Amarilli, Antoine, et al.
Published: (2025)

Confluence of the Node-Domination and Edge-Domination Hypergraph Rewrite Rules
by: Amarilli, Antoine, et al.
Published: (2025)

The Shapley Value in Database Management
by: Bertossi, Leopoldo, et al.
Published: (2024)

Minimizing Conjunctive Regular Path Queries
by: Figueira, Diego, et al.
Published: (2025)

Output-Sensitive Evaluation of Regular Path Queries
by: Khamis, Mahmoud Abo, et al.
Published: (2024)

Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries
by: Khamis, Mahmoud Abo, et al.
Published: (2025)

Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions
by: Figueira, Diego, et al.
Published: (2024)

Fine-Grained Complexity of Regular Path Queries
by: Casel, Katrin, et al.
Published: (2021)

Database Views as Explanations for Relational Deep Learning
by: Rissaki, Agapi, et al.
Published: (2025)

Accelerating Regular Path Queries over Graph Database with Processing-in-Memory
by: Ma, Ruoyan, et al.
Published: (2024)

The Importance of Parameters in Ranking Functions
by: Standke, Christoph, et al.
Published: (2026)

Evaluating Regular Path Queries on Compressed Adjacency Matrices
by: Arroyuelo, Diego, et al.
Published: (2023)

cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries
by: Park, Sungwoo, et al.
Published: (2026)

Regular Path Query Evaluation Sharing a Reduced Transitive Closure Based on Graph Reduction
by: Na, Inju, et al.
Published: (2021)

Skyline Operators for Document Spanners
by: Amarilli, Antoine, et al.
Published: (2023)

Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries
by: Khamis, Mahmoud Abo, et al.
Published: (2025)

Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries
by: Figueira, Diego, et al.
Published: (2022)

Compact Answers to Temporal Path Queries
by: Adnan, Muhammad, et al.
Published: (2025)

HITSnDIFFs: From Truth Discovery to Ability Discovery by Recovering Matrices with the Consecutive Ones Property
by: Chen, Zixuan, et al.
Published: (2023)

Answering Constraint Path Queries over Graphs
by: Li, Heyang, et al.
Published: (2025)

Survey of Results on the ModPath and ModCycle Problems
by: Amarilli, Antoine
Published: (2024)

Complexity of Evaluating GQL Queries
by: Figueira, Diego, et al.
Published: (2024)

Path-based Algebraic Foundations of Graph Query Languages
by: Angles, Renzo, et al.
Published: (2024)