{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T12:09:37Z","timestamp":1751285377512,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414810"},{"type":"electronic","value":"9783540445432"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44543-9_5","type":"book-chapter","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T18:23:52Z","timestamp":1181240632000},"page":"61-79","source":"Crossref","is-referenced-by-count":6,"title":["How to Make SQL Stand for String Query Language"],"prefix":"10.1007","author":[{"given":"G\u00f6sta","family":"Grahne","sequence":"first","affiliation":[]},{"given":"Emmanuel","family":"Waller","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,4,13]]},"reference":[{"key":"5_CR1","unstructured":"S. Abiteboul, R. Hull and V. Vianu. Foundations of Databases. Addison-Wesley, 1995. 62, 64, 65, 67, 69, 74, 78"},{"key":"5_CR2","unstructured":"N. Balkir, E. Sukan, G. Ozsoyoglu and Z. Oszoyoglu. VISUAL: A graphical iconbased query language. In IEEE International Conferecne on Data Engineering, 1996. 75"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"M. Benedikt, L. Libkin. Languages for Relational Databases over Interpreted Structures. In Proc. ACM Symp. on Principles of Database Systems, 1997. 68, 74","DOI":"10.1145\/263661.263672"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"M. Benedikt, L. Libkin. Safe Constraint Queries. In Proc. ACM Symp. on Principles of Database Systems, 1998.","DOI":"10.1145\/275487.275499"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/362384.362685","volume":"13","author":"E. F. Codd","year":"1970","unstructured":"E. F. Codd. A Relational Model of Data for Large Shared Data Banks. Communications of ACM, 13:6, 1970 61","journal-title":"Communications of ACM"},{"issue":"3","key":"5_CR6","first-page":"321","volume":"7","author":"J. Collado-Vides","year":"1991","unstructured":"J. Collado-Vides. The search for a grammatical theory of gene regulation is formally justified by showing the inadequacy of context-free grammars. Computer applications in the Biosciences, 7(3):321\u2013326, 1991. 61","journal-title":"Computer applications in the Biosciences"},{"key":"5_CR7","unstructured":"C. Date. An introduction to database systems. Addison-Wesley, 1994. 75"},{"key":"5_CR8","unstructured":"V. Diekert, Makanin\u2019s algorithm. Available at http:\/\/www.lri.fr\/~rtaloop\/92.html 66, 76"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"T. Eiter, G. Gottlob, Y. Gurevich. Existential Second-Order Logic over Strings. In Proc. Symp. on Logic in Computer Science, 1998. 76","DOI":"10.1109\/LICS.1998.705640"},{"issue":"1","key":"5_CR10","first-page":"49","volume":"9","author":"T. Etzold","year":"1993","unstructured":"T. Etzold and P. Argos. SRS-an indexing and retrieval tool for flat file data libraries. Computer applications in the Biosciences, 9(1):49\u201357, 1993. 74","journal-title":"Computer applications in the Biosciences"},{"issue":"1","key":"5_CR11","first-page":"59","volume":"9","author":"T. Etzold","year":"1993","unstructured":"T. Etzold and P. Argos. Transforming a set of biological flat file libraries to a fast access network. Computer applications in the Biosciences, 9(1):59\u201364, 1993 74","journal-title":"Computer applications in the Biosciences"},{"key":"5_CR12","unstructured":"European Molecular Biologiy Network (EMBNET). Strategies in Bioinformatics: a european perspective, 1994. 75"},{"issue":"3","key":"5_CR13","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1016\/0022-0000(83)90002-8","volume":"26","author":"Z. Galil","year":"1983","unstructured":"Z. Galil, J. I. Seiferas. Time-Space-Optimal String Matching. Journal of Computer and System Sciences 26(3): 280\u2013294, 1983. 75","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"S. Ginsburg, X. S. Wang. Pattern Matching by Rs-Operations: Toward a Unified Approach to Querying Sequenced Data. In Proc. ACM Symp. on Principles of Database Systems, 1992. 62, 75, 76","DOI":"10.1145\/137097.137895"},{"issue":"1","key":"5_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jcss.1997.1514","volume":"56","author":"S. Ginsburg","year":"1998","unstructured":"S. Ginsburg and W. Wang. Regular Sequence Operations and Their Use in Database Queries. Journal of Computer and System Science 56(1): 1\u201326 (1998) 67, 75","journal-title":"Journal of Computer and System Science"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"G. Grahne, M. Nyk\u00e4nen, E. Ukkonen. Reasoning about Strings in Databases. In Proc. ACM Symp. on Principles of Database Systems, 1994. 62, 75, 76","DOI":"10.1145\/182591.182656"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"G. Grahne, M. Nyk\u00e4nen. Safety, translation and evaluation of Alignment calculus. First East-European Symposium on Advances in Database Information Systems (ABDIS\u201997), St-Petersburg, Russia, 1997. 75","DOI":"10.14236\/ewic\/ADBIS1997.20"},{"key":"5_CR18","unstructured":"G. Grahne, R. Hakli, M. Nykanen and E. Ukkonen. AQL: An alignment based language for querying string databases. Proc. of the 9TH International Conference on Management of Data (Comad\u2019 98), Hyderabad, India, December 1998. 75"},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/BF01213204","volume":"31","author":"R. Hull","year":"1994","unstructured":"R. Hull, J. Su. Domain independence and the relational calculus. Acta informatica, 31:6, 1994. 77","journal-title":"Acta informatica"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"J. W. Lloyd Foundations of logic programming. Springer, 1984. 75","DOI":"10.1007\/978-3-642-96826-6"},{"key":"5_CR21","unstructured":"J. Barwise (Ed). Handbool of mathematical logic. North-Holland, 1991."},{"key":"5_CR22","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1070\/SM1977v032n02ABEH002376","volume":"32","author":"G. S. Makanin","year":"1977","unstructured":"G. S. Makanin. The problem of solvability of equations in a free semi-group. english translation in Math. USSR Sbornik, 32, 129\u2013198, 1977. 66, 76","journal-title":"Math. USSR Sbornik"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"G. Mecca, A. J. Bonner. Sequences, Datalog and Transducers. In Proc. ACM Symp. on Principles of Database Systems, 1995. 62, 67, 75, 76","DOI":"10.1145\/212433.212440"},{"key":"5_CR24","unstructured":"C. H. Papadimitriou. Computational complexity. Addison-Wesley, Chap. 17, 1994."},{"issue":"4","key":"5_CR25","doi-asserted-by":"publisher","first-page":"105","DOI":"10.2307\/2268308","volume":"11","author":"W. V. Quine","year":"1946","unstructured":"W. V. Quine. Concatenation as a basis for arithmetic. Journal of Symbolic Logic, 11(4):105\u2013114, 1946 62, 76","journal-title":"Journal of Symbolic Logic"},{"key":"5_CR26","unstructured":"J. Richardson. Supporting lists in a data model (a timely approach). Proc. of Intl. Conf. on Very Large Data Bases, 1992. 75"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"G. Rozenberg, A. Salomaa (Eds). Handbook of formal languages. Springer, 1997. 76","DOI":"10.1007\/978-3-642-59126-6"},{"key":"5_CR28","unstructured":"A. Salomaa. Formal languages, Chap. 3, Academic Press, 1973. 76"},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"D. Searls. String variable grammar: a logic grammar formalism for the biological language of DNA. Journal of Logic Programming, pp. 73\u2013102, 1995. 61","DOI":"10.1016\/0743-1066(95)00034-H"},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"P. Seshadri, M. Livny and R. Ramakrishnan. SEQ: a model for sequence databases. IEEE International Conference on Data Engineering, pp. 232\u2013239, 1995. 75","DOI":"10.1109\/ICDE.1995.380388"},{"key":"5_CR31","unstructured":"P. Seshadri, M. Livny and R. Ramakrishnan. The design and implementation of a sequence database system. Proc. of Intl. Conf. on Very Large Data Bases, 1996. 75"},{"key":"5_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3:1\u201322, 1977 62, 76","journal-title":"Theoretical Computer Science"},{"key":"5_CR33","doi-asserted-by":"crossref","unstructured":"B. Subramanian, T. Leung, S. Vandenberg and S. Zdonik. The AQUA appraoch to querying lists and trees in objsct-oriented databases. IEEE International Conference on Data Engineering, pp. 80\u201389, 1995. 62","DOI":"10.1109\/ICDE.1995.380405"},{"key":"5_CR34","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/0747-7171(92)90016-W","volume":"14","author":"R. Treinen","year":"1992","unstructured":"R. Treinen. A new method for undecidability proofs of first order theories. J. Symbolic Computation, 14:437\u2013457, 1992. 76","journal-title":"J. Symbolic Computation"},{"key":"5_CR35","unstructured":"J. Ullman. Principles of database and knowledge-base systems, Volume 1. Computer Science Press, 1988. 62"},{"key":"5_CR36","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/S0019-9958(83)80051-5","volume":"56","author":"P. Wolper","year":"1983","unstructured":"P. Wolper. Temporal logic can be more expressive. Information and Control, 56:72\u201399, 1983. 75","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","Research Issues in Structured and Semistructured Database Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44543-9_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T01:55:27Z","timestamp":1737078927000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44543-9_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540414810","9783540445432"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-44543-9_5","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}