60 Years of Databases (part four)

V.A. Reznichenko

Abstract


The article provides an overview of research and development of databases since their appearance in the 60s of the last century to the present time. The following stages are distinguished: the emer- gence formation and rapid development, the era of relational databases, extended relational data- bases, post-relational databases and big data. At the stage of formation, the systems IDS, IMS, Total and Adabas are described. At the stage of rapid development, issues of ANSI/X3/SPARC database architecture, CODASYL proposals, concepts and languages of conceptual modeling are highlighted. At the stage of the era of relation-al databases, the results of E. Codd’s scientific activities, the theory of dependencies and normal forms, query languages, experimental research and development, optimization and standardiza- tion, and transaction management are revealed. The extended relational databases phase is devot- ed to describing temporal, spatial, deductive, ac- tive, object, distributed and statistical databases, array databases, and database machines and data warehouses. At the next stage, the problems of post-relational databases are disclosed, namely, NOSQL-, NewSQL- and ontological databases. The sixth stage is devoted to the disclosure of the causes of occurrence, characteristic properties, classification, principles of work, methods and technologies of big data. Finally, the last section provides a brief overview of database research and development in the former Soviet Union.

Prombles in programming 2022; 2: 57-95


Keywords


Database types; hierarchical; network; relational; navigational; temporal; spatial; spatio-temporal; spatio-network; moving objects; deductive; active; object-oriented; object- relational; distributed; parallel; arrays; statistical; multidimensional

Full Text:

PDF (Ukrainian)

References


Strozzi C. NoSQL – A relational dat base management system. 2007–2010. – http://www.strozzi.it/cgi-bin/CSA/tw7/I/ en_US/nosql/Home%20Page

Evans E. NoSQL 2009. May 2009. – Blog post of 2009-05-12. - http://blog.sym- link.com/posts/2009/12/nosql_2009/

Evans E. NoSQL: What’s in a name? Oc- tober 2009. – Blog post of 2009-10-30. - http://blog.sym-link.com/posts/2009/30/ nosql_whats_in_a_name/

Fox A, Brewer E. Harvest, yield and scal- able tolerant systems. In: Proceedings of Workshop on Hot Topics in Operating Systems; 1999. p. 174–178.

Seth Gilbert, Nancy Lynch. Brewer’s conjecture and the feasibility of consistent,available, partition-tolerant web services. ACM SIGACT News, Volume 33 Issue 2, June 2002, pp. 51-59.

Abadi D. Consistency tradeoffs in modern distributed database system design: CAP is only part of the story. Computer

(2), 37-42 (2012)

Strauch Ch. "NoSQL Databases". - http://www.christof-strauch.de/ nosqldbs.pdf

Kepner J., Chaidez J., Gadepally, Jansen H. "Associative arrays: Unified mathematics for spreadsheets, databases, matrices, and graphs," New England Database Day, 2015.

Kepner J., Chaidez J., "The Abstract Algebra of Big Data and Associative Arrays," SIAM Meeting on Discrete Math, Jun 2014, Minneapolis, MN.

Jeremy Kepner, Vijay Gadepally, Dylan Hutchison, Hayden Jananthan, Timothy Mattson, Siddharth Samsi, Albert Reuther. Associative Array Model of SQL, NoSQL, and NewSQL Databases. 2016 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1–9. IEEE (2016).

A Brief History of NoSQL. - http://blog. knuthaugen.no/2010/03/a-brief-history- of-nosql.html

GT.M - https://en.wikipedia.org/wiki/GT.M 767. DB-Engines Ranking of Key-value Stores. - db-engines.com/en/ranking/key-

value+store

Rusher J., Networks R. Triple Store. - https://www.w3.org/2001/sw/Europe/ events/20031113-storage/positions/rusher.html

Tweed R., James G. A Universal NoSQL Engine, Using a Tried and Tested Technology. - http://www.mgateway.com/ docs/universalNoSQL.pdf, 2010. - 25 p.

Welcome to the UnQL Specification home

- http://www.unqlspec.org/display/UnQL

Bach M., Werner A. Standardization of NoSQL Database Languages. In: Kozielski S., Mrozek D., Kasprowski P., Małysiak-Mrozek B., Kostrzewa D. (eds) Beyond Databases, Architectures, and Structures. BDAS 2014. Communications in Computer and Information Science, vol 424. Springer, Cham. 2014, pp. 50–60.

Angles R., Gutierrez C. Survey of graph database models. ACM Comput. Surv. 40, 1, Article 1, 2008, 39 p.

Suciu D. Semi-structured Data Model. In Encyclopedia of Database Systems, Ling Liu, M. Tamer Özsu Editors, pp. 3446-3451.

Suciu D. Semi-structured Query Languages. In Encyclopedia of Database Systems, Ling Liu, M. Tamer Özsu Editors, pp. 3457-3459.

Luniewski A., Shoens K., Schwarz P., Stamos J., Thomas J. The Rufus system: information organization for semi-structured data. In: Proceedings of the 19th International Conference on Very Large Data Bases; 1993. p. 97–107.

Papakonstantinou Y., Garcia-Molina H., Widom J. Object exchange across het- erogeneous information sources. In: Proceedings of the 11th International Conference on Data Engineering; 1995. p. 251– 260.

Garcia-Molina H., Papakonstantinou Y., Quass D., Rajaraman A., Sagiv Y., Ullman J., Widom J. The TSIMMIS project: integration of heterogeneous information sources. J Intell Inf Syst. 1997;8(2):117–132.

Buneman P., Davidson S., Hillebrand G., Suciu D. A query language and optimization techniques for unstructured data. In: Proceedings of the ACM SIGMOD International Conference on Management of Data; 1996. p. 505–516.

Buneman P., Fernandez M., Suciu D. UNQL: a query language and algebra for semistructured data based on structural recursion. VLDB J. 2000;9(1): 76–110.

Deutsch A., Fernandez M., Florescu D., Levy A., Suciu D. A query language for XML. In: Proceedings of the 8th International World Wide Web Conference; 1999. p. 77–91.

Abiteboul S., Quass D., McHugh J., Widom J., Wiener J. The Lorel query language for semistructured data. 1996. http://www-db.stanford.edu/lore/.

Papakonstantinou Y., Abiteboul S., Gar- cia-Molina H. Object fusion in media- tor systems. In: Proceedings of the 22th International Conference on Very Large Data Bases; 1996. p. 413–424.

Best Document Databases. - https://www.g2.com/categories/document-databases

Estabrook G F., Brill R.C. The Theory of the TAXIR accessioner. Mathematical Biosciences, 1969, Vol. 5, No 3–4,

pp. 327-340.

Weyl S. Fries J.F. Wiederhold G., Germano F. "A Modular Self-describing Clinical Databank System". Computers and

Biomedical Research. 1975. 8 (3): 279–293.

Turner M.J., Hammond R., Cotton P. A DBMS for Large Statistical Databases. VLDB ‘79: Proceedings of the fifth international conference on Very Large Data Bases - Vol. 5, 1979, pp. 319–327.

"SCSS from SPSS, Inc". ComputerWorld. September 26, 1977. p. 28.

Karasalo I., Svensson P. An overview of cantor: a new system for data analysis. SSDBM’83: Proceedings of the Second International Workshop on Statistical Database ManagementSeptember, 1983,

pp.315–324.

Don S. Batory. On searching transposed files. ACM Transactions on Database Systems, 4(4):531–544, 1979.

