Graph structures in relational databases, constraint satisfaction and Bayesian networks

A. A. Filchenkov ; A. A. Zolotin ; A. L. Tulupyev

Nečetkie sistemy i mâgkie vyčisleniâ, Tome 10 (2015) no. 2, pp. 155-179.

Résumé

The paper is devoted to the comparative analysis of systems of knowledge representation based on graph structures. Such systems include relational databases, constraint satisfaction problems, Bayesian belief networks and algebraic Bayesian networks. The article examines the application of the principle of decomposition for each of these systems. The given comparative analysis of the graph structuress shows that in acyclic case all these structures are equivalent whereas in general the requirements for a graph structure of algebraic Bayesian networks are more stringent than for the other three structures.

Détail

Keywords: probabilistic graphical models, secondary structure, primary structure, knowledge with uncertainty, decomposition of the system, Bayesian networks, constraint satisfaction problems, relational database, join graphs.

Bibliographie

[1] Pospelov D. A. (red.), Iskusstvennyi intellekt, v. 2, Modeli i metody, Radio i svyaz, M., 1990, 304 pp.

[2] Codd E. F., “A relational model of data for large shared data banks”, Communications of the ACM, 13:6 (1970), 377–378 | DOI

[3] Codd E. F., “A database sublanguage founded on the relational calculus”, Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control (San Diego, California, November 11-12, 1971), ACM, NY, 1971, 35–68 | DOI

[4] Codd E. F., “Normalized data base structure: a brief tutorial”, Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control (San Diego, California, November 11-12, 1971), ACM, NY, 1971, 1–17 | DOI

[5] Codd E. F., “Further normalization of the database relational model”, Database Systems, Courant Computer Science Symposium 6, ed. R. Rustin, Prentice-Hall, Englewood Cliffs, NJ, 1972, 33–74

[6] Date C., An introduction to database systems, 8th Ed., Addison Wesley, Reading, MS, 2003, 1024 pp.

[7] Ullman J., Principles of database systems, Computer Science Press, Rockville, MD, 1980, 379 pp. | MR | Zbl

[8] Maier D., Theory of relational databases, Computer Science Press, Rockville, MD, 1983, 637 pp. | MR | Zbl

[9] Beeri C., Fagin R., Maier D., Yannakakis M., “On the desirability of acyclic database schemes”, Journal of the ACM, 30:3 (1983), 479–513 | DOI | MR | Zbl

[10] Honeyman P., Ladner R. E., Yannakakis M., “Testing the universal instance assumption”, Information Processing Letters, 10:1 (1980), 14–19 | DOI | MR | Zbl

[11] Maier D., Sagiv Y., Yannakakis M., “On the complexity of testing implications of functional and join dependencies”, Journal of the ACM, 28:4 (1981), 680–695 | DOI | MR | Zbl

[12] Bernstein P. A., Chiu D. M. W., “Using semi-joins to solve relational queries”, Journal of the ACM, 28:1 (1981), 25–40 | DOI | MR | Zbl

[13] Bernstein P. A., Goodman N., “Power of natural semijoins”, SIAM Journal on Computing, 10:4 (1981), 751–771 | DOI | MR | Zbl

[14] Vardi M. Y., “On decomposition of relational databases”, Proceedings of 23d Annual IEEE Symposium on Foundations of Computer Science, SFCS'08, 1982, 176–185 | MR

[15] Scherbina O. A., “Lokalnye eliminatsionnye algoritmy dlya resheniya nekotorykh zadach iskusstvennogo intellekta”, Trudy 11 Natsionalnoi konferentsii po iskusstvennomu intellektu (Dubna, 2008), v. 2, LENAND, M., 2008, 244–252

[16] Dechter R., Constraint processing, Morgan Kaufmann, San Francisco, 2003, 481 pp.

[17] Montanari U., “Networks of constraints: Fundamental properties and applications to picture processing”, Information Sciences, 7:2 (1974), 95–132 | DOI | MR | Zbl

[18] Russel S., Norvig P., Artificial intelligence: a modern approach, 3rd Ed., Prentice Hall, New Jersey, 2011, 1152 pp.

[19] Tsang E., Foundations of constraint satisfaction, Academic Press, New York, 1993, 421 pp.

[20] Walsch T., “Reformulating propositional satisfiability as constraint satisfaction”, Proceedings of the 4th International Symposium in Abstraction, Reformulation and Approximation, 2000, 233–246 | DOI

