6 papers
Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations
Mahmoud Abo-Khamis, Eden Chmielewski, Andrei Draghici +2
We study the classical incremental view maintenance problem: Given a query and a database, maintain the query output under single-tuple updates (inserts or deletes) to the database…
Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries
Mahmoud Abo Khamis, Alexandru-Mihai Hurjui, Ahmet Kara +2
We present an output-sensitive algorithm for evaluating an acyclic Conjunctive Regular Path Query (CRPQ). Its complexity is written in terms of the input size, the output size, and…
Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries
Mahmoud Abo Khamis, Alexandru-Mihai Hurjui, Ahmet Kara +3
Conjunctive Regular Path Queries, or CRPQs for short, are an essential construct in graph query languages. In this paper, we propose the first output-sensitive algorithm for evalua…
Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms
Omer Abramovich, Daniel Deutch, Nave Frost +2
In this paper, we introduce a novel approach to computing the contribution of input tuples to the result of the query, quantified by the Banzhaf and Shapley values. In contrast to…
Output-Sensitive Evaluation of Regular Path Queries
Mahmoud Abo Khamis, Ahmet Kara, Dan Olteanu +1
We study the classical evaluation problem for regular path queries: Given an edge-labeled graph and a regular path query, compute the set of pairs of vertices that are connected by…
Tractable Conjunctive Queries over Static and Dynamic Relations
Ahmet Kara, Zheng Luo, Milos Nikolic +2
We investigate the evaluation of conjunctive queries over static and dynamic relations. While static relations are given as input and do not change, dynamic relations are subject t…