♦

Charles William “Charlie” Bachman III (born December 11, 1924) is an American computer scientist, who spent his entire career as an industrial researcher, developer, and manager rather than in academia. He is particularly known for his work in the early development of database management systems. His techniques of layered architecture include his namesake Bachman diagrams.

Biography

Charles Bachman was born in Manhattan, Kansas in 1924, where his father, Charles Bachman Jr., was the head football coach at Kansas State College. He attended high school in East Lansing, Michigan.

In World War II he joined the United States Army and spent March 1944 through February 1946 in the South West Pacific Theater serving in the Anti-Aircraft Artillery Corps in New Guinea, Australia, and the Philippine Islands. There he was first exposed to and used fire control computers for aiming 90 mm guns.^[2]

After his discharge in 1946 he attended Michigan State College and graduated in 1948 with a bachelor’s degree in Mechanical Engineering where he was a member of Tau Beta Pi. In mid-1949 he married Connie Hadley.^[3] He then attended the University of Pennsylvania. In 1950, he graduated with a master’s degree in Mechanical Engineering, and had also completed three-quarters of the requirements for an MBA from the university’s Wharton School of Business.^[2]

Work

Bachman spent his entire career as a practicing software engineer or manager in industry rather than in academia. In 1950 he started working at Dow Chemical in Midland, Michigan. In 1957 he became Dow’s first data processing manager. He worked with the IBM user group SHARE, on developing new version of report generator software, which became known as 9PAC. However, the planned IBM 709 order was cancelled before it arrived.^[4] In 1960 he joinedGeneral Electric, where by 1963 he developed the Integrated Data Store (IDS) one of the first database management systems using what came to be known as the navigational database model in the Manufacturing Information And Control System (MIACS) product. Working for customer Weyerhaeuser Lumber, he developed the first multiprogramming network access to the IDS database, an early online transaction processing system called WEYCOS in 1965. Later at GE he developed the “dataBasic” product that offered database support to the Basic language timesharing users. In 1970, GE sold its computer business to Honeywell Information Systems, and so he an his family moved from Phoenix, Arizona to Lexington, Massachusetts.^[5]

He received the Turing Award from the Association for Computing Machinery (ACM) in 1973 for “his outstanding contributions to database technology”. He was elected as a Distinguished Fellow of the British Computer Society in 1977 for his pioneering work in database systems.^[6] In 1981, he joined a smaller firm, Cullinane Information Systems (later Cullinet), which offered a version of IDS that was called IDMS and supported IBM mainframes.^[5]

Bachman Information Systems

In 1983, he founded Bachman Information Systems, which developed a line of computer-aided software engineering(CASE) products. The centerpiece of these products was the BACHMAN/Data Analyst, which provided graphic support to the creation and maintenance of Bachman Diagrams. It was featured in IBM’s Reengineering Cycle marketing program,^{[citation needed]} combining:

1. the reverse engineering of obsolete mainframe databases,
2. data modeling,
3. forward engineering to new physical databases, and
4. optimization of physical database designs for performance and DBMS specifics.

In 1991 Bachman Information Systems had their initial public offering, trading on the NASDAQ with the symbol BACH. After reaching a high of $37.75 in February 1992, the price hit $1.75 in 1995. In 1996, his company merged with Cadre Technology to form Cayenne Software.^[7] He served as president of the combined company for a year, and then retired to Tucson, Arizona. He continued to serve as chairman of the board of Cayenne, which was acquired by Sterling Software in 1998.^[2][8]

Publications

Bachman published dozens of publications and papers.^[9] A selection:

• 1962. “Precedence Diagrams: The Key to Production Planning, Scheduling and Control.” In: ProCo Features. Supplement No 24, August 24. .
• 1965. “Integrated Data Store.” in: DPMA Quarterly, January 1965.
• 1969. “Software for Random Access Processing.” in: Datamation April 1965.
• 1969. “Data Structure Diagrams.” in: DataBase: A Quarterly Newsletter of SIGBDP. vol. 1, no. 2, Summer 1969.
• 1972. “Architecture Definition Technique: Its Objectives, Theory, Process, Facilities, and Practice.” co-authored with J. Bouvard. in: Data Description, Access and Control: Proceedings of the 1972 ACM-SIGFIDET Workshop, November 29-December 1, 1972.
• 1972. “The Evolution of Storage Structures.” In: Communications of the ACM vol. 15, no. 7, July 1972.
• 1972-73. “Set Concept for Data Structure.” In: Encyclopedia of Computer Science, 1972-1973.
• 1973. “The Programmer as Navigator.” 1973 ACM Turing Award lecture. In: Communications of the ACM vol. 16, no. 11, November 1973. (pdf)
• 1974. “Implementation Techniques for Data Structure Sets.” In: Data Base Management Systems, 1974.
• 1977. “Why Restrict the Modeling Capability of Codasyl Data Structure Sets?” In: National Computer Conference vol. 46, 1977.
• 1978. “Commentary on the CODASYL Systems Committee’s Interim Report on Distributed Database Technology.” National Computer Conference vol. 47, 1978.
• 1978. “DDP Will Be Infinitely Affected, So Managers Beware!” in: DM, March 1978.
• 1980. “The Impact of Structured Data Throughout Computer-Based Information Systems.” In: Information Processing 80, 1980.
• 1980. “The Role Data Model Approach to Data Structures.” In; International Conference on Data Bases, March 24, 1980.
• 1982. “Toward a More Complete Reference Model of Computer-Based Information Systems.” Co-authored with Ronald G. Ross. In: Computers and Standards 1, 1982.
• 1983. “The Structuring Capabilities of the Molecular Data Model.” In; Entity-Relationship Approach to Software Engineering. C. G. Davis, S. Jajodia, and R. T. Yeh. eds. June 1983.
• 1987. “A Case for Adaptable Programming.” In: Logic vol. 2, no. 1, Spring 1987.
• 1989. “A Personal Chronicle: Creating Better Information Systems, with Some Guiding Principles.” In: IEEE Transactions on Knowledge and Data Engineering vol. 1, no. 1, March 1989.

