Documentation Source Text

Check-in [e216c81d99]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Minor edits of fileformat.html.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:e216c81d99997acced782abc00a88175a82e3dba
User & Date: dan 2009-05-21 11:36:37
Context
2009-05-22
11:45
Add some more links to the docs.html page. Group the links under headings to try to make it easier to find pages. check-in: 379b9f7acd user: dan tags: trunk
2009-05-21
11:36
Minor edits of fileformat.html. check-in: e216c81d99 user: dan tags: trunk
2009-05-20
11:36
Modifications to the introduction of the file format document. check-in: 0f0af25556 user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/fileformat.in.

454
455
456
457
458
459
460
461







462
463
464
465
466
467
468
469
470
471

472
473
474






475
476
477
478
479
480







481

482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525

526
527
528
529
530
531

532
533

534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570


571
572
573
574
575
576
577
....
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
....
2964
2965
2966
2967
2968
2969
2970
2971





2972
2973
2974
2975

2976
2977
2978
2979
2980

2981
2982
2983
2984
2985

2986
2987
2988
2989
2990
2991
2992
2993
2994
-->
  

[h1 "Database Image Format Details" database_file_format]

  <p>
    This section describes the various fields and sub-structures that make up
    the format used by SQLite to serialize a logical SQL database. 







  <p>
    This section does not contain requirements governing the behaviour of any
    software system. Instead, along with the plain language description of the
    file format are a series of succinct, testable statements describing the
    properties of "well-formed SQLite database files".  Some of these
    statements describe the contents of the database file in terms of the
    contents of the logical SQL database that it is a serialization of. e.g.
    "For each SQL table in the database, the database file shall...".
    The contents and properties of a logical database
    include:

  <ul>
    <li>Whether or not the database is an auto-vacuum database, and if
        so whether or not incremental-vacuum is enabled,






    <li>The configured page-size of the database,
    <li>The configured text-encoding of the database,
    <li>The configured user-cookie value,
    <li>The set of database tables, indexs, triggers and views that make
        up the database schema and their properties, and
    <li>The data (rows) inserted into the set of database tables.







  </ul>


  <p class=todo>
    This concept of a logical database should be defined properly 
    in some requirements document so that it can be referenced from
    here and other places. The definition will be something like the
    list of bullet points above.

  <p>
    A well-formed SQLite database file is defined as a file for which
    all of the statements itemized as requirements within this section
    are true. <span class=todo>mention the requirements numbering scheme
    here.</span> A software system that wishes to interoperate with other
    systems using the SQLite database file format should only ever
    output well-formed SQLite databases. In the case of SQLite itself,
    the system should ensure that the database file is well-formed at
    the conclusion of each database transaction.

  [h2 "Image Format Overview" "fileformat_overview"]
    <p>
      A B-Tree is a data structure designed for offline storage of a set of
      unique key values. It is structured so as to support fast querying 
      for a single key or range of keys. As implemented in SQLite, each
      entry may be associated with a blob of data that is not part of the
      key. For the canonical introduction to the B-Tree and its variants, 
      refer to reference <cite>ref_comer_btree</cite>. The B-Tree 
      implementation in SQLite also adopts some of the enhancements 
      suggested in <cite>ref_knuth_btree</cite>
    <p>
      An SQLite database file contains one or more B-Tree structures. Each
      B-Tree structure stores the data for a single database table or 
      index. Hence each database file contains a single B-Tree to store
      the contents of the <i>sqlite_master</i> table, and one B-Tree
      for each database table or index created by the user. If the database
      uses auto-increment integer primary keys, then the database file
      also contains a B-Tree to store the contents of the automatically 
      created <i>sqlite_sequence</i> table.
    <p>
      SQLite uses two distinct variants of the B-Tree structure. One variant,
      hereafter refered to as a "table B-Tree" uses signed 64-bit integer
      values for keys. Each entry has an associated variable length blob of 
      data used to store a database record (see section
      <cite>record_format</cite>). Each SQLite database file contains one 
      table B-Tree for the schema table and one table B-Tree for each
      additional database table created by the user.

    <p>
      A database record is a blob of data containing an ordered list of
      SQL values (integers, real values, NULL values, blobs or strings).
      For each row in each table at the SQL level, there is an 
      entry in the corresponding table B-Tree structure in the file. The
      entry key is same as the SQL "rowid" or "integer primary key" field

      of the table row. The associated database record is made up of the
      row's column values, in declaration (CREATE TABLE) order.

    <p>
      The other B-Tree variant used by SQLite, hereafter an "index B-Tree"
      uses database records (section <cite>record_format</cite>) as keys.
      For this kind of B-Tree, there is no additional data associated with
      each entry. SQLite databases contain an index B-Tree for each database
      index created by the user. Database indexes may be created by CREATE
      INDEX statements, or by UNIQUE or PRIMARY KEY (but not INTEGER PRIMARY
      KEY) clauses added to CREATE TABLE statements. 
    <p>
      Index B-Tree structures contain one entry for each row in the 
      associated table at the SQL level. The database record used as the
      key consists of the row's value for each of the indexed columns in
      declaration (CREATE INDEX) order, followed by the row's "rowid" or
      "integer primary key" column value.
    <p>
      For example, the following SQL script:
    <pre>
      CREATE TABLE t1(a INTEGER PRIMARY KEY, b, c, d);
      CREATE INDEX i1 ON t1(d, c);

      INSERT INTO t1 VALUES(1, 'triangle', 3, 180, 'green');
      INSERT INTO t1 VALUES(2, 'square',   4, 360, 'gold');
      INSERT INTO t1 VALUES(3, 'pentagon', 5, 540, 'grey');
      ...</pre>
    <p>
      Creates a database file containing three B-Tree structures: one table
      B-Tree to store the <i>sqlite_master</i> table, one table B-Tree to 
      store table "t1", and one index B-Tree to store index "i1". The
      B-Tree structures created for the user table and index are populated
      as shown in figure <cite>figure_examplepop</cite>.

      [Figure examplepop.gif figure_examplepop "Example B-Tree Data"]

  [h2 "Global Structure"]
    <p>
      The following sections and sub-sections describe precisely the format
      used to house the B-Tree structures within an SQLite database file.



    [h3 "File Header" "file_header"]
      <p>
        Each SQLite database file begins with a 100-byte header. The header
        file consists of a well known 16-byte sequence followed by a series of
        1, 2 and 4 byte unsigned integers. All integers in the file header (as
        well as the rest of the database file) are stored in big-endian format.
