WO2001073544A1 - Systeme et procede pour bases de donnees et langages de programmation - Google Patents
Systeme et procede pour bases de donnees et langages de programmation Download PDFInfo
- Publication number
- WO2001073544A1 WO2001073544A1 PCT/US2000/007983 US0007983W WO0173544A1 WO 2001073544 A1 WO2001073544 A1 WO 2001073544A1 US 0007983 W US0007983 W US 0007983W WO 0173544 A1 WO0173544 A1 WO 0173544A1
- Authority
- WO
- WIPO (PCT)
- Prior art keywords
- node
- term
- database
- link
- terms
- Prior art date
- Legal status (The legal status 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 status listed.)
- Ceased
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/28—Databases characterised by their database models, e.g. relational or object models
- G06F16/289—Object oriented databases
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9024—Graphs; Linked lists
Definitions
- This invention is related to programming languages and database management systems by which arbitrary computing applications, especially information related applications such as Database Applications, Data Discovery and Mining. Artificial Intelligent, Knowledge-based reasoning systems and Web-based applications can be developed.
- Database management systems are the cores of almost all of the computing applications systems.
- the way of managing data called data model normally in the database research area, is a key factor to determine the productivity and the quality of developing and maintaining database application software. Even more, it determines the success or the failure of a complex database application development regardless the cost.
- the relational data model is the most popular data model widely spreading in the industry. However, it has a lot of limitations in presenting data and manipulating data. Many new data models have been proposed after the relational data model.
- the examples are objected-oriented data models as in ??, graph -oriented data models as in Finding a better data model has been a challenging research activity.
- the relational data model is the most popular data model widely spreading in the industry. However, it has a lot of limitations in presenting data and manipulating data.
- Many new data models have been proposed after the relational data model.
- the examples are objected-oriented data models as in "Introduction to Object Oriented Databases" by Won Ki .
- Fig 1 shows the system architecture of database servers, where no additional software beyond the database management systems is needed for arbitrary database applications
- Fig 2 shows the rules of forming valid db-terms - input expressions
- Fig 4 shows a typical database which stores a composite function, a numeral square function, a numeral root function, and an identity function with finite domains
- Fig 5 shows a typical database which stores a school administration information
- Fig 6 shows the database which stores the facto ⁇ al function
- Fig 7 shows a part of the built-in functions of the database 70 in Fig 1
- Fig 8 shows a part of the built-in functions of the database 70 in Fig 1
- Fig 9-a and Fig. 9-b show the data process 50 p ⁇ ma ⁇ ly including the computing rules 60 in Fig 1
- Fig 10 gives a directed graph
- Fig 1 1 shows the database presentation of the directed graph in Fig 10
- a preferred embodiment of the invention is Data Server 10 which comp ⁇ ses Receptionist 30, Database and Process 50. and Speaker 100
- Receptionist 30 is a unit that receives requests from users or other computing systems through Channel 20 It knows the identities of the senders and informs Speaker 100 the identities
- the Receptionist 30 comp ⁇ ses a scanner and a parser
- the scanner receives as inputs streams of arbitrary characters. All the characters, such as the alphabetic letter 'a', digital '4'. the special space character ' '. and the newline ' ⁇ n " in the Ascn character set. for example are valid characters
- the scanner passes a sequence of tokens to the parser
- a token is a sequence of characters
- these delimiters comp ⁇ se '(', ')', ' ⁇ ', ' ⁇ ', ',', ' ', ' ⁇ and ','.
- the second type of the tokens, called labels, is the tokens other than the delimiters, such as st ⁇ ngs "abc", “College”, "1234". and "1234.00” in Fig. 3.
- a label this invention can also be a long sequence of arbitrary characters like a binary file.
- the scanner of Receptionist 30 may accept requests (input expressions) in different formats through Channel 20. But the parser of Receptionist 30 converts all the formats into the uniform one of a preferred embodiment of this invention.
- This format called db-terms, is defined in Fig. 2.
- Rule 120 in Fig. 2 says that any label is a db-term, such as College, 123, and 123.4 in Fig. 3.
- Rule 121 says that the combinations of two db-terms are also db-terms
- the parentheses in db-terms are the delimiters for grouping sub db-terms.
- Rule 122 says that an abstraction ⁇ x M, or ⁇ x:[bool] M.
- M is a db-term, called the body of the abstraction: and bool is a boolean binary operation - a special form of db-terms. is a db-term.
- Rule 123 says that a binary operanons (M op N) with a built-in binary operator op is a db-term. Note that the form (M op N) of the binary operations could be expressed by combinations ((op M) N).
- Database 70 There are two p ⁇ mary sub units in Database and Process 50 One is Database 70 sto ⁇ ng a set of fixed functions and dynamic data. The second sub unit is Computing Rules 60 which convert db-terms from Channel 40 to their outputs 90 according to the db-terms and the states of Database 70.
- Database 70 is a system with permanent storage 80 which exhibits both the fixed functions and the dynamic data in a uniform data structure. No matter a function or data is fixed or dynamic, it is a node of an instance of the data structure
- the data structure is a finite set of nodes connected by the three types of connections: up- down links, solid arrows, and dash arrows Fig 4, 5.
- a up-down link is a physical reference (such as a one-way pointer or two-way pointers) that connects two nodes together at its two ends as a preferred embodiment of the invention
- a link is called the upper link of a node if the link is above the node and is connected with the node, and a link is called the lower link of a node if the link is below the node and connected with the node
- a node at the down side of a link is called the down-side node of the link
- a node at the up-side of a link is called the up-side node of the link
- the node at the other side can be located through the link
- all the non-directed links but with up to down o ⁇ entation in Fig 4, 5, and 6 including the link 130 are up- down links
- the node 131 is the up-side node of the link 130
- the node 132 is the down-side node
- a dash arrow is a physical reference (such as a one-way pointer or two-way pointers) that connects two nodes together at its two ends as a prefe ⁇ ed embodiment of the invenuon
- the node at the tail of a dash arrow is called the tail node of the arrow and the node at the head of the arrow is called the head node of the dash arrow
- the node at the other end can be located through the arrow
- all the allows in dash line in Fig 4, and 5 including arrows 136, 137, and 138 are dash arrows
- a solid arrow is a physical reference (such as a one-way pointer or two-way pointers) that connects two nodes together at its two ends as a preferred embodiment of the invention
- the node at the tail of a solid arrow is called the tail node of the arrow
- the node at the head of the arrow is called the head node of the arrow
- the node at the other end can be located through the arrow
- the arrows 139. 155. and 156 are solid arrows
- a node is an end of an up-down link, solid, or dash arrow, or a joint of more than one up-down l ⁇ nk(s). solid arrow(s). and/or dash a ⁇ ow(s)
- a node imposes the following constraints on the connected links and/or a ⁇ ows
- Each end of a link or an arrow is a node
- a node must not have more than one upper link If there is no upper link, the node is called a root
- Root 131 in Fig 4 and College in Fig 5 are roots
- the up-side node is called the supe ⁇ or of the downside node
- the down-side node is called a subordinate of the up-side node
- Node 132 is a subordinate of Node 131
- Node 131 is the supe ⁇ or of the Node 132.
- a node must not have more than one dash arrow pointing away from it. Given a dash arrow, the head node is called the parent of the tail node; and the tail node is called a child of the parent. For example, Node 134 is a child of Node 135, and Node 135 is the parent of Node 134
- a node may have zero or more than one subord ⁇ nate(s). If there is no subordinate, a node may have a tag. A node that has a tag is called a leaf node. For example, Nodes 132 and 140 are leaf nodes
- a node may have a label.
- the label of a node is displayed in the center of the node
- the labels of Nodes 131 and 132 are "Root" and "4" respectively
- a root shall have a label A non-root node without label must have a dash arrow pointing away from it.
- the Node 131 has the label "Root”
- Node 140 has the dash arrow 138 pointing away from it
- all the non-root nodes in Database 70 don't have to have labels in the nodes. If this is the case, all the labels are roots; all the non-root nodes will have dash arrows pointing to either label roots or other nodes; and they don't have labels inside the nodes.
- the nodes and the links with a single type of the connections in Database 70 form a structure of trees.
- all the nodes and the up-down links in Fig 4 form trees: all the nodes and the dash arrows in Fig 4 form directed trees; and all the nodes and the solid arrows in Fig 4 form directed trees Node that a single node without connection with other nodes is also a tree.
- the tag of a node can be one of the fallowings-
- Node 140 has Node 141 as its tag due to the solid arrow 139 between the two nodes
- Node 132 has the integer 2 as the tag (3)
- a built-in constant functions For example, integer/floating nume ⁇ c numbers, date, time, the a ⁇ thmetic operator +, the boolean operator ⁇ . more boolean operators to be discussed late, and a special constant labeled "Undefined " are constant functions Rather than their labels, the constant functions refer to the semantic meanings supported by additional processes
- Fig 7 and 8 demonstrate a few constant functions Note that a node with a constant function as the tag is a leaf node
- the dashed up-down links and dashed nodes in Fig 7 and 8 are not a physical, but logic illustration of the computing behaviors of the constant functions
- a third-party software Examples are multimedia (video/audio) data, a file in operating systems, and a program in software enginee ⁇ ng
- a node with a third-party software as the tag shall be able to present the value in its nature form as a constant function does
- a node with its value of a sound shall have its facility such as computer program that d ⁇ ves to perform the sound
- a node with a third- party software as the tag is a leaf node
- Each node in Database 70 has a name Given a node in Database 70. its name is formed in the following method
- db-term When a db-term is the name of a node, the db-term is used to refers to the node, and the node representing the db-term in the rest of the desc ⁇ ption of this invention
- Node 132 is the db-term Root 4 and the db-
- a label x is declared as a vanable if it appears ⁇ ght after the delimiter ⁇ in an abstraction.
- the entire body M of the abstraction ⁇ x. M is the scope of ⁇ x.
- Va ⁇ able x occurs free in a db-term N if x is not in the scope of a ⁇ x in N; x occurs bound otherwise.
- x and y are variables; and x occurs bound and y occurs free.
- a va ⁇ able can only be the label of a leaf node whose tag is the body of the abstraction. An example is the presentation of the factorial function in Fig. 6.
- Garbage is not in Database 70 as given in Fig. 4, 5, and 6, then Garbage will be equal to Undefined as it will be desc ⁇ bed in the computing process in Fig. 9-a and Fig. 9-b.
- Some app-data labels may symbolize third-party software.
- a db-term is called closed if there is no any free va ⁇ able in it.
- x + y is not a closed db-term while ⁇ x. ⁇ y.
- x + y is a closed db-term
- Database and Process 50 For each db-term from Channel 40, Database and Process 50 will reference Database 70. and compute the value of the db-term.
- the computation (or called reduction) process from a db-term to its value is another preferred embodiment of this invention.
- the value (or called normal form) of a db-term is the db-term from which no other db-term can be computed (reduced). In other words, A value, as a db-term. doesn't have any redex as a sub db-term in the db-term.
- a db-term M is a redex if:
- M is an application PQ, where P is a term appeared in Database 70, and Q is a closed db-term. but PQ is not a term appeared in Database 70.
- M is a ⁇ -redex, that is ( ⁇ x.P) Q.
- M is a ⁇ -redex: ⁇ x.Mx where x is not a free variable of M.
- M N
- M and N are convertible.
- Fig. 9-a and Fig.9-b are the computing process of Data Process 50 including Computing Rules 60. This process converts arbitrary db-terms to their values.
- Input 40 indicates that the process 60 accepts arbitrary db-terms M.
- Operation Box 510 says that if M is a label defined in Database 70 with a tag value, then the value of the M is the tag of M. For example. Node 132 (Root 4) in Fig. 4 has the value 2, the tag of Node 132; and Node 162 (College CS Head) in Fig. 5 has the value 163 (SSD Mike), the tag of Node 162.
- Operation Box 511 says that if M is a label not defined in Database 70, then the value of M is Undefined. For example, all the labels like “garbage” and “others” not appeared in Database 70 will have the value Undefined.
- Operation Box 512 says that if M is a label defined in Database 70, but it has no tas. then the value of M is M itself. All the numerals have themselves as the values. And any node in Database 70 which has no tag and no subordinate has itself as the value.
- Operation Box 515 says that if M is an abstraction ⁇ x.N, then evaluate N first by recursively calling the computing process illustrated in Fig. 9-a and Fig. 9-b.
- the value of M is the ⁇ x.N', where N' is the value of N after the evaluation. For example, ⁇ x.x + 1 +2 would be reduced to ⁇ x.x + 3.
- Operation Box 514 says that if M is a binary operation (Nl op N2), then the value of M is the result of the operation (Nl op N2). For example, 1 + 2 has the value 3.
- Binary operation expressions also could be expressed in the combinations of db- terms.
- Operation 525 says that if either Ml or M2 (or both) is (are) not closed db-terms, then the combination Ml M2 return itself as the value. For example, SQ (x + 3) has itself as the value since it cannot be reduced when there is a free variable in it.
- Operation 526 says that if Ml is in Database 70, and there is a M2' in Database 70 such that M2' and M2 have the same value, and Ml M2' is in Database 70, then M is reduced to the tag of Ml M2' if Ml M2' has a tag.
- Root (2 + 2) could be reduced to Root 4 since 2 + 2 and 4 have the same value 4; and Root 4 (Node 132) is defined in Database 70-a
- Root 4 has the value the tag 2 as its value In Fig 5, College CS Head is Node 162 and Node 162 has the tag of the solid arrow 164 pointing to Node 163 Then the db-term College CS Head is reduced to SSD Mike
- Operation 528 says that if Ml is in Database 70, and there is a M2' in Database 70 such that M2' and M2 have the same value, and Ml M2' is in Database 70, then M has the value of Ml M2' if Ml M2' has no tag
- Node 158 is the db-term (College CS) and it has no tag Then the db-term (College CS) has itself as the value
- the db-term College Admin (SSD John) Major Head has the following computing steps
- the db-term fac 3 has the following computing steps towards it value
- Database 70 comp ⁇ ses a infinite number of constants, built-in functions, and the related virtual subordinates of the built-in functions. For example. 000.3 and + 3 3 are logically a part of Database 70 although they don't show in Database 70. For the nodes in Fig 7 and 8 have infinite number of logic subordinates as indicated. Some of the built-in functions are illustrated in Fig. 7 and 8. Here is a summary:
- Undefined means meaningless or undefined as a result of a computanon. For example, College Math would be reduced to Undefined according to Operation Box 527 since College Math is not a node in Fig. 5 Applying Undefined to any db-term; or applying any db-term to Undefined is reduced to Undefined as shown in Operation Box 522.
- tl ⁇ c t2 If there is any variable among tl and t2, the value of the expression (tl ⁇ c t2) is itself. Given any two db-terms tl and t2, if tl ⁇ a t2. then tl ⁇ c t2 must be True. As a matter of fact, if tl ⁇ c t2 is True, there is a directed path consisting of zero or multiple up-down link(s) and zero or multiple solid arrow s). Starting from t2 along the path, one always walks through a up-down link by starting with the up-side node; walks through a solid arrow by starting either its tail node or its head node; and eventually reaches tl.
- tl ⁇ d t2 the value of the expression (tl ⁇ d t2) is itself. Given any two db-terms tl and t2, if tl ⁇ b t2, then tl ⁇ d t2 must be True. As a matter of fact, if tl ⁇ d t2 is True, there is a directed path consisting of zero or multiple dash arrow(s) and zero or multiple solid ar ⁇ ow(s). Starting from t2 along the path, one always walks through a dash arrow by starting with the head node: walks through a solid arrow by starting either its tail node or its head node; and eventually reaches tl .
- a format of expressing a selection statement is: "select xl x2 ... xn where bool-expression".
- a selection expression returns a set of sequences of db-terms such that the "bool-expression" is evaluated to be True for each sequence output when the sequence of the variables xl x2 ... xn are substituted with the sequence of the db-terms output.
- Delete as shown in Fig. 8. A format of expressing a deletion statement is: "delete xl , x2. ..., xn where bool-expression " .
- a deletion expression delete all the related nodes in the database 70 satisfying the "bool- expression".
- an creation expression creates a set of sequences of db-terms and assigns them values if necessary. For each sequence of the db-terms, the "bool-expression" is evaluated to be True when the sequence of the variables tl t2 ... tn are substituted with the sequence.
- the directed graph in Fig. 10 has the expression: B ⁇ c D, for the query "Is there a path from D to B?".
- the database presentation of the directed graph is given in Fig. 11.
- Speaker 100 in Fig. 1 takes db-terms from channel 90 and responds clients with the outputs 110 converted from the db-terms in the formats the clients need.
- the data server of this invention can store arbitrary data and accept arbitrary requests in a uniform framework under the scope of effectively computable functions.
- the uniform framework is an extended lambda calculus where db-terms are sufficient form of representing data and expressing queries.
- a set of boolean binary operators stemming from function/argument/value relationships of higher-order functions can be used to express fixpoint queries.
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Software Systems (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
La présente invention concerne un système et un procédé informatique de rangement et de gestion de données et de construction de programmes d'application. Ce système accepte des expressions d'entrée uniformes ou expressions de base de données servant à désigner les données en mémoire et à exprimer les requêtes utilisateur. Ainsi, une base de données (70a) est une collection de noeuds (131, 132) qui sont reliés par un ensemble de liens orientés (130). Il y a trois types de liens. En ignorant un type de liens, la base de données peut se représenter comme un ensemble d'arborescences. Tous les noeuds des bases de données se présentent comme des fonctions. Toutes les expressions de base de données permettent un calcul de leur valeur telles qu'elles existeraient par rapport à des bases de données et en fonction de règles de calcul. Les arborescences incluses dans les bases de données illustrent les relations de dépendance entre les données, et constituent des fonctions intégrées servant à la manipulation de la base de données tout en servant de principe directeur théorique pour la distribution des données. Les relations de valeur d'argument des fonctions entre les noeuds des bases de données constituent un principe directeur théorique pour un ensemble de fonctions intégrées utiles.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| PCT/US2000/007983 WO2001073544A1 (fr) | 2000-03-24 | 2000-03-24 | Systeme et procede pour bases de donnees et langages de programmation |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| PCT/US2000/007983 WO2001073544A1 (fr) | 2000-03-24 | 2000-03-24 | Systeme et procede pour bases de donnees et langages de programmation |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| WO2001073544A1 true WO2001073544A1 (fr) | 2001-10-04 |
Family
ID=21741200
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| PCT/US2000/007983 Ceased WO2001073544A1 (fr) | 2000-03-24 | 2000-03-24 | Systeme et procede pour bases de donnees et langages de programmation |
Country Status (1)
| Country | Link |
|---|---|
| WO (1) | WO2001073544A1 (fr) |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4930072A (en) * | 1987-08-31 | 1990-05-29 | At&T Bell Laboratories | Method for computing transitive closure |
| US5434972A (en) * | 1991-01-11 | 1995-07-18 | Gec-Marconi Limited | Network for determining route through nodes by directing searching path signal arriving at one port of node to another port receiving free path signal |
| US5787430A (en) * | 1994-06-30 | 1998-07-28 | International Business Machines Corporation | Variable length data sequence backtracking a trie structure |
| US5995958A (en) * | 1997-03-04 | 1999-11-30 | Xu; Kevin Houzhi | System and method for storing and managing functions |
-
2000
- 2000-03-24 WO PCT/US2000/007983 patent/WO2001073544A1/fr not_active Ceased
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4930072A (en) * | 1987-08-31 | 1990-05-29 | At&T Bell Laboratories | Method for computing transitive closure |
| US5434972A (en) * | 1991-01-11 | 1995-07-18 | Gec-Marconi Limited | Network for determining route through nodes by directing searching path signal arriving at one port of node to another port receiving free path signal |
| US5787430A (en) * | 1994-06-30 | 1998-07-28 | International Business Machines Corporation | Variable length data sequence backtracking a trie structure |
| US5995958A (en) * | 1997-03-04 | 1999-11-30 | Xu; Kevin Houzhi | System and method for storing and managing functions |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6643638B1 (en) | System and method for storing and computing data and functions | |
| US5640559A (en) | System and method of encoding units of data including entity/relationship data, function calls and file data using a common format (CDF) according to formal CDF grammar rules | |
| Brinkkemper et al. | Assembly techniques for method engineering | |
| Levin | AMICA: The AT&T mixed initiative conversational architecture | |
| JP2680255B2 (ja) | オブジェクト指向環境においてデータを転送するためのシステム及び方法 | |
| US7124144B2 (en) | Method and apparatus for storing semi-structured data in a structured manner | |
| US5228116A (en) | Knowledge base management system | |
| US5432930A (en) | System for accessing cobol data files by generating a dictionary of NF.sup.2 | |
| US5438511A (en) | Disjunctive unification | |
| US20020095397A1 (en) | Method of processing queries in a database system, and database system and software product for implementing such method | |
| US20020093522A1 (en) | Methods of encoding and combining integer lists in a computer system, and computer software product for implementing such methods | |
| KR20050000348A (ko) | 중간 언어 표현 방법 및 시스템 | |
| CA2302303A1 (fr) | Systeme pour acceder a une table de base de donnees configuree en memoire pour haute performance | |
| JPWO2009017158A1 (ja) | 変換プログラム探索システムおよび変換プログラム探索方法 | |
| EP2391958B1 (fr) | Traitement de donnees dans un environnement computationnel distribue | |
| JP2003141158A (ja) | 順序を考慮したパターンを用いた検索装置および方法 | |
| US7707159B2 (en) | Method and apparatus for storing semi-structured data in a structured manner | |
| Robinson | An entity/event data modelling method | |
| WO2001073544A1 (fr) | Systeme et procede pour bases de donnees et langages de programmation | |
| ter Hofstede et al. | Fact orientation in complex object role modelling techniques | |
| Butler et al. | Analyzing the logical structure of data flow diagrams in software documents | |
| JPH10240591A (ja) | Sqlプロシジャ実行時の計算機負荷分散方法 | |
| JPH08161208A (ja) | オブジェクト構造変換装置 | |
| US20120254248A1 (en) | System and Method for Storing and Computing Business Data and Logic | |
| CN117708187A (zh) | 标签条件组合的用户查询方法、系统、设备及存储介质 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| AK | Designated states |
Kind code of ref document: A1 Designated state(s): CN |
|
| AL | Designated countries for regional patents |
Kind code of ref document: A1 Designated state(s): AT BE CH CY DE DK ES FI FR GB GR IE IT LU MC NL PT SE |
|
| 121 | Ep: the epo has been informed by wipo that ep was designated in this application | ||
| 32PN | Ep: public notification in the ep bulletin as address of the adressee cannot be established |
Free format text: COMMUNICATION PURSUANT TO RULE 69 EPC (EPO FORM 2524 OF 170103) |
|
| 122 | Ep: pct application non-entry in european phase |