After his retirement, Bachman volunteered to help record the history of early software development. In 2002 he gave a lecture at the Computer History Museum on assembling the Integrated Data Store,^[10] and an oral history for the ACM in 2004.^[4] Bachman papers from 1951 to 2007 are available from the Charles Babbage Instituteat the University of Minnesota.^[9] In 2011, he contributed an oral history to the Institute of Electrical and Electronics Engineers.^[5]

Edgar Frank “Ted” Codd (August 19, 1923 – April 18, 2003) was an English computer scientistwho, while working for IBM, invented the relational model for database management, the theoretical basis for relational databases. He made other valuable contributions tocomputer science, but the relational model, a very influential general theory of data management, remains his most mentioned achievement.[6][7]

Database

A database is an organized collection of data. The data are typically organized to model relevant aspects of reality in a way that supports processes requiring this information.

Database management systems (DBMSs) are specially designed software applications that interact with

• the user
• other applications
• and the database itself

to capture and analyze data

A general-purpose DBMS is a software system designed to allow the definition, creation, querying, update, and administration of databases.

Well-known DBMSs include MySQL, MariaDB, PostgreSQL, SQLite, Microsoft SQL Server,Oracle,SAP HANA, dBASE, FoxPro, IBM DB2, LibreOffice Base and FileMaker Pro.

A database is not generally portable across different DBMSs, but different DBMSs can interoperate by using standards such as SQL and ODBC or JDBC to allow a single application to work with more than one database.

Formally, “database” refers to the data themselves and supporting data structures.

Databases are set up so that one set of software programs provides all users with access to all the data.

A “database management system” (DBMS) is a suite of computer software providing the interface between users and a database or databases.

The interactions catered for by most existing DBMSs fall into four main groups:

• Data definition – Defining new data structures for a database, removing data structures from the database, modifying the structure of existing data.
• Update – Inserting, modifying, and deleting data.
• Retrieval – Obtaining information either for end-user queries and reports or for processing by applications.
• Administration – Registering and monitoring users, enforcing data security, monitoring performance, maintaining data integrity, dealing with concurrency control, and recovering information if the system fails.

A DBMS is responsible for maintaining the integrity and security of stored data, and for recovering information if the system fails.

Both a database and its DBMS conform to the principles of a particular database model.[2]“Database system” refers collectively to the

• database model
• database management system
• database

Physically, database servers are dedicated computers that hold the actual databases and run only the DBMS and related software.

Hardware database accelerators, connected to one or more servers via a high-speed channel, are also used in large volume transaction processing environments.

DBMSs may be built around a custom multitasking kernel with built-in networking support, but modern DBMSs typically rely on a standard operating system to provide these functions.[citation needed]

Databases and DBMSs can be categorized according to the

1. database model(s) that they support (such as relational or XML), the type(s) of computer they run on (from a server cluster to a mobile phone),
2. the query language(s) used to access the database (such as SQL or XQuery),
3. and their internal engineering, which affects performance, scalability, resilience, and security.

Client-server or transactional DBMSs are often complex to maintain highperformance,availability and security when many users are querying and updating the database at the same time.

Personal, desktop-based database systems tend to be less complex.

For example, FileMaker and Microsoft Access come with built-in graphical user interfaces.

Increasingly, databases are not only used to support the internal operations of the organization, but also to underpin its online interactions with customers and suppliers (see Enterprise software).

Some general-purpose DBMSs such as Adabas, Oracle and DB2 have been undergoing upgrades since the 1970s.

General-purpose DBMSs aim to meet the needs of as many applications as possible, which adds to the complexity

However, a general-purpose DBMS is not always the optimal solution: in some cases a general-purpose DBMS may introduce unnecessary overhead. Therefore, there are many examples of systems that use special-purpose databases. A common example is an email system

wire protocol

or more likely through an application programming interface.

The development of database technology can be divided into three eras based on data model or structure:

1. navigational
2. SQL/relational
3. post-relational

The two main early navigational data models were the hierarchical model, epitomized by IBM’s IMS system, and the CODASYL model (network model), implemented in a number of products such as IDMS.

The relational model, first proposed in 1970 by Edgar F. Codd, departed from this tradition by insisting that applications should search for data by content, rather than by following links.

The relational model employs sets of ledger-style tables, each used for a different type of entity.

Only in the mid-1980s did computing hardware became powerful enough to allow the wide deployment of relational systems (DBMSs plus applications).

By the early 1990s, however, relational systems dominated in all large-scale data processing applications, and as of 2014 they remain dominant except in niche areas.

The dominant database language, standardised SQL for the relational model, has influenced database languages for other data models.

CODASYL

Edgar F. Codd

Object databases developed in the 1980s to overcome the inconvenience of object-relational impedance mismatch, which led to the coining of the term “post-relational” and also the development of hybrid object-relational databases.

The next generation of post-relational databases in the late 2000s became known as NoSQL databases, introducing fast key-value stores and document-oriented databases. A competing “next generation” known as NewSQL databases attempted new implementations that retained the relational/SQL model while aiming to match the high performance of NoSQL compared to commercially available relational DBMSs.