Hoffer J.A. , Severance D.G. The use of cluster analysis in physical data base design. In VLDB ‘75: Proceedings of the 1st

International Conference on Very Large Data BasesSeptember 1975 Pages 69–86, 1975.

Copeland G.P., Khoshafian S.N. . A decomposition storage model. In Proceedings of the ACM SIGMOD Conference on Management of Data,1985, pp. 268–279.

Khoshafian S., Valduriez P. Parallel execution strategies for declustered databases. In Proceedings of the International Workshop on Database Machines, pages 458–471, 1987.

Khoshafian S., Copeland G., Jagodis T., Boral H., Valduriez P. A query processing strategy for the decomposed storage model. In Proceedings of the International Conference on Data Endineering

(ICDE), pp. 636–643, 1987.

Boncz P. Monet: A next-generation DBMS kernel for queryintensive applications. University of Amsterdam, PhD Thesis, 2002.

Idreos S., Groffen F., Nes N., Manegold S., Mullender S., Kersten M.L MonetDB: Two Decades of Research in Column-ori-

ented Database Architectures. IEEE Data Eng. Bull., 35(1):40–45, 2012.

Boncz P., Zukowski M., Nes N. MonetDB/X100: Hyperpipelining query execution. In Proceedings of the biennial Conference on Innovative Data Systems Research (CIDR), 2005, pp. 225-237.

Zukowski M., Boncz P.A., Nes N, Heman S. MonetDB/X100 - A DBMS In The CPU Cache. IEEE Data Engineering Bulletin, 28(2): 17–22, June 2005.

Michael Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Samuel R. Madden, Elizabeth J. O’Neil, Patrick E. O’Neil, Alexander Rasin, Nga Tran, and Stan B. Zdonik. C-Store: A Column-Oriented DBMS. In Proceedings of the International Conference on Very Large Data Bases (VLDB), pages 553–564, 2005.

Lamb A., Fuller M., Varadarajan R., Tran N., Vandiver B., Doshi L., Bear C. The Vertica analytic database: C-store 7 years later. Proceedings of the VLDB Endowment, Vol. 5, No 12, 2012 pp. 1790–1801.

Abadi D.J., Madden S.R., Ferreira M. Integrating compression and execution in column-oriented database systems. In Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 671–682, 2006.

Abadi D.J., Myers D.S., DeWitt D.J., Madden S.R. Materialization strategies in a column-oriented DBMS. In Proceedings of the International Conference on Data Endineering (ICDE), pp. 466–475, 2007.

Idreos S., Kersten M.L., Manegold S. Self-organizing tuple reconstruction in column stores. In Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 297–308, 2009.

Zukowski M., Heman S., Nes N., Boncz P. Super-Scalar RAM-CPU Cache Compression. In Proceedings of the 22nd International Conference on Data Endineer- ing (ICDE), 2006. pp. 59-71.

Abadi D.J., Boncz P., Harizopoulos S., Idreos S., Madden S. (2013), "The Design and Implementation of Modern Column-Oriented Database Systems", Foundations and Trends® in Databases: Vol. 5: No. 3, pp 197-280.

a.Goncalves R., Kersten M.L. The Data Cyclotron Query Processing Scheme. ACM Transactions on Database Systems,

Vo. 36. No 4. December 2011, Article No. 27, pp. 1–35.

Manegold S., Boncz P., Nes N., Kersten M.. Cache-conscious radixdecluster projections. In Proceedings of the International Conference on Very Large Data Bases (VLDB), pages 684–695, 2004.

22) Abadi D.J., Madden S.R., Hachem N. Column-stores vs. row-stores: how different are they really? In: Proceedings of the ACM SIGMOD International Conference on Management of Data; 2008. p. 967– 980.

Halverson A., Beckmann J.L., Naughton J.F., DeWitt D.J. A Comparison of C-Store and Row-Store in a Common Framework.

Technical Report TR1570, University of Wisconsin-Madison, 2006. - https://minds.wisconsin.edu/bitstream/han- dle/1793/60514/TR1570.pdf?sequence=1

Harizopoulos S., Liang V., Abadi D.J.,

Madden S.R. Performance tradeoffs in

read-optimized databases. In VLDB, pag-

es 487–498, 2006.

Idreos S., Kersten M., Manegold S. Data-

base Cracking. Conference: CIDR 2007,

Third Biennial Conference on Innovative

Data Systems Research, Asilomar, CA,

USA, 2007, pp. 68-78.

Héman S., Zukowski M., Nes N.J., Sid-

irourgos L., Boncz P. Positional update

handling in column stores. In Proceed-

ings of the ACM SIGMOD Conference

on Management of Data, pp. 543–554,

Pingpeng Yuan and Hai Jin. Column

Stores. In: Encyclopedia of Database

Systems, Ling Liu, M. Tamer Özsu Edi-

tors. pp. 518-523.

Abadi D.J., Boncz P.A. Harizopoulos S.

Column-oriented database systems. Pro-

ceedings of the VLDB Endowment, Vol.

, No. 2, 2009, pp. 1664–1665.

Kanungo A. Column oriented databases. International Journal of Advanced Computational Engineering and Networking, 2017, Vol. 5, No 8, pp. 10-13.

Abadi D., Boncz P., Harizopoulos S. VLDB 2009 Tutorial on Column-Stores. - https://www.slideshare.net/abadid/vldb-2009-tutorial-on-columnstores

Robinson I., Webber J., Eifrem E. Graph Databases, 2nd Edition. O’Reilly Media, Inc. 2015, 218 р.

Wood P.T. Graph Database. In Encyclopedia of Database Systems, Ling Liu, M. Tamer Özsu Editors, pp. 1639-1643.

Angles R. Graph Databases - http://renzoangles.net/gdm/

Angles R., Gutierrez C Querying RDF data from a graph database perspective European semantic web conference, 2005, pp. 346-360.

Angles R., Gutierrez C. Survey of graph database models. ACM Computing Surveys, Vol. 40, No. 1, Article 1, 2008, pp. 1-39.

Angles R., Gutierrez C. The expressive

power of SPARQL International Seman-

tic Web Conference, 2008, pp.114-129.

Angles R. A comparison of current graph

database models. IEEE 28th International

Conference on Data Engineering Work-

shops, 2012, 171-177.

Angles R., Arenas M., Barceló P., Hogan A.,

Reutter J., Vrgoč D. Foundations of modern

query languages for graph databases. ACM

Computing Surveys (CSUR), 2017, Vol. 50,

No 5, Article No.: 68, pp. 1–40.

Angles R., Arenas M., Barceló P., Boncz

P., Fletcher G., Gutierrez C. G-CORE:

A core for future graph query languages.

Proceedings of the 2018 International

Conference on Management of Data,

, pp. 1421-1432.

а. Sakr S. Pardede М. (Eds.). Graph Data

Management: Techniques and Applica-

tions. IGI Global, 2011, 502 p.

Angles R. The property graph database

model. In Proceedings of the 12th Alberto

Mendelzon International Workshop on

Foundations of Data Management, Cali,

Colombia, CEUR Workshop Proceedings.

CEUR-WS.org, 2018, [Online] URL:

http://ceur-ws.org/Vol-2100/paper26.pdf

Angles R., Gutierrez C. An Introduction to Graph Data Management: Fundamen- tal Issues and Recent Developments. in Graph Data Management, Springer Pub- lishing Companyt, 2018, pp.1-32.

