00336nas a2200109 4500008004100000245004900041210004900090100001900139700001800158700001700176856003300193 2003 eng d00aIncremental Recomputation in Local Languages0 aIncremental Recomputation in Local Languages1 aLibkin, Leonid1 aWong, Limsoon1 aDong, Guozhu uhttp://knoesis.org/node/148100318nas a2200109 4500008004100000245004000041210004000081100001700121700001800138700001900156856003300175 2000 eng d00aLocal Properties of Query Languages0 aLocal Properties of Query Languages1 aDong, Guozhu1 aWong, Limsoon1 aLibkin, Leonid uhttp://knoesis.org/node/154200370nas a2200121 4500008004100000245005200041210005200093100001900145700001600164700001700180700001800197856003300215 1999 eng d00aMaintaining Transitive Closure of Graphs in SQL0 aMaintaining Transitive Closure of Graphs in SQL1 aLibkin, Leonid1 aSu, Jianwen1 aDong, Guozhu1 aWong, Limsoon uhttp://knoesis.org/node/153400396nas a2200121 4500008004100000245006200041210006200103100002200165700001900187700001700206700001800223856003300241 1998 eng d00aRelational expressive power of constraint query languages0 aRelational expressive power of constraint query languages1 aBenedikt, Michael1 aLibkin, Leonid1 aDong, Guozhu1 aWong, Limsoon uhttp://knoesis.org/node/151700318nas a2200109 4500008004100000245004000041210004000081100001800121700001900139700001700158856003300175 1997 eng d00aLocal properties of query languages0 aLocal properties of query languages1 aWong, Limsoon1 aLibkin, Leonid1 aDong, Guozhu uhttp://knoesis.org/node/151101855nas a2200145 4500008004100000245006200041210006200103300000900165520142600174100002201600700001701622700001901639700001801658856003301676 1996 eng d00aRelational Expressive Power of Constraint Query Languages0 aRelational Expressive Power of Constraint Query Languages a5-163 aThe 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.
1 aBenedikt, Michael1 aDong, Guozhu1 aLibkin, Leonid1 aWong, Limsoon uhttp://knoesis.org/node/150800484nas a2200121 4500008004100000245010100041210006900142260006400211100001700275700001900292700001800311856003300329 1995 eng d00aOn impossibility of decremental recomputation of recursive queries in relational calculus and SQ0 aimpossibility of decremental recomputation of recursive queries bFifth International Database Programming Languages Workshop1 aDong, Guozhu1 aLibkin, Leonid1 aWong, Limsoon uhttp://knoesis.org/node/1817