[go: up one dir, main page]

WO2003030019A2 - Procede et dispositif de memorisation de donnees hierarchiquement dependantes - Google Patents

Procede et dispositif de memorisation de donnees hierarchiquement dependantes Download PDF

Info

Publication number
WO2003030019A2
WO2003030019A2 PCT/DE2002/003592 DE0203592W WO03030019A2 WO 2003030019 A2 WO2003030019 A2 WO 2003030019A2 DE 0203592 W DE0203592 W DE 0203592W WO 03030019 A2 WO03030019 A2 WO 03030019A2
Authority
WO
WIPO (PCT)
Prior art keywords
data
data objects
objects
stored
data object
Prior art date
Application number
PCT/DE2002/003592
Other languages
German (de)
English (en)
Other versions
WO2003030019A3 (fr
Inventor
Giovanni Rabaioli
Original Assignee
Siemens Aktiengesellschaft
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Siemens Aktiengesellschaft filed Critical Siemens Aktiengesellschaft
Priority to EP02776708A priority Critical patent/EP1430425A2/fr
Publication of WO2003030019A2 publication Critical patent/WO2003030019A2/fr
Publication of WO2003030019A3 publication Critical patent/WO2003030019A3/fr

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2246—Trees, e.g. B+trees
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2272—Management thereof

Definitions

  • Directories usually have a hierarchical structure. Information recorded in a directory is managed by subdivision into hierarchy levels. For example, such a subdivision occurs first by country, then by organization, organizational unit and finally by person.
  • index-sequential access methods or relational database systems is known for managing such data.
  • the hierarchical structure of directory data is insufficiently taken into account.
  • Access methods manage data in sorted form without taking hierarchical dependencies into account.
  • relational database systems With relational database systems, only linear relations can be mapped. Neither the use of index-sequential access methods nor the use of relational database systems enable an effective optimization of write and read processes for hierarchically dependent data. Compared to computing processes, write and read processes for hierarchically dependent data even prove to be extremely time-consuming.
  • the present invention has for its object to provide a method and an arrangement for a management of hierarchically dependent data.
  • hierarchically dependent data are stored divided into data objects comprising first useful data and second data objects which have references to first and second data objects.
  • This subdivision usually means that the first data objects contain large amounts of data on object attributes without hierarchical dependency.
  • the second data objects are used to map hierarchical dependencies and allow a description of the structure of a directory tree.
  • the second data objects are significantly less memory-intensive.
  • the frequency of use of the second data objects is significantly higher than that of the first data objects. This results from the fact that reading and searching processes are by far the most common types of access in directory systems.
  • the directory tree described by the second data objects is first searched up to a node which fulfills predetermined search criteria. Finally, referenced useful data are read out by the determined node and the reading or search process is ended.
  • a large number of second data objects are used during a read or search process, while rend only a single first data object is read out. It follows from the memory intensity and the frequency of use of the first and second data objects that the probability for a first data object to be loaded into a main memory or cache of a data processing system is rather low. In contrast, the probability of a second data object tends to be very high.
  • An optimized management of hierarchically dependent data results according to the invention from the fact that frequently used data objects are available with high probability in a storage medium with high access speeds due to the division described above.
  • access to a working memory or a cache takes ten times less time than access to mass data storage media such as hard disks or CD-Roms.
  • FIG. 1 shows a directory tree with hierarchically dependent data
  • FIG. 2 shows a result of using a method for storing hierarchically dependent data
  • the directory tree shown in FIG. 1 has a large number of nodes 101 and references 102.
  • the references 102 are each from a node 101 to one or more
  • Node 101 directed which are assigned to a hierarchy level 103 directly subordinate to the referring node 101.
  • the highest hierarchical level 103 of the directory tree is called
  • subordinate hierarchy levels 103 are the hierarchy levels "Country”, “Network”, “Subnet”, “Organization”, “Location”, “Last Name” and “Name”.
  • the nodes 101 in the lowest hierarchy level 103 "first name” have additional attributes 104 which identify the objects represented by the nodes 101.
  • all nodes 101 can have attributes 104 regardless of the respective hierarchy level 103.
  • an explicit representation of the attributes 104 of the individual nodes 101 with the exception of the attributes 104 of the nodes 101 in the lowest hierarchical level 103 is dispensed with.
  • a node 101 is uniquely identified by specifying a path from the "root" to the respective node 101 and naming all nodes 101 in accordance with their sequence along the path. Such a path specification thus forms a unique key for a node 101.
  • Each node 101 also has a unique relative key in relation to the node 101 which is immediately superior.
  • the designations shown in the individual nodes 101 represent the respective relative keys.
  • An object represented by a node 101 can also have references to other objects as the attribute 104 in addition to the usual attributes such as "telephone number", “fax number”, “room number” etc. With such a reference, for example, a first employee “Klaus” can refer to a second employee “Erika” as his deputy. Such references are in principle also possible between nodes 101 of different hierarchy levels 103.
  • the memory structure shown in FIG. 2 reflects the management of the hierarchically dependent data shown in FIG. 1 after using a method for storing hierarchically dependent data. By means of such a method, hierarchically dependent data are stored in subdivided form in the first data objects 201 having useful data and in second data objects 202 which have arrows symbolized references to first 201 and second data objects 202.
  • the first data objects 201 are stored as data blocks in a first storage unit 205, while the second data objects 202 are stored as data blocks in a second storage unit 206.
  • Storage in two separate storage units 205, 206 offers the advantage of improved parallelization of write and read processes.
  • the storage units 205, 206 are usually formed by files or storage disks which are assigned to a data processing system which is not explicit in FIG. 2 and by which the described method for storing hierarchically dependent data is carried out.
  • the second storage unit 206 includes data blocks with third 203 and fourth data blocks 204, the meaning of which will be discussed in more detail below.
  • the useful data comprised by the first data objects 201 are stored in a field 211 of the respective data block provided for attributes.
  • the references to first 201 and second data objects 202 in the second file objects 202 symbolized by arrows represent the hierarchical dependencies between the data corresponding to FIG. 1. In the sense of a simple and understandable representation, only the hierarchy levels 103 "root”, “country”, “location”, "last name” and "first name” are taken into account in FIG.
  • the hierarchy levels from "root” to “surname” are mapped by second data objects 202, while the lowest hierarchy level 103 "first name” is mapped by first data objects 201.
  • first data objects 201 In the sense of a simplified representation, it is assumed for the hierarchy levels 103 "root” to "last name”, as already mentioned above, that nodes 101 assigned to these hierarchy levels 103 have no attributes 104.
  • block numbers of the data objects 201 to 204 correspond to the addresses of the respective data blocks.
  • the data blocks for the first data objects 201 have a field 212 for a relative key (RDN - Relative Distinguishing Name), a field 213 for a reference to a further first data object 201 (RAD - Reference Address) Field 214 for a reference to an immediately superordinate second data object 202 (PAD - Parent Address) as well as fields 215, 216 for a start flag and an end flag.
  • RDN relative key
  • PARENT - Reference Address a field 213 for a reference to a further first data object 201
  • Field 214 for a reference to an immediately superordinate second data object 202 (PAD - Parent Address)
  • fields 215, 216 for a start flag and an end flag.
  • a data block for a first data object 201 can be uniquely identified via the block number, which is also referred to as directory service identification in directory systems.
  • Data blocks for second data objects 202 have a list 221 with directly subordinate first 201 and second data objects 202 (CH - Child).
  • a list 221 is implemented, for example, by a hash table.
  • each possible key of a second data object 202 which in the directory system is also called Distinguishing name is known, the block number for the respective first 201 or second data object 202 is uniquely assigned.
  • Fields 222 for the relative keys and fields 223 for the block numbers of the subordinate data objects 201, 202 are provided in the list 221 for immediately subordinate first 201 or second data objects 202.
  • the reason for the basically redundant storage of relative keys on the one hand and block numbers on the other hand is due to a performance optimization. For a resolution of relative keys that are chained together
  • Third data objects 203 are generated for reference from a referencing first data object 201 to a referenced first data object 201 and stored in the second storage unit 206.
  • the respective third data object 203 has a reference to the referenced first data object 201.
  • a block number of a third data object 203 which represents a placeholder for a respectively referenced first data object 201, is stored in the field 213 in a data block of a referencing first data object 201.
  • the block number of a third data object 203 is stored in the field 213 provided for references to further first data objects 201 in the data block of the first data object 201 with the relative key "Klaus", which in turn refers to the referenced first data object 201 with the relative key " Erika "refers.
  • said third data object 203 contains the block number of the first data tenobjjekt 201 with the relative key "Erika”.
  • the block number of a second data object 202 superior to the referenced first data object and the relative key of the referenced first data object 201 can also be stored in a third data object 203.
  • the third data object 203 would refer indirectly to the referenced first data object 201 via the second data object 202 superordinate to the referenced first data object 201.
  • second data objects 202 which are hierarchically dependent on a selected second data object 202 and first data objects 201 assigned to them by references are determined.
  • storage locations of the determined first data objects 201 within the first storage unit 205 are used to identify positions that are stored in the fourth data object 204.
  • the respective fourth data object 204 is assigned to a second data object 202 that represents the start of a corresponding subtree.
  • the determined positions of the first data objects 201 are stored in a combined manner as a bit pattern in the respective data object 204.
  • a bit within the image pattern represents a storage location within the first storage unit 205.
  • the introduction of fourth data objects 204 enables simple handling of search queries which are limited only to selected subtrees of a directory tree. For this purpose, the entire search tree is searched in accordance with the search query and the positions of the determined first data objects 201 are stored analogously as a query bit pattern.
  • a plurality of data objects 202 to 204 of one type stored in the second storage device 206 are combined in one data block. In this way, the data stored in the second storage unit 206
  • the content of the second storage unit 206 is at least partially loaded into a working memory or a cache of a data processing system, not shown. Because of the small data block size and the high frequency of use of the data objects 202 to 204 stored in the second storage unit 206, there is a high probability that these data objects will be kept in the main memory or in the cache.
  • a first data object 201 can be stored in a single data block.
  • Outsourcing of data has proven to be advantageous in numerous cases, in order to be able to use a uniform data block length in this way without unnecessarily wasting memory resources and without unnecessary administration effort.
  • the data block length for the outsourced data can be variable.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Radar Systems Or Details Thereof (AREA)

Abstract

Selon l'invention, des données hiérarchiquement dépendantes sont divisées en premiers objets de données, qui contiennent des données utiles, et en seconds objets de données, qui contiennent des références aux premiers et/ou aux seconds objets de données, puis elles sont mémorisées dans au moins une unité de mémoire.
PCT/DE2002/003592 2001-09-28 2002-09-24 Procede et dispositif de memorisation de donnees hierarchiquement dependantes WO2003030019A2 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
EP02776708A EP1430425A2 (fr) 2001-09-28 2002-09-24 Procede et dispositif de memorisation de donnees hierarchiquement dependantes

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
DE10148008.3 2001-09-28
DE10148008A DE10148008A1 (de) 2001-09-28 2001-09-28 Verfahren und Anordnung zur Speicherung hierarchisch abhängiger Daten

Publications (2)

Publication Number Publication Date
WO2003030019A2 true WO2003030019A2 (fr) 2003-04-10
WO2003030019A3 WO2003030019A3 (fr) 2004-01-29

Family

ID=7700723

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/DE2002/003592 WO2003030019A2 (fr) 2001-09-28 2002-09-24 Procede et dispositif de memorisation de donnees hierarchiquement dependantes

Country Status (3)

Country Link
EP (1) EP1430425A2 (fr)
DE (1) DE10148008A1 (fr)
WO (1) WO2003030019A2 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7246102B2 (en) 2001-12-21 2007-07-17 Agere Systems Inc. Method of improving the lookup performance of three-type knowledge base searches

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5295261A (en) * 1990-07-27 1994-03-15 Pacific Bell Corporation Hybrid database structure linking navigational fields having a hierarchial database structure to informational fields having a relational database structure
US5630125A (en) * 1994-05-23 1997-05-13 Zellweger; Paul Method and apparatus for information management using an open hierarchical data structure
DE19538240A1 (de) * 1995-10-13 1998-08-06 Annette Brueckner Informationssystem und Verfahren zur Speicherung von Daten in einem Informationssystem
US5758353A (en) * 1995-12-01 1998-05-26 Sand Technology Systems International, Inc. Storage and retrieval of ordered sets of keys in a compact 0-complete tree

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7246102B2 (en) 2001-12-21 2007-07-17 Agere Systems Inc. Method of improving the lookup performance of three-type knowledge base searches

Also Published As

Publication number Publication date
DE10148008A1 (de) 2003-04-24
WO2003030019A3 (fr) 2004-01-29
EP1430425A2 (fr) 2004-06-23

Similar Documents

Publication Publication Date Title
DE3856055T2 (de) Verfahren und Einrichtung, um gleichzeitigen Zugriff zu indizierten sequentiellen Dateien zu ermöglichen
DE69530595T2 (de) System und verfahren für die x.500-datenbanknorm
DE4218025C2 (de) Vorrichtung und Verfahren zur automatischen Zuordnung von Datenspeichereinrichtungen in einem Computersystem
DE3382808T2 (de) Datenbankzugriffsverfahren mit einem benutzerfreundlichen Menü
DE60019839T2 (de) Verfahren zum Austauch von Daten zwischen einer Javasystemdatenbank und einem LDAP Verzeichnis
DE3855213T2 (de) Datenbanksystem und Verfahren für den gleichzeitigen Satzzugriff mit Hilfe eines Baumstrukturindexes
DE69430027T2 (de) Effiziente Speicherung eines Objektes in einem Dateisystem
DE3688529T2 (de) Verfahren zur Auffrischung von Mehrspaltentabellen in einer relationellen Datenbank mit Mindestinformation.
DE69229056T2 (de) Offene verzeichnis-datenbankansichten
DE69704085T2 (de) Optimierung des zugriffes auf multiplexierte datenströme
DE19747583B4 (de) Kommunikationssystem und Verfahren
EP0910829B1 (fr) Systeme de banque de donnees
DE69024932T2 (de) Verfahren um Dokumente, die ein bestimmtes Attribut haben, mit Hilfe eines vektorrelationalen charakteristischen Objektes zu identifizieren
DE60118973T2 (de) Verfahren zum abfragen einer struktur komprimierter daten
DE69031164T2 (de) Zeitlich begrenztes zentrumsystem für dezentralisiertes datenbanksystem
WO2015090668A1 (fr) Système de fichiers compatible posix, procédé de génération d'une liste de fichiers et dispositif de mémoire
DE19844013A1 (de) Strukturierter Arbeitsordner
DE69127399T2 (de) Verfahren zur automatischen Löschung vorübergehender Dokumentverbindungen in einem Datenverarbeitungssystem
DE10255128A1 (de) Computer-implementierte PDF-Dokumentenverwaltung
DE69700557T2 (de) Einrichtung und Verfahren um eine Dateinummer während einer Betriebsunterbrechung in einem client-server Netzwerk, abzubilden
EP0855062A2 (fr) Systeme d'informations et procede de memorisation de donnees dans un systeme d'informations
DE69027017T2 (de) Anordnung und Verfahren zur Speicherverwaltung in einem Mikrorechner
DE69123493T2 (de) Verarbeitungsverfahren und Gerät um einen Dateinamen von einem logischen zu einem richtigen Namen zu erstellen
DE19534819B4 (de) Verfahren und Vorrichtung zum Konfigurieren einer Datenbank
DE69932147T2 (de) Kommunikationseinheit und Kommunikationsverfahren mit Profilverwaltung

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BY BZ CA CH CN CO CR CU CZ DK DZ EC EE ES FI GB GD GE GH GM HR ID IL IN IS JP KE KG KP KR KZ LC LK LS LT LU LV MA MD MG MK MN MW MZ NO NZ OM PH PL PT RO RU SD SE SI SK SL TJ TM TN TR TT TZ UA UG UZ VC VN YU ZA ZM

AL Designated countries for regional patents

Kind code of ref document: A2

Designated state(s): GH GM KE LS MW MZ SD SL SZ UG ZM ZW AM AZ BY KG KZ RU TJ TM AT BE BG CH CY CZ DK EE ES FI FR GB GR IE IT LU MC PT SE SK TR BF BJ CF CG CI GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2002776708

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 2002776708

Country of ref document: EP

WWW Wipo information: withdrawn in national office

Ref document number: 2002776708

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: JP

WWW Wipo information: withdrawn in national office

Country of ref document: JP