Angles R., Barcelo P., Rios G. A practical query language for graph DBs. In: 7th Al- berto Mendelzon International Workshop on Foundations of Data Management (AMW), 2013.

Rodriguez M.A., Neubauer P. Construc- tions from dots and lines. Bulletin of the American Society for Information Science and Technology, 2010, 36,(6), pp. 35-41.

Berge C. Graph and Hypergraphs. North- Holland Publishing Company, Amsterdam, 1973.

Roussopoulos N., Mylopoulos, J. Using semantic networks for database management. In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 1975, 144–172.

Shipman D.W. The functional data model

and the data language DAPLEX. ACM

Transactions on Database Systems, vol.

, No. 1, 1981, pp. 140–173.

Kuper G.M., Vardi M.Y. A new approach

to database logic. In Proceedings of the

th Symposium on Principles of Database

Systems (PODS). ACM Press, 1984, pp.

–96.

Kunii H.S. DBMS with graph data model

for knowledge handling. In Proceedings

of the 1987 Fall Joint Computer Confer-

ence on Exploring technology: Today

and Tomorrow. IEEE Computer Society

Press, 1987, pp. 138–142

Lecluse C., Richard P., Velez F. O2, an

object-oriented data model. In Proceed-

ings of the ACM SIGMOD International

Conference on Management of Data.

ACM Press, 1988, pp. 424–433.

Tompa F.W. A data model for flexible hy-

pertext database systems. ACM Transac-

tions on Information Systems, Vol. 7, No

, 1989, pp. 85–100.

Gyssens M., Paredaens J., Den Bussche J.V., Gucht D.V. A graph-oriented object database model. In Proceedings of the 9th Symposium on Principles of Database Systems (PODS). ACM Press, 1990, pp. 417–424.

Watters C., Shepherd M.A. A transient hypergraph-based model for data access. ACM Trans. Inform. Syst. 8 (2), 1990,

pp. 77–102.

Levene M., Poulovassilis A. The Hyper- node model and its associated query lan- guage. In Proceedings of the 5th Jerusa- lem Conference on Information technol- ogy. IEEE Computer Society Press, 1990, pp. 520–530.

Levene M., Poulovassilis A. An object- oriented data model formalised through hypergraphs. Data Knowl. Eng. 6 (3),

, pp. 205–224.

Andries M., Gemis M., Paredaens J., Thyssens I., Den Bussche J.V. Concepts for graph-oriented object manipulation. In Proceedings of the 3rd International Conference on Extending Database Tech-

nology (EDBT). LNCS, vol. 580. Spring-

er, 1992., pp. 21–38.

Amann B., Scholl M. Gram: A Graph Data Model and Query Language. In European Conference on Hypertext Technology (ECHT). ACM, 1992, pp. 201–211.

Mainguenaud M., Simatic X.T. A data

model to deal with multi-scaled networks.

Computers, Environment and Urban Sys-

tems, 1992, vol.16, No 4, pp. 281–288.

Gemis M., Paredaens J. An object-ori-

ented pattern matching language. In Pro-

ceedings of the First JSSST International

Symposium on Object Technologies for

Advanced Software. Springer-Verlag,

, pp. 339–355.

Hidders J., Paredaens J. GOAL, A graph-

based object and association language.

Advances in Database Systems: Imple-

mentations and Applications, CISM,

, pp. 247–265.

Consens M., Mendelzon A. Hy+: A hy-

graph-based query and visualization sys-

tem. ACM SIGMOD Record, Vol. 22, No

, 1993, pp. 511–516.

Guting R.H. GraphDB: modeling and querying graphs in databases. In Proceedings of the 20th International Conference

on Very Large Data Bases (VLDB). Morgan Kaufmann, 1994, pp. 297–308.

Gutierrez A., Pucheral P., Steffen H., Thevenin J.-M. Database graph views: A practical model to manage persistent graphs. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, 1994. pp. 391–402.

Poulovassilis A., Levene M. A Nested- Graph Model for the Representation and Manipulation of Complex Objects. ACM Transactions on Information Systems (TOIS) 12(1), 1994, pp. 35–68.

Paredaens J., Peelman P., Tanca L. G- Log: A graph-based query language. IEEE Trans. Knowl. Data Eng. 7, 3, 1995, pp. 436–453.

Graves M., Bergeman E.R., Lawrence C.B. A graph-theoretic data model for genome mapping databases. In Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS). IEEE Computer Society, 1995, pp. 32-41.

Levene M., Loizou G. A graph-based data model and its ramifications. IEEE Trans. Knowl. Data Eng. 7, 5, 1995, pp. 809–

KIesel N., Schurr A., Westfechtel B. GRAS, graph-oriented software engineering database system.Information Systems, Vol. 20, No 1, 1995, pp. 21-51.

Sheng L., Ozsoyoglu Z. M., Ozsoyoglu G. A graph query language and its query processing. In Proceedings of the 15th International Conference on Data Engineering (ICDE). IEEE Computer Society, 1999, pp. 572–581.

Hidders J. Typing graph-manipulation operations. In Proceedings of the 9th International Conference on Database Theory (ICDT). Springer-Verlag, 2002. pp. 394–409.

Spyratos N., Sugibuchi T. (2016) PROP- ER - A Graph Data Model Based on Property Graphs. In: Grant E., Kotzinos D., Laurent D., Spyratos N., Tanaka Y. (eds) Information Search, Integration, and Per-

sonalization. ISIP 2015, pp. 23-35.

Wood, P.T.: Query languages for graph databases. ACM SIGMOD Record, 2012, Vol. 41, No 1, pp. 50–60.

Barceló P. Querying graph databases. In: PODS ‘13: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems, 2013, pp. 175–188.

Kowalik L Adjacency queries in dynamic sparse graphs. IInformation Processing Letters, 2007, vol. 102, pp. 191–195.

Papadopoulos A.N., Manolopoulos Y. Nearest neighbor search - a database perspective. Series in computer science. Springer, Berlin, 2005, 170 p.

Aggarwal C.C., Wang H. (eds) Managing and mining graph data. Advances in database systems. Springer Science – Busi- ness Media, Berlin, 2005.

Washio T.,Motoda H. State of the Art of Graph-based Data Mining. SIGKDD Ex- plorer Newsletter, 2003, vol. 5, no. 1, pp.

–68.

Yannakakis M. Graph-theoretic methods in database theory. In: Proceedings of the symposium on principles of database sys- tems (PODS). ACM, New York, 1990, pp 230–242

Barcelo P., Libkin L., Reutter J. Querying graph patterns. In Proc. of the 30th ACM SIGMOD-SIGACT-SIGART Sympo-

sium on Principles of Database Systems (PODS), 2011, pp. 199–210

Wang X. Finding patterns on protein sur- faces: Algorithms and applications to pro- tein classification. IEEE Transactions on Knowledge and Data Engineering, 2005, vol. 17, pp. 1065–1078.

Carroll J. Matching RDF Graphs. In Pro- ceedings of the International Semantic Web Conference (ISWC), 2002, pp. 5-15.

Cruz I.F., Mendelzon A.O., Wood P.T. A graphical query language supporting re- cursion. ACM SIGMOD Record, Vol. 16, No 3, 1987, pp 323–330.

Fan W., Li J. Ma S., Tang N., Wu Y. Adding regular expressions to graph reachability and pattern queries. iin Proc. of the IEEE 27th International Conference on Data Engineering (ICDE), 2011, pp. 39–50.