[21] Barták R., Salido M. A., Rossi F., “New trends in constraint satisfaction, planning and scheduling: a survey”, The Knowledge Engineering Review, 2010, no. 25, 249–279

[22] Castillo L., Borrajo D., Salido M. A., Planning, scheduling and constraint satisfaction: from theory to practice, Frontiers in Artificial Intelligence and Applications, IOS Press, Amsterdam, 2005, 208 pp. | Zbl

[23] Fox M. S., Constraint-directed search: a case study if job-shop scheduling, Morgan-Kaufmann, Pitman, 1987

[24] Boering A., Maher M., Martindale A., Wilson M., “Constraint hierarchies and logic programming”, Proceedings of 6th International Conference on Logic Programming, MIT Press, Cambgidge, 1989, 149–164 | MR

[25] van Hentenryck P., Simonis H., Dincbas M., “Constraint satisfaction using constraint logic programming”, Artificial Intelligence, 58:1–3 (1992), 113–159 | MR | Zbl

[26] Zabih R., McAllester D., “A rearrangement search strategy for determing propositional satisfiability”, Proceedings of the 7th National Conference on Artificial Intelligence, AAAI-88, AAAI Press, Palo Alto, CA, 1988, 155–160

[27] Ortiz-Bayliss J. C., Terashima-Marin H., Ozcan E., Parkes A., “On the idea of evolving decision matrix hyper-heuristics for solving constraint satisfaction problems”, Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, 255–256

[28] Allen J. F., Natural Language Understanding, 2nd Ed., Benjamin-Cummings Publishing Co, Redwood City, CA, 1995, 654 pp. | Zbl

[29] Menzel W., “Constraint satisfaction for robust parsing of spoken language”, Journal of Experimental and Theoretical Artificial Intelligence, 10 (1998), 77–89 | DOI | Zbl

[30] Sag I., Wasow T., “Performance-compatible competence grammar”, Non-Transformational Syntax: Formal and Explicit Models of Grammar, eds. R. Borsley, K. Borjars, Wiley-Blackwell, Oxford, 2011, 464 pp.

[31] Scherbina O. A., Udovletvorenie ogranichenii i programmirovanie v ogranicheniyakh, , 2012 http://soa7.socionet.ru/files/shcherbina_csp_review.pdf

[32] Barták R., “Constraint programming: in persuit of the holy grail”, Proceedings of the Week of Doctoral Students, WDS99, v. 4, MatFyzPress, Prague, 1999, 555–564

[33] Barták R., “Modelling soft constraints: a survey”, Neural Networks World, 12:5 (2002), 421–431

[34] Schiex T., “Possibilistic constraint satisfaction problems or "How to handle soft constraints?"”, Proc. of 8th International Conference on Uncertainty in Artificial Intelligence, Stanford, CA, 1992, 268–275

[35] Ruttkay Zs., “Fuzzy constraint satisfaction”, Proceedings of the IEEE 3rd International Conference on Fuzzy Systems, IEEE, NY, 1994, 1263–1268

[36] Rossie F., Petrie C., Dhar V., On the equivalence of constraint satisfaction problems, Technical Report ACT-AI-222-89, MCC, Austin, 1989

[37] Bitner J. R., Reingold E. M., “Backtrack programming techniques”, Communications of the Association for Computing Machinery, 18:11 (1975), 651–656 | DOI | Zbl

[38] Waltz D. L., “Understanding line drawings of scenes with shadows”, Psychology of Computer Vision, ed. P. Winston, McGraw-Hill, NY, 1975, 19–92 | MR

[39] McGregor L. L., “Relational consistency algorithms and their application in finding subgraph and graph isomorphism”, Information Sciences, 19:3 (1979), 229–250 | DOI | MR | Zbl

[40] Sabin D., Freuder E. C., “Contradicting conventional wisdom in constraint satisfaction”, Proceedings of 11th European Conference on Artifficial Intelligence, ECAI 94, Wiley, Amsterdam, 1994, 125–129

[41] Freuder E. C., “Synthesizing constraint expressions”, Communications of the Association for Computing Machinery, 21:11 (1978), 958–966 | DOI | MR | Zbl

[42] Freuder E. C., “A sufficient condition for backtrack-free search”, Journal of the ACM, 29:1 (1982), 24–32 | DOI | MR | Zbl