1960s, navigational DBMS

Further information: Navigational database

The introduction of the term database coincided with the availability of direct-access storage (disks and drums) from the mid-1960s onwards.

The term represented a contrast with the tape-based systems of the past, allowing shared interactive use rather than daily batch processing.

The Oxford English dictionary cites[6] a 1962 report by the System Development Corporation of California as the first to use the term “data-base” in a specific technical sense.

As computers grew in speed and capability, a number of general-purpose database systems emerged; by the mid-1960s a number of such systems had come into commercial use. Interest in a standard began to grow, and Charles Bachman, author of one such product, the Integrated Data Store (IDS), founded the “Database Task Group” within CODASYL, the group responsible for the creation and standardization of COBOL. In 1971 theDatabase Task Group delivered their standard, which generally became known as the “CODASYL approach”, and soon a number of commercial products based on this approach entered the market.

The CODASYL approach relied on the “manual” navigation of a linked data set which was formed into a large network. Applications could find records by one of three methods:

• use of a primary key (known as a CALC key, typically implemented by hashing)
• navigating relationships (called sets) from one record to another
• scanning all the records in a sequential order.

Later systems added B-Trees to provide alternate access paths. Many CODASYL databases also added a very straightforward query language. However, in the final tally, CODASYL was very complex and required significant training and effort to produce useful applications.

IBM also had their own DBMS system in 1968, known as IMS. IMS was a development of software written for the Apollo program on the System/360. IMS was generally similar in concept to CODASYL, but used a strict hierarchy for its model of data navigation instead of CODASYL’s network model. Both concepts later became known as navigational databases due to the way data was accessed, and Bachman’s 1973 Turing Award presentation was The Programmer as Navigator. IMS is classified[by whom?] as a hierarchical database. IDMS andCincom Systems‘ TOTAL database are classified as network databases. IMS remains in use as of 2014.[7]

1970s, relational DBMS[edit]

Edgar Codd worked at IBM in San Jose, California, in one of their offshoot offices that was primarily involved in the development of hard disk systems. He was unhappy with the navigational model of the CODASYL approach, notably the lack of a “search” facility.

In 1970, he wrote a number of papers that outlined a new approach to database construction that eventually culminated in the groundbreaking A Relational Model of Data for Large Shared Data Banks.[8]

In this paper, he described a new system for storing and working with large databases.

• Instead of linked list of free-form records
• “table” of fixed-length records, with each table used for a different type of entity

A linked-list system would be very inefficient when storing “sparse” databases where some of the data for any one record could be left empty. The relational model solved this by splitting the data into a series of normalized tables (or relations), with optional elements being moved out of the main table to where they would take up room only if needed. Data may be freely inserted, deleted and edited in these tables, with the DBMS doing whatever maintenance needed to present a table view to the application/user.

The relational model also allowed the content of the database to evolve without constant rewriting of links and pointers. The relational part comes from entities referencing other entities in what is known as one-to-many relationship, like a traditional hierarchical model, and many-to-many relationship, like a navigational (network) model. Thus, a relational model can express both hierarchical and navigational models, as well as its native tabular model, allowing for pure or combined modeling in terms of these three models, as the application requires.

For instance, a common use of a database system is to track information about users, their name, login information, various addresses and phone numbers. In the navigational approach all of these data would be placed in a single record, and unused items would simply not be placed in the database. In the relational approach, the data would be normalized into a user table, an address table and a phone number table (for instance). Records would be created in these optional tables only if the address or phone numbers were actually provided.

Linking the information back together is the key to this system. In the relational model, some bit of information was used as a “key“, uniquely defining a particular record. When information was being collected about a user, information stored in the optional tables would be found by searching for this key. For instance, if the login name of a user is unique, addresses and phone numbers for that user would be recorded with the login name as its key. This simple “re-linking” of related data back into a single collection is something that traditional computer languages are not designed for.

Just as the navigational approach would require programs to loop in order to collect records, the relational approach would require loops to collect information about anyone record. Codd’s solution to the necessary looping was a set-oriented language, a suggestion that would later spawn the ubiquitous SQL. Using a branch of mathematics known as tuple calculus, he demonstrated that such a system could support all the operations of normal databases (inserting, updating etc.) as well as providing a simple system for finding and returning sets of data in a single operation.

Codd’s paper was picked up by two people at Berkeley, Eugene Wong and Michael Stonebraker. They started a project known as INGRES using funding that had already been allocated for a geographical database project and student programmers to produce code. Beginning in 1973, INGRES delivered its first test products which were generally ready for widespread use in 1979. INGRES was similar to System R in a number of ways, including the use of a “language” for data access, known as QUEL. Over time, INGRES moved to the emerging SQL standard.

IBM itself did one test implementation of the relational model, PRTV, and a production one,Business System 12, both now discontinued. Honeywell wrote MRDS forMultics, and now there are two new implementations: Alphora Dataphor and Rel. Most other DBMS implementations usually called relational are actually SQL DBMSs.

IBM Peterlee Relational Test Vehicle (PRTV)

In 1970, the University of Michigan began development of the MICRO Information Management System[9] based on D.L. Childs’ Set-Theoretic Data model.[10][11][12] Micro was used to manage very large data sets by the US Department of Labor, the U.S. Environmental Protection Agency, and researchers from the University of Alberta, theUniversity of Michigan, and Wayne State University. It ran on IBM mainframe computers using the Michigan Terminal System.[13] The system remained in production until 1998.