Mendelzon A.O., Wood P.T. Finding regular simple paths in graph databases. SIAM J Comput, 1995, 24(6), pp. 1235–1258.

Zhu A.D., Ma H., Xiao X., Luo S,. Tang Y., Zhou S. Shortest path and distance queries on road networks: towards bridging theory and practice. In: Proceedings of the international conference on man-

agement of data (SIGMOD). ACM, New York, 2013, pp. 857–868

Kanza Y., Sagiv Y. Flexible queries over semistructured data. PODS ‘01: Proceed- ings of the twentieth ACM SIGMOD- SIGACT-SIGART symposium on Princi- ples of database systems, 2001, pp. 40–51.

Hurtado C.A., Poulovassilis A., Wood P.T. Ranking approximate answers to seman- tic web queries. Ranking Approximate Answers to Semantic Web Queries. In: Aroyo L. et al. (eds) The Semantic Web: Research and Applications. ESWC 2009. Lecture Notes in Computer Science, vol 5554. Springer, Berlin, Heidelberg. 2009,

pp. 263–277

Cruz, I.F., Mendelzon, A.O., Wood, P.T. G+: Recursive Queries without Recur- sion. In: Proceedings of the 2th Interna- tional Conference on Expert Database Systems (EDS). 1989, pp. 645–666

Consens, M.P., Mendelzon, A.O. GraphLog: a Visual Formalism for Real Life Recursion. In: Proceedings of the 9th ACM Symposium on Principles of Data- base Systems. 1990, pp. 404–416.

Wood, P.T.: Factoring Augmented Reg- ular Chain Programs. In: Proceedings of the 16th International Conference on Very Large Data Bases (VLDB). 1990, pp. 255– 263. Morgan Kaufmann Publishers Inc.

Abiteboul S., Quass D., McHugh J., Wi- dom J., Wiener J.L. The Lorel query lan- guage for semistructured data. Interna- tional Journal on Digital Libraries, 1997, 1(1), pp. 68–88.

Flesca, S., Greco, S.: Partially Ordered Regular Languages for Graph Queries. In: Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP). LNCS, 1999, pp. 321–330. 2001, 217 p. - https://pure.tue.nl/ws/ files/2236754/200142116.pdf

Buneman P., M. Fernandez, Suciu D. UnQL: A Query Language and Algebra for Semistructured Data Based on Struc- tural Recursion. The VLDB Journal, 2000, 9(1), pp. 76-110.

Hidders A.J.H. A Graph-based Up- date Language for Object-Orient- ed Data Models. Thesis (doctoral)- Technische Universiteit Eindhoven, 2001, 217 p. - https://pure.tue.nl/ws/ files/2236754/200142116.pdf

Cardelli L., Gardner P., Ghelli G.: A Spa- tial Logic for Querying Graphs. In: Pro- ceedings of the 29th International Col- loquium on Automata, Languages, and Programming (ICALP). 2002, pp. 597–

LNCS, Springer

Theodoratos D. Semantic Integration and Querying of Heterogeneous Data Sourc- es Using a Hypergraph Data Model. In: Proceedings of the 19th British National Conference on Databases (BNCOD), Advances in Databases. 2002, pp. 166– 182. LNCS, Springer.

Leser U. A query language for biological networks. Bioinformatics, 2005, 21(2), pp. 33-39

Liu Y.A., Stoller S.D. Querying complex graphs. In: Proc. of the 8th Int. Sympo- sium on Practical Aspects of Declarative Languages. 2006, pp. 16–30

Prud’hommeaux, E., Seaborne, A. SPARQL Query Language for RDF. W3C Rec- ommendation. (January 15 2008)

Ronen R., Shmueli O. SoQL: a language for querying and creating data in social networks. In: Proceedings of the inter- national conference on data engineering (ICDE). IEEE Computer Society, New York, 2009, pp 1595–1602

Dries A, Nijssen S., De Raedt L. A query language for analyzing networks. Proceed- ings of the 18th ACM conference on Infor- mation and knowledge, 2009, pp. 485-494

Rodriguez M.A. The Gremlin graph tra- versal machine and language (invited talk). In: DBPL 2015: Proceedings of the 15th Symposium on Database Program- ming Languages. ACM, New York, 2015, pp 1–10

San Martin M., Gutierrez C., Wood P.T. SNQL: A social networks query and transformation language. In: Barcelo, P. and Tannen, V. (eds.) Proceedings of the 5th Alberto Mendelzon International Workshop on Foundations of Data Management. CEUR Workshop Proceedings. CEUR-WS.org. 2011.

Cypher - Graph Query Language -http://neo4j.com/developer/cypher-query-lan- guage/

Barcelo P., Libkin L., Lin A.W., Wood

P.T. Expressive languages for path que-

ries over graph-structured data. ACM

Transactions on Database Systems, 2012,

Vol. 37, No 4, pp. 1–46.

Santini S.: Regular Languages with Variables on Graphs. Information and Computation, 2012, Vol. 211, pp. 1–28.

Feigenbaum L , Williams G.T., Clark K.G., Torres E. SPARQL 1.1 Protocol. W3C Recommendation. http://www. w3.org/TR/2013/REC-sparql11-proto- col-20130321/, March 21, 2013.

van Rest O., Hong S., Kim J., Meng X., Chafi H. PGQL: a property graph query language. In: Proceedings of the international workshop on graph data management experiences and systems (GRADES), 2013

Libkin L., Martens W., Vrgoc D. Query- ing Graph Databases with XPath. In: Pro- ceedings of the 16th International Confer- ence on Database Theory (ICDT), 2013, pp. 129–140

Brijder R., Gillis J.J.M., Van den Buss- che J. (2013) The DNA query language DNAQL. In: ICDT ‘13: Proceedings of the 16th International Conference on Da- tabase Theory, 2013, pp. 1–9

Reutter J.L., Romero M., Vardi M.Y.: Regular queries on graph databases. In: Proceedings of the 18th International

Conference on Database Theory (ICDT). 2015, pp. 177–194.

GraphQL: A data query language. https://code.fb.com/core-data/graphql-a-data-query-language/

Masseroli M., Pinoli P., Venco F., Kai-

toua A., Jalili V., Paluzzi F., Muller H.,

Ceri S. GenoMetric Query Language: A

novel approach to large-scale genomic

data management. Bioinformatics, 2015,

(12), pp. 1881-1888.

Giugno R., Shasha D. GraphGrep: a

fast and universal method for querying

graphs. In: Proceedings of the 16th Inter-

national Conference on Pattern Recogni-

tion, 2002. pp. 112–115.

He H., K. Singh A. Graphs-at-a-time:

query language and access methods for

graph databases. In: Proceedings of the

ACM SIGMOD International Confer-

ence on Management of Data; 2008. p.

–418.

Milo T., Suciu D.. Index structures for

path expressions. In: Proceedings of the

th International Conference on Database

Theory; 1999. pp. 277–295.

Picalausa F., Luo Y., Fletcher G.H.L., Hidders J, Vansummeren S. A structural approach to indexing triples. In: Proceedings of the 9th Extended Semantic Web Conference; 2012. p. 406–421.

Trißl S., Leser U. Fast and practical indexing and querying of very large graphs. In: Proceedings of the ACM SIGMOD International Conference on Management of Data; 2007. p. 845–856.

Calvanese D., De Giacomo G., Lenzerini M., Vardi M.Y. Reasoning on regular path queries. SIGMOD Rec. 2003;32(4):83–92.

