article

Free access

Implementing a generalized access path structure for a relational database system

Editor: David K. Hsiao Author:

Theo HaerderAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 3, Issue 3

Pages 285 - 298

https://doi.org/10.1145/320263.320284

Published: 01 September 1978 Publication History

PDF eReader

Abstract

A new kind of implementation technique for access paths connecting sets of tuples qualified by attribute values is described. It combines the advantages of pointer chain and multilevel index implementation techniques. Compared to these structures the generalized access path structure is at least competitive in performing retrieval and update operations, while a considerable storage space saving is gained. Some additional features of this structure support m-way joins and the evaluation of multirelation queries, and allow efficient checks of integrity assertions and simple reorganization schemes.

References

[1]

ASTRAHAN, M.M., ET AL. System R: Relational approach to database management. A CM Trans. Database Syst./, 2 (June 1976), 97-137.

Digital Library

Google Scholar

[2]

BACHMAN, C.W. Implementation techniques for data structure sets. In Data Base Management Systems, D.A. Jardine, Ed., North-Holland Pub. Co., Amsterdam, 1974, pp. 147-157.

Google Scholar

[3]

BAYER, R., AND MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acta

Google Scholar

[4]

BAYER, R., AND SCHKOLNICK, M. Concurrency of operations on B-Trees. IBM Res. Rep. RJ 1791, IBM Res. Lab., San Jose, Calif., May 1976. To appear in Acta Informatica.

Google Scholar

[5]

BLASGEN, M.W., CASEY, R.G., AND ESWARAN, K.P. An encoding method for multi-field sorting and indexing. IBM Res. Rep., RJ 1753, IBM Res. Lab., San Jose, Calif., March 1976.

Google Scholar

[6]

BLASGEN, M.W., AND ESWARAN, K.P. On the evaluation of queries in a relational database system. IBM Res. Rep. RJ 1745, IBM Res. Lab., San Jose, Calif., 1976.

Google Scholar

[7]

CADIOU, J.M. On semantic issues in the relational model of data. Proc. 5th Symp. on Math. Foundations of Compt. Sci. 1976, Gdansk, Poland, Lecture Notes in Computer Science 45, Springer-Verlag, pp. 23-38.

Crossref

Google Scholar

[8]

CODASYL DATA BASE TASK GROUP (DBTG) Report, April 1971 (available from ACM, New York).

Google Scholar

[9]

CODD, E.F. A relational model of data for large shared data banks. Comm. A CM 13, 6 (June 1970), 377-387.

Digital Library

Google Scholar

[10]

CODD, E.F., AND DATE, C.J. Interactive support for nonprogrammers: The relational and network approaches. IBM Res. Rep. RJ 1400, IBM Res. Lab., San Jose, Calif., June 1974.

Google Scholar

[11]

ESWARAN, K.P., AND CHAMBERLIN, D.D. Functional specifications of a subsystem for data base integrity. Proc. Int. Conf. on Very Large Data Bases, Framingham, Mass., Sept. 1975, pp. 48-68 (available from ACM, New York).

Digital Library

Google Scholar

[12]

HAERDER, T. An implementation technique for a generalized access path structure. IBM Res. Rep. RJ 1837, IBM Res. Lab., San Jose, Calif., Oct. 1976.

Google Scholar

[13]

WEDEKIND, H. On the selection of access paths in a data base system. In Data Base Management, J.W. Klimbie and K.L. Koffeman, Eds., North-Holland Pub. Co., Amsterdam, 1974, pp. 385-397.

Google Scholar

Cited By

View all

Boissier M(2022)Robust and budget-constrained encoding configurations for in-memory database systemsProceedings of the VLDB Endowment10.14778/3503585.350358815:4(780-793)Online publication date: 14-Apr-2022
https://dl.acm.org/doi/10.14778/3503585.3503588
Graefe G(2011)Modern B-Tree TechniquesFoundations and Trends in Databases10.1561/19000000283:4(203-402)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1561/1900000028
Graefe GKuno H(2010)Adaptive indexing for relational keys2010 IEEE 26th International Conference on Data Engineering Workshops (ICDEW 2010)10.1109/ICDEW.2010.5452743(69-74)Online publication date: Mar-2010
https://doi.org/10.1109/ICDEW.2010.5452743
Show More Cited By

Index Terms

Implementing a generalized access path structure for a relational database system
1. Information systems
  1. Data management systems
    1. Database design and models
      1. Relational database model
    2. Query languages
      1. Relational database query languages

Recommendations

Relational database: a practical foundation for productivity
ACM Turing award lectures

It is well known that the growth in demands from end users for new applications is outstripping the capability of data processing departments to implement the corresponding application programs. There are two complementary approaches to attacking this ...
System R: relational approach to database management

System R is a database management system which provides a high level relational data interface. The systems provides a high level of data independence by isolating the end user as much as possible from underlying storage structures. The system permits ...
Relational database: a practical foundation for productivity

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1978

Published in TODS Volume 3, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

74
Total Citations
View Citations
582
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)9

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Boissier M(2022)Robust and budget-constrained encoding configurations for in-memory database systemsProceedings of the VLDB Endowment10.14778/3503585.350358815:4(780-793)Online publication date: 14-Apr-2022
https://dl.acm.org/doi/10.14778/3503585.3503588
Graefe G(2011)Modern B-Tree TechniquesFoundations and Trends in Databases10.1561/19000000283:4(203-402)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1561/1900000028
Graefe GKuno H(2010)Adaptive indexing for relational keys2010 IEEE 26th International Conference on Data Engineering Workshops (ICDEW 2010)10.1109/ICDEW.2010.5452743(69-74)Online publication date: Mar-2010
https://doi.org/10.1109/ICDEW.2010.5452743
Graefe G(2009)The five-minute rule 20 years later (and how flash memory changes the rules)Communications of the ACM10.1145/1538788.153880552:7(48-59)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1145/1538788.1538805
Pettovello PFotouhi FNg JCouturier CVigder MChechik M(2008)Efficient XPath query processingProceedings of the 2008 conference of the center for advanced studies on collaborative research: meeting of minds10.1145/1463788.1463791(14-26)Online publication date: 27-Oct-2008
https://dl.acm.org/doi/10.1145/1463788.1463791
Graefe G(2008)The Five-Minute Rule 20 Years Later: and How Flash Memory Changes the RulesQueue10.1145/1413254.14132646:4(40-52)Online publication date: 1-Jul-2008
https://dl.acm.org/doi/10.1145/1413254.1413264
Graefe GAilamaki ALuo Q(2007)The five-minute rule twenty years later, and how flash memory changes the rulesProceedings of the 3rd international workshop on Data management on new hardware10.1145/1363189.1363198(1-9)Online publication date: 15-Jun-2007
https://dl.acm.org/doi/10.1145/1363189.1363198
Graefe G(2007)Master-detail clustering using merged indexesInformatik - Forschung und Entwicklung10.1007/s00450-007-0022-421:3-4(127-145)Online publication date: 8-May-2007
https://doi.org/10.1007/s00450-007-0022-4
Reimer M(2006)Implementation of the database programming language modula/R on the personal computer lilithSoftware: Practice and Experience10.1002/spe.438014100514:10(945-956)Online publication date: 30-Oct-2006
https://doi.org/10.1002/spe.4380141005
Puchmeral PThevenin J(2005)A graph based data structure for efficient implementation of main memory DBMS'sDatabase Machines10.1007/3-540-51324-8_29(73-96)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-51324-8_29
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Relational database: a practical foundation for productivity

System R: relational approach to database management

Relational database: a practical foundation for productivity

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations