Alcatel Lucent

Future Wei Technologies, Inc.

Huawei Technologies Co., Limited

Lucent Technologies Inc.

Alcatel-lucent USA Inc.

Wenfei Fan

Yu Cheng Chen

Philip L Bohannon

Minos N Garofalakis

Michael E Flaster

Ming Xiong

Anastasios Kementsietsidis

Rajeev R Rastogi

Xin Wang

Chao Tian

Demai Ni

Floris Geerts

Suryanarayan Perinkulam

Yinghui Wu

Ping Lu

Xibei Jia

Chee-Yong Chan

Chunming Hu

Yang Cao

Yu Chen

Xueli Liu

Gao Cong

A computer implemented method for detecting errors in data includes obtaining one or more graph functional dependency (GFD) rules comprising a set of GFD rules, obtaining a set of GFDs representative of the data, building a canonical graph for the GFD rules, and determining that one or more GFD of the set of GFDs conflict based on the set of GFD rules and the canonical graph and, based thereon, determining an error in the set of GFDs.

Graph functional dependency checking

A mechanism of updating query results for a graph linking data in a computer system is disclosed. Results of the query on the graph linking data are received along with a change to the graph. The change to the graph is determined to be localizable or relatively bounded. Based on the determination of the localizable or relatively bounded change to the graph, the results of the query are updated based on the change to the graph without determining updated results of the query over the graph. This is accomplished by discovering nodes that are affected by the change to the graph, updating data associated with the affected nodes, and applying the updated data to the results of the query.

Incremental graph computations for querying large graphs

A mechanism for rewriting a bounded query onto a view is disclosed. A query, access constraints, and cached view(s) are obtained. The cached view(s) contain results of the query as applied to a dataset stored in a database. A query rewriting plan is generated by adding a fetch from query operation to the plan when a rewritten query variable can be fetched from a query constant. A fetch from database operation is added to the plan when a rewritten query variable can be fetched as a query variable that obtains bounded data from the database. An access view operation is added to the plan when a rewritten query variable can be fetched from the cached view. The query rewriting plan is executed to fetch retrieved data. The query is executed on the retrieved data to determine updated results to the query without reapplying the query to the dataset.

Bounded query rewriting using views

A graph data search method and apparatus, where the method includes obtaining a query request including a query condition that carries a start graph node, the query request queries a first to-be-queried graph node matching the query condition from a graph data set, and the graph data set includes the start graph node, a plurality of to-be-queried graph nodes, an association relationship between the start graph node and the plurality of graph nodes, and an association relationship between each to-be-queried graph node and another graph node, filtering out, according to the query condition and a preset available resource condition, a second to-be-queried graph node that does not meet the query condition and an association relationship in the graph data set that includes the second to-be-queried graph node, and performing a query in the reduction subgraph using the query condition.

Graph data search method and apparatus

A grammar for mapping a first grouping of XML data into a second grouping of XML data and a method for accomplishing same to incorporate the first grouping into the second grouping. The grammar includes a first rule for computing a first child element attribute and a second rule for computing a second parent element attribute. The first rule and second rule vary according to a production of an element type of the first grouping. The element types include PCDATA, disjunctive, conjunctive and Kleene star, each having a unique rule set for defining inherited and synthesized attributes of the parent and child elements. The method includes the step of executing a mapping of a first grouping having at least one parent element and a set of corresponding child elements into a second grouping in accordance with the grammar rules based on the production of the element type.

Grammar and method for integrating XML data from multiple sources

Methods and apparatus are provided for evaluating XPath filters on fragmented and distributed XML documents. According to one aspect of the invention, a method is disclosed for evaluating a query over a tree having a plurality of fragments distributed over a plurality of sites. The method comprises the steps of identifying the plurality of sites storing at least one of the plurality of fragments of the tree; providing the query to the plurality of identified sites, wherein each of the identified sites partially evaluates the query against one of more fragments of the tree stored by the respective site; obtaining partial results from the plurality of identified sites; and composing the partial results to compute a result to the query. The query may be, for example, a boolean XPath query. The method can be performed, for example, by a coordinating site that stores a root fragment of the tree.

Methods and apparatus for evaluating XPath filters on fragmented and distributed XML documents

Methods and apparatus are provided for propagating functional dependencies with conditions. Propagation covers are computed using an SPC view of a dataset, wherein the SPC view comprises selection, projection and Cartesian product operations. Selection operations are processed to extract equivalence classes. Cartesian product operations are processed to obtain a renamed set of the plurality of conditional functional dependencies, that have attributes appearing in the SPC view. Domain constraints from the equivalence classes are applied to the renamed set to remove attributes not in the SPC view. Projection operations are processed using a reduction by resolution procedure to identify inferences that can be propagated to the SPC view from the conditional functional dependencies having attributes that do not appear in the SPC view. Domain constraints of the equivalence classes are converted to conditional functional dependencies; and a minimal cover of the SPC view is determined.

Methods and apparatus for propagating functional dependencies with conditions

Methods and apparatus are provided for identifying constraint violation repairs in data that is comprised of a plurality of records, where each record has a plurality of cells. A database is processed, based on a plurality of constraints that data in the database must satisfy. At least one constraint violation to be resolved is identified based on a cost of repair and the corresponding records to be resolved and equivalent cells are identified in the data that violate the identified at least one constraint violation. A value for each of the equivalent cells can optionally be determined, and the determined value can be assigned to each of the equivalent cells. The at least one constraint violation selected for resolution may be, for example, the constraint violation with a lowest cost. The cost of repairing a constraint is based on a distance metric between the attributes values.

Equivalence class-based method and apparatus for cost-based repair of database constraint violations

Methods and apparatus are provided for incremental update of an XML tree defined from a recursive XML view of a relational database. A method comprises the steps of detecting at least one change to the relational database; providing one or more queries to the relational database to map the change to the relational database into changes to the XML tree, wherein at least one component of a definition of the one or more queries is executed a plurality of times in traversing a path through the XML tree; and applying the mapped change to the XML tree. A bud-cut method and a reduction approach are presented.

Method and apparatus for incremental evaluation of schema-directed XML publishing

Methods and apparatus are provided for detecting data inconsistencies. Methods are disclosed for determining whether a set of conditional functional dependencies are consistent; determining a minimal cover of a set of conditional functional dependencies and detecting a violation of one or more conditional functional dependencies in a set of conditional functional dependencies. The conditional functional dependencies comprise one or more constraints that data in a database must satisfy including at least one pattern with data values.

Methods and apparatus for capturing and detecting inconsistencies in relational data using conditional functional dependencies

Methods and apparatus are provided for mapping XML source documents to target documents using schema embeddings. According to one aspect of the invention, one or more edges in the one or more source schemas are mapped to one or more paths in at least one target schema. The disclosed mapping techniques ensure that (i) one or more source documents that conform to one or more of the source schemas can be recovered from one or more target documents that conform to the at least one target schema, if a mapping exists between the one or more of the source schemas and the at least one target schema; (ii) queries on one or more source documents that conform to one or more of the source schemas in a given query language can be answered on one or more target documents that conform to the at least one target schema; and (iii) the one or more target documents conform to a target schema.

Methods and apparatus for mapping source schemas to a target schema using schema embedding

Method for providing controlled access to an XML document includes defining at least one access control policy for a user of the XML document, deriving a security view of the XML document for the user based upon said access control policy and schema level processing of the XML document and translating a user query based on the security view of the XML document to an equivalent query based on the XML document. An apparatus for same includes means for defining an access control policy for a user of the XML document and means for deriving a security view of the XML document for the user based on said access control policy and schema level processing of the XML document. Also included are means for translating a user query based on the security view of the XML document to an equivalent query based on the XML document.

Growing community of inventors

Wayne, PA, United States of America

Wenfei Fan