Fernandez M., Suciu D. Optimizing regu- lar path expressions using graph schemas. In: Proceedings of the 14th International Conference on Data Engineering; 1998. p. 14–23.

Goldman R., Widom J. DataGuides: en- abling query formulation and optimiza- tion in semistructured databases. In: Pro- ceedings of the 23rd International Confer- ence on Very Large Data Bases; 1997. p. 436–445.

Urbón P. NoSQL graph database ma- trix. - http://nosql.mypopescu.com/

post/619181345/nosql-graph-database-

matrix

Deepak Singh Rawat, Navneet Kumar

Kashyap. Graph Database: A Complete

GDBMS Survey.International Journal for

Innovative Research in Science & Tech-

nology ( IJIRST), 2017, Vol. 3, No 12, pp.

-226.

Pradeep Jadhav, Ruhi Oberoi. Compara-

tive Analysis of Different Graph Data-

bases, International Journal of Engineer-

ing Research & Technology (IJERT), Vol.

, No 9, 2014, pp. 820-824.

Stonebraker M., Madden S.R., Abadi D.J., Harizopoulos S., Hachem N.I. The End of an Architectural Era (It’s Time for

a Complete Rewrite). - VLDB ‘07: Proceedings of the 33rd international conference on Very large data bases September 2007 Pages 1150–1160.

R. Kallman, H. Kimura, J. Natkins, A. Pavlo, A. Rasin, S. Zdonik, E. Jones, S. Madden, M. Stonebraker, Y. Zhang,

J. Hugg & D. Abadi, "H-store: a high-performance, distributed main memory transaction processing system", Proceed-

ings of the VLDB Endowment, Volume 1 Issue 2, August 2008, pages 1496-1499.

M. Stonebraker, D. Abadi, A. Batkin, X. Chen, M. Cherniack, M. Ferreira, E. Lau, A. Lin, S. Madden, E. O’Neil, P. O’Neil,

A. Rasin, N.Tran & S. Zdonik, “C-store: a column-oriented DBMS,” Proceedings of the 31st International Conference on Very Large Data Bases (VLDB ’05), 2005, pages 553 – 564.

Cattell Rick. “Scalable SQL and NoSQL

data stores,” ACM SIGMOD Record 39.4 (2011): 12-27.

Matthew A. (2011). “How Will The Data- base Incumbents Respond To NoSQL And NewSQL?”. 451 Group - https://www.cs.cmu.edu/~pavlo/courses/fall2013/stat- ic/papers/aslett-newsql.pdf

Matthew A. (2011).” What we talk about when we talk about NewSQL”. 451 Group - https://blogs.451research.com/informa- tion_management/2011/04/06/what-we- talk-about-when-we-talk-about-newsql/

Stonebraker Mil. NewSQL: An Alter-native to NoSQL and Old SQL for New OLTP Apps. Communications of the ACM Blog. - https://cacm.acm.org/blogs/ blog-cacm/109710-new-sql-an-alterna-tive-to-nosql-and-old-sql-for-new-oltp-apps/fulltext

Pavlo A., Aslett M. What’s Really New with NewSQL?. SIGMOD Record, June 2016, Vol. 45, No. 2. pp. 45-55

Venkatesh, Prasanna (January 30, 2012).NewSQL - The New Way to Handle Big Data - https://www.opensourceforu.com/2012/01/newsql-handle-big-data/

Studer R., Benjamins R., Fensel D. Knowledge engineering: Principles and methods. Data & Knowledge Engineer- ing, 25(1–2):161–198, 1998.

Guarino N., Oberle D., Staab S. What is an ontology? In Handbook on ontologies, pages 1–17. Springer, 2009.

Alexaki S., Christophides V., Karvou-

narakis G., Plexousakis D., Tolle K.: The ICS-FORTH RDFSuite: Managing Volu- minous RDF Description Bases. In: Sem- Web’01: Proceedings of the Second International Conference on Semantic Web

- Volume 40 May 2001, pp. 1–13.

Broekstra J., Kampman A., van Harmelen

F. Sesame: A generic architecture for stor- ing and querying RDFand RDF schema. In Proc. of the First Inter. Semantic Web Conf., pp. 54–68, 2002.

Pan Z., Heflin J.: Dldb: Extending relational databases to support semantic web queries. In: Proceedings of the 1st Inter- national Workshop on Practical and Scalable Semantic Systems (PSSS’03). 2003, pp. 109–113.

Harris S., Gibbins N. 3store: Efficient

bulk RDF storage. In Proc. of the 1st Intern. Workshop on Practical and Scalable Semantic Systems (PSSS’03), 2003. pp. 1-15.

Theoharis Y., Christophides V., Karvounarakis G. (2005) Benchmarking Data- base Representations of RDF/S Stores. In: Gil Y., Motta E., Benjamins V.R., Musen M.A. (eds) The Semantic Web – ISWC 2005. ISWC 2005. Lecture Notes in Computer Science, vol 3729. Springer, Berlin, Heidelberg. pp. 685-701.

McBride B. Jena: Implementing the RDF

Model and Syntax Specification. Sem- Web’01: Proceedings of the Second In- ternational Conference on Semantic Web

- Volume 40, May 2001, pp, 23–28.

Agrawal R., Somani A., Xu Y. Storage and querying of e-commerce data. In: VLDB ’01: Proceedings of the 27th Inter- national Conference on Very Large Data Bases, Morgan Kaufmann Publishers Inc. (2001) 149–158.

Ma L., Su Z., Pan Y., Zhang М, Liu М. Rstar: an rdf storage and query system for enterprise resource management. thir- teenth ACM international conference on Information and knowledge management, 2004:484 – 491.

Erling O., Mikhailov I.: RDF Support in the Virtuoso DBMS. In: Conference on Social Semantic Web (CSSW’07). Vol- ume 113. (2007) 59–68.

Wu Z., Eadon G., Das S., Chong E.I., Kolovski, V., Annamalai, M., Srinivasan, J.: Implementing an Inference Engine for RDFS/OWL Constructs and User-Defined Rules in Oracle. In: Proceed-

ings of the 24th International Conference on Data Engineering (ICDE’08). (2008) 1239–1248.

Alexaki S., Christophides V., Karvounarakis G., Plexousakis D., Tolle K. On storing voluminous rdf descriptions: The

case of web portal catalogs. In Proceed-

ings of the Fourth International Work-

shop on the Web and Databases, WebDB

, Santa Barbara, California, USA,

May 24-25, 2001, in conjunction with

ACM PODS/SIGMOD 2001: 43-48

Abadi D.J., Marcus A., Madden S.R.,

Hollenbach K. Scalable Semantic Web

Data Management Using Vertical Parti-

tioning. In: Proceedings of the 33rd Inter-

national Conference on Very Large Data

Bases (VLDB’07). (2007) 411–422

Jing L., Li M.,Lei Z., Jean-Sébastien B., Chen W., Yue P., Yong Y., 2007. SOR: A Practical System for Ontology Storage, Reasoning. In VLDB 2007, 33rd Very Large Data Bases Conference,pp 1402- 1405.

Dehainsala H., Pierra G., Bellatreche L. (2007) OntoDB: An Ontology-Based Da- tabase for Data Intensive Applications. In: Kotagiri R., Krishna P.R., Mohania M., Nantajeewarawat E. (eds) Advances in Databases: Concepts, Systems and Ap- plications. DASFAA 2007. Lecture Notes in Computer Science, vol 4443. Springer, Berlin, Heidelberg. pp 497-508.

