Data structure in a GIS

Data Structure
-Information organization is concerned with the internal organization of data.
-It represents the user's view of data (conceptualizing of the real world)
-It is the lowest level of data abstraction, which can be done with or without any intent for computer implementation
-It is expressed in terms of data models as shown below:

 -The vector and raster methods of representing the real world are "data models"
-The relational, network, hierarchical and object-oriented databases are "database models" --- they are the software implementation of data models

-Data structure represents a higher level of data abstraction than information organization as it is concerned with the design and implementation of information organization.
-It represents the human implementation-oriented view of data
-It is expressed in terms of database models
(Data structure is software dependent).
-Data structure forms the basis for the next level of data abstraction in information system: file structure or file format
-File structure is the hardware implementation-oriented view of data
-It reflects the physical storage of the data on some specific computer media such as magnetic tapes or hard disk
-Hence, file structure is hardware-dependent

Descriptive data structures

Descriptive data structures describe the design and implementation of the information organization of non-spatial data.

-As most commercial implementations of information systems today are based on the relational and object-oriented database models, the data structures of these models are explained below:

- Relational data structure: the relational data structure is the table which is formally called a relation (shown below).

-a relation is a collection of tuples that correspond to the rows of the table

-the number of tuples in a relation is called the cardinality

-a tuple is made up of attributes that correspond to the columns of the table

-the number of attributes in a tuple is called the degree

-each relation has a unique identifier called the primary key

-the primary key is a column or combination of columns that at any given time has no identical values in any two rows - this means that the values of each row of the primary key are always unique

-this allows the use of the primary keys to relate data in different tables in data processing (shown below)

-the primary keys in those tables are called foreign keys

-in order to enforce database integrity, relations are always normalized

-normalization is built on the concept of normal form

-a relation is said to be in a certain normal form if it satisfies a prescribed set of conditions (Date, 1995)

-at minimum, a relation in the relational database has to satisfy the conditions of the first, second and third normal forms

-First Normal Form (1NF) --- a relation is said to be in 1NF if and only if its tuples contain no repeating attributes (i.e. there must not be multiple values for a single entity which might theoretically result from multiple sampling at a particular location)

-Second Normal Form (2NF) --- a relation is said to be in 2NF if it satisfies the condition for 1NF and if every non-key attribute is irreducibly dependent on the primary key

-Third Normal Form (3NF) --- a relation is said to be in 3NF if it satisfies the condition for 2NF and the non-key attributes are mutually independent

-Object-oriented data structure

Unlike the relational data structure, there is not a formalized object-oriented data structure; meaning that different object-orientation implementations have different data structures

However, object-oriented data structure can be explained in generic terms using the concepts of object identify, object structure and type constructors

The concept of object identity

-Each object in an object-oriented database is provided a unique system-generated object identifier (OID)

-The OID is for internal reference by the system and is therefore transparent to the user

-The OID is immutable, i.e. its value remains unchanged

-Even when a particular object is removed from the database, its OID will never be assigned to any new object

The concept of object structure

-The concept of object structure allows complex objects to be constructed from simple objects

-Each object is viewed as a triple (i, c, v) where

i = the object's unique identifier (OID) 

c = a constructor (which indicates how the object value is constructed) 

v = object value

Different object-oriented systems use different constructors, including: atom, tuple, set, list and array

An object value 'v' is interpreted on the basis of the value of the constructor c in the triple (i, c, v) that represents the object

-if c = atom, then v is an atomic value (i.e. it is an indivisible value)

-if c = tuple, then v is a tuple containing one or more attributes with their respective OIDs

-if c = set, then v is a set of object identifiers (OIDs) for a set of objects of the same type

-if c = list, then v is an ordered list of OIDs of the same type

-if c = array, then v is an array of OIDs of the same type

The concept of type constructors

A type constructor is used by an object-oriented definition language (OODDL) to define the data structure for an object-oriented database schema as shown in the figure below. 

Graphical data structures

Raster data structure

In the raster data structure space is subdivided into regular grids of square grid cells or other forms of polygonal meshes known as picture elements as shown in the figure below.