计算机科学技术学报 ›› 2019,Vol. 34 ›› Issue (4): 795-817.doi: 10.1007/s11390-019-1943-7

所属专题： Data Management and Data Mining

• Data Management and Data Mining • 上一篇    下一篇

论复杂对象约束数据库逻辑的表达能力

Hong-Cheu Liu, Jixue Liu   

  1. School of Information Technology and Mathematical Sciences, University of South Australia, Adelaide 5095, Australia
  • 收稿日期:2018-09-01 修回日期:2019-04-23 出版日期:2019-07-11 发布日期:2019-07-11
  • 作者简介:Hong-Cheu Liu received his B.S.degree in mathematics and his M.S.degree in engineering science from "National" Cheng Kung University,Tainan,in 1977 and 1985 respectively.He also received his M.Sc.degree in computer science from The University of Melbourne,Melbourne,and his Ph.D.degree in computer science from The Australian National University,Canberra.His main research areas include database theory,data mining and logic in computer science.Recently his research interests lie in biomedical informatics.In particular,he focuses on machine learning in Alzheimer's disease research.Dr.Liu is now a semiretired researcher.
  • 基金资助:
    This work was supported in part by the Taiwan Science Council, China, under Grant No. NSC90-2218-E-126-001.

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

Hong-Cheu Liu, Jixue Liu   

  1. School of Information Technology and Mathematical Sciences, University of South Australia, Adelaide 5095, Australia
  • Received:2018-09-01 Revised:2019-04-23 Online:2019-07-11 Published:2019-07-11
  • Supported by:
    This work was supported in part by the Taiwan Science Council, China, under Grant No. NSC90-2218-E-126-001.

PDF (PC)

197

补充材料

1

我们扩展约束数据模型以允许复杂对象，并研究各种查询语言在这类约束数据库上的表达能力。我们使用的工具来自以坍塌结果的形式，这些结果在一阶逻辑的背景下已经很好地建立。我们证明在一个条件下的自然主动坍塌和主动通用坍塌的o-极小性质的结构和复值关系中的任何特征在二阶逻辑下成立。本文研究了更强大逻辑的表现力，包括一元二阶逻辑，具有定点算子的一元二阶逻辑和二阶逻辑片段。我们讨论了约束数据库上二阶逻辑的数据复杂性。主要结果是三个理论MSO+Linn，MSO+Poly和Inflatingary DATALOG（cv-not，act）（SC，M）在没有powerset运算符时的的复杂性上界分别为Ui*SUM（NC1，i），NCH=Ui*SUM（NC，i），AC0/poly。我们还考虑了嵌入式有限模型和具有复杂对象的约束数据库的上下文中的查询闭和属性问题以及如何约束查询。

关键词: 约束数据库, 一元二阶逻辑, 自然主动坍塌, ramsey属性, o-最小结构

Abstract: 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 Datalogactcv,¬(SC, M) without powerset operator are ∪i ∑iNC1, NCH=∪i ∑iNC, and AC0/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.

Key words: constraint database, monadic second-order logic, natural-active collapse, Ramsey property, o-minimality structure