Park M.J., Lee J.H., Lee C.H., Lin J., Serres O., Chung C.W.: An Efficient and Scalable Management of Ontology. In: Proceedings of the 12th International Conference on Database Systems for Advanced Applications (DASFAA’07). (2007) 975–980.

Wilkinson K., Sayers C., Kuno H., Reynolds D. 2003. Efficient RDF storage and Retrieval in Jena2. Proceedings of the 1st International Workshop on Semantic Web Database (SWDB’03). pp. 131–150.

SWAD-Europe Deliverable 10.2: Mapping Semantic Web Data with RDBMSes. https://www.w3.org/2001/sw/Europe/reports/scalable_rdbms_mapping_report/

Bailey J., Bry F., Furche T., Schaffert S. (2005) Web and Semantic Web Query Languages: A Survey. In: Eisinger N., Małuszyński J. (eds) Reasoning Web. Lecture Notes in Computer Science, vol 3564. Springer, Berlin, Heidelberg, 2005, pp. 35–133.

Jean S., Aït-Ameur Y., Pierra G. (2006) Querying Ontology Based Database Using OntoQL (An Ontology Query Language). In: Meersman R., Tari Z. (eds) On the Move to Meaningful Internet Systems 2006: CoopIS, DOA, GADA, and ODBASE. OTM 2006. Lecture Notes in Computer Science, vol 4275. Springer, Berlin, Heidelberg. pp 704-721.

а. Melichar B., Holub J., Polcar T. Text searching algorithms Volume I: Forward string matching. Czech Technical University in Prague, 224 p. /http://www.stringology.org/athens/TextSearchingAl-gorithms/tsa-lectures-1.pdf

Melichar B., Holub J., Polcar T. Text searching algorithms Volume II: Back-ward string matching. Czech Technical University in Prague, 61 p.- http://www. stringology.org/athens/TextSearchingAl- gorithms/tsa-lectures-2.pdf

Hakak S., Kamsin A., Shivakumara P., Gilkar G., Khan W.Z., Imran M. Exact String Matching Algorithms: Survey, Issues, and Future Research Directions. IEEE Access, 2019, Vol. 7, pp 69614-

Christian Charras, Thierry Lecroq. Hand- book of exact string matching algorithms. College Publications (February 27, 2004), 256 p. - http://www-igm.univ- mlv.fr/~lecroq/string/string.pdf

Faro S. Exact Online String Matching Bibliography. 2016, 23 p. - https://arxiv.org/abs/1605.05067

Faro S., Lecroq T., Borzi, Di Mauro S., Maggio A.. The String Matching Algorithms Research Tool. Stringology 2016:

-111.

Faro S. Lecroq T, The exact online string matching problem: A review of the most recent results, ACM Comput. Survey, Article 13, 42 pages, February 2013.

Koloud Al-Khamaiseh, Shadi AL Shagarin. A Survey of String Matching Algorithms. Int. Journal of Engineering Re-

search and Applications, 2014, vol. 4, No

, pp.144-156

Morris, J.H., Jr; Pratt, V. (1970). A linear

pattern-matching algorithm (Technical

report). University of California, Berke-

ley, Computation Center. TR-40.

Knuth, Donald E. (1973). “The Dangers

of Computer-Science Theory”. Studies in

Logic and the Foundations of Mathemat-

ics. 74: 189–195.

Knuth D., Morris J.H., Pratt V. (1977).

“Fast pattern matching in strings”. SIAM

Journal on Computing. 6 (2): 323–350.

Matiyasevich, Yuri (1973). “Real-time

recognition of the inclusion relation”.

Journal of Soviet Mathematics. 1: 64–70

Boyer R.S., Moore J.S. A fast string

searching algorithm. Communications of

the ACM. 1977, vol. 20, No 10. pp. 762—

— doi:10.1145/359842.359859.

Baeza-Yates R., Gonnet G.H. A new ap-

proach to text searching. Communications

of the ACM, Vol. 35, No 10,1992 pp 74–82.

- https://doi.org/10.1145/135239.135243

Алгоритм Бойера-Мура - https://

ru.wikipedia.org/wiki/%D0%90%D0%B

B%D0%B3%D0%BE%D1%80%D0%B

%D1%82%D0%BC_%D0%91%D0%B

E%D0%B9%D0%B5%D1%80%D0%B0

_%E2%80%94_%D0%9C%D1%83%D1

%80%D0%B0

Horspool R.N. Practical fast searching

in strings, Software - Practice & Experi-

ence, 1980, 10(6) :501-506.

Zhu R.F., Takaoka T., 1987, On improv-

ing the average case of the Boyer-Moore

string matching algorithm, Journal of In-

formation Processing 10(3):173-177.

Turbo-BM algorithm - http://www-igm.univ-mlv.fr/~lecroq/string/node15.html

CROCHEMORE, M., CZUMAJ A., GASIENIEC L., JAROMINEK S., LECROQ T., PLANDOWSKI W., RYTTER W., 1992, Deux méthodes pour accélérer l’algorithme de Boyer-Moore, in Théorie des Automates et Applications, Actes des 2e Journées Franco-Belges, D. Krob ed.,

Rouen, France, 1991, pp 45-63, PUR 176, Rouen, France.

Apostolico A., Giancarlo R. The Boyer-Moore-Galil String Searching Strategies Revisited,” (in English), SIAM Journal

on Computing, vol. 15, No. 1, pp. 98-105,

Feb 1986.

Smith P.D., “Experiments with a very fast

substring search algorithm,” Software-

Practice and Experience, vol. 21, no. 10,

pp. 1065-1074, 1991.

Raita T. Tuning the Boyer-Moore-Hor-

spool string searching algorithm. Soft-

ware-Practice and Experience, vol. 22,

no. 10,pp. 879-884, 1992.

Crochemore M., Czumaj A., Gasieniec

L., Jarominek S., Lecroq T., Plandowski

W. Rytter W. “Speeding up two string-

matching algorithms,” Algorithmica

(4-5):247-267, 1994.

Berry T., Ravindran, S. (2001) A Fast

String Matching Algorithm and Ex-

perimental Results. Proceedings of the

Prague Stringology Club Workshop ’99,

Collaborative Report DC-99-05, Czech

Technical University, Prague, 16-26.

Sunday D.M. “ A very fast substring

search algorithm,” Communications of

the ACM, Vol. 33, No 8, 1990 pp 132–142.

- https://doi.org/10.1145/79173.79184.

Colussi L. Correctness and efficiency of

pattern matching algorithms. Information

and Computation, vol. 95, no. 2, pp. 225-

, 1991.

Xian-feng H., Yu-bao Y., Xia L. “Hybrid

pattern-matching algorithm based on BM-

KMP algorithm.” (ICACTE) 2010 3rd In-

ternational Conference on Advanced Com-

puter Theory and Engineering(ICACTE),

, pp. V5-310-V5-313, DOI: 10.1109/

ICACTE.2010.5579620.

Cao Z., Zhenzhen Y., Lihua L. “A fast

string matching algorithm based on low-

light characters in the pattern.” In Ad-

vanced Computational Intelligence (ICA-

CI), 2015 Seventh International Confer-

ence on, pp. 179-182. IEEE, 2015.

Hakak S., Kamsin A., Shivakumara P.,

Idna Idris M.Y., Gilkar G.A. “A new split

