Introduction to Computer Science and Database Systems Study Notes

The Definition and Scope of Computer Science

• The Concept of Algorithm:

  • Formal Definition (Merriam-Webster): A procedure for solving a mathematical problem in a finite number of steps that frequently involves repetition of an operation; broadly: a step-by-step method for accomplishing some task.
  • Informal Definition: An ordered sequence of instructions that is guaranteed to solve a specific problem. It is structured as a list:
    • Step 1: Do something.
    • Step 2: Do something.
    • Step 3: …
    • Step $N$: Stop, you are finished.

• The Gibbs and Tucker Definition: Professors Norman Gibbs and Allen Tucker proposed a definition that identifies the algorithm as the central concept of computer science. This definition frames the task of the computer scientist as designing and developing algorithms to solve important problems through four primary operations:

  • Formal and Mathematical Properties: Studying the behavior of algorithms to determine if they are correct and efficient.
  • Hardware Realizations: Designing and building computer systems capable of executing algorithms.
  • Linguistic Realizations: Designing programming languages and translating algorithms into these languages so they can be executed by hardware.
  • Applications: Identifying important problems and designing correct and efficient software packages to solve them.

Common Misconceptions of Computer Science

• MISCONCEPTION 1: Computer science is the study of computers:

  • This is incomplete. Fundamental theoretical work on logical foundations occurred between 1920 and 1940, prior to the development of the first physical computer systems.
  • Computer science was recognized as an independent field only in the late 1950s and early 1960s.
  • Theoretical Computer Science: Researchers use formal models of computation to study logical and mathematical properties of problems. This work often involves pencil and paper rather than physical hardware like circuit boards or disks.
  • Analogy (Fellows and Parberry): "Computer science is no more about computers than astronomy is about telescopes, biology is about microscopes, or chemistry is about beakers and test tubes. Science is not about tools. It is about how we use them and what we find out when we do."

• MISCONCEPTION 2: Computer science is the study of how to write computer programs:

  • Programming is a tool used by researchers to study new ideas and build and test solutions, but it is not the discipline itself.
  • Programs allow for empirical study. For example, to test a "new and improved" search technique for a database like the Social Security Administration ($63,000,000$ active listings), a scientist writes a program to measure performance and compare it against existing methods.
  • A program is a means to an end, not the end in itself. High-quality construction is valued alongside the methods embodied and results produced.

• MISCONCEPTION 3: Computer science is the study of the uses and applications of computers and software:

  • Learning to use popular packages (word processors, search engines, spreadsheets, smartphone apps) is practical but is not computer science.
  • Analogy: Learning to use software is like driver’s education; computer science is similar to automotive engineering. The computer scientist is responsible for specifying, designing, building, and testing the software and the systems upon which they run.

Historical Development and Milestones

• Timeline of "Firsts":

  • 1930s: Earliest theoretical work on logical foundations.
  • 1940\u20131946: Appearance of the first general-purpose electronic computers (experimental laboratory systems).
  • 1947: Establishment of the Association for Computing Machinery (ACM). It now has over $100,000$ members and is the world's largest professional computer science society ($www.acm.org$).
  • March 1951: Debut of the UNIVAC I, the first commercial machine, marking the start of the computer industry.
  • 1957: Debut of FORTRAN, the first high-level (natural language-based) programming language, marking the start of the software industry.
  • October 1962: First Department of Computer Science established at Purdue University.
  • 1964: Purdue awards its first M.Sc. degree in computer science.
  • 1966: Purdue awards its first Ph.D. in computer science.
  • 1967: Undergraduate program established at Purdue.

• Discipline Age: The field is roughly 50 to 80 years old, making it significantly younger than mathematics, physics, chemistry, or biology.

Virtual Tables: Creating and Using Views

• Definition: A view is a virtual table based on a SELECT query. It does not store data itself but draws from "base tables."

• Syntax: CREATE VIEW viewname [(column list)] AS SELECT query.