[1] Revesz P. Big data and spatial constraint databases. In Encyclopedia of GIS, Shekhar S, Xiong H, Zhou X (eds.), Springer, 2017, pp.118-122.
[2] Kanellakis P, Kuper G, Revesz P. Constraint query languages. Journal of Computer and System Sciences, 1995, 51(1):26-52.
[3] Libkin L. Embedded finite models and constraint databases. In Finite Model Theory and Its Applications, Grädel E, Kolaitis P G, Libkin L, Marx M, Spencer J, Vardi M Y (eds.), Springer, 2007, pp.257-337.
[4] Libkin L. Query languages with arithmetic and constraint databases. SIGACT News, 1999, 30(4):41-50.
[5] Hull R, Su J. Domain independence and the relational calculus. Acta Informatica, 1994, 31(6):513-524.
[6] Moschovakisl Y. Elementary Induction on Abstract Structures. North-Holland, 1974.
[7] Chandra A, Harel D. Structure and complexity of relational queries. Journal of Computer and System Sciences, 1982, 25(1):99-128.
[8] Kuper G, Libkin L, Paredaens J. Constraint Databases. Springer, 2000.
[9] Benedikt M, Dong G, Libkin L, Wong L. Relational expressive power of constraint query languages. Journal of the ACM, 1998, 45(1):1-34.
[10] Basu S. New results on quantifier elimination over real closed fields and application to constraint databases. Journal of the ACM, 1999, 46(4):537-555.
[11] Tarski A. A Decision Method for Elementary Algebra and Geometry. University of California Press, 1951.
[12] van den Dries L. O-minimal structures. In Logic:From Foundations to Applications:European Logic Colloquium, Hodges W, Hyland M, Steinhorn C, Truss J (eds.), Oxford Science Publications, 1996, pp.99-108.
[13] Nešetřil J, Rödl V. Mathematics of Ramsey Theory. Springer-Verlag Berlin Heidelberg, 1990.
[14] Graham R L, Rothschild B L, Spencer J H. Ramsey Theory (2nd edition). Wiley-Interscience, 1990.
[15] Benedikt M, Libkin L. Relational queries over interpreted structures. Journal of the ACM, 2000, 47(4):644-680.
[16] Abiteboul S, Beeri C. The power of languages for the manipulation of complex values. The Very Large Data Bases Journal, 1995, 4(4):727-794.
[17] Grädel E, Gurevich Y. Metafinite model theory. Information and Computation, 1998, 140(1):26-81.
[18] Rose E, Segev A. TOODM-A temporal object-oriented data model with temporal constraints. In Proc. the 10th International Conference on the Entity Relationship Approach, October 1991, pp.205-229.
[19] Revesz P. Safe query languages for constraint databases. Transactions on Database Systems, 1998, 23(1):58-99.
[20] Abiteboul S, Hull R, Vianu V. Foundations of Databases. Addison-Wesley, 1995.
[21] Libkin L. A collapse result for constraint queries over structures of small degree. Information Processing Letter, 2003, 86(5):277-281.
[22] Goldin D, Kanellakis P C. Constraint query algebras. Constraints, 1996, 1(1/2):45-83.
[23] Grädel E, Kreutzer S. Descriptive complexity theory for constraint databases. In Proc. the 13th International Workshop on Computer Science Logic, September 1999, pp.67-81.
[24] Kuijpers B, Paredaens J, van den Bussche J. Lossless representation of topological spatial data. In Proc. the 4th Symposium on Spatial Databases, August 1995, pp.1-13.
[25] Segoufin L, Vianu V. Querying spatial databases via topological invariants. In Proc. the 17th ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems, June 1998, pp.89-98.
[26] Wong L. A dichotomy in the intensional expressive power of nested relational calculi augmented with aggregate functions and a powerset operator. In Proc. the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, June 2013, pp.285-295.
[27] Otto M, van den Bussche J. First-order queries on databases embedded in an infinite structure. Information Processing Letters, 1996, 60(1):37-41.
[28] Aylamazyan A K, Gilula M M, Stolboushkin A P, Schwartz G F. Reduction of the relational model with infinite domains to the case of finite domains. Doklady Akademii Nauk SSSR, 1986, 286(2):308-311. (in Russian)
[29] Benedikt M, Grohe M, Libkin L, Segoufin L. Reachability and connectivity queries in constraint databases. Journal of Computer and System Sciences, 2003, 66(1):169-206.
[30] Arora S, Barak B. Computational Complexity:A Modern Approach (1st edition). Cambridge University Press, 2009.
[31] Kanellakis P C, Goldin D Q. Constraint programming and database query languages. In Proc. the 1994 International Conference on Theoretical Aspects of Computer Software, April 1994, pp.96-120.
[32] Karp R, Ramachandran V. Parallel algorithms for sharedmemory machines. In Handbook of Theoretical Computer Science:Volume A:Algorithm and Complexity, van Leeuween J (ed.), 1990, pp.869-941.
[33] Jonsson P, Lööw T. Computational complexity of linear constraints over the integers. Artificial Intelligence, 2013, 195:44-62.
[34] Benedikt M, Libkin L. Safe constraint queries. SIAM Journal on Computing, 2000, 29(5):1652-1682.
[35] Escobar-Molano M, Hull R, Jacobs D. Safety and translation of calculus queries with scalar functions. In Proc. the 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 1993, pp.253-264.
[36] Avron A, Lev S, Levi N. Safety, absoluteness, and computability. In Proc. the 27th EACSL Annual Conference on Computer Science Logic, September 2018, Article No. 8.
[37] Liu H C, Yu J X, Liang W F. Safety, domain independence and translation of complex value database queries. Inf. Sci., 2008, 178(12):2507-2533.
[38] Stolboushkin A, Taitslin M. Finite queries do not have effective syntax. In Proc. the 14th ACM SIGACT-SIGMODSIGART Symposium on Principles of Database Systems, May 1995, pp.277-285.
[39] Pillary A, Steinhorn C. Definable sets in ordered structures. Ⅲ. Transactions of the American Mathematical Society, 1988, 309(2):469-476.
[40] Ebbinghaus H D, Flum J. Finite Model Theory (2nd edition). Springer-Verlag Berlin Heidelberg, 1995.
[41] Immerman N. Descriptive Complexity. Springer-Verlag New York, 1999.
[42] Libkin L. Elements of Finite Model Theory. Springer-Verlag Berlin Heidelberg, 2004.
[43] Paredaens J, van den Bussche J, van Gucht D. First-order queries on finite structures over the reals. SIAM Journal on Computing, 1998, 27(6):1747-1763.
[44] Pillay A, Steinhorn C. Definable sets in ordered structures. Bulletin of the American Mathematical Society, 1984, 11(1):159-162.
[45] van den Dries L. Tame Aopology and O-Minimality Structures. Cambridge University Press, 1998.
[46] Kuijpers B, Paredaens J, van den Bussche J. Topological elementary equivalence of closed semi-algebraic sets in the real plane. Journal of Symbolic Logic, 2000, 65(4):1530-1555.
[47] Kuijpers B, van den Bussche J. On capturing first-order topological properties of planar spatial databases. In Proc. the 7th International Conference on Database Theory, January 1999, pp.187-198.
[48] Papadimitriou C, Suciu D, Vianu V. Topological queries in spatial databases. Journal of Computer and System Sciences, 1999, 58(1):29-53.
[49] Segoufin L, Vianu V. Querying spatial databases via topological invariants. Journal of Computer and System Sciences, 2000, 61(2):270-301.
[50] Vandeurzen L, Gyssens M, van Gucht D. On the expressiveness of linear-constraint query languages for spatial databases. Theoretical Computer Sciences, 2001, 254(1/2):423-463.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] C.Y.Chung; 华宣仁;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[2] 章萃; 赵沁平; 徐家福;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[3] 黄学东; 蔡莲红; 方棣棠; 迟边进; 周立; 蒋力;. A Computer System for Chinese Character Speech Input[J]. , 1986, 1(4): 75 -83 .
[4] 唐同诰; 招兆铿;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[5] 夏培肃; 方信我; 王玉祥; 严开明; 张廷军; 刘玉兰; 赵春英; 孙继忠;. Design of Array Processor Systems[J]. , 1987, 2(3): 163 -173 .
[6] 孙永强; 陆汝占; 黄小戎;. Termination Preserving Problem in the Transformation of Applicative Programs[J]. , 1987, 2(3): 191 -201 .
[7] 林琦; 夏培肃;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[8] 谢立; 陈珮珮; 杨培根; 孙钟秀;. The Design and Implementation of an OA System ZGL1[J]. , 1988, 3(1): 75 -80 .
[9] 罗银芳;. Algorithm and Implementation of Parallel Multiplication in a Mixed Number System[J]. , 1988, 3(3): 203 -213 .
[10] 陈国良;. A Partitioning Selection Algorithm on Multiprocessors[J]. , 1988, 3(4): 241 -250 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：