................................................................................
    that can be used. So long as the above requirements (and
    those in sections <cite>locking_protocol</cite> and 
    <cite>database_header_cookies_protocol</cite>) are honoured, any method may
    be used by an SQLite database writer to update the database file-system
    representation. Sections <cite>rollback_journal_method</cite> and 
    <cite>atomic_write_method</cite> do not contain formal requirements. Formal
    requirements governing the way in which SQLite safely updates database
    file-system representations may be found in <span class=todo>ref</span>.

  <p class=todo> Refer to webpage "How SQLite Implements Atomic Commit" too?

  [h3 "The Rollback-Journal Method" rollback_journal_method]

    <p>
      This section describes the method usually used by SQLite to update a database 
      image within a database file-system representation. This is one way
      to modify a database image in accordance with the requirements in the
................................................................................

    [fileformat_import_requirement2 H33040]
    [fileformat_import_requirement2 H33050]
    [fileformat_import_requirement2 H33070]


[h1 References]






  <table id="refs" style="width:auto; margin: 1em 5ex">
    <tr><td style="width:5ex" id="ref_comer_btree">\[1\]<td>
     Douglas Comer, <u>Ubiquitous B-Tree</u>, ACM Computing Surveys (CSUR),
     v.11 n.2, pages 121-137, June 1979.

    <tr><td style="width:5ex" id="ref_knuth_btree">\[2\]<td>
     Donald E. Knuth, <u>The Art Of Computer Programming, Volume 3:
     "Sorting And Searching"</u>, pages 473-480. Addison-Wesley
     Publishing Company, Reading, Massachusetts.
    <tr><td style="width:5ex" id="capi_sqlitert_requirements">\[3\]<td>

      C API Requirements Document.
    <tr><td style="width:5ex" id="sql_sqlitert_requirements">\[4\]<td>
      SQL Requirements Document.
    <tr><td style="width:5ex" id="io_sqlitert_requirements">\[5]<td>
      File IO Requirements Document.

  </table>

}]
</tcl>

<div id=toc>
<tcl>hd_puts $TOC</tcl>
</div id=toc>
<tcl>hd_puts [FixReferences $body]</tcl>







|
>
>
>
>
>
>
>







|
|
<
>

|
|
>
>
>
>
>
>
|
|
<
<
<
<
>
>
>
>
>
>
>
|
>


|
|
|
|


|



|

|
|