Integrated approach

In the 1970s and 1980s attempts were made to build database systems with integrated hardware and software. The underlying philosophy was that such integration would provide higher performance at lower cost. Examples were IBM System/38, the early offering of Teradata, and the Britton Lee, Inc. database machine.

Another approach to hardware support for database management was ICL‘s CAFS accelerator, a hardware disk controller with programmable search capabilities. In the long term, these efforts were generally unsuccessful because specialized database machines could not keep pace with the rapid development and progress of general-purpose computers. Thus most database systems nowadays are software systems running on general-purpose hardware, using general-purpose computer data storage. However this idea is still pursued for certain applications by some companies like Netezza and Oracle (Exadata).

Late 1970s, SQL DBMS

IBM started working on a prototype system loosely based on Codd’s concepts as System R in the early 1970s. The first version was ready in 1974/5, and work then started on multi-table systems in which the data could be split so that all of the data for a record (some of which is optional) did not have to be stored in a single large “chunk”. Subsequent multi-user versions were tested by customers in 1978 and 1979, by which time a standardized query language – SQL[citation needed] – had been added. Codd’s ideas were establishing themselves as both workable and superior to CODASYL, pushing IBM to develop a true production version of System R, known asSQL/DS, and, later, Database 2 (DB2).

Larry Ellison‘s Oracle started from a different chain, based on IBM’s papers on System R, and beat IBM to market when the first version was released in 1978.[citation needed]

Stonebraker went on to apply the lessons from INGRES to develop a new database, Postgres, which is now known as PostgreSQL. PostgreSQL is often used for global mission critical applications (the .org and .info domain name registries use it as their primary data store, as do many large companies and financial institutions).

In Sweden, Codd’s paper was also read and Mimer SQL was developed from the mid-1970s atUppsala University. In 1984, this project was consolidated into an independent enterprise. In the early 1980s, Mimer introduced transaction handling for high robustness in applications, an idea that was subsequently implemented on most other DBMSs.

Another data model, the entity-relationship model, emerged in 1976 and gained popularity fordatabase design as it emphasized a more familiar description than the earlier relational model. Later on, entity-relationship constructs were retrofitted as a data modeling construct for the relational model, and the difference between the two have become irrelevant.[citation needed]

1980s, on the desktop

The 1980s ushered in the age of desktop computing. The new computers empowered their users with spreadsheets like Lotus 1,2,3 and database software like dBASE. The dBASE product was lightweight and easy for any computer user to understand out of the box. C. Wayne Ratliffthe creator of dBASE stated: “dBASE was different from programs like BASIC, C, FORTRAN, and COBOL in that a lot of the dirty work had already been done. The data manipulation is done by dBASE instead of by the user, so the user can concentrate on what he is doing, rather than having to mess with the dirty details of opening, reading, and closing files, and managing space allocation.“ [14] dBASE was one of the top selling software titles in the 1980s and early 1990s.

1980s, object-oriented

The 1980s, along with a rise in object-oriented programming, saw a growth in how data in various databases were handled.

Programmers and designers began to treat the data in their databases as objects.

That is to say that if a person’s data were in a database, that person’s attributes, such as their address, phone number, and age, were now considered to belong to that person instead of being extraneous data. T

his allows for relations between data to be relations to objects and their attributes and not to individual fields.[15]

The term “object-relational impedance mismatch” described the inconvenience of translating between programmed objects and database tables. Object databases and object-relational databases attempt to solve this problem by providing an object-oriented language (sometimes as extensions to SQL) that programmers can use as alternative to purely relational SQL. On the programming side, libraries known as object-relational mappings (ORMs) attempt to solve the same problem.

2000s, NoSQL and NewSQL

The next generation of post-relational databases in the 2000s became known as NoSQL databases, including fast key-value stores and document-oriented databases.XML databases are a type of structured document-oriented database that allows querying based onXML document attributes.

XML databases are mostly used in enterprise database management, where XML is being used as the machine-to-machine data interoperability standard. XML databases are mostly commercial software systems, that include Clusterpoint,[16] MarkLogic[17]and Oracle XML DB.[18]

NoSQL databases are often very fast, do not require fixed table schemas, avoid join operations by storing denormalized data, and are designed to scale horizontally. The most popular NoSQL systems include MongoDB, Couchbase, Riak, memcached, Redis, CouchDB, Hazelcast, Apache Cassandra and HBase,[19] which are all open-source software products.

In recent years there was a high demand for massively distributed databases with high partition tolerance but according to the CAP theorem it is impossible for adistributed systemto simultaneously provide consistency, availability and partition tolerance guarantees. A distributed system can satisfy any two of these guarantees at the same time, but not all three. For that reason many NoSQL databases are using what is called eventual consistency to provide both availability and partition tolerance guarantees with a maximum level of data consistency.

NewSQL is a class of modern relational databases that aims to provide the same scalable performance of NoSQL systems for online transaction processing (read-write) workloads while still using SQL and maintaining the ACID guarantees of a traditional database system. Such databases include Clustrix, EnterpriseDB, NuoDB[20] andVoltDB.

Research

Database technology has been an active research topic since the 1960s, both in academia and in the research and development groups of companies (for example IBM Research). Research activity includes theory and development of prototypes. Notable research topics have included models, the atomic transaction concept and relatedconcurrency control techniques, query languages and query optimization methods, RAID, and more.

