1.3 Exchanging Data

Compression

Process of reducing the storage space required by a file, important for sharing files over networks or on the internet

Compression - purpose

More files can be stored in a set space in storage

Files transmitted quicker over networks

Compression technique

Algorithm followed to reduce file size by reducing the number of binary digits and therefore the number of bits

Compression ratio

Indication of effectiveness of compression method in reducing file size, allows comparison of compression algorithms, measure of relative reductive of file size

Compression ratio - calculation

Size of original file/size of compressed file

Lossy compression

Some information removed, original file cannot be recovered; reduces file size more but also reduces the quality

Lossless compression

Reduces file size without losing any information, original file can be recovered from compressed version; reduces file size less but maintains quality

Run length encoding

Method of lossless compression, repeated values removed and replaced with one occurrence of data followed by the number of times it should be repeated

Run length encoding - suitability

Relies on consecutive pieces of data being the same, does not cause great reduction in file size if there is little repetition

Dictionary encoding

Method of lossless compression, frequently occurring pieces of data replaced with an index and compressed data stored alongside a dictionary which matches frequently occurring data to the index, original data restored using dictionary

Dictionary encoding - requirement

Data cannot be used without dictionary

Symmetric encryption

Same private key used for both sender and receiver

Key exchange

Key shared between sender and receiver for symmetric encryption, danger of interception

Asymmetric encryption

Uses a private key and a public key, mathematically related, messages encrypted with recipient’s public key, can only be decrypted using recipient’s private key

Digital signatures

User can encrypt message using own private key for others to decrypt using their public key to prove they sent it

Hashing

Process where key (input) is turned into a hash (fixed size value) using a hash function (algorithm)

Hashing - reversal

Output of a hash function cannot be reversed to form the key

Hashing - usage

Storing passwords - password inputted, used with hash function, hash checked against hash stored, formed from known password

Hash tables

Data structure which holds key-value pairs, formed from bucket array and hash function and used to look up data in an array in constant time

Hash tables - function

Data inserted and used as the key for the hash function, stored in bucket corresponding to hash

Hash tables - usage

Used extensively in situations where a lot of data needs to be stored with constant access times e.g. in caches and databases

Collision

Occurs when two keys produce the same hash, low chance if hash function is good

Collisions - overcome

Store items together in a list under the hash value, use a second hash function to generate a new hash

Hash function - output

Output should be smaller than input otherwise searching for the hash could take longer than simply searching for the key

Entity

Item of interest about which information is stored

Record

Collection of data stored about a single entity (a row)

Field

Specific piece of information stored about the entity (cell)

Attribute

Characteristic of the entity, category about which data is collected

Relational database

Database that recognises the differences between entities by creating different tables for each entity

Flat file

Database that consists of a single file, most likely based around a single entity and its attributes

Primary key

Unique identifier for each record in the table, shown by underlining

Foreign key

Attribute that links two tables together, primary key in one table and the foreign key in another, shown with asterisk \*

Secondary key

Allows a database to be searched quickly, makes it possible to search and order by secondary key to find certain records in the database

Composite primary key

Primary key that consists of more than one attribute

Entity relationship modelling

Shows the relationship between tables, depending on how entities are related in the real world

One-to-one

Each entity is only linked to one other entity

One-to-many

One entity can be associated with many other entities

Many-to-many

One entity can be associated with many other entities and vice versa

Indexing

Method used to store the position of each record ordered by a certain attribute

Use of indexing

To look up and access data quickly

Indexing - primary key

Automatically indexed but almost never queried as not normally remembered

Indexing - secondary keys

Remembered so indexed to make the table easier and faster to search through

Magnetic Ink Character Recognition (MICR)

Magnetic ink used which can be recognised by computer, used for cheques - amount must be entered manually

Optical Mark Recognition (OMR) use

Multiple choice questions on a test

Optical Character Recognition (OCR) use

Used by forms

Exchanging data - process

Process of transferring the collected data

Electronic Data Interchange (EDI)

Common way of exchanging data, doesn’t require human interaction, enables data transfer between computers

Normalisation

Process of creating best possible layout for a relationship database, process of splitting data in a database and arranging it into tables to move it into the 3rd normal form

Purpose of normalisation

Attempts to remove any redundancy, make sure data is consistent throughout linked tables, ensures records can be added and removed without issue and that complex queries can be carried out

