Technical Reports

Answering Queries Determined by Views(.pdf format)(.ps format) by Foto Afrati
December, 2005.

Most Recent Publications

On Approximation Algorithms for Data Mining Applications(.pdf format) by Foto Afrati
     Chapter in Book, in volume "Approximation Algorithms in Combinatorial Optimization" of the series Lecture Notes in Computer Science (Springer Verlag) no 3484, 2006.
Eds: E. Bampis, K. Jansen, C. Kenyon.

Designing PTASs for MIN-SUM Scheduling Problems(.pdf format)
F. Afrati and I. Milis,
in Discrete Applied Mathematics, 2006

Scheduling trees with large communication delays on two identical processors,
F. Afrati, E. Bampis, L. Finta and I. Milis,
in Journal of Scheduling, 2005

Datalog programs and their persistency numbers (.pdf format)
       ACM Transactions on Computational Logic (TOCL), 2005
             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.
 

On the Expressiveness of First-Order Constraint Languages (.PS Format)
Proceedings of 2nd workshop on Constraint Databases, Springer Verlag Lecture Notes in CS, 1995
Foto Afrati, Theodore Andronikos, Theodore Kavalieros
Abstract. We investigate the expressive power of query languages for constraint databases. We examine languages over first order logic enhanced with the inequality constraint and linear constraints. We show that the query "one-line" is not expressible in FO+order (i.e. inequality constraint). In fact, the result is stronger in that we prove that it is not expressible in any higher order logic either. Furthermore, we show that the same query can be expressed in FO+linear by giving a non-trivial sentence that characterizes the class of databases consisting of exactly one line.

On the Expressiveness of Query Languages with Linear Constraints; Capturing Desirable Spatial Properties (.PS Format)
Proceedings of 3d workshop on Constraint Databases, Springer Verlag Lecture Notes in CS, 1997
Foto Afrati, Theodore Andronikos, Theodore Kavalieros
Abstract We explore the expressive power of the query language of first order logic with linear constraints. Natural queries are shown to be expressible in this language in a non-trivial fashion. We further investigate the ability of the language to capture certain properties that seem desirable in spatial databases. We show that, although these properties are captured in a certain extent, there are still cases where the language has counter-intuitive behavior. In this context, we show that FO+linear cannot distinguish between databases that carry similar spatial characteristics e.g. two different ellipses.

