TY - JOUR
T1 - Incremental Recomputation in Local Languages
Y1 - 2003
A1 - Leonid Libkin
A1 - Limsoon Wong
A1 - Guozhu Dong
ER -
TY - JOUR
T1 - Local Properties of Query Languages
Y1 - 2000
A1 - Guozhu Dong
A1 - Limsoon Wong
A1 - Leonid Libkin
ER -
TY - JOUR
T1 - Maintaining Transitive Closure of Graphs in SQL
Y1 - 1999
A1 - Leonid Libkin
A1 - Jianwen Su
A1 - Guozhu Dong
A1 - Limsoon Wong
ER -
TY - JOUR
T1 - Relational expressive power of constraint query languages
Y1 - 1998
A1 - Michael Benedikt
A1 - Leonid Libkin
A1 - Guozhu Dong
A1 - Limsoon Wong
ER -
TY - JOUR
T1 - Local properties of query languages
Y1 - 1997
A1 - Limsoon Wong
A1 - Leonid Libkin
A1 - Guozhu Dong
ER -
TY - JOUR
T1 - Relational Expressive Power of Constraint Query Languages
JF - Journal of the ACM
Y1 - 1996
A1 - Michael Benedikt
A1 - Guozhu Dong
A1 - Leonid Libkin
A1 - Limsoon Wong
AB - The expressive power of first-order query languages with several classes of equality and inequality constraints is studied in this paper. We settle the conjecture that recursive queries such as parity test and transitive closure cannot be expressed in the relational calculus augmented with polynomial inequality constraints over the reals. Furthermore, noting that relational queries exhibit several forms of genericity, we establish a number of collapse results of the following form: The class of generic boolean queries expressible in the relational calculus augmented with a given class of constraints coincides with the class of queries expressible in the relational calculus (with or without an order relation). We prove such results for both the natural and active-domain semantics. As a consequence, the relational calculus augmented with polynomial inequalities expresses the same classes of generic boolean queries under both the natural and active-domain semantics. In the course of proving these results for the active-domain semantics, we establish Ramsey-type theorems saying that any query involving certain kinds of constraints coincides with a constraint free query on databases whose elements come from a certain innite subset of the domain. To prove the collapse results for the natural semantics, we make use of techniques from nonstandard analysis and from the model theory of ordered structures.
ER -
TY - CONF
T1 - On impossibility of decremental recomputation of recursive queries in relational calculus and SQ
Y1 - 1995
A1 - Guozhu Dong
A1 - Leonid Libkin
A1 - Limsoon Wong
PB - Fifth International Database Programming Languages Workshop
ER -