Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-10-18
2004-01-20
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06681221
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to XML, and more particularly to achieving directed acyclic graph (DAG) representations of data in XML.
BACKGROUND OF THE INVENTION
The omnipresence of the Internet in today's society has created an expectation that desired information be readily available, easily accessible, and user-friendly. Conformance with established practices allows website designers and developers to meet the needs of Internet users. In general, hypertext markup language (HTML) was designed to display data, and to focus on how data looks. In a similar manner, extensible markup language (XML), was designed to describe data, and to focus on what data is.
XML provides a way to structure, store and send information and achieves a cross-platform, software- and hardware-independent tool for transmitting information. XML uses a DTD (Document Type Definition) to describe the constraints and define the valid elements of an XML document. Currently, XML capably represents data of a hierarchical data structure (‘tree structure’), i.e., data with a traditional direct parent-child relationship, where each child has a single parent. Thus, an XML document can be represented as a tree of elements. A simple example of a hierarchical organization of information similar to the tree nature of XML documents is a file system, where files and folders are organized hierarchically, such that a folder may have files in it or other folders, and everything is descended from one root folder. Each file can be viewed as a child of the folder parent from which it descends.
There is no specific support in XML for representing data having a graph structure, e.g., a directed acyclic graph (DAG), where a child has multiple direct parents. Without support for a DAG, there is also no enforcement of the semantics of a DAG. For example, in a given situation, complex relationships may need to be represented, such as when a user of a system is associated as a member of several groups. A problem could exist in the specification of this type of relationship with XML.
FIGS. 1
a
and
1
b
illustrate circle graph diagrams for representing the example relationship where a user is a member of multiple groups. As shown in
FIG. 1
a
, a choice could be made to represent a user
10
as a child of multiple parents, group
12
and group
14
. Unfortunately, as stated above, XML only supports representation of a relationship where a child descends from a single parent. Thus, in order to represent the user
10
and its relationship to the multiple groups
12
and
14
in XML, the user
10
could become the parent for the individual children of groups
12
and
14
, as shown in the diagram of
FIG. 1
b
. In order to represent the relationships in this way, the semantics must be modified from “users belong to groups” to “groups belong to users.” This reorganization, in which a user must designate the groups to which it belongs, is not optimal. While this choice as shown in
FIG. 1
b
maintains a parent-child relationship that can be represented in XML, a problem arises when attempting to include other users that could exist for the groups
12
or
14
. Having already been specified as children of user
10
, they cannot be represented as children of another user, nor can the other users be their children without also descending from user
10
.
As demonstrated by this example, a problem exists in XML in not being fully able to provide a more human-oriented manner of specifying data that accommodates situations where a DAG representation rather than a tree representation is appropriate.
Accordingly, what is needed is a generalized method and system for representing a directed acyclic graph (DAG) in a hierarchical XML information set. The present invention addresses such a need.
SUMMARY OF THE INVENTION
The present invention provides method and system aspects for achieving directed acyclic graph (DAG) representations of data in XML. The aspects include augmenting a document type definition (DTD) for allowing description of the DAG in an XML file and for providing an API for processing the DAG transparently. The API is consistent with and interoperates with the standard document object model application program interface (DOM API) for processing the XML file.
According to the system and method disclosed herein, a more human-oriented way of specifying data relationships within the hierarchical structure of XML is achieved. The data specification allows an element to be specified initially with subsequent references linked to the initial specification. Further, the present invention provides the functions necessary to properly process the new data definitions in a seamless and straightforward manner.
REFERENCES:
patent: 6263332 (2001-07-01), Nasr et al.
patent: 6347307 (2002-02-01), Sandhu et al.
patent: 6366934 (2002-04-01), Cheng et al.
patent: 6457103 (2002-09-01), Challenger et al.
Shanmugasundaram et al. (“Relational Databases for Querying XML Documents: Limitations and Opportunities”).*
Rafael Berlanga, Maria Jose Aramburu and Salvador Garcia “Efficient Retrieval of Structured Documents From Object-Relational Databases”).*
Masatoshi Yoshikawa Hiroyuki Kato and Hiroko Kinutani (“Design Framework of a Database for Structured Documents with object links”) 1998.
Docent, Inc.
Mizrahi Diane D.
Sawyer Law Group LLC
Wu Yicun
LandOfFree
Method and system for achieving directed acyclic graph (DAG)... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for achieving directed acyclic graph (DAG)..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for achieving directed acyclic graph (DAG)... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3265199