<p>Hmm...</p>

<p>You could use <a href="http://en.wikipedia.org/wiki/Multigraph#Undirected_multigraph_.28edges_without_own_identity.29" rel="nofollow">undirected multigraphs</a> or <a href="http://en.wikipedia.org/wiki/Graph-structured_stack" rel="nofollow">alternative graph structures stacks</a> (epicly space inefficient).</p>

CC BY-SA 3.0
2012-03-05T20:41:59.683Z
Multigraphs are not data structures.
Jeffε
CC BY-SA 3.0
2012-03-05T16:49:54.207Z
2012-03-05T16:49:54.207Z
A T
<p>This question might be a little ill-specified, but the idea I want to explore is:</p>

<ol>
<li><p>User writes a bunch of queries that they want to perform over some data (for concreteness, just consider it a read-only database table)</p></li>
<li><p>The schema for the data is specified</p></li>
</ol>

<p>Using this input, what data structures need to be generated to "efficiently" query the table? The program would read the input data and then generate a bunch of indexess/pre-aggregations so that the queries will be ultra fast.</p>

<p>For a really simple example, say I have a table of logs:</p>

<pre><code>(URL, IP address, user agent, response code)
</code></pre>

<p>And I input a queries like:</p>

<pre><code>select * where URL = http://foo
</code></pre>

<p>Then it should know to automatically generate an index on the URL field.</p>

<p>If I also specify:</p>

<pre><code>select count(*) from table group by IP_address desc limit 20
</code></pre>

<p>or however you specify the 20 most common IP addresses, then it should also generate some pre-aggregation that is efficient (think of having 100 million rows).</p>

<p>I'm sure I am not specifying the problem completely, but I found some papers that seem related, i.e. <a href="http://scholar.google.com/scholar?cluster=1230153639822613926&amp;hl=en&amp;as_sdt=0,5" rel="nofollow">http://scholar.google.com/scholar?cluster=1230153639822613926&amp;hl=en&amp;as_sdt=0,5</a></p>

<p>Looking for more references in this area. This is a computer science/algorithm question; I'm not looking for ways implement to implement this with MySQL or anything like that. Thanks.</p>

<reference-request><ds.data-structures><db.databases><relational-structures>
How to automatically generate indexes and preaggregations from queries
Andy
# How to automatically generate indexes and preaggregations from queries

(Asked by: username_0 on 2011-09-18)

This question might be a little ill-specified, but the idea I want to explore is:

User writes a bunch of queries that they want to perform over some data (for concreteness, just consider it a read-only database table)
The schema for the data is specified

Using this input, what data structures need to be generated to "efficiently" query the table? The program would read the input data and then generate a bunch of indexess/pre-aggregations so that the queries will be ultra fast.
For a really simple example, say I have a table of logs:
(URL, IP address, user agent, response code)

And I input a queries like:
select * where URL = http://foo

Then it should know to automatically generate an index on the URL field.
If I also specify:
select count(*) from table group by IP_address desc limit 20

or however you specify the 20 most common IP addresses, then it should also generate some pre-aggregation that is efficient (think of having 100 million rows).
I'm sure I am not specifying the problem completely, but I found some papers that seem related, i.e. http://scholar.google.com/scholar?cluster=1230153639822613926&hl=en&as_sdt=0,5
Looking for more references in this area. This is a computer science/algorithm question; I'm not looking for ways implement to implement this with MySQL or anything like that. Thanks.

**Tags:** reference-request, ds.data-structures, db.databases, relational-structures


---

## 1 answers

### Answer by username_1 on 2012-03-05. Score: -3

Hmm...

You could use [undirected multigraphs](http://en.wikipedia.org/wiki/Multigraph#Undirected_multigraph_.28edges_without_own_identity.29) or [alternative graph structures stacks](http://en.wikipedia.org/wiki/Graph-structured_stack) (epicly space inefficient).

> **Comments:**
> **username_2**: Multigraphs are not data structures.  

---