|












|



|
>


|
|
|
<
>
|
|
>










|
|













|







<


|
>
>







 







|
|
<







 








>
>
>
>
>

|


>
|



<
>
|
|
|
<
<
>

<







454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477

478
479
480
481
482
483
484
485
486
487
488
489




490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548

549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585

586
587
588
589
590
591
592
593
594
595
596
597
....
2540
2541
2542
2543
2544
2545
2546
2547
2548

2549
2550
2551
2552
2553
2554
2555
....
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004

3005
3006
3007
3008


3009
3010

3011
3012
3013
3014
3015
3016
3017
-->
  

[h1 "Database Image Format Details" database_file_format]

  <p>
    This section describes the various fields and sub-structures that make up
    the format used by SQLite to serialize a logical SQL database. A serialized
    logical database is referred to as a database image. Section
    <cite>file_system_usage</cite> describes the way a database image is stored
    in the file-system. Most of the time a database image is stored in a single
    file, the database file. So while reading this section, the term database 
    image may be understood to mean "contents of the database file". However,
    it is important to remember that there are exceptions to this.

  <p>
    This section does not contain requirements governing the behaviour of any
    software system. Instead, along with the plain language description of the
    file format are a series of succinct, testable statements describing the
    properties of "well-formed SQLite database files".  Some of these
    statements describe the contents of the database file in terms of the
    contents of the logical SQL database that it is a serialization of. e.g.
    "For each SQL table in the database, the database file shall...". The 
    contents of a logical database consist of:


  <ul>
    <li>The database schema: The set of database tables, virtual tables, 
        indexes, triggers and views stored in the database.

    <li>The database contents: The set of tuples (rows) stored in
	each database table.

    <li>Other database properties, as follows:
      <ul>
	<li>The page-size of the database.
	<li>The text-encoding of the database.




	<li>A flag indicating whether or not the database is an auto-vacuum 
	    database.
	<li>The value of the database user-cookie.
	<li>If the database is an auto-vacuum database, a flag indicating 
	    whether or not the database is in incremental vacuum mode or not.
	<li>The default page cache size in pages to use with the database (an 
	    integer field).
      </ul>
  </ul>

  <p class=todo>
    The concept of a logical database and its contents should be defined
    properly in some requirements document so that it can be referenced from
    here and other places. The definition will be something like the list of
    bullet points above.

  <p>
    A well-formed SQLite database image is defined as an image for which
    all of the statements itemized as requirements within this section
    are true. <span class=todo>mention the requirements numbering scheme
    here.</span> A software system that wishes to interoperate with other
    systems using the SQLite database image format should only ever
    output well-formed SQLite databases. In the case of SQLite itself,
    the system should ensure that the database file contains a well-formed 
    database image the conclusion of each transaction.

  [h2 "Image Format Overview" "fileformat_overview"]
    <p>
      A B-Tree is a data structure designed for offline storage of a set of
      unique key values. It is structured so as to support fast querying 
      for a single key or range of keys. As implemented in SQLite, each
      entry may be associated with a blob of data that is not part of the
      key. For the canonical introduction to the B-Tree and its variants, 
      refer to reference <cite>ref_comer_btree</cite>. The B-Tree 
      implementation in SQLite also adopts some of the enhancements 
      suggested in <cite>ref_knuth_btree</cite>.
    <p>
      An SQLite database file contains one or more B-Tree structures. Each
      B-Tree structure stores the data for a single database table or 
      index. Hence each database file contains a single B-Tree to store
      the contents of the <i>sqlite_master</i> table, and one B-Tree
      for each database table or index created by the user. If the database
      uses auto-increment integer primary keys, then the database file
      also contains a B-Tree to store the contents of the automatically 
      created <i>sqlite_sequence</i> table.
    <p>
      SQLite uses two distinct variants of the B-Tree structure. One variant,
      hereafter refered to as a "table B-Tree" uses signed 64-bit integer
      values as keys. Each entry has an associated variable length blob of 
      data used to store a database record (see section
      <cite>record_format</cite>). Each SQLite database file contains one 
      table B-Tree for the schema table and one table B-Tree for each
      additional database table created by the user. If it is present, the
      sqlite_sequence table is also stored as a table B-Tree.
    <p>
      A database record is a blob of data containing an ordered list of
      SQL values (integers, real numbers, NULL values, blobs or strings).
      For each row in each table in the logical database, there is an 
      entry in the corresponding table B-Tree structure in the database 

      image. The entry's integer key value is same as the SQL "rowid" or 
      "integer primary key" field of the table row. The associated database 
      record is made up of the row's column values, in declaration (CREATE 
      TABLE) order.
    <p>
      The other B-Tree variant used by SQLite, hereafter an "index B-Tree"
      uses database records (section <cite>record_format</cite>) as keys.
      For this kind of B-Tree, there is no additional data associated with
      each entry. SQLite databases contain an index B-Tree for each database
      index created by the user. Database indexes may be created by CREATE
      INDEX statements, or by UNIQUE or PRIMARY KEY (but not INTEGER PRIMARY
      KEY) clauses added to CREATE TABLE statements. 
    <p>
      Index B-Tree structures contain one entry for each row in the 
      associated table in the logical SQL database. The database record used 
      as the key consists of the row's value for each of the indexed columns in
      declaration (CREATE INDEX) order, followed by the row's "rowid" or
      "integer primary key" column value.
    <p>
      For example, the following SQL script:
    <pre>
      CREATE TABLE t1(a INTEGER PRIMARY KEY, b, c, d);
      CREATE INDEX i1 ON t1(d, c);

      INSERT INTO t1 VALUES(1, 'triangle', 3, 180, 'green');
      INSERT INTO t1 VALUES(2, 'square',   4, 360, 'gold');
      INSERT INTO t1 VALUES(3, 'pentagon', 5, 540, 'grey');
      ...</pre>
    <p>
      Creates a database image containing three B-Tree structures: one table
      B-Tree to store the <i>sqlite_master</i> table, one table B-Tree to 
      store table "t1", and one index B-Tree to store index "i1". The
      B-Tree structures created for the user table and index are populated
      as shown in figure <cite>figure_examplepop</cite>.

      [Figure examplepop.gif figure_examplepop "Example B-Tree Data"]


    <p>
      The following sections and sub-sections describe precisely the format
      used to serialize the B-Tree structures within an SQLite database image.

  [h2 "Global Structure"]

    [h3 "File Header" "file_header"]
      <p>
        Each SQLite database file begins with a 100-byte header. The header
        file consists of a well known 16-byte sequence followed by a series of
        1, 2 and 4 byte unsigned integers. All integers in the file header (as
        well as the rest of the database file) are stored in big-endian format.