based searching for exact pattern match-

ing for natural texts.” PloS ONE 13, no. 7

(2018): e0200912. Skid

Hakak S., Amirrudin K., Shivakumara P., Idna Idris M.Y. Partition-Based Pattern Matching Approach for Efficient Retrieval Of Arabic Text.” Malaysian Journal of Computer Science 31, no. 3

(2018): 200-209.

Franek F., Jennings C.G., Smyth W.F. A simple fast hybrid pattern-matching algorithm. J. Discrete Algorithms, 5(4):682–

, 2007.

Rabin M.O., Karp R.M. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development. 1987, vol. 31, No 2, pp. 249–260. — doi:10.1147/rd.312.0249.

Rabin–Karp algorithm. - https://en.wikipedia.or g/wiki/ Rabin%E2%80%93Karp_algorithm

Wu S., Manber U. “A fast algorithm for multi-pattern searching,” Department of Computer Science, University of Arizo- na, Tucson, AZ, Report TR-94-171994.

Kim S., Kim Y., “A fast multiple string pattern matching algorithm,” in Proceed- ings of 17th AoM/IAoM Conference on

-Computer Science, 1999, pp. 44-49.

Simone F. “A very fast string matching

algorithm based on condensed alpha-

bets.” In International Conference on Al-

gorithmic Applications in Management,

pp. 65-76. Springer, Cham, 2016.

Lecroq T. “Fast exact string matching

algorithms,”Information Processing Let-

ters, vol. 102, no. 6, pp. 229-235, Jun 15

Kalsi P., Peltola H., Tarhio J. “Compari-

son of exact string matching algorithms

for biological sequences,” in Proceedings

of the Second International Conference

on Bioinformatics Research and Devel-

opment, BIRD, 2008. pp. 417-426.

Daciuk J., Mihov S, Watson B., Watson

R. Incremental construction of minimal

acyclic finite state automata. Computa-

tional Linguistics, 2000, 26(1), pp.3-16.

Yang. W. Mealy machines are a better

model of lexical analyzers. Computer

Languages, Vol. 22, No 1, 1996, pp. 27-38

Blumer A., Blumer J., Ehrenfeucht A.,

Haussler D., McConnel R. Linear size fi-

nite automata for the set of all subwords

of a word: an outline of results. Bull.

European Assoc. Theoret. Comput. Sci.,

:12-20, 1983.

Commentz-Walter B. A string matching algorithm fast on the average. Proceedings of the 6th Colloquium, on Automata, Languages and Programming, 1979, pp. 118–132.

Allauzen C., Raffinot M. Simple optimal string matching algorithm, Journal of Algorithms, Vol. 36, No 1, 2000, pp. 102–116.

Allauzen C., Crochemore M., Raffinot M. Factor oracle: A new structure for pattern matching. In 26th Seminar on Cur- rent Trends in Theory and Practice of Informatics (SOFSEM’99), Nov 1999, Milovy, Czech Republic, Czech Repub- lic. pp.291-306.

Faro S., Lecroq T. Efficient variants of the Backward-Oracle-Matching algorithm. In Proceedings of the Prague Stringology Conference, Czech Republic, 2008, pp. 146-160: Czech Technical University.

Fan H., Yao N., Ma H. Fast variants of the backward-oraclemarching algorithm. In Fourth International Conference on Internet Computing for Science and Engineering, 2009, pp. 56-59.

He L., Fang B., Sui J. The wide window

string matching algorithm. Theoretical

Computer Science, vol. 332, no. 1-3,

, pp. 391-404.

Liu C., Wang Y., Liu D., Li D. Two im-

proved single pattern matching algo-

rithms. In ICAT Workshops, Hangzhou,

China„ 2006, pp. 419-422: IEEE Com-

puter Society.

Hongbo F., Shupeng S., Jing Z., Li D.

Suffix Type String Matching Algorithms

Based on Multi-windows and Integer

Comparison. In International Conference

on Information and Communications

Security, pp. 414-420. Springer, Cham,

Masaki Waga, Ichiro Hasuo, Kohei

Suenaga. “Efficient online timed pattern

matching by automata-based skipping.”

In International Conference on Formal

Modeling and Analysis of Timed Sys-

tems, pp. 224-243. Springer, Cham, 2017.

Bitap algorithm. - https://en.wikipedia.

org/wiki/Bitap_algorithm

Bálint Dömölki, An algorithm for syntac-

tical analysis, Computational Linguistics

, Hungarian Academy of Science pp.

–46, 1964.

Bálint Dömölki, A universal compiler

system based on production rules, BIT

Numerical Mathematics, 8(4), pp 262–

, 1968. doi:10.1007/BF01933436

Shyamasundar R.K. Precedence parsing

using Dömölki’s algorithm, International

Journal of Computer Mathematics, 6(2)

pp 105–114, 1977.

Baeza-Yates R., Gonnet G.H. A new ap-

proach to text searching. Communica-

tions of the ACM, Vol. 35, No 10,1992 pp

–82

Ricardo A. Baeza-Yatesm Gaston H. Gon-

net. A New Approach to Text Searching.

Communications of the ACM, 1992, vol.

, No 10, pp. 74-82 - ПОВТОРЕНИЕ 5а)

Fredriksson K., Grabowski S. Practical

and optimal string matching. In SPIRE’05:

Proceedings of the 12th international con-

ference on String Processing and Infor-

mation Retrieval, 2005, pp. 376–387. -

https://doi.org/10.1007/11575832_42

Salmela L., Tarhio J., Kytojoki J. Multi

pattern string matching with q-grams.

Journal of Experimental Algorithms,

, Vol. 11, pp. 1-19

Udi Manber, Sun Wu. “Fast text search

allowing errors.” Communications of the

ACM, 35(10): pp. 83–91, October 1992,

doi:10.1145/135239.135244.

R. Baeza-Yates and G. Navarro. A faster

algorithm for approximate string match-

ing. In Dan Hirchsberg and Gene Myers,

editors, Combinatorial Pattern Matching

(CPM’96), LNCS 1075, pages 1–23, Ir-

vine, CA, June 1996.

G. Myers. “A fast bit-vector algorithm for approximate string matching based on dynamic programming.” Journal of the ACM 46 (3), May 1999, 395–415.

Navarro G., Raffinot M. A Bit-parallel Approach to Suffix Automata: Fast Ex- tended String Matching. In Proc CPM’98, Lecture Notes in Computer Science 1448: 14-33, 1998.

Navarro G., Raffinot M. Fast and flexible string matching by combining bit-paral- lelism and suffix automata. ACM Journal. Experimental Algorithmics,2000, 5(4):1-36.

Peltola H., Tarhio J. Alternative Algo- rithms for Bit-Parallel String Matching. In String Processing and Information Re-

trieval, Spire Springer, LNCS 2857, pp.

-93, 2003.

Branislav Durian, Jan Holub, Hannu Pel-

tola and Jarma Tarhio,”Tuning BNDM

with q-grams”, In the proc. Of workshop

on algorithm engineering and experi-

ments, SIAM USA, pp. 29-37, 2009.

Miao C., Chang G., Wang X. Filtering

Based Multiple String Matching Algo-

rithm Combining q-Grams and BNDM.

In ICGEC ‘10: Proceedings of the 2010

Fourth International Conference on Ge-

netic and Evolutionary Computing, 2010,

pp. 82–585. - https://doi.org/10.1109/IC-

GEC.2010.149

