1 EP O 526 034 B1 2
Description the one or more first search criteria match one or
more of the previously-stored data files, retrieving
Technical Field the or eaCh previouSly-Stored data file whiCh
matches the one or more first search criteria.
_OO01 l The present invention relates to a computer _
system and, more particularly, to the accessing of a file _OO05l A second aspect of the present invention
system thereof. provides a method of accessing a plurality of previously
stored data files as defined in claim 1 1.
Back round of the Invention _OO06l According to the present invention, a compu-
Io ter-based filed apparatus permits a real-time user-
_OO02l Ne_or_, such as local area ne_orks selectable search request of previously stored data
(LANs), now enable personal computers (PCs) (typi- objects using file access system calls which use search
cally referred to as clients) to share resources, such as criteria other than a file-name-substring matching. The
disk storage and printers, typically located at a host or file access system call includes a purported file name
server. These types of ne_orks are generally referred 1_ containing one or more non-file-name-substring-based
to as clien_server ne_orks. In such clien_server net- search criteria. Using my non-file-name-substring-
works common databases required by the clients are based search technique, a user can do look-up-by-key,
also typically stored at the server location. To enable cli- relational look-up, phonetic look-up, and find-operator
ents to access the various common databases usually look-up to locate one or more stored data objects of any
requires the use of one or more database management 2o database or file system of the apparatus. A user may be
systems (DBMS) at the server location. Moreover, to a person, a program or an apparatus desiring to access
enable a client access to one of the common databases stored data objects. According to one feature, a key
also requires that each client has the DBMS access associated with each located data object is returned to
so_ware. Unfortunately, the various DBMS access soft- the user. The search criteria may identify single-data
ware required at a client location utilizes significant 2_ object or multiple-data objects. Another feature enables
memory space, is costly, and must periodically be multiple-data objects to be organized in a virtual direc-
administered or updated. Moreover, when more than tory to facilitate subsequent data object access by the
one type of DBMS is required at a server location, user.
because of the types of database utilized or because of
client needs or preferences, the problem becomes more 3o Brief Descri tion of the Drawin
severe. Thus, there is a continuing need to improve cli-
ent database access arrangements in a practical, cost- _OOOll ln the drawing
effective manner.
_ooo3l The,,grep,, or,,find,, commands of a uNlx_ FIG. 1 is a block diagram of a clien_server network
system can locate purported file names which fulfil non- 3_ including a server computer in which the present
file name substring-based search criteria. These com- invention may be utilized;
mands are disclosed in ''the UNIX system V'' by S. R. FIG. 2 shows a logical and physical structure of a
Bourne, Addison Wesley, 1 988. file and a file system;
_OO04l A first aspect of the present invention pro- FIG. 3 defines various terms useful in describing
vides a computer based file apparatus for accessing a 4o the present invention;
plurality of previously-stored data files, the apparatus FIGs. 4 and 5 illustrate a flow chart describing vari-
comprising. ous operating features of the present invention;
FIG. 6 shows an illustrative flow chart for imple-
means for receiving a user request including a pur- menting a single-object look-up criteria;
ported file name; 4_ FIG. 7 shows an illustrative flow chart for imple-
means for comparing the purported file name with menting a multi-object look-up criteria; and
the file names of the previously-stored data files FIG. 8 illustrates a logical structure of a directory.
and, if the purported file name matches the file
name of one of the previously-stored data files, Hi h Level Descri tion
retrieving the previously-stored data file whose file _o
name matches the purported file name; _OO08l ln the following description, each item or
means for, if the purported file name does not block of each figure has a reference designation associ-
match the file name of one of the previously-stored ated therewith, the first number of which refers to the fig-
data files, parsing the purported file name using a ure in which that item is first located (e.g., 1 1 O is located
first logical syntax to generate one or more non-file- __ in FIG. 1 and step 439 is located in FIG. 4).
name-substring-based first search criteria; and _OO09l Shown in FIG. 1 is a block diagram of an
means for comparing the one or more first search illustrative clien_server system or ne_ork in which the
criteria with the previously-stored data files and, if present invention may be utilized. The ne_ork includes
2
3 EP O 526 034 B1 4
a server computer IOO connected to a plurality of client 1 30, or just the kernel, emphasizing its isolation from
workstations or computers 1 02, I03 via a local area net- user programs. Because user programs are independ-
work (LAN) 1 04. Server computer 1 OO, illustratively, pro- ent of the underlying hardware, it is easy to move them
vides the client computers 1 02, 1 03 shared access to between UNIX systems running on different hardware.
data Stored on hard diSk 1 80. _ The general deSCription of the well-_own operation of a
_ool ol In one iIIustrative arrangement, each of the UNIX OPerating SYStem iS derived frOm Cha Pter 2 Of the
one or more client computers 1 o2, 1 o3 may be a per- bOOk entitled ''The DeSign Of the UNIX OPerating SYS-
sonal computer (PC) which operates using the well- tem'' bY Mauri Ce J_ BaCh_
known MS-DoS_ operating system or oS12_ operat- _ool 6l The system caII interface 1 31 represents the
ing system. (MS-DOS is a registered trademark of the 1o border be_een user level 1 20 (user programs 1 21 and
Microso_ Corporation. OS12 is a registered trademark program libraries 1 22) and the kernel level 1 30. System
of IBM). The LAN 1 04 may, illustratively, be the A__T call interface 131 converts user program calls into UNIX
STARLAN system. The server computer 1 OO may, illus- system calls. System calls look like ordinary function
tratively, be an A__T 6386 WorkGroup System compu- calls in C programs, and libraries map these function
ter running on uNIx_ System v Release 4.o operating 1_ caIIs to the primitives needed to enter the operating sys-
system. (UNIX is a registered trademark of UNIX Sys- tem in a well-_own manner. The set of system calls
tem Laboratories, lnc.). The client PCs 1 02, 1 03 and includes those that interact with the file system driver
server computer 1 OO may use the A__T StarGROUP'M 1 32 and those that interact with the process control sub-
system sof_are. This StarGROUP system so_ware systems 1 33. The file system driver 1 32 manages files,
allows MS-DOS and OS12 client PCs to transparently 2o allocating file space, controlling access to files, and
share data files on a LAN. retrieving data for users. Processes interact with the file
_O01 1 l The server computer 1 OO running the server system driver 1 32 via a specific set of system calls,
program 1 23 on top of the UNIX operating system 1 20 such as open (to open a file for reading or writing),
can support one or more large hard disks (e.g., I05) close, read, write, stat (query the attributes of a file),
that can be made available to client PCs 1 02 and 1 03 on 2_ chown (change the record of who owns the file) and
the LAN 1 04. chmod (change the access permissions of a file). The
_O01 2l So_are on the client computer 1 03 inter- file system driver 1 32 accesses file data using a buffer
acts with the server program 1 23 on the server compu- 1 36 that regulates data flow between the kernel and
ter 1 OO to allow access to disk 1 80 by client program secondary storage devices. The buffering mechanism
1 1 O. Specifically, system calls referencing disk 1 80 are 3o interacts with block lIO device drivers 1 37 to initiate data
packaged into request messages by the redirector 1 1 2 transfer to and from the kernel. Device drivers 1 34 are
and transmitted to the server program 123 by the net- the kernel modules that control the operation of periph-
work so_ware 1 1 3 (_own in the art as netbios and pro- eral devices. Block lIO devices 1 41 are random access
tocol sof_are) over the local area ne_ork 1 04. The storage devices; alternatively, their device drivers 137
server program 1 23 processes the request and sends a 3_ make them appear to be random access storage
response to the client computer 1 03. devices to the rest of the system. For example, a tape
_O01 3l A more detailed description of the operating driver may allow the kernel to treat a tape unit as a ran-
aspects of the clien_server interaction is described in dom access storage device. The file system also inter-
the article entitled ''DOS Server Program for UNIX Com- acts directly with ''raw'' or character lIO device drivers
puters'' by l. J. Heizer, published in A__T Technolo 4o 1 38 without the intervention of a buffering mechanism.
Volume 4, Number One, 1 989. Raw devices, sometimes called character lIO devices
_O014l Server computer 1 OO, hereinafter referred to 1 42, include all devices that are not block devices.
as the computer-based file system, operates under con- _O01 ll The process control subsystem 1 33 is
trol of a UNIX operating system I05, shown using a responsible for process synchronization, interprocess
high-level architecture layer diagram. The layer diagram 4_ communication, memory management, and process
includes a user level 1 20, a kernel level 1 30, and a hard- scheduling. The file system driver 1 32 and the process
ware level 1 40. The user level 120 interfaces to clients control subsystem 1 33 interact when loading a file into
(hereina_er users) 1 02, I03 via LAN 1 04 enabling memory for execution. The process control subsystem
access to the desired file stored in disk 1 80. 1 33 reads executable files into memory before execut-
_O01 5l The user level 120 includes user programs _o ing them.
1 21 (such as the server program) and libraries 1 22. The _O018l Some of the system calls for controlling
hardware level 1 40 provides the operating system 1 1 O processes include the following. fork (create a new
with basic services needed by computer 1 OO. The ker- process), exec (overlay the image of a program onto the
nel level 1 30 interacts directly with the hardware level running process), exit (finish executing a process), wait
1 40 providing common services to user level 120 pro- __ (synchronize process execution with the exit of a previ-
grams and insulating them from hardware idiosyncra- ously forked process), brk (control the size of memory
sies. Viewing the system as a set of layers, the allocated to a process), and signal (control process
operating system is commonly called the system kernel response to e_raordinary events).
3
5 EP O 526 034 B1 6
_O01 9l With joint reference to FIGs. 1, 2 and 3 we The inode list 223 is a list of inodes that follows the
describe an overview of a file system. Every file is super block in the file system. Administrators specify the
named by one or more path names, 3IO. A path name, size of the inode list 223 when configuring a file system.
as shown in 31 O, includes file names (e.g., home) sep- The file system driver 132 references inodes by index
arated by delimiters (_. File names may be any of the _ into the inode list 223. One inode is the root inode of the
types shown in 330. The internal representation of a file file system. it is the inode by which the root directory
is given by an inode, 200, which contains a description structure of the file system is accessible a_er execution
of the disk layout of the file data and other information of the mount system call. The data blocks 224 start at
such as the file owner, access permissions, and access the end of the inode list and hold the contents of file
timeS. The term inode iS a Contra Ction of the term index 1o data. An alloCated data bloCk ContainS the a Ctual data of
node and is commonly used in literature on the UNIX a file and can belong to one and only one file in the file
system. Every file has one inode, but it may have sev- system.
eral Path nameS, all Of WhiCh maP intO the in Ode_ EaCh _oo22l The operation of the present invention will be
Path name iS Called a link_ When a PrOCeSS referS tO a described as utilized in an Enhanced File System (EFS)
file bY Path name, the kernel ParSeS the Path name One 1_ implemented on a UNIX system using a virtual file sys-
file name COmPOnent at a time, CheCkS that the PrOCeSS tem. Some UNIX systems use a Virtual File System
haS PermiSSi On tO SearCh the direCtOrieS in the Path, and (VFS) concept to organize all file system operations.
eVentUalIY retrieVeS the in Ode fOr the file_ FOr eXamPle, if Although the present invention does not require a VFS
a PrOCeSS makeS the Call ''OPen C_Omeli4P)'' the kernel mechanism, VFS provides a convenient conceptual
retrieveS the inOde fOr ''_Ome_j4P''_ AS Sh Own bY 31 5 a 2o model to explain the invention. VFS is a merge of the
''file SYStem tree'' fOr a full Path name StartS with a SlaSh System V File System Switch (FSS) and the SUN OS
Chara Cter C''_') and SPeCifieS that the Path name iS rela- VFS mechanism. It is important to note that user pro-
tiVe tO the ''rOOt'' Of the file SYStem tree_ FOlIOWing the grams will be unaffected by the SVR4.o VFS architec-
branCheS that lead tO SUCCeSSiVe COmpOnent nameS Of ture.
the Path name ''_Ome__4PlmemOirS'' deSignateS a fUll 2_ _oo23l VFS provides a file system type independent
Path name while ''Ii4PlmemOirS'' dOeS n Ot_ A Path name interface to programs and users while allowing each
dOeS nOt have tO Start frOm rOOt but Can be deSignated particular file system to process file system operations
relatiVe tO the ''CUrrent dire CtOrY'' Of an eXeCUting PrOC- in their own manner. File system type dependent kernel
eSS bY Omitting the initial SlaSh in the Path name_ ThUS, routines do the work specific to the type.
Starting frOm CUrrent direCtOrY ''lhOme'', the Path name 3o _oo24l A key strength of VFS is that it allows new
''Bin'' deSignateS the file WhOSe fUll Path name iS file system types to _e defined and implemented by
''_OmeIBin''_ third-party so_ware houses. The set of kernel interfaces
_O020l When a process creates a new file, the file that constitute VFS are available in a VFS file system
system driver 1 32 assigns it an unused inode. Inodes type writers' guide available from USL.
are stored in a section 223 of the physical file system 3_
220, as will be described shortly, but the file system General Descri tion
driver 1 32 reads them into an incore-memory inode
table when manipulating files. The UNIX system typi- _O025l The present invention permits a program-
cally keeps regular files and directories on block devices matic or human user of the file system (hereina_er col-
such as disks. An installation may have several physical 4o lectively referred to as a user) to access files by
disk units each containing one or more file systems. A purported file names that are completely unrelated to
file system 220 is organized as a sequence of logical the actual name of the file stored in the directory struc-
blocks, each containing 512, 1 024, 2048, or any con- ture. The purported file name is first tested for an exact
venient multiple of 512 bytes, depending on the system match against the file names of existing files. If an exact
implementation. Multiples of 51 2 are used by conven- 4_ match is not found, then EFS attempts to parse the pur-
tion and there is no intrinsic reason to use 512 byte ported name using a logical syntax (described later). If
blocks. the purported file name correctly matches one of the
_O021 l A physical file system may have the physical logical syntaxes (called back-door syntax), then EFS
structure illustrated by 220 of FIG. 2. The boot block 221 returns either the file that matches the logical criteria
(only on some file systems) occupies the beginning of a _o specified via the back-door syntax, or returns a virtual
file system, typically the first disk sector, and may con- directory containing the files that match the logical crite-
tain the bootstrap code that is read into the machine to ria.
boot, or initialize the operating system. Although only _O026l According to another feature of the present
one boot block 221 is needed to boot the system, every invention, there may be many types of exotic look-up cri-
file system may have a (possibly empty) boot block. The __ teria. As previously discussed, existing file systems sup-
super block 222 describes the state of a file system-- port file name matching either by exact character
how large it is, how many files it can store, where to find matching of file names, or by case-insensitive matching,
free space on the file system, and other information. or by some form of substring matching (e.g., ''fo?'', ''f*'').
4
7 EP O 526 034 B1 8
Henceforth, these exotic types of file name matching look-ups are presented as files within a directory. On
are referred to as ''non-conventional '' file name match- conventional file systems the members of a direnory
ing. Thus, in addition to conventional matching, this are the names of the files immediately subordinate to
invention covers non-conventional look-up criteria (i.e., that directory. FIG. 8 illustrates the logical structure of a
non-file-name-substring-based search criteria) for _ directory. Elements in a directory are identified by an
which the purported file name is neither an exact char- inumber-filename pair. In additon to inumber-filename
acter, case-insensitive, nor substring of the target file pairs for all of the files and directories immediately sub-
name. Non-conventional look-up criteria fall into _o ordinate to the particular direnory, there are entries for
broad categories. 1) single-object criteria that can both ''.'' and ''..'' The ''.'' entry identifies the inumber of
match O or 1 objects; 2) multi-objen criteria that can 1o this particular directory, while the ''..'' entry identifies the
match O, 1, or more objens. A single-object criteria may inumber of this directory's immediate superior.
be a Charaneri StiC Of the deSired data Obien, SUCh aS a _oo3ol ln the present invention, the results of a
Uni4Ue identifier Or keY tO the deSired data Obien Ce_g_, multi-object criteria look-up are returned via the get
SoCial SeCuritY number)_ Conventional file name matCh- directory entry (getdents()) system call. Each object is
ing iS a Single-ObjeCt Criteria beCaUSe the file SYStem 1_ returned with a file name and a unique access key as
gUaranteeS that a PartiCUlar file name iS Uni4Ue Within a the inode of the entry. Given the unique access key
direCtOrY_ A IOOk-UP bY in Ode nUmber CaISO referred tO aS (e.g., inumber) of each target entry, a user can then use
inO) iS a Single-ObieCt Criteria beCaUSe in OdeS are a single object criteria, such as,,ino=decimal-inumber,,,
defined tO be Uni4Ue_ A IOOk-UP tO identifY all ObieCtS On to access the target entry. These direnories are,,virtual,,
a file SYStem Owned bY a PartiCular uSer Or tO identifY all 2o in the sense that they are created on demand when a
fileS held in a Parti Cular direCtOrY iS a multi-ObieCt Crite- user as_ to see the contents of the directory, and they
ria beCaUSe SeVeral ObjeCtS COUld SimUltaneOUSIY meet are automatically removed when the user is _one with it.
theSe Criteria_ For example, consider using this invention to implement
_O021l The single object criteria (e.g., key) can an elenronic phone book. An application issues a pho-
directly reference the file object, much like the well- 2_ netic look-up by interrogating the directory ''Iphone-
known ''hard'' or ''symbolic'' link mechanism (using path boo Mphonetic=kacurro.'' Successive calls to the get
names) currently supported in UNIX file systems. In directory entry system call might return. ''caccuro,anne-
essence, a single object criteria may be just another link marie'' with inumber 745; and ''caccuro,john'' with inum-
to a file if 1 file matches the criteria, or just another file ber 1 1 24. The user would select ''caccuro, john'' and the
name that is not found if O files match the criteria. In 3o application would access that entry by opening ''Iphone-
addition to conventional file name matching, this inven- booMno=1 1 24.'' Note that because virtual directories
tion permits prescribed syntaxes, such as syntax 1 in are being created and manipulated, an implementation
332, to be used. could return several entries with identical file names but
_O028l This aspect of the present invention permits different inumbers, such as ''smith,john.''
a 'back-door' access to files to emulate the Macintosh 3_ _O031 l A virtual directory is created when it is first
file identifier (fileid) and directory identifier (dirid) mech- referenced via 'VFS loo_p' and persists until the kernel
anisms. Fileid's and dirid's are fixed-size numeric values signals that it is no longer referenced. Typically, the ker-
that reference a Macintosh file or directory. These id's nel signals that the object is no longer referenced via
are more tractable than the arbitrary-length path names the VFS 'inactive' routine. Note that the ''virtual'' direc-
that are generally used to reference files or directories. 4o tory ''Iphoneboo Mphonetic=kacurro'' is virtual in that it
The present invention permits a file or direnory to be will not appear if one listed the direnories immediately
named (and hence opened, looked up, etc.) by creating subordinate to ''phonebook''.
a special file name based upon the value of file system _O032l Another aspect of this invention could permit
parameters that are associated with a particular file. a relational database query, 332 syntax 3, to be used to
Specifically, each file on a file system can be uniquely 4_ selen files. For example, the 'phonebook' file system
identified by its inumber (the index into a file system could be built to also recognize simple database que-
table) and its generation number (a 'serial' number that ries, such as ''organization=''. Hence, a request to
is incremented each time an inumber slot in the inode ''lslphoneboo Morganization=sales'' could enumerate all
Iist, 223, is reallocated). An algorithm permits these _o sales personnel.
numbers to be combined into or de-combined from a _o _O033l Another multi-object syntax type, which may
single number. The present invention permits a file to be be more flexible, may use a file name such as ''find.
accessed by using a file name of the following form. user=root, mode=644''. The system would return a ref-
ino=decimal-inumber, erence to a virtual direnory containing links to all the file
gen=decimal-generation-number. This is merely one of objens (files or directories) on the file system that
the many non-conventional single object criteria that __ matched the search criteria (owner and mode). This
could be implemented via a prescribed syntax. invention permits the single and multi-object criteria to
_O029l The typical file system model for a set of files be computed at run-time, such as to perform ''grep''
is a directory, and thus the results of multi-objen criteria operations (search for regular expressions within files).
5
9 EP O 526 034 B1 1 O
For example, a request to ''ls _omelgrep.A__T'' could our example, recall the path name is ''lhomeljqplmem-
enumerate all files subordinate to ''_ome'' containing oirs''. If path name was a null then in step 409 an ''entry
the string ''A__T''. not found'' error is returned to the system user.
_O041 l lf path name is not a null then in step 41 1 the
Detailed Descri tion _ trailing delimiters or slashes in the path name are elimi-
nated. (Note our example has no trailing slashes a_er
_O034l With reference to the layer diagram of FIG. 1 ''memoirs''). In step 41 3, if the first character of 'name' is
we now provide a more detailed operating description of a ''_' character (indicating a path name starting at root),
the present invention. then the working directory is set to root, otherwise the
_O035l With joint reference to FIGs. 1 and 4 we 1o working directory is set to the current directory. In step
describe the detailed operation of the present invention. 415, it is determined whether the working directory is a
The present invention is implemented to perform a file directory. If not, then in step 41 7 a ''not in directory'' error
system-specific look-up feature as part of the standard is returned to the user. If wor_ng directory is a directory,
Iook-up path name feature which occurs during a con- then in step 41 9 the leading file name component (i.e.,
version of a path name to a vnode. 1_ ''home'' in our example) is stripped off the path name.
_O036l The initial access to a file is by its path name, _O042l ln step 421, the stripped off file name com-
as in the open, chdir (change directory), or link system ponent ''home'' is compared to ''.'' lf equivalent, then in
calls. Because the kernel 1 30 works internally with step 423 the system will reference the current working
vnodes rather than with path names, it converts the path directory and then control returns to step 41 5. If file
names to vnodes to access files. An algorithm of the 2o name component is not ''. '' then in step 425 it is com-
UNIX system kernel parses the path name one compo- pared to ''..''. If equivalent to ''..'' then in step 427 the par-
nent at a time, converting each component into a vnode ent of the current working directory is referenced and
based on its name and the directory being searched, control returns to step 41 5. Othennrise, step 427, the file
and eventually returns the vnode of the input path system-specific look-up feature of the present invention,
name. 2_ as illustrated in FIG. 5, is performed on the stripped-off
_O031l The steps 401 -425 and steps 429-439 illus- file name ''home''.
trate the existing steps of the path name to vnode con- _O043l Hence, a_er the steps of FIG. 5 are per-
version which are briefly described so that the detailed formed on the file name ''home'' it returns to step 429
operation of the present invention (FIG. 5) can be with a vnode reference to access the file object of the
explained in a typical operating conte_. 3o file ''home''. If no vnode reference was found then an
_O038l ln response to a user search request or error is returned to the user in step 431. Otherwise, in
other system request, user program 1 21 makes a proc- step 433, the system checks if the vnode reference
ess call (e.g., a user-program search request). When a refers to a data object which is a symbolic link. If so,
user program 1 21 makes a process call, e.g., open then in step 435, the contents of the link are placed at
(path name, open flag), the operating system kernel 3_ the front of the remaining path name. Othennrise, in step
(hereina_er kernel) 1 30 generates the well-known com- 437 the system determines whether there are more file
mand vn-open(name, seg, file mode, create mode, vpp, name components in the path name. If no more file
cnnrhy) in step 401. The command vn-open performs name components then in step 439 control is returned
permission checks and opens a file by name, returning with a vnode reference to the data object. If more file
a pointer to the resulting vnode. In the command 4o name components exist then control is returned to step
vn-open the parameter name contains the file name; 415 for further processing.
seg is the address space the file name is in, either user _O044l With reference to FIG. 5 we now describe
space or kernel space; file mode is the open mode; cre- the present invention, as illustratively embodied, as a
ate mode contains the permission bits if the file is to be file system-specific look-up feature. We describe the
created; vpp is a pointer to a vnode pointer for the 4_ processing of the file name ''home'' of our example path
result; and cnnrhy is the reason why this routine is called, name ''_ome_jqplmemoirs''. In step 501 the requester's
it is defined if and only if file mode has the Fcreate bit execute permission in the current directory is checked in
set. the standard way. If permission does not exist an
_O039l ln step 402, a file name is received from a access error message is returned to the user in step
user program 1 21. In step 403, the kernel 130 checks if _o 502.
the Fcreate bit is set. If so, then in step 405 a command _O045l lf permission does exist, then in step 509 the
vn-create() is generated in the conventional manner. file name ''home'' is processed to determine if such a file
The command of vn-create indicates to the kernel 1 30 name exists in the wor_ng directory. If it does then, in
that the process call wishes to create a new file, an step 51 1, the file name is looked up using conventional
operation which is well-_own and not important to an __ criteria and in step 513 a success indication is returned
understanding of the present invention. with a reference to the found file object.
_O_Ol lf the Fcreate bit is not set then in step 407 _O046l Thus, in our example, path name
the path name is checked to determine if it is not null. In ''_omeljqplmemoirs'' a_er the file name ''home'' is proc-
6
1 1 EP O 526 034 B1 12
essed via steps 501, 509, 51 1, 51 3 and then by steps _O053l lf a generation number match results from
429, 433 and 437. Subsequently, in step 41 5, 41 9, 421, step 61 O, then in step 61 2, a ''yes'' or ''match found''
425 and 427 the file name ''jqp'' is processed. File name response is returned to step 527 of FIG. 5. Because this
''jqp'' is processed in the same manner as ''home'', i.e., was a single-object search only, one data object on disk
by steps 501, 509, 51 1, 51 3 and then by steps 429, 433 _ 1 80 satisfies the search criteria ino=X, gen=Y. As
and 437. A_er processing file names ''home'' and ''jqp'' described in a later paragraph a key which uniquely
the file name ''memoirs'' is processed in a similar man- identifies the identified data object (a physical address
ner. or maybe ino=X, gen=Y itsel_ may be returned on the
_O_ll Returning to step 5o9, assume that the user uSer'S diSPlaY_
entered a purported path name that included a non- 1o _O054l Returning to FIG. 5, in step 527, if a match is
conventional file name and therefore the file name was found using the look-up criteria of step 525, then
not found via conventional means. Recall that a non- processing continues via the previously-described
conventional file name includes one or more non-file- steps 429, 433 and 437. If no match is found in step
name-substring-based search criteria. In steps 509-541 527, then in step 529 the base name is checked against
the program attempts to locate one or more data objects 1_ syntax 2 criteria. If a syntax 2 match exists in step 529,
using the non-file-name-based search criteria. then in step 531 the criteria 2 is used to check the direc-
_O_8l ln step 523 the program checks whether the tory.
purported file name matches one of a group of pre- _O055l With reference to FIG. 7 we describe a typi-
scribed syntaxes (in steps 523, 529 and 535). Thus, in cal multi-object search criteria (e.g., organization
step 523, the non-conventional file name is checked 2o name=orgname) which will serve as an illustration of
against syntax 1 (ino=X, gen=_. If the file name does syntax 2 search criteria performed in step 531.
not utilize the syntax 1 format then processing _O056l ln step 702 the file name is parsed to e_ract
advances to step 529. If a match is found, however, then the requested organization name ''orgname''. In step
in step 525, the syntax 1 criteria is used to perform the 704 the data base or stored items are accessed to
directory look-up. 2_ determine if ''orgname'' is a valid data object grouping. If
_O_9l With reference to FIG. 6, we illustrate in not, then ''no match'' return is returned in step 706 (to
more detail the typical look-up steps performed in 525. step 535 of FIG. 5). If an ''orgname'' data object group-
Assume that the user requests to access a file using a ing is valid, then in step 708 a vnode is allocated for a
file name having syntax 1 format which is assumed to virtual directory which will store all the data objects
be ''ino=X, gen=Y.'' lllustratively, the inode number (ino) 3o under the grouping ''orgname''. In step 71 O the vnode is
may be viewed as a mailbox number while the genera- initialized in the normal manner. In step 71 2 all of the
tion number (gen) may be viewed as the party assigned data object (or files) matching the ''orgname'' criteria are
to that mailbox number. Thus, if a mailbox is reassigned located. In step 714 a data buffer is allocated. In step
the generation number is changed but the mailbox 716 the name and key values (inode numbers, ino) are
number (or inode number) is not. 3_ written into data buffer in directory format (as in FIG. 8).
_O050l The syntax ''ino=X, gen=Y'' is a single-object ln step 71 8 the data buffer is linked to the virtual direc-
syntax because it identifies zero or one data object tory vnode. In step 720 an indication that the match was
(e.g., file or directory). Another single-object syntax successful is returned to step 513 of FIG. 5.
could be, for example, a social security number. _O051l Returning to FIG. 5, if no match is found, in
_O051 l ln step 601 the system parses the inode 4o steps 531 and 533 carried out in our FIG. 7 example,
number (ino) value X from the file name (ino=X, gen=_. then other syntax matching steps continue up to syntax
In step 602 the system parses the generation (gen) N in step 535. If a directory match is found in step 533,
number Y from the file name. In step 604 the system then in step 51 1 et al the success is returned along with
accesses the inode list, 223, to fetch the file identified by the appropriate vnode identifier. If no criteria 2 match is
inode number (ino) X. Note inode number value X refers 4_ found, then step 535 follows in step 539. Step 535
to a vnode associated therewith. In step 606 the system checks whether the file name fits syntax N. If so, then
determines a valid data object was fetched. If not, then steps 537 and 539 are performed in the same manner
in step 608 a no match or false condition is returned to as previous steps 531, 533 otherwise step 541 is per-
step 527 of FIG. 5. formed. Step 541 returns a ''no entry'' error to the user
_O052l lf an inode having the index value X is found _o indicating that the user-provided file name could be
on disk 180, the locate or fetch operation of step 606 is found in the directory.
okay. In step 61 O, the system then chec_ if the genera- _O058l lt should be recognized that the above-
tion (gen) number of the inode is Y. As previously noted, described sequence of doing the various conventional
the generation number may be any number which can file name searching and non-conventional file name
be used to uniquely identify a particular version of the __ searching can be reversed or changed according to the
desired data object. If the generation number of the particular needs of the application.
fetched inode is not the same as Y, then control is _O059l With reference to FIG. 3, we describe some
returned to previously described step 608. of the possible non-conventional file names which are
l
1 3 EP o _26 034 B1 1 4
shown in syntax group 332 and phonetic syntax match- PurPorted file name,
ing 333. For example, one syntax type may uSe an means for comparing the purported file name
inode number ''ino'' to identify a file (i.e., which item from with the file names of the previously-stored
inode list 332 of FIG. 3). Another syntax type maY USe data files and, if the purported file name
''ino'' in addition to a generation number ''gen'' which is a 5 matches the file name of one of the previously-
serial number which is incremented each time the inode stored data files, retrieving the previously-
is accessed. Using the additional ''gen'' number Pro- stored data file whose file name matches the
vides a secondary check which is useful since inode purported file name;
slots in a physical file system are reused it is oftentimeS means for, if the purported file name does not
important to be certain that the file currently in inode slot 1o match the file name of one of the previously-
'Y' is the same file that was in that slot at some previOuS stored data files, parsing the purported file
time. Generation number is a sequence number that iS name using a first logical syntax to generate
incremented every time an inode slot is freed. Hence, if one or more non-file-name-substring-based
both the number and generation numbers are the Same, first search criteria; and
then this is the same file objen, although the contentS or 15 means for comparing the one or more first
attributes may, of course, have changed. search criteria with the previously-stored data
_oo6ol Note that this file naming scheme permits files and, if the one or more fir St SearCh Criteria
data streams to be accessed remotely using any file match one or more of the PreViOUSIY-StOred
sharing mechanism, for example, Remote File Sharing data files, retrieving the Or eaCh PreViOUSIY-
(RFS) or Ne_ork File Sharing (NFS) mechanisms. 2o stored data file whiCh matCheS the One Or mOre
Moreover, this scheme can be used with any future file fir St SearCh Criteria_
sharing mechanism which can access files using file
names. 2. An apparatus as claimed in Claim 1 and fUrther
_O061 l Another application of my single-object file comPri Sing_
naming convention is to provide rapid access to file 25
objects. For example with reference to 31 5 of FIG. 3, if means for, if the one Or mOre firSt SearCh Crite-
one were trying to obtain the file ''childhood'' memoirs, ria do not match one Or mOre Of the PreViOUSIY-
using conventional file access techniques would require stored data files, ParSing the PUrPOrted file
the path name,'lname_Jqplmemoirslchildhood''. Using name using a SeCond IOgi Cal SYntaX tO gener-
my invention, this ''childhood'' memoirs file is accessed 3o ate one or more nOn-file-name-SUbString-
using a path name to directly access the physical loca- based seCond SearCh Criteria, and
tion, e.g.,,,_no=29, gen=8,,. Depending on the configu- means for comParing the One Or mOre SeCOnd
ration of a file system(s) a file name may need to be search criteria with the PreviOUSIY-StOred data
included in the path name, e.g., ''lname_no=29, gen=8''. files and, if the one Or mOre SeCOnd SearCh Cri-
_oo62l While the present invention has been 35 teria match one or more of the PreViOUSIY-
describgd for use in a clien_server network of FIG. 1 it stored data fileS, retrieVing the Or eaCh PreVi-
can also be implemented direnly on the client compu- ously-stored data file whiCh matCheS the One Or
ter. Moreover, the present invention can be utilized on- more seCond SearCh Criteria_
top-of a conventional physical file system (e.g., UNIX
file system UFS), a data base managemen_ system 4o 3. An aPParatus as claimed in Claim 1 Or 2 and fUrther
(e.g., such as lnformix_, or other data storage mecha- including
nism where data can be accessed using absolute
addresses. (Informix is a registered trademark of means for returning a keY aSSOCiated With eaCh
Informix So_ware, lnc.) located data file to the uSer, eaCh keY identifY-
_oo63l What has been described is merely illustra- 45 ing the location of an aSSoCiated data ObjeCt_
tive of the application of the principles of the preSent
invention. Other arrangements and methods can be 4. An apparatus as claimed in Claim 3 Wherein Said
implemented by those skilled in the art without depart- keY value is a MaCintoSh file indentifier_
ing from the scope of the present invention as defined
by the claims. 5o 5. An apparatus as claimed in Claim 3 Wherein Said
key value is a Macintosh direnory identifier.
Claims 6. An apparatus as claimed in claim 3 wherein the key
1. A computer based file apparatus for accessing a is an mode index value_
plurality of previously-stored data files, the appara- 55
tus comprising. l. An apparatus as claimed in Claim 3 Wherein the keY
includes an mode index value and a generation
means for receiving a user request including a number.
8
1 5 EP O 526 034 B1 16
8. An apparatus as claimed in any preceding claim Patentansprüche
wherein at least one search criteria is a phonetic
rePreSentatiOn Of a name_ 1. Computergestützte Dateivorrichtung zum Zugreifen
auf eine Vielzahl von zuvor gespeicherten Daten-
9. An apparatus as claimed in any preceding claim _ dateien, wobei die Vorrichtung aufweist.
wherein at least one search criteria is a relational
characteristic which exists between _o or more of eine Einrichtung zum Empfangen einer Benut-
said data objects. zeranforderung einschließlich eines vorgege-
benen Dateinamens;
1 O. An apparatus as claimed in any preceding claim 1o eine Einrichtung zum Vergleichen des vorge-
wherein at least one search criteria is a substring gebenen Dateinamens mit den Dateinamen
which is to be matched against the contents of the der zuvor gespeicherten Datendateien und,
previously-stored data objects. wenn der vorgegebene Dateiname zu dem
Dateinamen einer der zuvor gespeicherten
1 1. A method of accessing a plurality of previously- 1_ Datendateien paßt, zum Wiedergewinnen der
stored data files, the method comprising the steps zuvor gespeicherten Datendatei, deren Datei-
of. namen zu dem vorgegebenen Dateinamen
paßt;
receiving a user request including a purported eine Einrichtung zum Zergliedern des vorgege-
file name; 2o benen Dateinamens unter Verwendung einer
comparing the purported file name with the file ersten logischen Syntax, um ein oder mehrere
names of the previously stored data files (509); dateinamenlose, Teilketten-basierte erste
if the purported file name matches the file Suchkriterien zu erzeugen, wenn der vorgege-
name of one of the previously-stored data files, bene Dateiname nicht zu dem Dateinamen
retrieving the previously-stored data file whose 2_ einer der zuvor gespeicherten Datendateien
file name matches the purported file name paßt; und
(51 1, 51 3); eine Einrichtung zum Vergleichen der einen
if the purported file name does not match the oder mehreren ersten Suchkriterien mit den
file name of one of the previously-stored data zuvor gespeicherten Datendateien und zum
files, parsing the purported file name to gener- 3o Wiedergewinnen der oder jeder zuvor gespei-
ate one or more non-file-name-substring- cherten Datendatei, die zu dem einen oder
based first search criteria; mehreren ersten Suchkriterien paßt, wenn die
comparing the one or more first search criteria einen oder mehreren ersten Suchkriterien zu
with the previously-stored data files (523); and einer oder mehreren der zuvor gespeicherten
if the one or more first search criteria match 3_ Datendateien passen.
one or more of the previously stored data files,
retrieving the or each previously-stored data 2. Vorrichtung nach Anspruch 1 und ferner aufwei-
file which matches the one or more first search send.
criteria (525, 51 3). 4o eine Einrichtung zum Zergliedern des vorgege-
1 2. A method as claimed in claim 1 1 and comprising benen Dateinamens unter Verwendung einer
the further steps of. zweiten logischen Syntax, um ein oder meh-
rere dateinamenlose, Teilketten-basierte
if the one or more first search criteria do not zweite Suchkriterien zu erzeugen, wenn die
match one or more of the previously-stored 4_ einen oder mehreren ersten Suchkriterien nicht
data files, parsing the purported file name zu einer oder mehreren der zuvor gespeicher-
using a second logical syntax to generate one ten Datendateien passen; und
or more second search criteria; eine Einrichtung zum Vergleichen der einen
comparing the one or more non-file-name-sub- oder mehreren zweiten Suchkriterien mit den
string-based second search criteria with the _o zuvor gespeicherten Datendateien und zum
previously-stored data files (529); and Wiedergewinnen der oder jeder zuvor gespei-
if the one or more second search criteria match cherten Datendatei, die zu den einen oder
one or more of the previously stored data files, mehreren zweiten Suchkriterien paßt, wenn die
retrieving the or each previously stored data file einen oder mehreren zweiten Suchkriterien zu
which matches the one or more second search __ einer oder mehreren der zuvor gespeicherten
criteria (531, 51 3). Datendateien passen.
3. Vorrichtung nach Anspruch 1 oder 2 und ferner ein-
9
1 7 EP O 526 034 B1 1 8
schließend. Datendateien (523); und
Wiedergewinnen der oder jeder zuvor gespei-
eine Einrichtung zum Zurückgeben eines jeder cherten Datendatei, die zu dem einen oder
Iokalisierten Datendatei zugeordneten Schlüs- mehreren ersten Suchkriterien (525, 51 3) paßt,
sels an den Benutzer, wobei jeder Schlüssel 5 wenn die einen oder mehreren ersten Suchkri-
die Stelle eines zugehörigen DatenobjeMs terien zu einer oder mehreren der zuvor
identifiziert. gespeicherten Datendateien passen.
4. Vorrichtung nach Anspruch 3, wobei der Schlüssel- 1 2. Verfahren nach Anspruch 1 1 und aufweisend die
wert ein Macintosh-Dateiidentifizierer ist. Io weiteren Schritte.
5. Vorrichtung nach Anspruch 3, wobei der Schlüssel- Zergliedern des vorgegebenen Dateinamens
wert ein Macintosh-Verzeichnisidentifizierer ist. unter Vennrendung einer zweiten logischen
Syntax, um ein oder mehrere zweite Suchkrite-
6. Vorrichtung nach Anspruch 3, wobei der Schlüssel 15 rien zu erzeugen, wenn die einen oder mehre-
ein lndexknoten-lndexwert ist. ren ersten Suchkriterien nicht zu einer oder
mehreren der zuvor gespeicherten Datenda-
l. Vorrichtung nach Anspruch 3, wobei der Schlüssel teien passen;
einen lndexknoten-lndexwert und eine Erzeu- Vergleichen der einen oder mehreren dateina-
gungsnummer einschließt. 2o menlosen, Teilketten-basierten zweiten Such-
kriterien mit den zuvor gespeicherten
8. Vorrichtung nach einem vorangegangenen Datendateien (529); und
Anspruch, wobei zumindest ein Suchkriterium eine Wiedergewinnen der oder jeder zuvor gespei-
phonetische Darstellung eines Namens ist. cherten Datendatei, die zu einem oder mehre-
25 ren zweiten Suchkriterien (531, 51 3) paßt,
9. Vorrichtung nach einem vorangegangenen wenn die einen oder mehreren zweiten Such-
Anspruch, wobei zumindest ein Suchkriterium eine kriterien zu einer oder mehreren der zuvor
relationale Eigenschaft ist, die zwischen zwei oder gespeicherten Datendateien passen.
mehreren der DatenobjeMe existiert. 3o Revendications
1 O. Vorrichtung nach einem vorangegangenen
Anspruch, wobei zumindest ein Suchkriterium eine 1. Appareil de fichiers basé sur ordinateur pour accé-
Teilkette ist, die an den lnhalt der zuvor gespeicher- der à une pluralité de fichiers de données stockés
ten DatenobjeMe angepaßt werden soll. préalablement, l'appareil comprenant.
35
1 1. Verfahren zum Zugreifen auf eine Vielzahl von un moyen pour recevoir une requete utilisateur
zuvor gespeicherten Datendateien, wobei das Ver- incluant un nom de fichier prétendu;
fahren die folgenden Schritte aufweist. un moyen pour comparer le nom de fichier pré-
tendu avec les noms de fichier des fichiers de
Empfangen einer Benutzeranforderung ein- 4o données stockés préalablement et si le nom de
schließlich eines vorgegebenen Dateinamens; fichier prétendu correspond au nom de fichier
Vergleichen des vorgegebenen Dateinamens de l'un des fichiers de données stockés préala-
mit den Dateinamen von den zuvor gespeicher- blement, pour retrouver le fichier de données
ten Datendateien (509); stocké préalablement dont le nom de fichier
Wiedergewinnen der zuvor gespeicherten 45 correspond au nom de fichier prétendu;
Datendatei, deren Dateiname zu den vorgege- un moyen pour, si le nom de fichier prétendu ne
benen Dateinamen (51 1, 513) paßt, wenn der correspond pas au nom de fichier de l'un des
vorgegebene Dateiname zu dem Dateinamen fichiers de données stockés préalablement,
von einer der zuvor gespeicherten Datenda- analyser grammaticalement le nom de fichier
teien paßt; 5o prétendu en utilisant une première syntaxe
Zergliedern des vorgegebenen Dateinamens, logique afin de générer un ou plusieurs pre-
um ein oder mehrere dateinamenlose, Teilket- miers critères de recherche non basés sur
ten-basierte erste Suchkriterien zu erzeugen, sous-cha:nes de nom de fichier; et
wenn der vorgegebene Dateiname nicht zu un moyen pour comparer le ou les plusieurs
dem Dateinamen von einer der zuvor gespei- 55 premiers critères de recherche avec les fichiers
cherten Datendateien paßt; de données stockés préalablement et si l'un ou
Vergleichen der einen oder mehreren ersten les plusieurs premiers critères de recherche
Suchkriterien mit den zuvor gespeicherten correspondent à un ou plusieurs des fichiers de
1 O
1 9 EP O 526 034 B1 20
données stockés préalablement, pour retrou- nées.
ver le ou chaque fichier de données stocké
Préalablement 4ui COrreSPOnd au Ou aux Plu- 1 O. Appareil selon l,une quelconque des revendications
SieUrS PremierS CritèreS de reCherChe_ précédentes, dans lequel au moins un critère de
_ recherche est une sous-cha:ne qui doit etre mise
2. Appareil selon la revendication 1, et comprenant en en correspondance avec les contenus des objets
outre. de données stockés préalablement.
un moyen pour, si l'un ou les plusieurs premiers 1 1. Procédé d'accès à une pluralité de fichiers de don-
critères de recherche ne correspondent pas à 1o nées stockés préalablement, le procédé compre-
un ou plusieurs des fichiers de données stoc- nant les étapes de.
kés préalablement, analyser grammaticale-
ment le nom de fichier prétendu en utilisant une réception d'une requete utilisateur incluant un
seconde syntaxe logique afin de générer un ou nom de fichier prétendu;
plusieurs seconds critères de recherche non 1_ comparaison du nom de fichier prétendu avec
basés sur sous-cha:nes de nom de fichier; et les noms de fichier des fichiers de données
un moyen pour comparer le ou les plusieurs stockés préalablement (509);
seconds critères de recherche avec les fichiers si le nom de fichier prétendu correspond au
de données stockés préalablement et si l'un ou nom de fichier de l'un des fichiers de données
Ies plusieurs seconds critères de recherche 2o stockés préalablement, recherche du fichier de
correspondent à un ou plusieurs des fichiers de données stocké préalablement dont le nom de
données stockés préalablement, pour retrou- fichier correspond au nom de fichier prétendu
ver le ou chaque fichier de données stocké (51 1, 51 3);
préalablement qui correspond au ou aux plu- si le nom de fichier prétendu ne correspond
sieurs seconds critères de recherche. 2_ pas au nom de fichier de l'un des fichiers de
données stockés préalablement, analyse
3. Appareil selon la revendication 1 ou 2, et incluant grammaticale du nom de fichier prétendu afin
en outre. de générer un ou plusieurs premiers critères
de recherche non basés sur sous-cha:nes de
un moyen pour retourner une clé associée à 3o nom de fichier;
chaque fichier de données localisé à l'utilisa- comparaison du ou des plusieurs premiers cri-
teur, chaque clé identifiant l'emplacement d'un tères de recherche avec les fichiers de don-
objet de données associé. nées stockés préalablement (523); et
si l'un ou les plusieurs premiers critères de
4. Appareil selon la revendication 3, dans lequel ladite 3_ recherche correspondent à un ou plusieurs des
valeur de clé est un identificateur de fichier Macin- fichiers de données stockés préalablement,
tosh. recherche du ou de chaque fichier de données
stocké préalablement qui correspond au ou
5. Appareil selon la revendication 3, dans lequel ladite aux plusieurs premiers critères de recherche
valeur de clé est un identificateur de répertoire 4o (525, 51 3).
Macintosh. 1 2. Procédé selon la revendication 1 1, et comprenant
6. Appareil selon la revendication 3, dans lequel la clé les étapes supplémentaires de.
est une valeur d'index de noeud i. 4_ si l'un ou les plusieurs premiers critères de
l. Appareil selon la revendication 3, dans lequel la clé recherche ne correspondent pas à un ou plu-
inclut une valeur d'index de noeud i et un numéro sieurs des fichiers de données stockés préala-
de génération. blement, analyse grammaticale du nom de
fichier prétendu en utilisant une seconde syn-
8. Appareil selon l'une quelconque des revendications _o taxe logique afin de générer un ou plusieurs
précédentes, dans lequel au moins un critère de seconds critères de recherche;
recherche est une représentation phonétique d'un comparaison du ou des plusieurs seconds cri-
nom. tères de recherche non basés sur sous-cha:-
nes de nom de fichier avec les fichiers de
9. Appareil selon l'une quelconque des revendications __ données stockés préalablement (529); et
précédentes, dans lequel au moins un critère de si l'un ou les plusieurs seconds critères de
recherche est une caractéristique relationnelle qui recherche correspondent à un ou plusieurs des
existe entre deux ou plus desdits objets de don- fichiers de données stockés préalablement,
1 1
21 EP O 526 034 B1 22
recherche du ou de chaque fichier de données
stocké préalablement qui correspond au ou
aux plusieurs seconds critères de recherche
(531, 51 3). 5
IO
15
20
25
30
35
40
45
50
55
1 2