27 citations · 106 across the 17 of their papers we have counts for
18 papers
Semi-interval Comparison Constraints in Query Containment and Their Impact on Certain Answer Computation
Foto N. Afrati, Matthew Damigos
We consider conjunctive queries with arithmetic comparisons (CQAC) and investigate the computational complexity of the problem: Given two CQAC queries, and , is contai…
Safe Subjoins in Acyclic Joins
Foto N. Afrati
It is expensive to compute joins, often due to large intermediate relations. For acyclic joins, monotone join expressions are guaranteed to produce intermediate relations not large…
Querying collections of tree-structured records in the presence of within-record referential constraints
Foto N. Afrati, Matthew Damigos
In this paper, we consider a tree-structured data model used in many commercial databases like Dremel, F1, JSON stores. We define identity and referential constraints within each t…
On the complexity of query containment and computing certain answers in the presence of ACs
Foto N. Afrati, Matthew Damigos
We often add arithmetic to extend the expressiveness of query languages and study the complexity of problems such as testing query containment and finding certain answers in the fr…
SharesSkew: An Algorithm to Handle Skew for Joins in MapReduce
Foto Afrati, Nikos Stasinopoulos, Jeffrey D. Ullman +1
In this paper, we investigate the problem of computing a multiway join in one round of MapReduce when the data may be skewed. We optimize on communication cost, i.e., the amount of…
Computing Marginals Using MapReduce
Foto Afrati, Shantanu Sharma, Jeffrey D. Ullman +1
We consider the problem of computing the data-cube marginals of a fixed order (i.e., all marginals that aggregate over dimensions), using a single round of MapReduce. The f…
Meta-MapReduce: A Technique for Reducing Communication in MapReduce Computations
Foto Afrati, Shlomi Dolev, Shantanu Sharma +1
MapReduce has proven to be one of the most useful paradigms in the revolution of distributed computing, where cloud services and cluster computing become the standard venue for com…
Assignment Problems of Different-Sized Inputs in MapReduce
Foto Afrati, Shlomi Dolev, Ephraim Korach +2
A MapReduce algorithm can be described by a mapping schema, which assigns inputs to a set of reducers, such that for each required output there exists a reducer that receives all t…
Handling Skew in Multiway Joins in Parallel Processing
Foto N. Afrati, Jeffrey D. Ullman, Angelos Vasilakopoulos
Handling skew is one of the major challenges in query processing. In distributed computational environments such as MapReduce, uneven distribution of the data to the servers is not…
Consistent Answers of Conjunctive Queries on Graphs
Foto N. Afrati, Phokion G. Kolaitis, Angelos Vasilakopoulos
During the past decade, there has been an extensive investigation of the computational complexity of the consistent answers of Boolean conjunctive queries under primary key constra…
Assignment of Different-Sized Inputs in MapReduce
Foto Afrati, Shlomi Dolev, Ephraim Korach +2
A MapReduce algorithm can be described by a mapping schema, which assigns inputs to a set of reducers, such that for each required output there exists a reducer that receives all t…
GYM: A Multiround Join Algorithm In MapReduce
Foto Afrati, Manas Joglekar, Christopher Ré +2
Multiround algorithms are now commonly used in distributed data processing systems, yet the extent to which algorithms can benefit from running more rounds is not well understood.…
Efficient Lineage for SUM Aggregate Queries
Foto N. Afrati, Dimitris Fotakis, Angelos Vasilakopoulos
AI systems typically make decisions and find patterns in data based on the computation of aggregate and specifically sum functions, expressed as queries, on data's attributes. This…
Enumerating Subgraph Instances Using Map-Reduce
Foto N. Afrati, Dimitris Fotakis, Jeffrey D. Ullman
The theme of this paper is how to find all instances of a given "sample" graph in a larger "data graph," using a single round of map-reduce. For the simplest sample graph, the tria…
Upper and Lower Bounds on the Cost of a Map-Reduce Computation
Foto N. Afrati, Anish Das Sarma, Semih Salihoglu +1
In this paper we study the tradeoff between parallelism and communication cost in a map-reduce computation. For any problem that is not "embarrassingly parallel," the finer we part…
Vision Paper: Towards an Understanding of the Limits of Map-Reduce Computation
Foto N. Afrati, Anish Das Sarma, Semih Salihoglu +1
A significant amount of recent research work has addressed the problem of solving various data management problems in the cloud. The major algorithmic challenges in map-reduce comp…
A New Framework for Join Product Skew
Foto Afrati, Victor Kyritsis, Paraskevas V. Lekeas +1
Different types of data skew can result in load imbalance in the context of parallel joins under the shared nothing architecture. We study one important type of skew, join product…
On relating CTL to Datalog
Foto Afrati, Theodore Andronikos, Vassia Pavlaki +2
CTL is the dominant temporal specification language in practice mainly due to the fact that it admits model checking in linear time. Logic programming and the database query langua…