Faro S., Lecroq T. Efficient variants of

the backward-oracle-matching algorithm.

International Journal of Foundations of

Computer Science, vol. 20, no. 6, pp.

–984, Dec. 2009,

Peltola H., Tarhio J. (2003) Alterna-

tive Algorithms for Bit-Parallel String

Matching. In: Nascimento M.A., de

Moura E.S., Oliveira A.L. (eds) String

Processing and Information Retrieval.

SPIRE 2003. pp. 80-93. Lecture Notes in

Computer Science, vol 2857. Springer,

Berlin, Heidelberg.

M. Oguzhan Külekci, Filter based fast matching of long patterns by using SIMD instructions, in Proceedings of the Prague Stringology Conference, Prague, Czech Republic, 2009. pp. 118-128.

M. Oguzhan Külekci, A method to overcome computer word size limitation in bit-parallel pattern matching, in Proceedings of the 19th International Symposium on Algorithms and Computation, ISAAC, 2008. pp. 496-506.

Gupta S., Rasool A. Bit Parallel String Matching Algorithms: A Survey. Interna- tional Journal of Computer Applications, 2014, vol. 95, No 10, pp. 27-32.

M. Crochemore, A. Czumaj, L. GaÌ˘gsieniec, T. Lecroq, W. Plandowski, and W. Rytter, “Fast practical multi-pat- tern matching,” Information Processing Letters, vol. 71, no. 3-4, pp. 107-113,

Aug 27 1999.

G. Navarro, Nrgrep: A fast and flexible pattern matching tool. Software—Prac- tice & Experience, Vol. 31, No 13, 2001, pp. 1265–1312. - https://doi.org/10.1002/spe.411.

F. Franek, Jennings, C. G., and Smyth, W.F., A simple fast hybrid pattern-matching algorithm,” J. Discret. Algorithms, pp. 682-695, 2007.

S. Deusdado and P. Carvalho, “GRASPm: an efficient algorithm for exact pattern-matching in genomic sequences,” Int J

Bioinform Res Appl, vol. 5, no. 4, pp. 385-401, 2009.

P. Shivendra Kumar, H. K. Tiwari, and P. Tripathi. Hybrid approach to reduce time complexity of string matching algorithm using hashing with chaining. In Proceedings of International Conference on ICT for Sustainable Development, pp. 185-193. Springer, Singapore, 2016.

Hamming R. W. Error detecting and error correcting codes. The Bell System Technical Journal. 1950, 29 (2): 147–160.

Levenshtein V.I. Binary codes with correction of dropouts, insertions and substitutions of symbols (RUS). Reports of the Academy of Sciences of the USSR, 1965. 163.4: 845-848.

Levenshtein, Vladimir I. (February 1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 1966. 10 (8): 707–710.

Dan Gusfield. Algorithms on stings, trees, and sequences: Computer science and computational biology ACM SIGACT News, Vol. 28, No 4, Dec. 1997, pp. 41–60 - https://doi.org/10.1145/270563.571472

Damerau F.J. A technique for computer

detection and correction of spelling er-

rors. Communications of the ACM, 1964,

vol. 7, No 3, pp 171–176.

Winkler, W. E. (1990). “String Com-

parator Metrics and Enhanced Decision

Rules in the Fellegi-Sunter Model of

Record Linkage” (PDF). Proceedings of

the Section on Survey Research Meth-

ods. American Statistical Association:

–359.

Jaro, M. A. Advances in record link-

age methodology as applied to the 1985

census of Tampa Florida Journal of the

American Statistical Association. 1989,

Vol. 84, No. 406, pp. 414-420.

Longest common subsequence problem.

- https://en.wikipedia.org/wiki/Longest_ common_subsequence_problem

Hall P., Dowling G. Approximate string

matching. ACM Computing Surveys,

(4) :381-402, 1980.

Sankoff D., Kruskal J., editors. Time

Warps. String Edits, arid Macro molecules:

The Theory arid Practice of Sequence

Comparison. Add is on-Wesley, 1983.

Apostolico A., Galil Z. Combinatorial

Algorithms on Words. NATO ISI Series.

Springer-Verlag, 1985.

Galil Z., Giancarlo R. Data structures and

algorithms for approximate string match-

ing. Journal of Complexity, Vol. 4, No 1,

, pp. 33-72.

Jokinen P, Tarhio J, Ukkonen E. A com-

parison of approximate string matching

algorithms. Software Practice arid Expe-

rience, 26(12): 1439-1458,1996.

Navarro G. A guided tour to approximate

string matching. ACM Computing Sur-

veys, Vol. 33, No , 1, 2001, pp 31–88.

Syeda Shabnam Hasan, F. Ahmed, Rosina

Surovi Khan. Approximate String Match-

ing Algorithms: A Brief Survey and Com-

parison. International Journal of Com-

puter Applications, 2015, Vol. 120, No. 8,

pp. 26-31.

Licklider J.C.R. Libraries of the future.

Cambridge, MA: The MIT Press; 1965.

Charles P. Bourne, Trudi Bellardo Hahn.

A History of Online Information Servic-

es, 1963-1976. MIT Press, 2003, 496 p.

Project Gutenberg. - https://en.wikipedia.

org/wiki/Project_Gutenberg

Schatz B. (1996). Chen H. (ed.). “Build-

ing large-scale digital libraries”. IEEE

Computer. 29 (5): 22–25.

Functional Requirements for Bibliograph-

ic Records, Final Report / IFLA Study

Group on the Functional Requirements

for Bibliographic Records. – München:

K.G. Saur, 1998.

Crofts N., Doerr M., Gill T., Stead S.,,

Stiff M. (editors), Definition of the CI-

DOC Conceptual Reference Model, Janu-

ary 2008. Version 4.2.4.

CERIF in Brief. - https://www.eurocris.

org/eurocris_archive/cerifsupport.org/

cerif-in-brief/index.html

David Shotton. Introduction the Semantic Publish-ing and Referencing (SPAR) Ontologies. October 14, 2010. http://opencitations.wordpress.com/ 2010/10/14/introducing-the-semantic-publishing-and-referencing-spar-ontologies/

Candela L., Castelli D., Fuhr N., Ioan-

nidis Y., Klas C.-P., Pagano P., Ross

S., Saidis C., Schek H.-J., Schuldt H.,

Springmann M. Current Digital Library

Systems: User Requirements vs Provided

Functionality. IST-2002- 2.3.1.12. Tech-

nology-enhanced Learning and Access to

Cultural Heritage. March 2006.

Candela L., Castelli D., Ioannidis Y., Koutrika G., Pagano P., Ross S., Schek H.J., Schuldt H. Setting the foundations of digital libraries: the DELOS manifes- to. D-Lib Mag. 2007;13(3/4).

Candela L., Castelli D., Dobreva M., Ferro N., Ioannidis Y., Katifori H., Koutrika G., Meghini C., Pagano P., Ross S., Agosti M., Schuldt H., Soergel D. The DELOS Digital Library Reference Model Foundations for Digital Libraries. IST-2002-2.3.1.12. Technology-enhanced Learning and Access to Cultural Heritage. Version

98, December 2007.

Goncalves M.A., Fox E.A.., Watson L.T. and Kipp N.A. Streams, structures, spaces, sce- narios, societies (5S): A formal model for digital libraries. ACM Transactions on Infor- mation Systems. 22(2), 2004, p. 270–312.


Refbacks

  • There are currently no refbacks.