The database research area has several dedicated academic journals (for example, ACM Transactions on Database Systems-TODS, Data and Knowledge Engineering-DKE) and annualconferences (e.g., ACM SIGMOD, ACM PODS, VLDB, IEEE ICDE).

Examples

One way to classify databases involves the type of their contents, for example: bibliographic, document-text, statistical, or multimedia objects. Another way is by their application area, for example: accounting, music compositions, movies, banking, manufacturing, or insurance. A third way is by some technical aspect, such as the database structure or interface type. This section lists a few of the adjectives used to characterize different kinds of databases.

• An in-memory database is a database that primarily resides in main memory, but is typically backed-up by non-volatile computer data storage. Main memory databases are faster than disk databases, and so are often used where response time is critical, such as in telecommunications network equipment.[21]SAP HANAplatform is a very hot topic for in-memory database. By May 2012, HANA was able to run on servers with 100TB main memory powered by IBM. The co founder of the company claimed that the system was big enough to run the 8 largest SAP customers.

• An active database includes an event-driven architecture which can respond to conditions both inside and outside the database. Possible uses include security monitoring, alerting, statistics gathering and authorization. Many databases provide active database features in the form of database triggers.

• A cloud database relies on cloud technology. Both the database and most of its DBMS reside remotely, “in the cloud”, while its applications are both developed by programmers and later maintained and utilized by (application’s) end-users through aweb browser and Open APIs.

• Data warehouses archive data from operational databases and often from external sources such as market research firms. The warehouse becomes the central source of data for use by managers and other end-users who may not have access to operational data. For example, sales data might be aggregated to weekly totals and converted from internal product codes to use UPCs so that they can be compared with ACNielsen data. Some basic and essential components of data warehousing include retrieving, analyzing, and mining data, transforming, loading and managing data so as to make them available for further use.

• A deductive database combines logic programming with a relational database, for example by using the Datalog language.

• A distributed database is one in which both the data and the DBMS span multiple computers.

• A document-oriented database is designed for storing, retrieving, and managing document-oriented, or semi structured data, information. Document-oriented databases are one of the main categories of NoSQL databases.

• An embedded database system is a DBMS which is tightly integrated with an application software that requires access to stored data in such a way that the DBMS is hidden from the application’s end-users and requires little or no ongoing maintenance.[22]

• End-user databases consist of data developed by individual end-users. Examples of these are collections of documents, spreadsheets, presentations, multimedia, and other files. Several products exist to support such databases. Some of them are much simpler than full fledged DBMSs, with more elementary DBMS functionality.

• A federated database system comprises several distinct databases, each with its own DBMS. It is handled as a single database by a federated database management system (FDBMS), which transparently integrates multiple autonomous DBMSs, possibly of different types (in which case it would also be a heterogeneous database system), and provides them with an integrated conceptual view.

• Sometimes the term multi-database is used as a synonym to federated database, though it may refer to a less integrated (e.g., without an FDBMS and a managed integrated schema) group of databases that cooperate in a single application. In this case typicallymiddleware is used for distribution, which typically includes an atomic commit protocol (ACP), e.g., the two-phase commit protocol, to allow distributed (global) transactionsacross the participating databases.

• A graph database is a kind of NoSQL database that uses graph structures with nodes, edges, and properties to represent and store information. General graph databases that can store any graph are distinct from specialized graph databases such as triplestoresandnetwork databases.

• In a hypertext or hypermedia database, any word or a piece of text representing an object, e.g., another piece of text, an article, a picture, or a film, can be hyperlinkedto that object. Hypertext databases are particularly useful for organizing large amounts of disparate information. For example, they are useful for organizing online encyclopedias, where users can conveniently jump around the text. The World Wide Web is thus a large distributed hypertext database.

• A knowledge base (abbreviated KB, kb or Δ[23][24]) is a special kind of database forknowledge management, providing the means for the computerized collection, organization, and retrieval of knowledge. Also a collection of data representing problems with their solutions and related experiences.

• A mobile database can be carried on or synchronized from a mobile computing device.

• Operational databases store detailed data about the operations of an organization. They typically process relatively high volumes of updates using transactions. Examples includecustomer databases that record contact, credit, and demographic information about a business’ customers, personnel databases that hold information such as salary, benefits, skills data about employees, enterprise resource planning systems that record details about product components, parts inventory, and financial databases that keep track of the organization’s money, accounting and financial dealings.

• A parallel database seeks to improve performance through parallelization for tasks such as loading data, building indexes and evaluating queries.

The major parallel DBMS architectures which are induced by the underlyinghardware architecture are:

• Shared memory architecture, where multiple processors share the main memory space, as well as other data storage.
• Shared disk architecture, where each processing unit (typically consisting of multiple processors) has its own main memory, but all units share the other storage.
• Shared nothing architecture, where each processing unit has its own main memory and other storage.

• Probabilistic databases employ fuzzy logic to draw inferences from imprecise data.

• Real-time databases process transactions fast enough for the result to come back and be acted on right away.

• A spatial database can store the data with multidimensional features. The queries on such data include location based queries, like “Where is the closest hotel in my area?”.

• A temporal database has built-in time aspects, for example a temporal data model and a temporal version of SQL. More specifically the temporal aspects usually include valid-time and transaction-time.

• A terminology-oriented database builds upon an object-oriented database, often customized for a specific field.

• An unstructured data database is intended to store in a manageable and protected way diverse objects that do not fit naturally and conveniently in common databases. It may include email messages, documents, journals, multimedia objects, etc. The name may be misleading since some objects can be highly structured. However, the entire possible object collection does not fit into a predefined structured framework. Most established DBMSs now support unstructured data in various ways, and new dedicated DBMSs are emerging.

