0
$\begingroup$

I confused about the description & definition of "key" occuring as terminology for databases and b-trees.

In first case dealing with theory of databases a key is defined as a choice for a in certain sense minimal (see below) subset $K \subset A := \{A_1,A_2,...,A_n\}$ of a fixed set of attributes $A_i$ parametrizing a data table (consisting of relations; a single relation is abstraction of a row in the table), where each attribute is literally a column specifying a property of objects = relations.

A key is characterized by property that there exist no two different relations (a relation is a row) which have exactly the same values for all attributes which belong to the key. And a key is a minimal subset with this property, ie there not exist a proper smaller subset of attributes contained in the key and having the property described in last sentence. Clearly keys are not unique. So the set of a keys is certain subset of the power set $\Omega(A)$ of the set attributes $A_i$. See also here: https://en.wikipedia.org/wiki/Unique_key

On the other hand the key concept occures as well for b-trees: https://en.wikipedia.org/wiki/B-tree#Definition

Here keys are a priori numbers or integers and different knots of b-tree contain different totally ordered subsets of keys where the total order on the space of keys is inherited from the order "$\ge$" for integers $\mathbb{Z}$. Especially the set of keys is a totally ordered subset of integers.

Question: How are the two concept of 'key' related to each other? My first idea was that if we consider in light of for definition (as elements of power set of attributes), we can simply randomly enumerate all the keys (that is associate to each key an number; formally speaking to specify an injection $f:\mathcal{K} \to \mathbb{Z}, K \mapsto f(K)$ where $\mathcal{K} \subset \Omega(A)$)

and then treat them as numbers when working with b-trees. Is this exactly the correct connection or is there another deeper one and my approach is wrong?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ (If this question was about RDB terminology, I'd challenge a tuple of attribute values (a row / entry, modelling an entity) being a relation. Far as I remember, relation was used for the whole (contents of a) table.) $\endgroup$
    – greybeard
    Jun 28, 2020 at 9:53
  • $\begingroup$ (Ah - and the things between tree branches are nodes.) $\endgroup$
    – greybeard
    Jun 28, 2020 at 9:58

1 Answer 1

Reset to default
1
$\begingroup$

There's an indeed a relation that maps the database keys to the B-trees keys $K_d \mapsto K_b, K_b \in \mathbb{Z}$

The B-Tree keys are not random though, they represent the physical location of data stored for that key. At the leaf level there are multiple ( up to the order of the tree) database $K_d$s associated with a single $K_b$ key. The relation is thus not an injective function.

Improve this answer
$\endgroup$
9
  • $\begingroup$ So indeed the B-Tree keys represent abstract keys of a given data (considered as a database) by a map $f:\mathcal{K} \to \mathbb{Z}$? and so by this map the keys are distributed to single knots but as you remarked since this distribution has to be compatible with b-tree structure this forces the function to be in general not injective. but all in all this intuition that the b-tree keys can be thought as a precedure "to number consecutively abstract (database keys" in compatible way with physical location of stored data correct? $\endgroup$
    – user267839
    Jun 28, 2020 at 22:03
  • $\begingroup$ @katalaveino I don't feel that intuition is correct. B-Trees partition the database in such a way that records can quickly be retrieved with a given key. The data records don't need to be numbered consecutively. The partitions may be numbered sequentially but not the data in them. $\endgroup$
    – Koenig Lear
    Jun 28, 2020 at 22:38
  • $\begingroup$ The important bit is that data records are in the correct partitions according to their keys e.g. all records with keys ($K_d$) starting with 'A' to 'C' must be in partition 1 ($K_b$) all those 'D' to 'E' must be in partition 2 ($K_b$) etc. $\endgroup$
    – Koenig Lear
    Jun 28, 2020 at 23:00
  • $\begingroup$ This numbering though can change easily if there are too many records within a given partition e.g. partition 3 may be created from 'A' to 'B' and partition 4 from 'B' to 'C' $\endgroup$
    – Koenig Lear
    Jun 28, 2020 at 23:05
  • $\begingroup$ When you generally talk about 'data' you mean in this context a huge table in databases sense, ie a set of "tuple of attribute values" aka relations aka rows in the table, is it correct? So if I understood you now correctly, the relation beween the two key concepts is that the map $f:\mathcal{K} \to \mathbb{Z}, K_d \mapsto K_b$ "gathers" certain database keys $K_d$ together to numerical b-tree keys $K_b$ in following sense: $\endgroup$
    – user267839
    Jun 29, 2020 at 0:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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