[43] Mackworth A. K., Freuder E. C., “The complexity of some polynomialnetwrok consistency algorithms for constraint satisfaction problems”, Artificial Intelligence, 25:1 (1985), 65–74 | DOI | MR

[44] Dechter R., “Enhancement schemes for constraint processing: backjumping, learning and cutset decomposition”, Artificial Intellegence, 41 (1990), 273–312 | DOI

[45] Dechter R., Pearl J., “Network-based heuristics for constraint-satisfaction problems”, Artificial Intelligence, 31:1 (1987), 1–38 | DOI | MR

[46] Even S., Graph Algorithms, Computer Science Press, Potomac, 1979 | MR | Zbl

[47] Robertson N., Seymour P., “Graph minors III: Planar tree-width”, Journal of Combinatorial Theory. Series B, 36:1 (1984), 49–64 | DOI | MR | Zbl

[48] Halin R., “S-functions for graphs”, Journal of Geometry, 8 (1976), 171–186 | DOI | MR | Zbl

[49] Dechter R., Pearl J., “Tree clustering for constraint networks”, Artificial Intelligence, 38:3 (1989), 353–366 | DOI | MR | Zbl

[50] Pearl J., “Reverend Bayes on inference engines: a distributed hierarchical approach”, Proceedings of the National Conference on Artificial Intelligence, AAAI-82, Morgan Kaufmann, Pittsburgh, Pennsylvania, 1982, 133–136

[51] Kim J. H., Pearl J., “A computational model for combined causal and diagnostic reasoning ininference systems”, Proceedings of the 8-th International Joint Conference on Artificial Intelligence, IJCAI-83, Morgan Kaufmann, Karlsruhe, Germany, 1983, 190–193

[52] Pearl J., “Fusion, propagation, and structuring in belief networks”, Artificial Intelligence, 29:3 (1986), 241–288 | DOI | MR | Zbl

[53] Pearl J., Probabilistic reasoning in intelligent systems, Morgan Kaufmann, NY, 1988, 552 pp. | MR

[54] Lauritzen S., Spiegelhalter D., “Local computations with probabilities on graphical structures andtheir application to expert systems”, Journal of the Royal Statistical Society, 50:2 (1988), 157–224 | MR | Zbl

[55] Spiegelhalter D. J., Knill-Jones R. P., “Statistical and knowledge-based approaches to clinical decision-support systems”, Journal of the Royal Statistical Society. Series A, 147 (1984), 35–77 | DOI | Zbl

[56] Lauritzen S., Wermuth N., “Graphical models for associations between variables, some of which are qualitative and some quantitative”, Annals of Statistics, 17 (1989), 31–57 | DOI | MR | Zbl

[57] Tulupev A. L., Sirotkin A. V., Nikolenko S. I., Baiesovskie seti doveriya: logiko-veroyatnostnyi vyvod v atsiklicheskikh napravlennykh grafakh, Izd-vo S.-Peterb. un-ta, SPb., 2009, 400 pp.

[58] Jensen F. V., Bayesian networks and decision graphs, Springer-Verlag, New York, 268 pp. | MR

[59] Gorodetskii V. I., “Algebraicheskie baiesovskie seti — novaya paradigma ekspertnykh sistem”, Yubileinyi sbornik trudov institutov Otdeleniya informatiki, vychislitelnoi tekhniki i avtomatizatsii RAN, v. 2, RAN, M., 1993, 120–141

[60] Gorodetsky V. I., Drozdgin V. V., Jusupov R. M., “Application of attributed grammar and algorithmic sensitivity model for knowledge representation and estimation”, Artificial Intelligence and Information, Control Systems of ROBOTS, Elsevier Science Publishers B.V., Amsterdam, 1984, 232–237

[61] Tulupev A. L., Nikolenko S. I., Sirotkin A. V., Baiesovskie seti: logiko-veroyatnostnyi podkhod, Nauka, SPb., 2006, 607 pp.

[62] Tulupev A. L., Algebraicheskie baiesovskie seti: logiko-veroyatnostnye graficheskie modeli baz fragmentov znanii s neopredelennostyu, Dissertatsiya na soiskanie uchenoi stepeni d-ra fiz.-mat. nauk, SPb., 2009, 670 pp.

[63] Tulupev A. L., “Atsiklicheskie algebraicheskie baiesovskie seti: logiko-veroyatnostnyi vyvod”, Nechetkie sistemy i myagkie vychisleniya, 1:1 (2006), 57–93 | MR | Zbl