Design and modeling

The first task of a database designer is to produce a conceptual data model that reflects the structure of the information to be held in the database. A common approach to this is to develop an entity-relationship model, often with the aid of drawing tools. Another popular approach is the Unified Modeling Language. A successful data model will accurately reflect the possible state of the external world being modeled: for example, if people can have more than one phone number, it will allow this information to be captured. Designing a good conceptual data model requires a good understanding of the application domain; it typically involves asking deep questions about the things of interest to an organisation, like “can a customer also be a supplier?”, or “if a product is sold with two different forms of packaging, are those the same product or different products?”, or “if a plane flies from New York to Dubai via Frankfurt, is that one flight or two (or maybe even three)?”. The answers to these questions establish definitions of the terminology used for entities (customers, products, flights, flight segments) and their relationships and attributes.

Producing the conceptual data model sometimes involves input from business processes, or the analysis of workflow in the organization. This can help to establish what information is needed in the database, and what can be left out. For example, it can help when deciding whether the database needs to hold historic data as well as current data.

Having produced a conceptual data model that users are happy with, the next stage is to translate this into a schema that implements the relevant data structures within the database. This process is often called logical database design, and the output is a logical data modelexpressed in the form of a schema. Whereas the conceptual data model is (in theory at least) independent of the choice of database technology, the logical data model will be expressed in terms of a particular database model supported by the chosen DBMS. (The termsdata modeland database model are often used interchangeably, but in this article we use data model for the design of a specific database, and database model for the modelling notation used to express that design.)

The most popular database model for general-purpose databases is the relational model, or more precisely, the relational model as represented by the SQL language. The process of creating a logical database design using this model uses a methodical approach known as normalization. The goal of normalization is to ensure that each elementary “fact” is only recorded in one place, so that insertions, updates, and deletions automatically maintain consistency.

The final stage of database design is to make the decisions that affect performance, scalability, recovery, security, and the like. This is often called physical database design. A key goal during this stage is data independence, meaning that the decisions made for performance optimization purposes should be invisible to end-users and applications. Physical design is driven mainly by performance requirements, and requires a good knowledge of the expected workload and access patterns, and a deep understanding of the features offered by the chosen DBMS.

Another aspect of physical database design is security. It involves both defining access controlto database objects as well as defining security levels and methods for the data itself.

Models

A database model is a type of data model that determines the logical structure of a database and fundamentally determines in which manner data can be stored, organized, and manipulated. The most popular example of a database model is the relational model (or the SQL approximation of relational), which uses a table-based format.

Common logical data models for databases include:

• Hierarchical database model
• Network model
• Relational model
• Entity–relationship model
  • Enhanced entity–relationship model
• Object model
• Document model
• Entity–attribute–value model
• Star schema

An object-relational database combines the two related structures.

Physical data models include:

• Inverted index
• Flat file

Other models include:

• Associative model
• Multidimensional model
• Multivalue model
• Semantic model
• XML database
• Named graph

External, conceptual, and internal views

A database management system provides three views of the database data:

• The external level defines how each group of end-users sees the organization of data in the database. A single database can have any number of views at the external level.
• The conceptual level unifies the various external views into a compatible global view.[26]It provides the synthesis of all the external views. It is out of the scope of the various database end-users, and is rather of interest to database application developers and database administrators.
• The internal level (or physical level) is the internal organization of data inside a DBMS (see Implementation section below). It is concerned with cost, performance, scalability and other operational matters. It deals with storage layout of the data, using storage structures such as indexes to enhance performance. Occasionally it stores data of individual views (materialized views), computed from generic data, if performance justification exists for such redundancy. It balances all the external views’ performance requirements, possibly conflicting, in an attempt to optimize overall performance across all activities.

The three-level database architecture relates to the concept of data independence which was one of the major initial driving forces of the relational model. The idea is that changes made at a certain level do not affect the view at a higher level. For example, changes in the internal level do not affect application programs written using conceptual level interfaces, which reduces the impact of making physical changes to improve performance.

In practice usually a given DBMS uses the same data model for both the external and the conceptual levels (e.g., relational model). The internal level, which is hidden inside the DBMS and depends on its implementation (see Implementation section below), requires a different level of detail and uses its own types of data structure types.

Separating the external, conceptual and internal levels was a major feature of the relational database model implementations that dominate 21st century databases.[26]

Languages

Database languages are special-purpose languages, which do one or more of the following:

• Data definition language – defines data types and the relationships among them
• Data manipulation language – performs tasks such as inserting, updating, or deleting data occurrences
• Query language – allows searching for information and computing derived information

Database languages are specific to a particular data model. Notable examples include:

• SQL combines the roles of data definition, data manipulation, and query in a single language. It was one of the first commercial languages for the relational model, although it departs in some respects from the relational model as described by Codd (for example, the rows and columns of a table can be ordered). SQL became a standard of theAmerican National Standards Institute (ANSI) in 1986, and of the International Organization for Standardization (ISO) in 1987. The standards have been regularly enhanced since and is supported (with varying degrees of conformance) by all mainstream commercial relational DBMSs.[27][28]

• OQL is an object model language standard (from the Object Data Management Group). It has influenced the design of some of the newer query languages like JDOQLand EJB QL.

• XQuery is a standard XML query language implemented by XML database systems such as MarkLogic and eXist, by relational databases with XML capability such as Oracle and DB2, and also by in-memory XML processors such as Saxon.

• SQL/XML combines XQuery with SQL.[29]

