×

zbMATH — the first resource for mathematics

Speeding up inferences using relevance reasoning: a formalism and algorithms. (English) Zbl 0904.68163
Summary: Irrelevance reasoning refers to the process in which a system reasons about which parts of its knowledge are relevant (or irrelevant) to a specific query. Aside from its importance in speeding up inferences from large knowledge bases, relevance reasoning is crucial in advanced applications such as modeling complex physical devices and information gathering in distributed heterogeneous systems. This article presents a novel framework for studying the various kinds of irrelevance that arise in inference and efficient algorithms for relevance reasoning. We present a proof-theoretic framework for analyzing definitions of irrelevance. The framework makes the necessary distinctions between different notions of irrelevance that are important when using them for speeding up inferences. We describe the query-tree algorithm which is a sound, complete and efficient algorithm for automatically deriving certain kinds of irrelevance claims for Horn-rule knowledge bases and several extensions. Finally, we describe experimental results that show that significant speedups (often orders of magnitude) are obtained by employing the query-tree in inference.

MSC:
68T30 Knowledge representation
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abiteboul, S.; Hull, R., Data functions, Datalog and negation, ()
[2] Addanki, S.; Cremonini, R.; Penberthy, J., Reasoning about assumptions in graphs of models, () · Zbl 0719.68066
[3] Anderson, A.R.; Belnap, N.D., ()
[4] Arens, Y.; Knoblock, C.A.; Shen, W.-M., Query reformulation for dynamic information integration, Internat. J. intelligent and cooperative information systems, 6, 2/3, 99-130, (1996)
[5] Avron, A., Whither relevance logic?, J. philos. logic, 21, 243-281, (1992) · Zbl 0773.03015
[6] Baader, F.; Hollunder, B., A terminological knowledge representation system with complete inference algorithm, (), 67-86
[7] Bacchus, F.; Grove, A.J.; Halpern, J.Y.; Koller, D., Statistical foundations for default reasoning, ()
[8] Bancilhon, F.; Maier, D.; Sagiv, Y.; Ullman, J., Magic sets and other strange ways to implement logic programs, (), 1-15
[9] Beeri, C.; Ramakrishnan, R., On the power of magic, (), 269-283
[10] Blakeley, J.A.; Coburn, N.; Larson, P.A., Updating derived relations: detecting irrelevant and autonomously computable updates, Trans. database systems, 14, 3, 369-400, (1989)
[11] ()
[12] Borgida, A.; Patel-Schneider, P., A semantics and complete algorithm for subsumption in the CLASSIC description logic, J. artif. intell. res., 1, 277-308, (1994) · Zbl 0900.68397
[13] Brodsky, A.; Sagiv, Y., On termination of Datalog programs, (), 47-64
[14] Bruynooghe, M.; De Schreye, D.; Krekels, B., Compiling control, J. logic programming, 6, 135-162, (1989) · Zbl 0668.68025
[15] Bruynooghe, M.; De Schreye, D.; Martens, B., A general criterion for avoiding infinite unfolding during partial deduction of logic programs, (), 117-131
[16] Carnap, R., ()
[17] Chandra, A.; Kozen, D.; Stockmeyer, L., Alternation, J. ACM, 28, 1, 114-133, (1981) · Zbl 0473.68043
[18] Chang, C.L., Resolution plans in theorem proving, (), 143-148
[19] Clancey, W.J., The advantages of abstract control knowledge in expert system design, (), 74-78
[20] Cousot, P.; Cousot, R., Abstract interpretation and application to logic programs, J. logic programming, 13, 2-3, 103-179, (1992) · Zbl 0776.68024
[21] Darwiche, A., A logical notion of conditional independence, Artificial intelligence, 97, 45-82, (1997), (this issue) · Zbl 0903.68055
[22] Davis, R., Diagnostic reasoning based on structure and behavior, Artificial intelligence, 24, 347-410, (1984)
[23] Draper, D.L., Relevance measures for localized partial evaluation of belief networks, ()
[24] Dunn, M., Relevance logic and entailment, (), 117-224 · Zbl 0875.03051
[25] Elkan, C., A decision procedure for conjunctive query disjointness, ()
[26] Elkan, C., Independence of logic database queries and updates, (), 154-160
[27] Ellman, T., Abstraction via approximate symmetry, (), 916-921
[28] Etzioni, O., Why PRODIGY/EBL works, ()
[29] Etzioni, O., Acquiring search-control knowledge via static analysis, Artificial intelligence, 62, (1993) · Zbl 0778.68071
[30] Etzioni, O.; Minton, S., Why EBL produces overly-specific knowledge: a critique of the PRODIGY approaches, ()
[31] Etzioni, O.; Weld, D., A softbot-based interface to the Internet, Comm. ACM, 37, 7, 72-76, (1994)
[32] Falkenhainer, B.; Forbus, K., Compositional modeling: finding the right model for the job, Artificial intelligence, 51, 95-143, (1991)
[33] Fikes, R.; Cutkosky, M.; Gruber, T.; Van Baalen, J., Knowledge sharing technology, project overview, Knowledge systems laboratory tech. rept. no. KSL 91-71, (1991), Stanford, CA
[34] Gärdenfors, P., On the logic of relevance, Sythese, 37, 351-367, (1978) · Zbl 0395.03005
[35] Gärdenfors, P., ()
[36] Geffner, H.; Pearl, J., A framework for reasoning with defaults, ()
[37] Genesereth, M.R., An overview of metalevel architectures, (), 119-123
[38] Genesereth, M.R., An agent-based framework for software interoperability, ()
[39] Genesereth, M.R.; Nilsson, N.J., ()
[40] Giunchiglia, F.; Walsh, T., A theory of abstraction, Artificial intelligence, 56, 3, (1992) · Zbl 0762.68054
[41] Greiner, R., RLL-1: a representation language language, Stanford heuristic programming project, HPP-80-9 (working paper), (1980), Stanford, CA
[42] Greiner, R., Finding optimal derivation strategies in a redundant knowledge base, Artificial intelligence, 50, 1, 95-116, (1991) · Zbl 0738.68076
[43] Greiner, R., Learning efficient query processing strategies, ()
[44] Greiner, R.; Jurišica, I., A statistical approach to solving the EBL utility problem, ()
[45] Hayes, P.J., Computation and deduction, ()
[46] Iwasaki, Y.; Levy, A.Y., Automated model selection for simulation, (), 1183-1190
[47] Keynes, J.M., ()
[48] Kifer, M., On safety, domain independence and capturability of database queries, ()
[49] Klug, A., On conjunctive queries containing inequalities, J. ACM, 35, 1, 146-160, (1988) · Zbl 0637.68109
[50] Knoblock, C.A., Learning abstraction hierarchies for problem solving, () · Zbl 1080.68609
[51] ()
[52] Kowalski, R., A proof procedure using connection graphs, J. ACM, 22, 4, 572-595, (1975) · Zbl 0357.68097
[53] Lakemeyer, G., A logical account of relevance, (), 853-859
[54] Lenat, D.B.; Davis, R.; Doyle, J.; Genesereth, M.R., Reasoning about reasoning, ()
[55] Levy, A.Y., Irrelevance reasoning in knowledge based systems, ()
[56] Levy, A.Y., Creating abstractions using relevance reasoning, (), 588-594
[57] Levy, A.Y.; Fikes, R.E.; Sagiv, Y., A proof-theoretic approach to irrelevance: foundations and applications, ()
[58] Levy, A.Y.; Mumick, I.Singh; Sagiv, Y., Query optimization by predicate move-around, (), 96-107
[59] Levy, A.Y.; Mumick, I.Singh; Sagiv, Y.; Shmueli, O., Equivalence, query-reachability and satisfiability in Datalog extensions, (), 109-122
[60] Levy, A.Y.; Rajaraman, A.; Ordille, J.J., Query answering algorithms for information agents, (), 40-47
[61] Levy, A.Y.; Sagiv, Y., Constraints and redundancy in Datalog, (), 67-80
[62] Levy, A.Y.; Sagiv, Y., Exploiting irrelevance reasoning to guide problem solving, (), 138-144
[63] Levy, A.Y.; Sagiv, Y., Queries independent of updates, (), 171-181
[64] Levy, A.Y.; Sagiv, Y., Semantic query optimization in Datalog programs, (), 163-173
[65] Levy, A.Y.; Srivastava, D.; Kirk, T., Data model and query evaluation in global information systems, Special issue on networked information discovery and retrieval, J. intelligent information systems, 5, 2, (1995)
[66] Littlestone, N., Learning quickly when irrelevant attributes abound: a new linear-threshold algorithm, Machine learning, 2, 285-318, (1988)
[67] Lloyd, J.W.; Shepherdson, J.C., Partial evaluation in logic programming, J. logic programming, 11, 217-242, (1991) · Zbl 0741.68030
[68] Minton, S., Quantitative results concerning the utility of explanation based learning, ()
[69] Minton, S.; Carbonell, J.; Knoblock, C.; Kuokka, D.; Etzioni, O.; Gil, Y., Explanation based learning: a problem solving perspective, Artificial intelligence, 40, 63-118, (1989)
[70] Pearl, J., ()
[71] Pearl, J., System Z: a natural ordering of defaults with tractable applications to nonmonotic reasoning, (), 121-135
[72] Petalson, C., The BACK system: an overview, (), 114-119, 3
[73] Plaisted, D., Theorem proving with abstraction, Artificial intelligence, 16, 47-108, (1981) · Zbl 0454.68113
[74] Rao, R.B.; Greiner, R.; Hancock, T., Exploiting the absence of irrelevant information: what you don’t know can help you, ()
[75] Rombauer, I.S.; Rombauer-Becker, M., ()
[76] Russell, S., The complete guide to MRS, ()
[77] Sacerdoti, E.D., Planning in a hierarchy of abstraction spaces, Artificial intelligence, 5, 115-135, (1974) · Zbl 0288.68052
[78] Sagiv, Y.; Yannakakis, M., Equivalence among relational expressions with the union and difference operators, J. ACM, 27, 4, 633-655, (1981) · Zbl 0456.68123
[79] Sagiv, Y., On testing effective computability of magic programs, (), 244-262
[80] Sagiv, Y., A termination test for logic programs, (), 518-532
[81] Segre, A.; Elkan, C., A high-performance explanation-based learning algorithm, Artificial intelligence, 69, 1-50, (1994)
[82] Shmueli, O., Equivalence of Datalog queries is undecidable, J. logic programming, 15, 231-241, (1993) · Zbl 0825.68352
[83] Sickel, S., A search technique for clause interconnectivity graphs, IEEE trans. comput., 25, 8, 823-835, (1976) · Zbl 0331.68053
[84] Smith, D., Controlling inference, () · Zbl 0676.68059
[85] Smith, D.A.; Mickey, T.J., Partial evaluation of a CLP language, (), 119-138
[86] Srivastava, D.; Ramakrishnan, R., Pushing constraint selections, J. logic programming, 16, 3-4, 361-414, (1993) · Zbl 0805.68035
[87] Subramanian, D.; Genesereth, M.R., The relevance of irrelevance, ()
[88] Subramanian, D., A theory of justified reformulations, () · Zbl 0792.68169
[89] Ullman, J.D., ()
[90] Ullman, J.D., Information integration using logical views, () · Zbl 0944.68047
[91] Van Gelder, A., A message passing framework for logical query evaluation, (), 155-165
[92] Vardi, M.Y., Automata theory for database theoreticians, (), 83-92 · Zbl 0766.68097
[93] Vieille, L., Recursive query processing: the power of logic, Theoret. comput. sci., 69, 1-53, (1989) · Zbl 0685.68077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.