Revising Propositional Horn Clause Knowledge Bases (.PS Format)
ERCIM-11/94-R034, November '94
Foto Afrati, Theodoros G. Kavalieros, Dimitri Theodoratos.
Abstract. We investigate the problem of revising a propositional knowledge base, viewed as a set of Horn clauses. We present algorithms that revise the knowledge base with a Horn clause according to the Set of Theories [Fagin and Ullman and Vardi] and the When In Doubt Through It Out approaches [Ginsberg]. Under the first approach the problem has shown to be intractable even when further restrictions are applied. We show that the algorithms run in polynomial time in the case where the number of "relevant" negative clauses and rules (definite clauses having at least one negative literal) in the knowledge base is bounded. Intermediate results about resolution deduction of literals from a set of Horn clauses are obtained, which are of interest in their own right.
On the Relationship between Chain Queries and Linear Datalog Programs(.PS Format)
Proc. DDLP'97, 5th International Workshop on Deductive Databases and Logic Programming, U. Geske, C. Ruiz, D. Seipel, eds., GMD-Studien Nr 317, Sankt Augustin, pages 49-58 (1997)
Foto Afrati, Francesca Toni .
Abstract. We study the linearisability of chain queries and identify a new class of linearisable chain queries, referred to as pseudo-regular. We prove linearisability constructively, by generating, for any given pseudo-regular chain query, the Datalog program corresponding to it.
On Transformations into Linear Database Logic Programs (.PS Format)
In D. Bjorner, M. Broy and I. V. Pottosin (Eds.) Perspectives of System Informatics, 2nd International Andrei Ershov Memorial Conference Akademgorodok, Novosibirsk, Russia, June 1996. Lecture Notes in Computer Science (LNCS) 1181, pages 433-444, Springer-Verlag
Foto Afrati, Manolis Gergatsoulis, Maria Katzouraki
Abstract. We consider the problem of transformations of logic programs without function symbols database logic programs in to a special sub class, namely linear logic programs. Linear logic programs are defined to be the programs whose rules have at most one intentional atom in their bodies. a) We investigate linearizability of several syntactically defined sub classes of programs and present both positive and negative results (i.e. demonstrate programs that cannot be transformed in to a linear program by any transformation technique), and b) We develop an algorithm which transforms any program in a specific subclass namely the piecewise logic programs in to a linear logic program.
Two Processor Scheduling with Large Communication Delays (.PS Format)
F. Afrati, E. Bampis, L. Finta, I. Milis
Abstract. The problem of scheduling partially ordered tasks on two identical processors is considered. It is assumed that tasks have unit execution time, and the arcs of the task graph are associated with integral identical communication delays greater or equal to two time units. We prove that the problem of minimizing the schedule length is NP-hard even for binary trees and it becomes polynomial for complete binary trees.
Inheritance in Object Oriented Datalog (.PS Format)
NTUA Technical Report
Foto Afrati, Isambo Karali, Theodoros Mitakos
Abstract. Modularity is a special form of logic programming composition that allows incremental development and code reusability. It is natural to be considered as the formal framework to supply semantics to languages of logic programs (such as datalog) when the underlying data model is object oriented. We show here that a) for varius interesting forms of inheritance, clean and natural semantics can indeed be defined based on the modular logic programming franework that avoids the undesired complication of datalog and b) that for cetrain forms of inheritance, this semantics is equivalent to the semantics of datalog which is provided by transformation to datalog.
Datalog, Units and Information Hiding (.PS Format)
Languages and Models with Objects '97, Roscoff France.
Foto Afrati, Isambo Karali, Theodoros Mitakos
Abstract. In this paper, we propose the introduction of structured units in datalog. This allows modularity and information hiding. Units are divided into a public and private part. This structure calls for new composition operators which are defined here. These operators express various forms of inheritance including the common ones in the object oriented framework.
Arity Hierarchies for Fixed-Point Logics (.PS Format)
Panhellenic Symposium on Logic, Cyprus, 1997
Foto Afrati
Abstract. Fixed-point logic is the logic of inductively definable relations over structures of a specific signature. The inductive definitions are given via expressions of the first order logic or fragments of it. A natural question is whether we can increase the expressive power of the logic by allowing larger arities of the inductively defined relations. A number of results appeared lately that essentially solved that problem for the most important variants of fixed-point logic, by showing that the arity hierarchy formed is strict even in the case when the inductive definitions are over structures containing a single binary relation (i.e. graphs). We review these results and comment on the techniques that were used to prove them. In fact, for the query language Datalog, a strict hierarchy is also shown with respect to the persistency-arity of the inductively defined relations.
The expressiveness of Datalog circuits (DAC) (.PS Format)
In proceeedings of MFCS 1997
Foto Afrati, Irene Guessarian , Michel de Rougemont
Abstract. We define a new logic query language, called DAC, which is an extension of Datalog. We exhibit queriew which are not Datalog expressible but are DAC expressible. We also prove non-expressiveness results for DAC and we infer various strict hierarchies obtained by allowing more rapidly growing functions on the bound parameters.
Answering Queries Using Materialized Views with Disjunctions (.PS Format)
In proceedings of ICDT99, Jerousalem 1999
Foto Afrati, Manolis Gergatsoulis, and Theodoros Kavalieros

Abstract. We consider the problem of answering datalog queries using materialize d 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 P is there a datalog program Pv which uses only views as EDB predicates and (i) produces a subset of the answers that P produces and (ii) any other program Pv' over the views with property (i) is contained in Pv? In this paper we investigate the problem in the case of disjunctive view definitions.

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 r_uwhich uses only views as EDB predicates and (i) produces a subset of the answers that rproduces and (ii) any other programr_u^’over the views with property (i) is contained inr_u? 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