The authors consider relational databases organized over an ordered domain with some additional relations - a typical example is the ordered domain of rational numbers together with the operation of addition. In the f...The authors consider relational databases organized over an ordered domain with some additional relations - a typical example is the ordered domain of rational numbers together with the operation of addition. In the focus of our study are the FO （first-order） queries that are invariant under order-preserving permutations-such queries are called order-generic. It was discovered that for some domains order-generic FO queries fail to express more than pure order queries. The collapse result theorem was proved for locally genetic queries over a linearly ordered domain with the Pseudo finite Homogeneity Property （or / and the Isolation Property） by Belegradek et al.. Here the authors consider a circularly ordered domain and prove the collapse result theorem over a quasi circularly minimal domain.展开更多
We extend the constraint data model to allow complex objects and study the expressive power of various query languages over this sort of constraint databases.The tools we use come in the form of collapse results which...We extend the constraint data model to allow complex objects and study the expressive power of various query languages over this sort of constraint databases.The tools we use come in the form of collapse results which are well established in the context of first-order logic.We show that the natural-active collapse with a condition and the activegeneric collapse carry over to the second-order logic for structures with o-minimality property and any signature in the complex value relations.The expressiveness results for more powerful logics including monadic second-order logic,monadic second-order logic with fix-point operators,and fragments of second-order logic are investigated in the paper.We discuss the data complexity for second-order logics over constraint databases.The main results are that the complexity upper bounds for three theories,MSO+(LIN),MSO+(POLY),and Inflationary DATALOGact^cv(SC,M)without powerset operator are∪iΣi^NC1,NCH=∪iΣi^NC,and AC^0/poly,respectively.We also consider the problem of query closure property in the context of embedded finite models and constraint databases with complex objects and the issue of how to determine safe constraint queries.展开更多
文摘The authors consider relational databases organized over an ordered domain with some additional relations - a typical example is the ordered domain of rational numbers together with the operation of addition. In the focus of our study are the FO （first-order） queries that are invariant under order-preserving permutations-such queries are called order-generic. It was discovered that for some domains order-generic FO queries fail to express more than pure order queries. The collapse result theorem was proved for locally genetic queries over a linearly ordered domain with the Pseudo finite Homogeneity Property （or / and the Isolation Property） by Belegradek et al.. Here the authors consider a circularly ordered domain and prove the collapse result theorem over a quasi circularly minimal domain.
文摘We extend the constraint data model to allow complex objects and study the expressive power of various query languages over this sort of constraint databases.The tools we use come in the form of collapse results which are well established in the context of first-order logic.We show that the natural-active collapse with a condition and the activegeneric collapse carry over to the second-order logic for structures with o-minimality property and any signature in the complex value relations.The expressiveness results for more powerful logics including monadic second-order logic,monadic second-order logic with fix-point operators,and fragments of second-order logic are investigated in the paper.We discuss the data complexity for second-order logics over constraint databases.The main results are that the complexity upper bounds for three theories,MSO+(LIN),MSO+(POLY),and Inflationary DATALOGact^cv(SC,M)without powerset operator are∪iΣi^NC1,NCH=∪iΣi^NC,and AC^0/poly,respectively.We also consider the problem of query closure property in the context of embedded finite models and constraint databases with complex objects and the issue of how to determine safe constraint queries.
