On the Expressive Power of Logics on Constraint Databases with Complex Objects

作     者：Hong-Cheu Liu Jixue Liu 

作者机构：School of Information Technology and Mathematical SciencesUniversity of South AustraliaAdelaide 5095Australia 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2019年第34卷第4期

页      面：795-817页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported in part by the Taiwan Science Council  China 

主　　题：constraint database monadic second-order logic natural-active collapse Ramsey property o-minimality structure 

摘      要：We extend the constraint data model to allow complex objects and study the expressive power of various query languages over this sort of constraint *** tools we use come in the form of collapse results which are well established in the context of first-order *** 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 *** 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 *** discuss the data complexity for second-order logics over constraint *** 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,*** 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.