html>
Lectures of Dennis Shasha
A Strong Working Knowledge of K
Dennis Shasha
Courant Institute of Mathematical Sciences
Department of Computer Science
New York University
shasha@cs.nyu.edu
http://cs.nyu.edu/cs/faculty/shasha/index.html
Unit 3: Tables and Database Facilities
-
In K, one can implement tables and do selects, group bys,
and sorts in a natural way.
The cool thing is that the operations take place on ordered
data allowing for far more efficient implementations
than using sybperl or embedded SQL.
-
In this unit we concentrate on queries.
Later we will discuss transactions.
Topics
-
tables and how to form them.
-
the K tree and its relationship to tables
-
select, sort, group, etc.
-
exercise: the cost of goods sold.
-
exercise: typical table queries.
-
exercise: relational algebra
Constructing Tables, method 1
Constructing Tables, method 2
The K (data and function) tree
-
Like Unix, NT, and the Mac, K organizes data into a tree.
When you first invoke the system, you are in a subtree
which is denoted dot (.k).
-
When you create a table, that creates a subnode within the current
node.
One can descend into that node by using \d
One goes up by typing \d ^
One finds the current node by typing \d
names: (`bob; `carol; `ted; `alice)
name: names[100 _draw 4]
id: 100 _draw 999999999 / social security numbers
salary: 100 _draw 1000000
emp3: .+(`id`name`salary;(id;name;salary))
id[!10] / returns nothing
\d emp3
\v / list elements of the node
id[!10] / returns the first 10 ids
name[!10] / returns the first 10 names
\d ^
name[!10] / returns nothing
\d . / root node
-
(Navigation in the tree):
Just as other operating systems have absolute references
(e.g. /usr/bin in Unix or c:\winnt\system32 in NT),
so does K.
All such references start with the root node dot (.).
Recall that the initial node is
.k
For example,
names: (`bob; `carol; `ted; `alice)
name: names[100 _draw 4]
id: 100 _draw 999999999 / social security numbers
salary: 100 _draw 1000000
\d
emp3: .+(`id`name`salary;(id;name;salary))
\d .k.emp3
newtable: .+(`new1 `new2;(!10; 10 + !10))
\d
\d .k.emp3.newtable / specifying a location with an absolute path
\d
\v
\d ^ / go up
\d
\d newtable / go back down using relative navigation
\d
\v
-
As a final note, if you run a script starting in node x,
you will end up in x even if the script ends in some
other node.
For example, put the above into a file and fun the file.
After the script is done, type
\d
Summary of Using the Tree
-
Purpose:
The K tree stores variables.
The Windows tree stores files.
-
Root:
The root of the K tree is dot (.)
The root of a Windows file system is backslash as in
c:\
-
Absolute path:
The absolute path from the root in the K tree is
indicated by a sequence that begins
with a dot and has dots between each directory
in the path, as in
.dir1.dir2.dir3.v
Windows uses backslashes
c:\dir1\dir2\dir3\v
-
Relative path:
The relative path from a directory
is also a sequence of names and dots but does
not begin with a dot.
For example if dir1 has subdirectory dir2 which has
subdirectory dir3, then descending to dir3 from dir1
requires the K command:
\d dir2.dir3
The corresponding command in windows is
cd dir2\dir3
-
Finding out which directory one is in requires using
the K command
\d
The windows equivalent is
cd
-
Going up from a subdirectory to a superdirectory in K
entails using the up-caret.
\d ^
The equivalent in windows is
cd ..
Using Tables
Partitioning (Group by) and Tables
-
Suppose we want to find the sum of salaries of each employee name.
-
part: = emp3.name / list of entries, each holding
/ an indexes of everyone with same name.
-
Then we form the names without duplicates
in same order as the lists.
r.people: ? emp3.name
-
r.sumofsalaries: +/'emp3.salary[part]
/ where the +/' means sum over each / partition.
Exercise
-
Find the names of people who have the median salary.
Note: You may find it useful to know that _ means floor
(take integer less than or equal to a number, e.g. 3 = _ 3.2
and % means divided by.
Names Having the Median Salary
Exercise: Assemble a Table with Grouping
-
Given a table of purchases
purchase.date: (!10), (|!5)
purchase.item: (10 # `candy), (5 # `toys)
purchase.qty: 100 + 15 _draw 400
purchase.price: 20 + !15
form the itempurchase table which
holds each item with all the purchase, qty and price information.
itempurchase.item: ? purchase.item / remove duplicates
part: = purchase.item / gives itemsets in the same order as above
itempurchase.qtys: purchase.qty[part]
itempurchase.price: purchase.price[part]
itempurchase.date: purchase.date[part]
Exercise: FIFO Accounting
-
Suppose we are a trading company.
Using FIFO accounting, the cost of selling w widgets
is the cost of the first w widgets we have bought.
This is a difficult query to do in a relational context,
because relations don't support order.
How would you do it?
purchase.date: (!10), (|!5)
purchase.item: (10 # `candy), (5 # `toys)
purchase.qty: 100 + 15 _draw 400
purchase.price: 20 + !15
sold.item: `candy `toys
sold.qty: 123 756
result.item: ()
result.cost: ()
Cost of Goods Sold: solution
-
The first part of the solution is to formulate
the functions that apply to each vector.
/ given an item, the quantity sold, the quantities bought in order
/ and the prices of those purchases,
/ produce the cost of selling that item.
cogs:{[item; soldqty; boughtvec; pricevec]
scanqty: +\boughtvec
i: (soldqty < scanqty) ? 1 / finds the first point when that holds
if[i > 0
cost: +/ boughtvec[!i] * pricevec[!i]
cost+: (soldqty-scanqty[i-1]) * pricevec[i]
]
if[i = 0
cost: soldqty*pricevec[0]
]
result.item,: item
result.cost,: cost
}
/ takes an index of the sold table.
setup:{[sellindex]
item: sold.item[sellindex]
soldqty: sold.qty[sellindex]
i: & purchase.item = item
boughtvec: purchase.qty[i]
pricevec: purchase.price[i]
dates: purchase.date[i]
j: < dates
boughtvec: boughtvec[j]
pricevec: pricevec[j]
cogs[item;soldqty;boughtvec;pricevec]
}
setup'!#sold.item
`show $ `sold
`show $ `result
`show $ `purchase
More Exercises
-
Given a table for sales:
/ sale(saleid, amount, district, salesagent)
size: 10
sale.saleid: !size
sale.amount: 5000 + size _draw 100000
districts: `rich `posh `extravagant
sale.district: districts[size _draw 3]
salesagents: `alice `bob `carol `fred
sale.salesagent: salesagents[size _draw 4]
`show $ `sale
-
Find all sales by salesagent fred.
-
Find the sum of sales by district.
-
Find the sum of sales by district of fred.
-
Find the top three sales per district.
If there are fewer than three sales in a district,
then don't give any of them.
-
Find the sum of sales by district and sales agent
select salesagent, district sum(sale)
from sale
group by salesagent, district
Sales Solutions
/ I. Find all sales by salesagent fred.
i: & sale.salesagent = `fred / Find the indexes of sales by fred.
+sale[;i] / the initial + puts it in record format
/ II. Find the sum of sales by district.
part: = sale.district
+(?sale.district; +/'sale.amount[part])
/ III. Find the sum of sales by district of fred.
i: & sale.salesagent = `fred
part: = sale.district[i]
/ Among those in i, find groups with the same district.
+(?sale.district[i]; +/' sale.amount[i][part])
/ IV. Find the top three sales per district.
/ If there are fewer than three sales in a district,
/ then don't give any of them.
top:{[number; district]
i: & sale.district = district / find the indexes in that district
amounts: sale.amount[i] / find the sales there
orderedvec: amounts[> amounts] / sort by amount
:[number < #orderedvec / depending on number in result, take the top
district, ,orderedvec[!number]
district, ,orderedvec]}
top[3]'?sale.district
/ V. Find the sum of sales by district and sales agent
/ select salesagent, district sum(sale)
/ from sale
/ group by salesagent, district
part: = sale.salesagent,' sale.district / need the each to get all pairs
groupers: ? sale.salesagent ,' sale.district
groupers ,' +/'sale.amount[part]
/ VI. Find pairs of salesagents who work in the same district.
/ select s1.district, s1.salesagent, s2.salesagent
/ from sale s1, sale s2
/ where s1.district = s2.district
findcross:{[district]
i: & sale.district = district
all: sale.salesagent[i] ,\:/: sale.salesagent[i]
allnodups: ?,/all
district ,/: allnodups}
findcross'?sale.district
Exercise: Most of Relational Algebra
-
Relational algebra consists essentially of select,
project, union, intersect, and join.
We have already seen how to do select and project.
Let's do union, intersect, and foreign key join.
/ finds the non-duplicated union of two lists
union:{[x;y] ?x,y}
/finds intersection of two lists
intersect:{[x;y] x[& x _in\: y]}
/finds set difference of two lists x - y
differ:{[x;y] x[&~ x _in\: y]}
/ select r1 from r1, r2 where r1.a1 = r2.a2
/ This is for a foreign key join with r2.a2 as the key field,
/ so there is at most one r2 tuple with a given a2 value.
foreignKeyJoin:{[r1;a1;r2;a2]
r1[;& r1[a1] _in\: r2[a2]]}
subset:{[subList; superList]
&/ subList _lin superList}
-
Try to find apply this to sets of your choosing.
Then try implementing a general join.
Importing Large Text Files to Tables
-
(advanced topic)
Sometimes, you have extremely large text files and you must
read them in.
-
In this case we have a file having three fields, a string, integer,
and float.
The widths are 5, 4, and 8 respectively.
jack 23 45.633
jill 24 55.33
ed 4 5.33
ellen20 444.3
jack 23 45.633
jill 24 55.33
ed 4 5.33
ellen20 444.3
jack 23 45.633
jill 24 55.33
ed 4 5.33
ellen20 444.3
jack 23 45.633
jill 24 55.33
ed 4 5.33
ellen20 444.3
jack 23 45.633
jill 24 55.33
ed 4 5.33
ellen20 444.3
-
Here is the code, called import.k, to read this and output it to three files
each representing one column.
I've loaded the columns here, but you can adjust both their
names and their types.
This code reads the data in chunks.
/ k import infile
/ infile is for text and outputs are fieldnames
infile: _i[0] / take input from this file
size: 30 / chunk size for importing
process:{[infile;start;size; types; sizes]
while[#*b:(types; sizes) 0:(infile;start;size)
/ while more data
(fieldnames) 5:' b
start+:size
] /increment starting byte
}
fieldnames: `id `age `salary
fieldnames 1:' 0 #' (`;0;0.0) / initialize this
types: "SIF " / last one is for the carriage return/linefeed
fieldsizes: 5 6 8 1 / field widths, the last 1 is for carriage return.
/ calculate size to be an integral number of fieldsizes
multiplier: _ size % (1 + +/fieldsizes) / 1 is for carriage return/linefeed
size: multiplier * (1 + +/fieldsizes)
process[infile;0;size;types;fieldsizes]