• Special Characteristics:

  • Usability: A view name can be used anywhere a table name is expected in SQL.
  • Dynamic Updates: The view is re-created on demand each time it is invoked. Changes in base table data (e.g., adding a product where P_PRICE > 50.00) are automatically reflected.
  • Security: Restricts users to specific columns and rows (e.g., departmental assistants seeing only their own department's employee data).
  • Reporting: Views can group and summarize data (e.g., using SUM, MAX, MIN, AVG).

• Updatable Views: Used for batch update routines (e.g., updating PROD_QOH in a master table from summary sales transactions).

  • Restrictions:
    • Cannot use GROUP BY or aggregate functions.
    • Cannot use set operators (UNION, INTERSECT, MINUS).
    • JOINS are restricted; the base table must be key-preserved (primary key values must remain unique in the view).

Database Sequence Management and Auto-Increment

• MS Access: Uses the AutoNumber data type and the system variable @@IDENTITY (similar to Scope_Identity in SQL Server).

• MySQL: Uses the AUTO_INCREMENT property.

  • Requirement: Only one column per table, must be the primary key, and must be an integer type (INT, SMALLINT, BIGINT).
  • MySQL does not allow AUTO_INCREMENT on NUMERIC or DECIMAL types.
  • Function: Last_Insert_ID() returns the last generated value; it is session-specific but not table-specific.

• MS SQL Server: Uses the Identity column property.

  • Scope_Identity(): Session-aware; returns the last identity value generated in the current session.
  • Ident_Current('tablename'): Not session-aware; returns the last identity value generated for a specific table by any user.

• Oracle: Traditionally uses Sequences.

  • Sequence Characteristics: Independent objects (not a data type), have names, are not tied to a specific table/column, and the resulting values can be edited.
  • Syntax: CREATE SEQUENCE name [START WITH n] [INCREMENT BY n] [CACHE | NOCACHE].
    • START WITH: Initial value (default is 1).
    • INCREMENT BY: Step value (can be positive or negative).
    • CACHE/NOCACHE: Preallocates numbers in memory. Oracle defaults to NOCACHE (preallocating 20 values); SQL Server uses NO CACHE as two words.
  • Pseudo-columns:
    • NEXTVAL: Retrieves the next available value and increments the sequence.
    • CURRVAL: Retrieves the current value (last used NEXTVAL) in the current session. Cannot be used before a NEXTVAL is issued in that session.

Advanced SQL Implementation Examples

• Creating a Sequence (Oracle): sql CREATE SEQUENCE CUS_CODE_SEQ START WITH 20010 NOCACHE; CREATE SEQUENCE INV_NUMBER_SEQ START WITH 4010 NOCACHE;     

• Inserting with Sequences (Oracle): sql INSERT INTO CUSTOMER VALUES (CUS_CODE_SEQ.NEXTVAL, 'Walker', 'James', NULL, '615', '898-2007', 0.00); INSERT INTO INVOICE VALUES (INV_NUMBER_SEQ.NEXTVAL, 20010, SYSDATE); INSERT INTO LINE VALUES (INV_NUMBER_SEQ.CURRVAL, 1, '13-Q2/P2', 1, 14.99);     

• Batch Update via Updatable View:

  1. Create the view:

  CREATE VIEW PSVUPD AS (SELECT PRODMASTER.PROD_ID, PROD_QOH, PS_QTY FROM PRODMASTER JOIN PRODSALES ON PRODMASTER.PROD_ID = PRODSALES.PROD_ID);
      ```
  2. Update through the view:
  

  sql UPDATE PSVUPD SET PROD_QOH = PROD_QOH - PS_QTY;     ```

• Vendor Syntax Variations for Batch Updates:

  • MS SQL Server: Requires UPDATE FROM syntax. sql UPDATE PRODMASTER SET PROD_QOH = PROD_QOH - PS_QTY FROM PRODMASTER JOIN PRODSALES ON PRODMASTER.PROD_ID = PRODSALES.PROD_ID;     
  • Oracle: Does not allow joins directly in an UPDATE statement; requires an updatable view or procedural SQL.