Đang chuẩn bị liên kết để tải về tài liệu:
An Ehrenfeucht-Fra¨ ıss´ e Game Approach to Collapse Results in Database Theory ⋆

The WHERE conditions of this query specify various predicates that must be sat- isfied by the attributes of four tuples X, Y, Z, T in a sequence. The evaluation of the applicable predicates on these four variables, however, is not delayed un- til all four tuples are read; instead each predicate is evaluated as soon all its variables in the predicate are known—that is, as soon as the predicate becomes fully instantiated. For instance, the predicate Y:amount | An Ehrenfeucht-Fraisse Game Approach to Collapse Results in Database Theory Nicole Schweikardt Institut fur Informatik Humboldt-Universitat zu Berlin Unter den Linden 6 D-10099 Berlin Germany Email schweika@informatik.hu-berlin. de Abstract Pursuing an Ehrenfeucht-Fraisse game approach to collapse results in database theory we show that in principle every natural generic collapse result may be proved via a translation of winning strategies for the duplicator in an Ehrenfeucht-Fraisse game. Following this approach we can deal with certain infinite databases where previous highly involved methods fail. We prove the natural generic collapse for Z-embeddable databases over any linearly ordered context structure with arbitrary monadic predicates and for N-embeddable databases over the context structure R MonQ roups where roups is the collection of all subgroups of R that contain the set of integers and MonQ is the collection of all subsets of a particular infinite set Q of natural numbers. This in particular implies the collapse for arbitrary databases over N MonQ and for N-embeddable databases over R Z Q . I.e. first-order logic with can express the same order-generic queries as first-order logic with etc. Restricting the complexity of the formulas that may be used to formulate queries to Boolean combinations of purely existential first-order formulas we even obtain the collapse for N-embeddable databases over any linearly ordered context structure with arbitrary predicates. Finally we develop the notion of N-representable databases which is a natural generalisation of the notion of finitely representable databases. We show that natural generic collapse results for N-embeddable databases can be lifted to the larger class of N-representable databases. To obtain in particular the collapse result for N Monọ we explicitly construct a winning strategy for the duplicator in the presence of the built-in addition relation . This as a side product also leads to an .