1

The below is from Fundamentals of Database Systems (7th Edition)

17.1 Types of Single-Level Ordered Indexes

There are several types of ordered indexes. A primary index is specified on the ordering key field of an ordered file of records. Recall from Section 16.7 that an ordering key field is used to physically order the file records on disk, and every record has a unique value for that field. If the ordering field is not a key field—that is, if numerous records in the file can have the same value for the ordering field—another type of index, called a clustering index, can be used. The data file is called a clustered file in this latter case. Notice that a file can have at most one physical ordering field, so it can have at most one primary index or one clustering index, but not both. A third type of index, called a secondary index, can be specified on any nonordering field of a file. A data file can have several secondary indexes in addition to its primary access method. We discuss these types of single-level indexes in the next three subsections.

17.1.1 Primary Indexes

A primary index is an ordered file whose records are of fixed length with two fields, and it acts like an access structure to efficiently search for and access the data records in a data file. The first field is of the same data type as the ordering key field—called the primary key—of the data file, and the second field is a pointer to a disk block (a block address). There is one index entry (or index record) in the index file for each block in the data file. Each index entry has the value of the primary key field for the first record in a block and a pointer to that block as its two field values.

Specifically my question is about a "primary index" as it relates to a more formal academic parlance -- I never went to a university so I have no idea how they're using this term. Is the "primary index is specified on the ordering key field of an ordered file of records" correct? Was that the original distinction between a PRIMARY key (for a primary index), and a regular key into a non-primary non-clustered index?

I'm thinking that this book didn't go through 7 editions at $151.00 a pop with the false idea that a primary key necessitate "ordered file of records."

  • 2
    You are confusing the SQL term PRIMARY KEY which refers to constraints with the physical implementation term "primary index" which - probably, I assume, haven't read the whole book - refers to file/indexing implementations, and not only, not necessarily related to SQL products. – ypercubeᵀᴹ Jan 12 '18 at 16:50
  • @ypercubeᵀᴹ that's what I was actually thinking, if you have more to add to that it'd be great or just pop that in the bottom and I'll mark it as chosen. So outside of SQL the term Primary Key and Primary Index have different meanings. #TIL. – Evan Carroll Jan 12 '18 at 16:51
2

A "key" is a logical construct used to identify a specific record. Given their purpose, keys require uniqueness. Primary Key fields are also required to be declared as NOT NULL. There are also "alternate" keys which allow key fields to be declared as NULL. Both Primary and Alternate keys have an optional, secondary purpose of establishing relationships via Foreign Keys (declarative referential integrity).

An "index" is a physical construct used to access one-or-more records. Uniqueness is not required for this purpose. When an index is declared as unique, it is not required that the indexed column(s) be declared as NOT NULL; NULL is allowed so long as it is unique, or a unique combination when working with multiple index columns.

Given the two quoted paragraphs, here is a terminology translation table:

  • BOOKSQL Server
  • "file" → Table or Index
  • "primary index" → UNIQUE CLUSTERED Index
  • "clustering index" → non-unique CLUSTERED Index (due to the cluster key column(s) being the row identifier, there is a need for true uniqueness, and so SQL Server will guarantee that uniqueness by adding a hidden, auto-incrementing INT value called the uniqueifier, but only for actual non-unique key values: please see Clustered Index Uniquifier Existence and Size for details)
  • "secondary index" → NONCLUSTERED Index
  • "primary key" → PRIMARY KEY defined on a UNIQUE CLUSTERED Index

In SQL Server, a Primary Key does not need to be defined on a UNIQUE CLUSTERED Index, it just requires a Unique Index (though the default behavior when creating a PK when no clustered Index exists is to make the PK clustered).

Also, a Foreign Key can reference either a Primary Key or an "Alternate" Key (i.e. Unique Constraint or Unique Index)

The following example shows both a PK on a NONCLUSTERED Index, and an FK referencing an Alternate Key defined on a column allowing NULL values:

USE [tempdb];

-- DROP TABLE dbo.Parent
CREATE TABLE dbo.Parent
(
  [ParentID] INT NOT NULL
             CONSTRAINT [PK_Parent] PRIMARY KEY
             NONCLUSTERED,
  [AltKey]   INT NULL
             CONSTRAINT [UQ_Parent_AltKey] UNIQUE NONCLUSTERED
);

-- DROP TABLE dbo.ChildID
CREATE TABLE dbo.ChildID
(
  [ChildID]  INT NOT NULL
             CONSTRAINT [PK_Child] PRIMARY KEY
             NONCLUSTERED,
  [AltKey]   INT NULL
             CONSTRAINT [FK_Child_Parent_AltKey] FOREIGN KEY
             REFERENCES dbo.Parent ([AltKey])
);
  • When? Indexes are ordered. At least I have never seen a case where they aren't. Not sure what the purpose would be of a non-ordered index. key fields are not necessarily ordered. I am testing something and was going to add info about alternate keys and using FKs to refer to them (i.e. unique index / constraint)..just need to confirm if alternate keys require NOT NULL. – Solomon Rutzky Jan 12 '18 at 21:16
  • I wasn't referring to the index, the definition above says "A primary index is specified on the ordering key field of an ordered file of records." SQL Server, afaik, stores the records unordered in the page. – Evan Carroll Jan 12 '18 at 21:21
  • I was ignoring the two terms "ordered file" and "clustered file" since they are using "file" to mean table. And I assume "unordered file" = heap table. I can also test the physical order of the rows in the slot-array (it's been a while since I did that testing), but even if the rows are not in physical order within the page, a) that will be fairly minimal in scope since the pages are in physical order so the rows won't be more than a few off, and b) once you do a rebuild I would be surprised if all rows were not in physical order. – Solomon Rutzky Jan 12 '18 at 21:31
  • If the pages are ordered, what happens in SQL Server if you insert a bunch of crap in the middle of a table that has a UNIQUE CLUSTERED INDEX you trigger a full table and index rewrite? – Evan Carroll Jan 12 '18 at 21:35
  • well, that's the difference between logical and physical ordering...the pages in a clustered index will always be logically linked in the proper order...but they can be physically out of order...this is known as logical fragmentation (i.e. the fragmentation that the DMVs report). Rebuilding the index will put the pages back in physical order. – Solomon Rutzky Jan 12 '18 at 21:40
0

Indexes are not the part of relational math at all. They are part of RDBMS implementations only to speed up data proceeding. Keys in opposite are r/math constraints that are applied on the sets that should conform some restrictions like uniqness or existence. In practice primary key is the table-wide always-existent unique identifier, sometimes implicit and automatic. Primary index can be built over the primary key but that is not necessary. Moreover, table can have more than one key suitable to be primary key at the same time. And that alternatives can become primary key ad hoc.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.