A database language may also incorporate features like:

• DBMS-specific Configuration and storage engine management
• Computations to modify query results, like counting, summing, averaging, sorting, grouping, and cross-referencing
• Constraint enforcement (e.g. in an automotive database, only allowing one engine type per car)
• Application programming interface version of the query language, for programmer convenience

Storage

Database storage is the container of the physical materialization of a database. It comprises the internal (physical) level in the database architecture. It also contains all the information needed (e.g., metadata, “data about the data”, and internal data structures) to reconstruct theconceptual level and external level from the internal level when needed. Putting data into permanent storage is generally the responsibility of the database engine a.k.a. “storage engine”. Though typically accessed by a DBMS through the underlying operating system (and often utilizing the operating systems’ file systems as intermediates for storage layout), storage properties and configuration setting are extremely important for the efficient operation of the DBMS, and thus are closely maintained by database administrators. A DBMS, while in operation, always has its database residing in several types of storage (e.g., memory and external storage). The database data and the additional needed information, possibly in very large amounts, are coded into bits. Data typically reside in the storage in structures that look completely different from the way the data look in the conceptual and external levels, but in ways that attempt to optimize (the best possible) these levels’ reconstruction when needed by users and programs, as well as for computing additional types of needed information from the data (e.g., when querying the database).

Some DBMSs support specifying which character encoding was used to store data, so multiple encodings can be used in the same database.

Various low-level database storage structures are used by the storage engine to serialize the data model so it can be written to the medium of choice. Techniques such as indexing may be used to improve performance. Conventional storage is row-oriented, but there are alsocolumn-oriented and correlation databases.

The acronym ACID describes some ideal properties of a database transaction:

• Atomicity
• Consistency
• Isolation
• Durability

Migration

See also section Database migration in article Data migration

After the database is created, initialised and populated it needs to be maintained. Various database parameters may need changing and the database may need to be tuned (tuning) for better performance; application’s data structures may be changed or added, new related application programs may be written to add to the application’s functionality, etc.

Backup and restore

To achieve this a backup operation is done occasionally or continuously, where each desired database state (i.e., the values of its data and their embedding in database’s data structures) is kept within dedicated backup files (many techniques exist to do this effectively) (e.g., by specifying this state by a desired point in time when the database was in this state), these files are utilized to restore that state.

Other

Other DBMS features might include:

• Database logs
• Graphics component for producing graphs and charts, especially in a data warehouse system
• Query optimizer – Performs query optimization on every query to choose for it the most efficient query plan (a partial order (tree) of operations) to be executed to compute the query result. May be specific to a particular storage engine.
• Tools or hooks for database design, application programming, application program maintenance, database performance analysis and monitoring, database configuration monitoring, DBMS hardware configuration (a DBMS and related database may span computers, networks, and storage units) and related database mapping (especially for a distributed DBMS), storage allocation and database layout monitoring, storage migration, etc.

Von Neumann cellular automata are the original expression of cellular automata, the development of which were prompted by suggestions made to John von Neumann by his close friend and fellow mathematician Stanislaw Ulam. Their original purpose was to provide insight into the logical requirements for machine self-replication and were used in von Neumann’s universal constructor.

Nobili’s cellular automaton is a variation of von Neumann’s cellular automaton, augmented with the ability for confluent cells to cross signals and store information. The former requires an extra three states, hence Nobili’s cellular automaton has 32 states, rather than 29. Hutton’s cellular automaton is yet another variation, which allows a loop of data, analogous to Langton’s loops, to replicate.

Definition

Configuration

In general, cellular automata (CA) constitute an arrangement of finite state automata (FSA) that sit in positional relationships between one another, each FSA exchanging information with those other FSAs to which it is positionally adjacent. In von Neumann’s cellular automaton, the finite state machines (or cells) are arranged in a two-dimensional Cartesian grid, and interface with the surrounding four cells. As von Neumann’s cellular automaton was the first example to use this arrangement, it is known as the von Neumann neighbourhood.

The set of FSAs define a cell space of infinite size. All FSAs are identical in terms of state-transition function, or rule-set.

The neighborhood (a grouping function) is part of the state-transition function, and defines for any cell the set of other cells upon which the state of that cell depends.

All cells transition state synchronously, in step with a universal “clock” as in a synchronous digital circuit.

States

Each FSA of the von Neumann cell space can accept any of the 29 states of the rule-set. The rule-set is grouped into five orthogonal subsets. Each state includes the colour of the cell in the cellular automata program Golly in (red, green, blue). They are

1. a ground state U (48, 48, 48)
2. the transition or sensitised states (in 8 substates)
   1. S (newly sensitised) (255, 0, 0)
   2. S0 – (sensitised, having received no input for one cycle) (255, 125, 0)
   3. S00 – (sensitised, having received no input for two cycles) (255, 175, 50)
   4. S01 – (sensitised, having received no input for one cycle and then an input for one cycle) (255, 200, 75)
   5. S000 – (sensitised, having received no input for three cycles) (251, 255, 0)
   6. S1 – (sensitised, having received an input for one cycle) (255, 150, 25)
   7. S10 – (sensitised, having received an input for one cycle and then no input for one cycle) (255, 255, 100)
   8. S11 – (sensitised, having received input for two cycles) (255, 250, 125)
3. the confluent states (in 4 states of excitation)
   1. C00 – quiescent (and will also be quiescent next cycle) (0, 255, 128)
   2. C10 – excited (but will be quiescent next cycle) (255, 255, 128)
   3. C01 – next-excited (now quiescent, but will be excited next cycle) (33, 215, 215)
   4. C11 – excited next-excited (currently excited and will be excited next cycle) (255, 128, 64)
