Database queries, searching and sorting

In an online shop you tick “price under 50 manat” and “rating above 4” — and out of thousands of products only a few are left. That is a query: the DBMS checks every record against the condition and shows only the ones that fit.

Every entrance exam paper has one query task: find how many records satisfy a query, which record numbers are selected, or how a record moves after sorting. The structure of tables is explained in the lesson “Databases: models, DBMS and related tables”.

Queries and simple conditions

Compound conditions: AND, OR, NOT

Simple conditions are combined with logical operations — the AND, OR and NOT from the lesson “Boolean logic and logic gates”. DİM tasks write them in English: AND, OR, NOT. Once we know the set of records for each simple condition, a compound condition becomes operations on sets. M(A) is the set of numbers of the records that meet condition A.

Examples on the “Olympiad” table: (Math > 18) AND (Informatics >= 20) → {2, 4, 6} ∩ {1, 3, 5, 6} = {6}; (Math > 18) OR (Physics > 20) → {2, 4, 6} ∪ {2, 4, 7} = {2, 4, 6, 7}; NOT (Physics > 15) → {1, 6}. Order of operations: brackets first (from the inside out), then NOT, then AND, and OR last. DİM queries usually have brackets: start from the innermost one, and where there are none, follow the order NOT → AND → OR. The same logic works in internet search — see “Searching the internet: search engines and queries”.

1. 1
   Split into simple conditions

   For each simple condition in the query write down its set of records.

2. 2
   Apply NOT

   For a condition under NOT take the remaining records — or flip the sign.

3. 3
   Open brackets from the inside

   AND → intersection, OR → union; write every intermediate result down.

4. 4
   Read off the answer

   The final set gives the selected record numbers; the number of its elements is the number of records.

Masks: * and ?

In a text field we sometimes look not for an exact value but for a mask — a pattern. A mask has two special signs: * — any number of any characters (zero included), ? — exactly one arbitrary character. In DİM notation a mask is written in quotes after an equals sign: Destination = “*n”.

Sorting

When sorting by two fields, records are first arranged by the first field; records with equal values in the first field are then ordered by the second field. For example, Baku, Ganja, Lankaran, Shaki is an ascending list of cities. DİM’s hardest query task combines a filter and a sort:

1. 1
   Apply the query

   Write the selected records into a new table in their original order.

2. 2
   Note the old position

   Write down which row of this new table holds the record you need: k.

3. 3
   Sort

   Sort the result table by the given field in ascending or descending order.

4. 4
   Compare with the new position

   Let the new position be m: k − m > 0 means “k − m rows up”, k − m < 0 means down, k = m means unchanged.

rows = [('Kamran', 72, 81, 64), ('Sabina', 88, 69, 90), ('Orkhan', 65, 77, 71),
        ('Fidan', 90, 85, 58), ('Tural', 70, 62, 83), ('Gunay', 59, 74, 76)]

# query: ((Math >= 70 OR Chemistry > 75) AND Physics > 65)
result = [r for r in rows if (r[1] >= 70 or r[3] > 75) and r[2] > 65]
print('After the query:', [r[0] for r in result])

# sort by Chemistry, ascending (reverse=True would give descending)
sorted_rows = sorted(result, key=lambda r: r[3])
print('After sorting: ', [r[0] for r in sorted_rows])

k = [r[0] for r in result].index('Fidan') + 1
m = [r[0] for r in sorted_rows].index('Fidan') + 1
print('Fidan:', k, '->', m, '| rows up:', k - m)

After the query: ['Kamran', 'Sabina', 'Fidan', 'Gunay']
After sorting:  ['Fidan', 'Kamran', 'Gunay', 'Sabina']
Fidan: 3 -> 1 | rows up: 2