[64] Sirotkin A. V., Tulupev A. L., “Lokalnyi apriornyi vyvod v algebraicheskikh baiesovskikh setyakh: kompleks osnovnykh algoritmov”, Trudy SPIIRAN, 5 (2007), 100–111

[65] Tulupev A. L., Algebraicheskie baiesovskie seti. Logiko-veroyatnostnyi podkhod k modelirovaniyu baz znanii s neopredelennostyu, SPIIRAN, SPb., 2000, 292 pp.

[66] Tulupev A. L., Algebraicheskie baiesovskie seti: lokalnyi logiko-veroyatnostnyi vyvod, Ucheb. posobie, Elementy myagkikh vychislenii, SPbGU, SPb.; OOO Izdatelstvo «Anatoliya», SPb., 2007, 80 pp.

[67] Tulupev A. L., “Algebraicheskie baiesovskie seti: logiko-veroyatnostnaya model baz fragmentov znanii s neopredelennostyu”, Trudy Vserossiiskoi nauchnoi konferentsii po nechetkim sistemam i myagkim vychisleniyam, NSMV-2006 (Tver, 2006), 31–47

[68] Sirotkin A. V., Algebraicheskie baiesovskie seti: vychislitelnaya slozhnost algoritmov logiko-veroyatnostnogo vyvoda v usloviyakh neopredelennosti, Dissertatsiya ... kandidata fiz.-mat. nauk, SPb., 2011, 216 pp.

[69] Tulupev A. L., Sirotkin A. V., “Algebraicheskie baiesovskie seti: printsip dekompozitsii i logiko-veroyatnostnyi vyvod v usloviyakh neopredelennosti”, Informatsionno-izmeritelnye i upravlyayuschie sistemy, 6:10 (2008), 85–87

[70] Tulupev A. L., Algebraicheskie baiesovskie seti: globalnyi logiko-veroyatnostnyi vyvod, Ucheb. posobie, Elementy myagkikh vychislenii, SPbGU, SPb.; OOO Izdatelstvo «Anatoliya», SPb., 2007, 40 pp.

[71] Filchenkov A. A., Sintez grafov smezhnosti v mashinnom obuchenii vtorichnoi struktury algebraicheskikh baiesovskikh setei, Dissertatsiya na soiskanie uchenoi stepeni k-ta fiz.-mat. nauk, Samara, 2013, 339 pp.

[72] Tulupev A. L., Sirotkin A. V., Nikolenko S. I., Baiesovskie seti doveriya: logiko-veroyatnostnyi vyvod v atsiklicheskikh napravlennykh grafakh, Izd-vo S.-Peterb. un-ta, SPb., 2009, 400 pp.

[73] Tulupev A. L., Stolyarov D. M., Mentyukov M. V., “Predstavlenie lokalnoi i globalnoi struktury algebraicheskoi baiesovskoi seti v Java-prilozheniyakh”, Trudy SPIIRAN, 5 (2007), 71–99

[74] Vyatkin A. V., Filchenkov A. A., Tulupev A. L., Musina V. F., Frolenkov K. V., “Podkhody k ustraneniyu tsiklichnosti pervichnoi struktury algebraicheskoi baiesovskoi seti”, Trudy SPIIRAN, 26 (2013), 216–233

[75] Filchenkov A. A., “Ierarkhiya globalnykh struktur algebraicheskoi baiesovskoi seti kak sistema grafov i gipergrafov”, Nauchno-tekhnicheskii vestnik informatsionnykh tekhnologii, mekhaniki i optiki, 2013, no. 1(83), 75–81

[76] Filchenkov A. A., Tulupev A. L., “Strukturnyi analiz sistem minimalnykh grafov smezhnosti”, Trudy SPIIRAN, 11 (2009), 104–127

[77] Filchenkov A. A., Tulupev A. L., Sirotkin A. V., “Minimalnye grafy smezhnosti algebraicheskoi baiesovskoi seti: formalizatsiya osnov sinteza i avtomaticheskogo obucheniya”, Nechetkie sistemy i myagkie vychisleniya, 6:2 (2011), 145–163 | Zbl

[78] Filchenkov A. A., Frolenkov K. V., Sirotkin A. V., Tulupev A. L., “Sistema algoritmov sinteza podmnozhestv minimalnykh grafov smezhnosti”, Trudy SPIIRAN, 27 (2013), 200–-244