Redundancy

Unnecessary duplicates

Dependency

A value that varies in line with another value

First normal form, 1NF

There must be no attribute that contains more than a single value

1NF rules

All field names must be unique

Values in fields should be from the same domain (only one kind of data per column)

Values in fields should be atomic (only a single value per cell)

No two records can be identical

Each table needs a primary key

Second normal form, 2NF

A database that doesn’t have any partial dependencies and is in 1NF, no attributes can depend on part of a composite key

2NF rules

Each table should serve its own purpose

Fix any many-to-many relationships that have been formed

No partial dependencies

In 1NF

No attributes can depend on part of a composite key

Third normal form, 3NF

No non-key/transitive dependencies, is in 2NF - attribute only depends on the value of the primary key

Structured query language, SQL

Declarative language used to manipulate databases

SELECT

Collects fields from a given table

FROM

Used with select to specify which table(s) the information will come from

WHERE

Used to specify the search criteria

ORDER BY

Specifies the arrangement of data, automatically in ascending order unless ‘Desc’ is added to the end of the statement - can be ordered by 2 fields

JOIN

Combines rows from multiple table based on a common field between them

CREATE

Allows creation of new databases, requires some details: primary key, data type, whether it must be filled in (not null)

ALTER

Used to add, delete or modify the columns in a table

ALTER TABLE TableName ADD AttributeX (dataType)

Adds column

ALTER TABLE TableName DROP COLUMN AttributeX

Deletes column

ALTER TABLE TableName MODIFY COLUMN AttributeX (newDataType)

Changes data type

INSERT INTO (column1, column2) VALUES (value1, value2)

Used to insert a new record into a database table

UPDATE TableName SET column1=value1, column2=value2….. WHERE columnX=valueX

Used to update a record in a database table

DELETE FROM TableName WHERE columnX=value

Used to delete a record from a database table

LIKE

Condition meaning similar to e.g. CDTitle LIKE “S%”

BETWEEN … AND …

Condition meaning within a range which includes the values defining the limits

IS NULL

Condition meaning field does not contain a value

Symbol used on either side of date

\# e.g. #01/01/2010#

Referential integrity

Process of ensuring consistency, information must not be removed if it is required elsewhere in a linked database

Transaction processing

Single operation executed on data

What does ACID stand for?

Atomicity, consistency, isolation, durability

Atomicity

A transaction must be processed in its entirety or not at all

Consistency

A transaction must maintain the referential integrity rules between linked tables

Isolation

Simultaneous executions of transactions should lead to the same result as if they were executed one after the other

Durability

Once a transaction has been executed, it will remain so regardless of the circumstances surrounding it e.g. in the event of a power cut

Record locking

The process of preventing simultaneous access to records in a database

Purpose of record locking

To prevent inconsistencies or a loss of updates

Issue with record locking

Deadlock

Deadlock

Two people are accessing records and waiting to access the record that the other is currently accessing. Neither becomes free so there is no progress

Redundancy

Having one or more copies of data in physically different locations

Purpose of redundancy

In the event of damage to one copy, the other copies will remain unaffected and can be recovered

Network

2+ computers connected together with the ability to transmit data between them

LAN (Local Area Network)

Network spread over a small geographical location/single site

WAN (Wide Area Network)

Network spread over a large geographical location/multiple sites

Requirement for WAN

Extra telecommunication hardware, usually owned by 3rd parties

Types of network topology

Physical and logical

Physical topology

Physical layout of the wires and components that form the network e.g. bus, star, mesh

Logical topology

The layout that shows how data flows

Physical bus topology - description

All terminals connected to backbone cable with ends plugged into terminator

Physical bus topology - advantages

Relatively inexpensive to set up, does not require any additional hardware

Physical bus topology - disadvantages

If backbone cable fails, the entire network gets disconnected

If traffic increases, performance decreases

All computers can see the data transmission

Physical star topology - description

Uses a central node, often a switch, to direct data through the network. MAC addresses are used to identify each device on the network.

Physical star topology - advantage

Consistent performance even with heavy network traffic

If one cable fails, only that single terminal is affected

Better performance and speed of data transmission than bus

Easy to add new stations

No data collisions

Physical star topology - disadvantage

Expensive due to the switch and cabling

If the central switch fails, the rest of the network fails