................................................................................
    that can be used. So long as the above requirements (and
    those in sections <cite>locking_protocol</cite> and 
    <cite>database_header_cookies_protocol</cite>) are honoured, any method may
    be used by an SQLite database writer to update the database file-system
    representation. Sections <cite>rollback_journal_method</cite> and 
    <cite>atomic_write_method</cite> do not contain formal requirements. Formal
    requirements governing the way in which SQLite safely updates database
    file-system representations may be found in <span class=todo>Not available yet!</span>.
    An informal description is available in <cite>atomic_commit_page</cite>.


  [h3 "The Rollback-Journal Method" rollback_journal_method]

    <p>
      This section describes the method usually used by SQLite to update a database 
      image within a database file-system representation. This is one way
      to modify a database image in accordance with the requirements in the
................................................................................

    [fileformat_import_requirement2 H33040]
    [fileformat_import_requirement2 H33050]
    [fileformat_import_requirement2 H33070]


[h1 References]

[proc Ref {no id details} {
  set ::References($id) "\[$no\]"
  return "<tr><td style=\"width:5ex ; vertical-align:top\" id=\"$id\">\[$no\]<td>$details"
}]

  <table id="refs" style="width:auto; margin: 1em 5ex">
  [Ref 1 ref_comer_btree {
     Douglas Comer, <u>Ubiquitous B-Tree</u>, ACM Computing Surveys (CSUR),
     v.11 n.2, pages 121-137, June 1979.
  }]
  [Ref 2 ref_knuth_btree {
     Donald E. Knuth, <u>The Art Of Computer Programming, Volume 3:
     "Sorting And Searching"</u>, pages 473-480. Addison-Wesley
     Publishing Company, Reading, Massachusetts.

  }]
  [Ref 3 atomic_commit_page {
    SQLite Online Documentation,<u>How SQLite Implements Atomic Commit</u>,
    <a href="http://www.sqlite.org/atomiccommit.html">http://www.sqlite.org/atomiccommit.html</a>.


  }]
  </table>

}]
</tcl>

<div id=toc>
<tcl>hd_puts $TOC</tcl>
</div id=toc>
<tcl>hd_puts [FixReferences $body]</tcl>