Guozhu Dong

TCS Journal 2005 Journal Article

On the complexity of finding emerging patterns

• Lusheng Wang
• Hao Zhao
• Guozhu Dong
• Jianping Li

Emerging patterns have been studied as a useful type of pattern for the diagnosis and understanding of diseases based on the analysis of gene expression profiles. They are useful for capturing interactions among genes (or other biological entities), for capturing signature patterns for disease subtypes, and deriving potential disease treatment plans, etc. In this paper we study the complexity of finding emerging patterns (with the highest frequency). We first show that the problem is MAX SNP-hard. This implies that polynomial time approximation schemes do not exist for the problem unless P = NP. We then prove that for any constant δ < 1, the emerging pattern problem cannot be approximated within ratio 2 log δ n in polynomial time unless NP ⊆ DTIME [ 2 polylog n ], where n is the number of positions in a pattern.

TCS Journal 2004 Journal Article

On the decidability of the termination problem of active database systems

• James Bailey
• Guozhu Dong
• Kotagiri Ramamohanarao

Active database systems enhance the functionality of traditional databases through the use of active rules or ‘triggers’. One of the principal analysis questions for such systems is that of termination—is it possible for the rules to recursively activate one another indefinitely, given an initial triggering event. In this paper, we study the decidability of the termination problem, our aim being to delimit the boundary between the decidable and the undecidable. We present results for two broad types of variations, variations in rule syntax and variations in meta level features. Within each of these, we identify members close to the boundary of (un)decidability and also look at the effect of combining members of each type. The maximal decidable class we present is capable of expressing some useful kinds of application requirements, such as checking and repairing inclusion constraints. The work is also interesting from a theoretical point of view, since the context is similar to the while query language and the dynamics gives an interesting contrast to Datalog with negation.

I&C Journal 2003 Journal Article

Incremental recomputation in local languages

• Guozhu Dong
• Leonid Libkin
• Limsoon Wong

We study the problem of maintaining recursively defined views, such as the transitive closure of a relation, in traditional relational languages that do not have recursion mechanisms. The main results of this paper are negative ones: we show that a certain property of query languages implies impossibility of such incremental maintenance. The property we use is locality of queries, which is known to hold for relational calculus and various extensions, including those with grouping and aggregate constructs (essentially, plain SQL).

TCS Journal 2000 Journal Article

Local properties of query languages

• Guozhu Dong
• Leonid Libkin
• Limsoon Wong

In this paper we study the expressiveness of local queries. By locality we mean — informally — that in order to check if a tuple belongs to the result of a query, one only has to look at a certain predetermined portion of the input. Examples include all relational calculus queries. We start by proving a general result describing outputs of local queries. This result leads to many easy inexpressibility proofs for local queries. We then consider a closely related property, namely, the bounded degree property. It describes the outputs of local queries on structures that locally look “simple. ” Every query that is local is shown to have the bounded degree property. Since every relational calculus (first-order) query is local, the general results proved for local queries can be viewed as “off-the-shelf” strategies for proving inexpressibility results, which are often easier to apply than Ehrenfeucht–Fraı̈ssé games. We also show that some generalizations of the bounded degree property that were conjectured to hold, fail for relational calculus. We then prove that the language obtained from relational calculus by adding grouping and aggregates, which is essentially plain SQL, has the bounded degree property, thus answering a question that has been open for several years. Consequently, first-order queries with Härtig or Rescher quantifiers also have the bounded degree property. Finally, we apply our results to incremental maintenance of views, and show that SQL and relational calculus are incapable of maintaining the transitive closure view even in the presence of auxiliary relations of moderate degree.

ICML Conference 2000 Conference Paper

The Space of Jumping Emerging Patterns and Its Incremental Maintenance Algorithms

• Jinyan Li 0001
• Kotagiri Ramamohanarao
• Guozhu Dong

TCS Journal 1990 Journal Article

On the decomposition of datalog program mappings

• Guozhu Dong
• Seymour Ginsburg

In an earlier paper one of the authors initiated an investigation into the composition of datalog program mappings in order to analyze serially executed datalog queries. In this paper, the reverse process of composition, namely decomposition, and related topics are examined. A number of results are presented and shown to be useful for the optimization of datalog queries. In particular, a canonical decomposition into (usually) smaller programs is given, as well as the decomposition of strongly linear programs and bounded programs into single-rule programs. The class of prime or nondecomposable programs is then introduced and scrutinized. Major results include the primality of a class of single-rule programs called symmetric, and the existence of arbitrarily large primes. Finally established are the decomposition of bounded programs into single-rule primes, and a condition for the uniqueness of decomposition into primes.