4. the ordinary transmission states (in 4 directions, excited or quiescent, making 8 states)
   1. North-directed (excited and quiescent) (36, 200, 36) (106, 106, 255)
   2. South-directed (excited and quiescent) (106, 255, 106) (139, 139, 255)
   3. West-directed (excited and quiescent) (73, 255, 73) (122, 122, 255)
   4. East-directed (excited and quiescent) (27, 176, 27) (89, 89, 255)
5. the special transmission states (in 4 directions, excited or quiescent, making 8 states)
   1. North-directed (excited and quiescent) (191, 73, 255) (255, 56, 56)
   2. South-directed (excited and quiescent) (203, 106, 255) (255, 89, 89)
   3. West-directed (excited and quiescent) (197, 89, 255) (255, 73, 73)
   4. East-directed (excited and quiescent) (185, 56, 255) (235, 36, 36)

“Excited” states carry data, at the rate of one bit per state transition step.

Note that confluent states have the property of a one-cycle delay, thus effectively holding two bits of data at any given time.

Transmission state rules

The flow of bits between cells is indicated by the direction property. The following rules apply:

• Transmission states apply the OR operator to inputs, meaning a cell in a transmission state (ordinary or special) will be excited at time t+1 if any of the inputs pointing to it is excited at time t
• Data passes from cells in the ordinary transmission states to other cells in the ordinary transmission states, according to the direction property (in the cell’s direction only)
• Data passes from cells in the special transmission states to other cells in the special transmission states, according to the direction property (in the cell’s direction only)
• The two subsets of transmission states, ordinary and special, are mutually antagonistic:
  • Given a cell A at time t in the excited ordinary transmission state
  • pointing to a cell B in any special transmission state
  • at time t+1 cell B will become the ground state. The special transmission cell has been “destroyed.”
  • a similar sequence will occur in the case of a cell in the special transmission state “pointing” to a cell in the ordinary transmission state

Confluent state rules

The following specific rules apply to confluent states:

• Confluent states do not pass data between each other.
• Confluent states take input from one or more ordinary transmission states, and deliver output to transmission states, ordinary and special, that are not directed toward the confluent state.
• Data are not transmitted against the transmission state direction property.
• Data held by a confluent state is lost if that state has no adjacent transmission state that is also not pointed at the confluent state.
• Thus, confluent-state cells are used as “bridges” from transmission lines of ordinary- to special-transmission state cells.
• The confluent state applies the AND operator to inputs, only “saving” an excited input if all potential inputs are excited simultaneously.
• Confluent cells delay signals by one generation more than OTS cells; this is necessary due to parity constraints.

Construction rules

Initially, much of the cell-space, the universe of the cellular automaton, is “blank,” consisting of cells in the ground state U. When given an input excitation from a neighboring ordinary- or special transmission state, the cell in the ground state becomes “sensitised,” transitioning through a series of states before finally “resting” at a quiescent transmission or confluent state.

The choice of which destination state the cell will reach is determined by the sequence of input signals. Therefore, the transition/sensitised states can be thought of as the nodes of a bifurcation tree leading from the ground-state to each of the quiescent transmission and confluent states.

In the following tree, the sequence of inputs is shown as a binary string after each step:

• a cell in the ground state U, given an input, will transition to the S (newly sensitised) state in the next cycle (1)
• a cell in the S state, given no input, will transition into the S0 state (10)
  • a cell in the S0 state, given no input, will transition into the S00 state (100)
    • a cell in the S00 state, given no input, will transition into the S000 state (1000)
      • a cell in the S000 state, given no input, will transition into the east-directed ordinary transmission state (10000)
      • a cell in the S000 state, given an input, will transition into the north-directed ordinary transmission state (10001)
    • a cell in the S00 state, given an input, will transition into the west-directed ordinary transmission state (1001)
  • a cell in the S0 state, given an input, will transition into the S01 state (101)
    • a cell in the S01 state, given no input, will transition into the south-directed ordinary transmission state (1010)
    • a cell in the S01 state, given an input, will transition into the east-directed special transmission state (1011)
• a cell in the S state, given an input, will transition into the S1 state (11)
  • a cell in the S1 state, given no input, will transition into the S10 state (110)
    • a cell in the S10 state, given no input, will transition into the north-directed special transmission state (1100)
    • a cell in the S10 state, given an input, will transition into the west-directed special transmission state (1101)
  • a cell in the S1 state, given an input, will transition into the S11 state (111)
    • a cell in the S11 state, given no input, will transition into the south-directed special transmission state (1110)
    • a cell in the S11 state, given an input, will transition into the quiescent confluent state C00 (1111)

Note that:

• one more cycle of input (four after the initial sensitization) is required to build the east- or north-directed ordinary transmission state than any of the other states (which require three cycles of input after the initial sensitization),
• the “default” quiescent state resulting in construction is the east-directed ordinary transmission state- which requires an initial sensitization input, and then four cycles of no input.

Destruction rule

• An input into a confluent-state cell from a special-transmission state cell will result in the confluent state cell being reduced back to the ground state.
• Likewise, an input into an ordinary transmission-state cell from a special-transmission state cell will result in the ordinary-transmission state cell being reduced back to the ground state.
• Conversely, an input into a special transmission-state cell from an ordinary-transmission state cell will result in the special-transmission state cell being reduced back to the ground state.

Sample cpp code from Golly latest version:

generationsalgo.cpp