Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
| Autor: | Alfred V. Aho, Thomas G. Szymanski, Jeffrey D. Ullman, Yehoshua Sagiv |
|---|---|
| Rok vydání: | 1981 |
| Předmět: |
Theoretical computer science
General Computer Science Relational database General Mathematics InformationSystems_DATABASEMANAGEMENT Relational algebra Quantitative Biology::Genomics Nested set model Tree (data structure) Tree traversal Relational model Quantitative Biology::Populations and Evolution Conjunctive query Lowest common ancestor Algorithm Mathematics |
| Zdroj: | SIAM Journal on Computing. 10:405-421 |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/0210030 |
| Popis: | We present an algorithm for constructing a tree to satisfy a set of lineage constraints on common ancestors. We then apply this algorithm to synthesize a relational algebra expression from a simple tableau, a problem arising in the theory of relational databases. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|