Recent Publications

(See also  DBLP list and Citations)
Most Recent Publications.
On Approximation Algorithms for Data Mining Applications(.pdf format)
by Foto Afrati
     Chapter in Book, to appear in the volume "Approximation Algorithms in Combinatorial Optimization" of the series Lecture Notes in Computer Science (Springer Verlag) no 3484, Eds: E. Bampis, K. Jansen, C. Kenyon, to appear
        
 
      to appear in Journal of Combinatorial Optimization.
          F. Afrati, T. Aslanidis, E. Bampis and I. Milis
Scheduling trees with large communication delays on two identical processors,
      accepted in Journal of Scheduling
         F. Afrati, E. Bampis, L. Finta and I. Milis,
Designing PTASs for MIN-SUM Scheduling Problems(.pdf format)
     Journal of Discrete Applied Mathematics, to appear
         Foto Afrati, Ioannis Milis
         A Survey
Datalog programs and their persistency numbers (.pdf format)
       ACM Transactions on Computational Logic (TOCL) to appear
             Foto Afrati, Stavros Cosmadakis, Eugenie Foustoucos
             Abstract. The relation between Datalog programs and homomorphism problems and,
             between Datalog programs and bounded treewidth structures has been recognized
             for some time and given much attention recently. Additionally,
             the essential role of persistent variables (of program expansions)
             in solving several relevant problems has also started to be
             observed. It turns out that to understand the contribution of these persistent
             variables to the difficulty of some expressibility problems, we need to
             understand the interrelationship among different notions of persistency
             numbers some of which we introduce and/or formalize in the present work.
              This paper is the first foundational study of the various persistency numbers and their
             interrelationships. To prove the relations among these pesistency
             numbers we had ot develop some non trivial technical tools that pormise to help in proving other
             interesting rsults too. More precisely, we define the
             adorned dependency graph of a program, a useful tool for visualizing sets
             of persistent variables, and we define automata that recognize persistent sets in expansions.
                We start by elaborating on finer definitions of wxpansions and queries, which
             capture aspects of homomorphism problems on bounded treewidth structurs. The
             main results of this paper are: a) a program transformation technique, based
             on automata-theoretic tools, which manipulates persistent variables (leading,
             in certain cases, to programs of fewer persistent variales), b) a
             categorization of the different roles of persistent variables; this is done by
             defining four notions of persistency numbers which capture the propagation of
             persistent variables from a syntactical level to a semantical one, c)
             decidability results concerning the syntactical notions of persistency numbers
             that we have defined and d) exhibition of new classes of programs for which boundednesss is undecidable.
 

More Publications in Chronological Order.
 

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates (.PS Format)


In proceedings of FOCS99, 1999

Foto Afrati, Evripidis bampis, Chandra Chekuri , David Karger, Claire Kenyon, Sanjeen Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella,Cliff Stein  and Maxim Sviridenko

 Abstract. We consider the problem of schedulingn jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation schemes for several variants of this problem. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our schemes are efficient: for all variants the running time for a (1+e) approximation is of the form¦(1/e, m) poly(n).

Answering Queries Using Materialized Views with Disjunctions (.PS Format)


In proceedings of ICDT99, 1999

Foto Afrati, Manolis Gergatsoulis, and Theodoros Kavalieros.

Abstract: We consider the problem of answering datalog queries using materialized views. More specifically, queries are rewritten to refer to views instead of the base relations over which the queries were originally written. Much work has been done on program rewriting that produces an equivalent query. In the context of information integration, though, the importance of using views to infer as many answers as possible has been pointed out. Formally, the problem is: Given a datalog program r is there a datalog program ruwhich uses only views as EDB predicates and (i) produces a subset of the answers that rproduces and (ii) any other programru˘over the views with property (i) is contained inru? In this paper we investigate the problem in the case of disjunctive view definitions.

Datalog Trees and Their Automata (.PS Format)
In proceedings of the 2nd Pan Hellenic Symposium on Logic, Delphi 1999
Foto Afrati, Eugenie Foustoucos, and Theodore Andronikos.
 
Definability and Compression  (.PS Format)


In proceedings of LICS, 2000

Foto Afrati, Hans Lei? and Michel de Rougemont

 Abstract. A compression algorithm takes a finite structure of a class K as input and produces a finite structure of a different class K' as output. Given a property P on a class K defined in a logic L, we study the definability of property P on the class K'. We consider two compression schemas on unary ordered structures (words), compression by run-length encoding and the classical Lemel-Ziv. First-order properties of strings are first-order on run-length compressed strings, but this fails for images, i.e. 2-dimentional strings. We present simple first-order properties of strings which are not first-order definable on strings compressed with the Lempel-Ziv compression schema. We show that all properties of strings that are first-order definable on strings are definable on Lempel-Ziv compressed strings in FO(TC), the extension of first-order logic with the transitive closure operator. We define a subclass F of the first-order properties of strings such that if L is defined by a property in F, it is also first-order definable on Lempel-Ziv compressed strings. Monadic second-order properties of strings are dyadic second order definable on lempel-Zev compressed strings.

Generating Efficient Plans for Queries Using Views (.PS Format)
Foto Afrati, Chen Li, and Jeff Ullman
In Proceedings of the 30th ACM SIGMOD Conference, Santa Barbara, CA, May, 2001.
 Abstract. We study the problem of generating efficient, equivalent rewritings using views to compute the answer to a query. We take the closed­world assumption, in which views are materialized from base relations, rather than views describing sources in terms of abstract predicates, as is common when the open­world assumption is used. In the closed­world model, there can be an infinite number of different rewritings that compute the same answer, yet have quite different performance. Query optimizers take a logical plan (a rewriting of the query) as an input, and generate efficient physical plans to compute the answer. Thus our goal is to generate a small subset of the possible logical plans without missing an optimal physical plan. We first consider a cost model that counts the number of subgoals in a physical plan, and show a search space that is guaranteed to include an optimal rewriting, if the query has a rewriting in terms of the views. We also develop an
efficient algorithm for finding rewritings with the minimum number of subgoals. We then consider a cost model that counts the sizes of intermediate relations of a physical plan, without dropping any attributes, and give a search space for finding optimal rewritings. Our final cost model allows attributes to be dropped in  intermediate relations. We show that, by careful variable renaming, it is possible to do better than the standard ``supplementary relation'' approach, by dropping attributes that the latter approach would retain. Experiments show that our algorithm of generating optimal rewritings has good efficiency and scalability.
Answering Queries Using Views with Arithmetic
  Comparisons. Foto Afrati, Chen Li, and Prasenjit Mitra. To appear in ACM Symposium on Principles of Database Systems (PODS), June 3-6, 2002 Madison, Wisconsin.(.PS Format)
 
Scheduling to minimize the average completion time of dedicated tasks(.PS Format)
Foto Afrati, Evripidis Bampis, Aleksei V. Fishkin, Klaus Jansen, and Claire Kenyon.
In Proceedings of the FSTTCS 2000, K. Sanjiv, P. Sanjiva (Eds), New Delhi, LNCS 1974, 2000, 454-464.
Designing PTASs for MIN-SUM Scheduling Problems.
(.PS Format)
Foto Afrati, Ioannis Milis
In proceedings of WEA 2001