Pattern matching by Rs-operations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Pattern matching by Rs-operations: towards a unified approach to querying sequenced data

Full text

Pdf (675 KB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems table of contents

San Diego, California, United States

Pages: 293 - 300

Year of Publication: 1992

ISBN:0-89791-519-4

Authors

Seymour Ginsburg
Xiaoyang Wang

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 7, Citation Count: 9

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/137097.137895 What is a DOI?

ABSTRACT

A family of sequence operations (rs-operations), based on pattern matching and including most of the “natural” operations on sequences, is introduced. In order to apply rs-operations to calculus-like query languages, a logic about sequences (SL) is defined by converting rs-operations to special predicates. To illustrate the applicability of our concepts to database queries, rs-operations and SL are used in an algebra and a calculus, respectively, over an extended relational data model containing sequences.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Alfred V. Aho , Brian W. Kernighan , Peter J. Weinberger, The AWK programming language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
	3	Antonio Albano , Luca Cardelli , Renzo Orsini, GALILEO: a strongly-typed, interactive conceptual language, ACM Transactions on Database Systems (TODS), v.10 n.2, p.230-260, June 1985 [doi>10.1145/3857.3859]
	4	M. Atkinson, F. Bancilhon, D. DeWitt, K. Dittrich, D. Mater, and S. Zdonik. The object-oriented database manifesto. In Proceedings of the international Conference on Deductzve and Object Or#- enled Databases, 1989.
	5	François Bancilhon , Sophie Cluet , C. Delobel, A query language for the O2 object-oriented databases, Proceedings of the second international workshop on Database programming languages, p.122-138, December 1989, Salishan Lodge, Gleneden Beach, Oregon, United States
	6	Michael J. Carey , David J. DeWitt, A data model and query language for EXODUS, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.413-423, June 01-03, 1988, Chicago, Illinois, United States
	7	E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
	8	O. Deux, The O2 system, Communications of the ACM, v.34 n.10, p.34-48, Oct. 1991 [doi>10.1145/125223.125238]
	9	Seymour Ginsburg , Chang-Jie Tang, Canonical forms for interval functions, Theoretical Computer Science, v.54 n.2-3, p.299-313, Oct. 1987 [doi>10.1016/0304-3975(87)90135-6 ]
	10	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	11	Douglas P. Metzler , Stephanie W. Haas, The constituent object parser: syntactic structure matching for information retrieval, ACM Transactions on Information Systems (TOIS), v.7 n.3, p.292-316, July 1989 [doi>10.1145/65943.65949]
	12	Ontologic, Inc. Vbase Technical Overview, version 1.0 edition, March 1987.
	13	P Pistor , R Traunmueller, A database language for sets, lists and tables, Information Systems, v.11 n.4, p.323-336, Oct. 1986 [doi>10.1016/0306-4379(86)90012-8]
	14	Avi Silberschatz , Michael Stonebraker , Jeffrey D. Ullman, Database systems: achievements and opportunities, ACM SIGMOD Record, v.19 n.4, p.6-22, Dec. 1990 [doi>10.1145/122058.122059]
	15	The Committee for Advanced DBMS Function Corporate, Third-generation database system manifesto, ACM SIGMOD Record, v.19 n.3, p.31-44, Sep. 1990 [doi>10.1145/101077.390001]
	16	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	17	Scott L. Vandenberg , David J. DeWitt, Algebraic support for complex objects with arrays, identity, and inheritance, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.158-167, May 29-31, 1991, Denver, Colorado, United States

CITED BY 9

	Gösta Grahne , Matti Nykänen , Esko Ukkonen, Reasoning about strings in databases, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.303-312, May 24-27, 1994, Minneapolis, Minnesota, United States
	Giansalvatore Mecca , Anthony J. Bonner, Query Languages for Sequence Databases: Termination and Complexity, IEEE Transactions on Knowledge and Data Engineering, v.13 n.3, p.519-525, May 2001
	Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, The Design and Implementation of a Sequence Database System, Proceedings of the 22th International Conference on Very Large Data Bases, p.99-110, September 03-06, 1996
	H. V. Jagadish , Alberto O. Mendelzon , Tova Milo, Similarity-based queries, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.36-45, May 22-25, 1995, San Jose, California, United States
	Joel Richardson, Supporting Lists in a Data Model (A Timely Approach), Proceedings of the 18th International Conference on Very Large Data Bases, p.127-138, August 23-27, 1992
	Giansalvatore Mecca , Anthony J. Bonner, Sequences, Datalog and transducers, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.23-35, May 22-25, 1995, San Jose, California, United States
	Latha S. Colby , Edward L. Robertson , Lawrence V. Saxton , Dirk Van Gucht, A query language for list-based complex objects, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.179-189, May 24-27, 1994, Minneapolis, Minnesota, United States
	Michael Benedikt , Leonid Libkin , Thomas Schwentick , Luc Segoufin, String operations in query languages, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.183-194, May 2001, Santa Barbara, California, United States
	Michael Benedikt , Leonid Libkin , Thomas Schwentick , Luc Segoufin, Definable relations and first-order query languages over strings, Journal of the ACM (JACM), v.50 n.5, p.694-751, September 2003